Skip to content
#machine learning Conference Open access

Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension

Jul 2024 · Annual Conference Computational Learning Theory · Vol abs/2407.00966 · 15 citations · ⚡ 1 influential · 78 references
Computer Science

TL;DR

A smoothed-analysis framework that requires a learner to compete only with the best classifier that is robust to small random Gaussian perturbation is introduced, and the first algorithm for agnostic learning intersections of halfspaces in time is obtained, where $γ$ is the margin parameter.

Abstract

In traditional models of supervised learning, the goal of a learner-- given examples from an arbitrary joint distribution on $\mathbb{R}^d \times \{\pm 1\}$-- is to output a hypothesis that is competitive (to within $ε$) of the best fitting concept from some class. In order to escape strong hardness results for learning even simple concept classes, we introduce a smoothed-analysis framework that requires a learner to compete only with the best classifier that is robust to small random Gaussian perturbation. This subtle change allows us to give a wide array of learning results for any concept that (1) depends on a low-dimensional subspace (aka multi-index model) and (2) has a bounded Gaussian surface area. This class includes functions of halfspaces and (low-dimensional) convex sets, cases that are only known to be learnable in non-smoothed settings with respect to highly structured distributions such as Gaussians. Our definition of smoothed agnostic learning is an interpolation between the case where the instance distribution $D$ and the optimal classifier can be arbitrarily coupled (which corresponds to agnostic learning and $σ= 0$) and completely decoupled (when $σ= \infty$). This decoupling allows us to avoid worst-case concepts that can encode complexity-theoretic primitives. Surprisingly, our analysis also yields new results for traditional non-smoothed frameworks such as learning with margin. In particular, we obtain the first algorithm for agnostically learning intersections of $k$-halfspaces in time $k^{\mathrm{poly}(\frac{\log k}{εγ}) }$ where $γ$ is the margin parameter. Before our work, the best-known runtime was exponential in $k$ (Arriaga and Vempala, FOCS' 99). 50 pages. This is the TheoretiCS journal version

Read PDF

Similar papers

Preprint Oct 2026

Wasserstein approximation of measures via orthogonal frames: statistical and computational complexities

Dimension-reduction methods such as PCA identify a subspace capturing most of the variation in the data, but not a distinguished basis within it. Selecting a basis in which the samples are sparsely represented is a recurring task in unsupervised learning, addressed by methods in factor analysis, dictionary learning, an...

Mateo Díaz Díaz, N. G. Trillos, Daniel López-Castaño et al. · 0 citations
#artificial intelligence Preprint Oct 2026

Dimension-Free Scaling Laws for Size Generalization: An Exponential Separation

Modern machine learning models increasingly operate on variable-size structured data, such as sets and graphs. A central requirement is \emph{size generalization}: the ability of a model trained on inputs of one size to generalize to inputs of a different, potentially much larger, size. Classical statistical learning t...

B. Tahmasebi, Melanie Weber · 0 citations
#machine learning Preprint Oct 2026

Combinatorial Characterizations of the Learnability of Conditional Distributions

The PAC-learnability of function classes that map inputs to probability distributions over a finite space is studied, and it is shown that a distribution-valued function class is learnable if and only if each of its coordinate classes is learnable in the probabilistic concept model.

Mihir Dhanakshirur, Ambuj Tewari · 0 citations

Learning Positive Linear Combinations of ReLUs in Fully Polynomial Time

We study the fundamental problem of PAC learning positive linear combinations of $k$ arbitrary ReLU activations on $\mathbb{R}^d$ with respect to the Gaussian distribution, in $L_2$ loss. We give the first fully-polynomial time algorithm for this learning task. Specifically, our algorithm draws $\mathrm{poly}(d, k, 1/\...

Ilias Diakonikolas, Jelena Diakonikolas, Pu-Qian Wang et al. · 0 citations

Sparse Priors for Efficient Distribution Learning

The results show that learning under an appropriate prior overcomes the curse of dimensionality with respect to the dependence on $n$ and introduces the class of sparse priors and defines the "Sparse Dimension" as a measure of sparsity of a prior over the space of all distributions.

Saumya Goyal, B. Póczos · 0 citations
Preprint Oct 2026

Lower expected Fisher rank implies better PAC generalization

Deep learning architectures tend to generalize well to unseen data, but explaining this capability is still an open area of research. Under the assumption of i.i.d. data, PAC-Bayes provides a bound on generalization error, and its tightness relies on a parameter distribution that covers a large volume of low-loss solut...

M. Miani, Albert Kjøller Jacobsen, A. Serrano et al. · 0 citations

Related blog posts

Microsoft Research Blog Nov 16, 2026

TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient

AI coding agents are increasingly help developers fix bugs and build features largely on their own, but every interaction with their models consumes tokens. In each session, an agent sends instructions, tool descriptions, and session history to its model. Most efforts to reduce this cost focus on individual tasks. Yet developers return to the same […] The post TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient appeared first on Microsoft Research.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.