Fast Agnostic Learners in the Plane

• URL: http://arxiv.org/abs/2510.18057v1
• Date: Mon, 20 Oct 2025 19:49:33 GMT
• Title: Fast Agnostic Learners in the Plane
• Abstract summary: 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)$.
• Score: 4.4861549416559185
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We investigate the computational efficiency of agnostic learning for several fundamental geometric concept classes in the plane. While the sample complexity of agnostic learning is well understood, its time complexity has received much less attention. We study the class of triangles and, more generally, the class of convex polygons with $k$ vertices for small $k$, as well as the class of convex sets in a square. We present a proper agnostic learner for the class of triangles that has optimal sample complexity and runs in time $\tilde O({\epsilon^{-6}})$, improving on the algorithm of Dobkin and Gunopulos (COLT `95) that runs in time $\tilde O({\epsilon^{-10}})$. For 4-gons and 5-gons, we improve the running time from $O({\epsilon^{-12}})$, achieved by Fischer and Kwek (eCOLT `96), to $\tilde O({\epsilon^{-8}})$ and $\tilde O({\epsilon^{-10}})$, respectively. We also design a proper agnostic learner for convex sets under the uniform distribution over a square with running time $\tilde O({\epsilon^{-5}})$, improving on the previous $\tilde O(\epsilon^{-8})$ bound at the cost of slightly higher sample complexity. Notably, agnostic learning of convex sets in $[0,1]^2$ under general distributions is impossible because this concept class has infinite VC-dimension. Our agnostic learners use data structures and algorithms from computational geometry and their analysis relies on tools from geometry and probabilistic combinatorics. Because our learners are proper, they yield tolerant property testers with matching running times. Our results raise a fundamental question of whether a gap between the sample and time complexity is inherent for agnostic learning of these and other natural concept classes.

Related papers

• Learning Sparse Quantum States [0.8122270502556375]
  We give the first near optimal algorithm for learning $n$-qubit $k$-sparse pure quantum states.<n>We obtain fidelity at least $1-varepsilon$ with high probability using $tildeO(k/varepsilon)$ copies of the state and $tildeO(kn/varepsilon)$ time.<n>As an implication, we also obtain an algorithm with near optimal $tildeO(kr/varepsilon)$ sample complexity for learning $k$-sparse rank-$r
  arXiv  Detail & Related papers  (2026-09-10T21:28:21Z)
• Agnostic learning in (almost) optimal time via Gaussian surface area [2.797422854005701]
  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.
  arXiv  Detail & Related papers  (2026-03-06T08:22:59Z)
• Faster Algorithms for Agnostically Learning Disjunctions and their Implications [37.35692862344027]
  We study the algorithmic task of learning Boolean disjunctions in the distribution-free PAC model.<n>We develop an agnostic learner for this concept class with complexity $2tildeO(n1/2)$.
  arXiv  Detail & Related papers  (2025-04-21T17:16:14Z)
• 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)
• 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)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  We show that any efficient SQ algorithm for the problem requires sample complexity at least $Omega(d1/2/(maxp, epsilon)2)$. Our lower bound suggests that this quadratic dependence on $1/epsilon$ is inherent for efficient algorithms.
  arXiv  Detail & Related papers  (2023-07-13T18:59:28Z)
• 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)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  We show that HSDMPG can attain an $mathcalObig (1/sttnbig)$ which is at the order of excess error on a learning model. For loss factors, we prove that HSDMPG can attain an $mathcalObig (1/sttnbig)$ which is at the order of excess error on a learning model.
  arXiv  Detail & Related papers  (2020-09-18T02:18:44Z)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  We study the problem of agnostic $Q$-learning with function approximation in deterministic systems. We show that if $delta = Oleft(rho/sqrtdim_Eright)$, then one can find the optimal policy using $Oleft(dim_Eright)$.
  arXiv  Detail & Related papers  (2020-02-17T18:41:49Z)

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.