Cover Image

All ERMs Can Fail in Stochastic Convex Optimization Lower Bounds in Linear Dimension

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Burla, Tal, Livni, Roi
Format:	Preprint
Published:	2026
Subjects:	Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The Sample Complexity of Gradient Descent in Stochastic Convex Optimization
by: Livni, Roi
Published: (2024)

Information Theoretic Lower Bounds for Information Theoretic Upper Bounds
by: Livni, Roi
Published: (2023)

Rapid Overfitting of Multi-Pass Stochastic Gradient Descent in Stochastic Convex Optimization
by: Vansover-Hager, Shira, et al.
Published: (2025)

Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorization
by: Attias, Idan, et al.
Published: (2024)

On Traceability in $\ell_p$ Stochastic Convex Optimization
by: Voitovych, Sasha, et al.
Published: (2025)

Data Selection for ERMs
by: Hanneke, Steve, et al.
Published: (2025)

Can Copyright be Reduced to Privacy?
by: Elkin-Koren, Niva, et al.
Published: (2023)

Low Resource Reconstruction Attacks Through Benign Prompts
by: Yarkoni, Sol, et al.
Published: (2025)

New Lower Bounds for Stochastic Non-Convex Optimization through Divergence Decomposition
by: Saad, El Mehdi, et al.
Published: (2025)

Credit Attribution and Stable Compression
by: Livni, Roi, et al.
Published: (2024)

Provable Complexity Improvement of AdaGrad over SGD: Upper and Lower Bounds in Stochastic Non-Convex Optimization
by: Jiang, Ruichen, et al.
Published: (2024)

On Linear Convergence in Smooth Convex-Concave Bilinearly-Coupled Saddle-Point Optimization: Lower Bounds and Optimal Algorithms
by: Kovalev, Dmitry, et al.
Published: (2024)

The Dimension Strikes Back with Gradients: Generalization of Gradient Methods in Stochastic Convex Optimization
by: Schliserman, Matan, et al.
Published: (2024)

Margin in Abstract Spaces
by: Ashlagi, Yair, et al.
Published: (2026)

Learning from Equivalence Queries, Revisited
by: Braverman, Mark, et al.
Published: (2026)

Complexity of Vector-valued Prediction: From Linear Models to Stochastic Convex Optimization
by: Schliserman, Matan, et al.
Published: (2024)

Lower Complexity Bounds for Nonconvex-Strongly-Convex Bilevel Optimization with First-Order Oracles
by: Ji, Kaiyi
Published: (2025)

Effective Dimension Aware Fractional-Order Stochastic Gradient Descent for Convex Optimization Problems
by: Partohaghighi, Mohammad, et al.
Published: (2025)

Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks
by: Kovalev, Dmitry, et al.
Published: (2024)

Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound
by: Sakaue, Shinsaku, et al.
Published: (2025)

Enhancing Parallelism in Decentralized Stochastic Convex Optimization
by: Eisen, Ofri, et al.
Published: (2025)

Improved Dimension Dependence for Bandit Convex Optimization with Gradient Variations
by: Yu, Hang, et al.
Published: (2026)

Stochastic Difference-of-Convex Optimization with Momentum
by: Chayti, El Mahdi, et al.
Published: (2025)

The Price of Adaptivity in Stochastic Convex Optimization
by: Carmon, Yair, et al.
Published: (2024)

Lower Bounds and Accelerated Algorithms in Distributed Stochastic Optimization with Communication Compression
by: He, Yutong, et al.
Published: (2023)

Riemannian Stochastic Optimization for Sufficient Dimension Reduction
by: Pautrel, Thibault, et al.
Published: (2026)

Optimal Rates for Robust Stochastic Convex Optimization
by: Gao, Changyu, et al.
Published: (2024)

We Should Separate Memorization from Copyright
by: Haviv, Adi, et al.
Published: (2026)

Asymptotics of Non-Convex Generalized Linear Models in High-Dimensions: A proof of the replica formula
by: Vilucchio, Matteo, et al.
Published: (2025)

Not Every Image is Worth a Thousand Words: Quantifying Originality in Stable Diffusion
by: Haviv, Adi, et al.
Published: (2024)

Complexity Lower Bounds of Adaptive Gradient Algorithms for Non-convex Stochastic Optimization under Relaxed Smoothness
by: Crawshaw, Michael, et al.
Published: (2025)

Bilevel Optimization with Lower-Level Uniform Convexity: Theory and Algorithm
by: Wu, Yuman, et al.
Published: (2026)

Simulation Based Bayesian Optimization
by: Naveiro, Roi, et al.
Published: (2024)

Flat Minima and Generalization: Insights from Stochastic Convex Optimization
by: Schliserman, Matan, et al.
Published: (2025)

Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variance
by: Fazla, Arda, et al.
Published: (2026)

Tight Lower Bounds under Asymmetric High-Order Hölder Smoothness and Uniform Convexity
by: Bai, Cedar Site, et al.
Published: (2024)

A Gapped Scale-Sensitive Dimension and Lower Bounds for Offset Rademacher Complexity
by: Jia, Zeyu, et al.
Published: (2025)

Distributed Online Convex Optimization with Efficient Communication: Improved Algorithm and Lower bounds
by: Yang, Sifan, et al.
Published: (2026)

Regret Lower Bounds for Learning Linear Quadratic Gaussian Systems
by: Ziemann, Ingvar, et al.
Published: (2022)

Tight Bounds for Online Convex Optimization with Adversarial Constraints
by: Sinha, Abhishek, et al.
Published: (2024)