Subhroshekhar Ghosh, Soumendu Sundar Mukherjee
arXiv 20 Jan 2022 · Statistics — Methodology
arXiv:2201.08326 · PDF · DOI · OpenAlex · Extracted main text
Group or cluster structure on explanatory variables in machine learning problems is a very general phenomenon, which has attracted broad interest from practitioners and theoreticians alike. In this work we contribute an approach to learning under such group structure, that does not require prior information on the group identities. Our paradigm is motivated by the Laplacian geometry of an underlying network with a related community structure, and proceeds by directly incorporating this into a penalty that is effectively computed via a heat flow-based local network dynamics. In fact, we demonstrate a procedure to construct such a network based on the available data. Notably, we dispense with computationally intensive pre-processing involving clustering of variables, spectral or otherwise. Our technique is underpinned by rigorous theorems that guarantee its effective performance and provide bounds on its sample complexity. In particular, in a wide range of settings, it provably suffices to run the heat flow dynamics for time that is only logarithmic in the problem dimensions. We explore in detail the interfaces of our approach with key statistical physics models in network science, such as the Gaussian Free Field and the Stochastic Block Model. We validate our approach by successful applications to real-world data from a wide array of application domains, including computer science, genetics, climatology and economics. Our work raises the possibility of applying similar diffusion-based techniques to classical learning tasks, exploiting the interplay between geometric, dynamical and stochastic structures underlying the data.
appendix boundary found by appendix_command · 55% of the source is main text. Read the extracted text to check this.
The works this paper leans on most, across its whole bibliography — not restricted to papers in our corpus. Ranked by composite intensity, which combines how often a work is mentioned, how many sections mention it, and how much of that falls in the main text rather than the appendix.
| Reference | Intensity | Mentions | Sections | Main text | |
|---|---|---|---|---|---|
| 1 | Berestycki, N (2015) Introduction to the gaussian free field and liouville quantum gravity | 0.737 | 3 | 2 | 100% |
| 2 | Abbe, E (2017) Community detection and stochastic block models: recent developments | 0.644 | 2 | 2 | 100% |
| 3 | Bühlmann, P., Rütimann, P., van de Geer, S., and Zhang, C.-H (2013) Correlated variables in regression: clustering and sparse estimation | 0.644 | 2 | 2 | 100% |
| 4 | Coifman, R. R., Lafon, S., Lee, A. B., Maggioni, M., Nadler, B., War… (2005) Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps | 0.644 | 2 | 2 | 100% |
| 5 | Coifman, R. R. and Lafon, S (2006) Diffusion maps | 0.644 | 2 | 2 | 100% |
| 6 | Friedli, S. and Velenik, Y (2017) Statistical mechanics of lattice systems: a concrete mathematical introduction | 0.644 | 2 | 2 | 100% |
| 7 | Goldenberg, A., Zheng, A. X., Fienberg, S. E., and Airoldi, E. M (2010) A survey of statistical network models | 0.644 | 2 | 2 | 100% |
| 8 | Holland, P. W., Laskey, K. B., and Leinhardt, S (1983) Stochastic blockmodels: First steps | 0.644 | 2 | 2 | 100% |
| 9 | Karrer, B. and Newman, M. E (2011) Stochastic blockmodels and community structure in networks | 0.644 | 2 | 2 | 100% |
| 10 | Kelner, J., Koehler, F., Meka, R., and Moitra, A (2019) Learning some popular gaussian graphical models without condition number bounds | 0.644 | 2 | 2 | 100% |
Showing the top 10 of 70 scored citations.