Learning with latent group sparsity via heat flow dynamics on networks
  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.
