Low-Degree Learning from Localization Schemes

Abstract

The low-degree algorithm is a cornerstone in computational learning theory. For product or Gaussian distributions, it shows that efficiently learnability follows from Fourier concentration. However, a longstanding obstacle towards building such a theory over nonproduct distributions is that we can no longer rely on having closed-form expressions for a good basis of orthogonal functions. This hints that the analysis of the low-degree algorithm might be brittle to the underlying distributional assumptions. We refute this intuition by showing that the low-degree algorithm provably succeeds for a large class of graphical models under mild high-temperature conditions. As an application, for nearly every Ising model that is known to rapidly mix, we obtain learning algorithms for every function class for which the Fourier approach succeeds for product distributions (e.g. low-depth circuits, halfspaces, intersections, monotone, among others) with no significant loss. Our framework is based on a strikingly clean connection with the coordinate-by-coordinate localization scheme of Chen and Eldan introduced for establishing rapid mixing in high-temperature models, as well as other analytical transference principles to product distributions.