Agnostic learning in (almost) optimal time via Gaussian surface area

• URL: http://arxiv.org/abs/2603.06027v1
• Date: Fri, 06 Mar 2026 08:22:59 GMT
• Title: Agnostic learning in (almost) optimal time via Gaussian surface area
• Abstract summary: Klivans, Klivans (2008) show that degree $d = O(2 / varepsilon4)$ suffices to achieve an $varepsilon$-approximation.<n>In light of lower bounds due to Diakonikolas, we show that degree $d = tilde O (2 / varepsilon2)$ is enough.
• Score: 2.797422854005701
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The complexity of learning a concept class under Gaussian marginals in the difficult agnostic model is closely related to its $L_1$-approximability by low-degree polynomials. For any concept class with Gaussian surface area at most $Γ$, Klivans et al. (2008) show that degree $d = O(Γ^2 / \varepsilon^4)$ suffices to achieve an $\varepsilon$-approximation. This leads to the best-known bounds on the complexity of learning a variety of concept classes. In this note, we improve their analysis by showing that degree $d = \tilde O (Γ^2 / \varepsilon^2)$ is enough. In light of lower bounds due to Diakonikolas et al. (2021), this yields (near) optimal bounds on the complexity of agnostically learning polynomial threshold functions in the statistical query model. Our proof relies on a direct analogue of a construction of Feldman et al. (2020), who considered $L_1$-approximation on the Boolean hypercube.

Related papers

• A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces [0.0]
  We study the complexity of smoothed learning of halfspaces on $pm 1n$ under uniform marginals in the model ofciteKM25.
  arXiv  Detail & Related papers  (2026-05-04T08:53:40Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem.<n>Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms.
  arXiv  Detail & Related papers  (2026-03-19T15:53:41Z)
• Statistical Query Lower Bounds for Smoothed Agnostic Learning [42.71001191804269]
  We study the complexity of smoothed learning, recently introduced byciteCKKMS24, in which the learner competes with the best in a target class under slight perturbations of prototypical inputs.<n>Specifically, we focus on agnostically learning halfspaces under subgaussian distributions in the smoothed model.
  arXiv  Detail & Related papers  (2026-02-24T18:46:46Z)
• Fast Agnostic Learners in the Plane [4.4861549416559185]
  We investigate the computational efficiency of agnostic learning for several fundamental geometric concept classes in the plane.<n>We present a proper agnostic learner for the class of triangles that has optimal sample complexity and runs in time $tilde O(epsilon-6)$.<n>We also design a proper learner for convex sets under the uniform distribution over a square with running time $tilde O(epsilon-5)$.
  arXiv  Detail & Related papers  (2025-10-20T19:49:33Z)
• Robust Learning of Multi-index Models via Iterative Subspace Approximation [36.138661719725626]
  We study the task of learning Multi-Index Models (MIMs) with label noise under the Gaussian distribution.<n>We focus on well-behaved MIMs with finite ranges that satisfy certain regularity properties.<n>We show that in the presence of random classification noise, the complexity of our algorithm scales agnosticly with $1/epsilon$.
  arXiv  Detail & Related papers  (2025-02-13T17:37:42Z)
• A Theory of Interpretable Approximations [61.90216959710842]
  We study the idea of approximating a target concept $c$ by a small aggregation of concepts from some base class $mathcalH$. For any given pair of $mathcalH$ and $c$, exactly one of these cases holds: (i) $c$ cannot be approximated by $mathcalH$ with arbitrary accuracy. We show that, in the case of interpretable approximations, even a slightly nontrivial a-priori guarantee on the complexity of approximations implies approximations with constant (distribution-free and accuracy-
  arXiv  Detail & Related papers  (2024-06-15T06:43:45Z)
• Agnostically Learning Multi-index Models with Queries [54.290489524576756]
  We study the power of query access for the task of agnostic learning under the Gaussian distribution. We show that query access gives significant runtime improvements over random examples for agnostically learning MIMs.
  arXiv  Detail & Related papers  (2023-12-27T15:50:47Z)
• A Quadratic Sample Complexity Reduction for Agnostic Learning via Quantum Algorithms [0.0]
  We find a new sample complexity upper bound of $O(mboxlog(frac1delta)/epsilon) as $epsilon,deltarightarrow 0arrow. For general learning, the quantum speedup in the rate of learning is quadratic in $epsilon-1$.
  arXiv  Detail & Related papers  (2023-10-24T07:39:16Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
  arXiv  Detail & Related papers  (2022-03-17T23:52:08Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  One of its most powerful and successful modalities approximates every distribution to an $ell$ distance essentially at most a constant times larger than its closest $t$-piece degree-$d_$. We provide a method that estimates this number near-optimally, hence helps approach the best possible approximation.
  arXiv  Detail & Related papers  (2022-02-15T03:49:28Z)
• Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals [10.06689891744466]
  We consider the well-studied problem of learning intersections halfspaces under the Gaussian distribution in the challenging emphagnostic learning model. We prove two variants of our lower bound, each of which combines ingredients from Diakonikolas et al. (2021) with (an extension of) a different earlier approach for SQ lower bounds for the Boolean setting.
  arXiv  Detail & Related papers  (2022-02-10T15:34:10Z)
• The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals [47.81107898315438]
  We develop a method for finding hard families of examples for a wide class of problems by using duality LP. We show that the $L1$-regression is essentially best possible, and therefore that the computational difficulty of learning a concept class is closely related to the degree required to approximate any function from the class in $L1$-norm.
  arXiv  Detail & Related papers  (2021-02-08T18:06:32Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  We show that there exists an $epsilon$-cover for $S$ of cardinality $M = (k/epsilon)O_d(k1/d)$. Building on our structural result, we obtain significantly improved learning algorithms for several fundamental high-dimensional probabilistic models hidden variables.
  arXiv  Detail & Related papers  (2020-12-14T18:14:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.