원문 초록
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.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2604.06109v2제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.