A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity
원문 초록
A remarkable recent paper by Rubinfeld and Vasilyan (2022) initiated the study of \emph{testable learning}, where the goal is to replace hard-to-verify distributional assumptions (such as Gaussianity) with efficiently testable ones and to require that the learner succeed whenever the unknown distribution passes the corresponding test. In this model, they gave an efficient algorithm for learning halfspaces under testable assumptions that are provably satisfied by Gaussians. In this paper we give a powerful new approach for developing algorithms for testable learning using tools from moment matching and metric distances in probability. We obtain efficient testable learners for any concept class that admits low-degree \emph{sandwiching polynomials}, capturing most important examples for which we have ordinary agnostic learners. We recover the results of Rubinfeld and Vasilyan as a corollary of our techniques while achieving improved, near-optimal sample complexity bounds for a broad range of concept classes and distributions. Surprisingly, we show that the information-theoretic sample complexity of testable learning is tightly characterized by the Rademacher complexity of the concept class, one of the most well-studied measures in statistical learning theory. In particular, uniform convergence is necessary and sufficient for testable learning. This leads to a fundamental separation from (ordinary) distribution-specific agnostic learning, where uniform convergence is sufficient but not necessary.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Self-Supervised Evolution Operator Learning for High-Dimensional Dynamical Systems
auto-fpt: Automating Free Probability Theory Calculations for Machine Learning Theory
Double descent in quantum machine learning
Gradient Equilibrium in Online Learning: Theory and Applications
NLPrompt: Noise-Label Prompt Learning for Vision-Language Models
Federated Learning from Vision-Language Foundation Models: Theoretical Analysis and Method
토론
이 논문과 연결된 포럼 글이 아직 없습니다.