Cover Image

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

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Pesenti, Lucas, Slot, Lucas, Wiedmer, Manuel
Format:	Preprint
Published:	2026
Subjects:	Machine Learning Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Testably Learning Polynomial Threshold Functions
by: Slot, Lucas, et al.
Published: (2024)

Universality of first-order methods on random and deterministic matrices
by: Gorini, Nicola, et al.
Published: (2026)

Discrepancy Minimization via Regularization
by: Pesenti, Lucas, et al.
Published: (2022)

Efficient Sample-optimal Learning of Gaussian Tree Models via Sample-optimal Testing of Gaussian Mutual Information
by: Gayen, Sutanu, et al.
Published: (2024)

Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginals
by: Guo, Anxin, et al.
Published: (2024)

Fourier Analysis of Iterative Algorithms
by: Jones, Chris, et al.
Published: (2024)

Optimization of Inter-group Criteria for Clustering with Minimum Size Constraints
by: Laber, Eduardo S., et al.
Published: (2024)

Unrolled denoising networks provably learn optimal Bayesian inference
by: Karan, Aayush, et al.
Published: (2024)

A Competitive Algorithm for Agnostic Active Learning
by: Price, Eric, et al.
Published: (2023)

Faster Algorithms for Agnostically Learning Disjunctions and their Implications
by: Diakonikolas, Ilias, et al.
Published: (2025)

Statistical Query Lower Bounds for Smoothed Agnostic Learning
by: Diakonikolas, Ilias, et al.
Published: (2026)

Agnostic Learning of General ReLU Activation Using Gradient Descent
by: Awasthi, Pranjal, et al.
Published: (2022)

Sharper Bounds for Chebyshev Moment Matching, with Applications
by: Musco, Cameron, et al.
Published: (2024)

Polynomial-time derivation of optimal k-tree topology from Markov networks
by: Dastjerdi, Fereshteh R., et al.
Published: (2024)

Hesse's Redemption: Efficient Convex Polynomial Programming
by: Slot, Lucas, et al.
Published: (2025)

Efficient learning of bosonic Gaussian unitaries
by: Fanizza, Marco, et al.
Published: (2025)

Approximation Algorithms for D-optimal Design
by: Singh, Mohit, et al.
Published: (2018)

Fast Agnostic Learners in the Plane
by: Eden, Talya, et al.
Published: (2025)

Revisiting Agnostic PAC Learning
by: Hanneke, Steve, et al.
Published: (2024)

The SMART approach to instance-optimal online learning
by: Banerjee, Siddhartha, et al.
Published: (2024)

OPTWIN: Drift identification with optimal sub-windows
by: Tosi, Mauro Dalle Lucca, et al.
Published: (2023)

Efficient Certificates of Anti-Concentration Beyond Gaussians
by: Bakshi, Ainesh, et al.
Published: (2024)

Reliable Learning of Halfspaces under Gaussian Marginals
by: Diakonikolas, Ilias, et al.
Published: (2024)

Near-optimal Swap Regret Minimization for Convex Losses
by: Hu, Lunjia, et al.
Published: (2026)

MNL-Bandit with Knapsacks: a near-optimal algorithm
by: Aznag, Abdellah, et al.
Published: (2021)

Near-optimal Active Regression of Single-Index Models
by: Li, Yi, et al.
Published: (2025)

Learning general Gaussian mixtures with efficient score matching
by: Chen, Sitan, et al.
Published: (2024)

An efficient, provably optimal algorithm for the 0-1 loss linear classification problem
by: He, Xi, et al.
Published: (2023)

Online Search with Predictions: Pareto-optimal Algorithm and its Applications in Energy Markets
by: Lee, Russell, et al.
Published: (2022)

Provably learning a multi-head attention layer
by: Chen, Sitan, et al.
Published: (2024)

Robust learning of halfspaces under log-concave marginals
by: Lange, Jane, et al.
Published: (2025)

Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity
by: Amanatidis, Georgios, et al.
Published: (2021)

Achieving adaptivity and optimality for multi-armed bandits using Exponential-Kullback Leibler Maillard Sampling
by: Qin, Hao, et al.
Published: (2025)

On the Distribution of Unweighted Minimum Knapsack Instances with Large SOS Rank
by: Kurpisz, Adam, et al.
Published: (2026)

Proper decision trees: An axiomatic framework for solving optimal decision tree problems with arbitrary splitting rules
by: He, Xi, et al.
Published: (2025)

The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Bandits
by: Assadi, Sepehr, et al.
Published: (2023)

Efficient distributional regression trees learning algorithms for calibrated non-parametric probabilistic forecasts
by: Duchemin, Quentin, et al.
Published: (2025)

Combinatorial optimization of the coefficient of determination
by: Harary, Marc
Published: (2024)

Learning Mixtures of Spherical Gaussians via Fourier Analysis
by: Chakraborty, Somnath, et al.
Published: (2020)

Structure learning of Hamiltonians from real-time evolution
by: Bakshi, Ainesh, et al.
Published: (2024)