Research map / Learning theory and algorithms / Sample complexity
Sparse Polyak: an adaptive step size rule for high-dimensional M-estimation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Sparse Polyak, an adaptive step size for iterative hard thresholding that uses the hard-thresholded gradient norm (restricted Lipschitz smoothness) instead of the full gradient norm, giving dimension-invariant convergence for high-dimensional M-estimation.
Problem
Choosing step sizes for iterative hard thresholding in high-dimensional sparse M-estimation (d much larger than n); classical Polyak step sizes degrade as dimension grows even when conditioning and statistical precision are fixed.
Approach
Replace the full gradient norm in Polyak's step size with the norm of the hard-thresholded gradient, so the step size tracks restricted (sparse-direction) smoothness rather than the ambient Lipschitz constant that scales with d, yielding rate invariance under RSC/RSS.
Key results
- Sparse Polyak achieves rate invariance: iterations to statistical precision stay roughly constant as d grows (5000 to 20000) while classical Polyak's iteration count increases.
- Theorem 1 gives linear contraction at rate (1 - 1/(80 kappa)) up to precision 36||HT_s(grad f(theta_hat))||^2 / mu_bar^2, matching the rate of IHT with known smoothness up to constants.
- Adaptive lower-bound variant (Algorithm 2) reaches optimal statistical precision when only a lower bound on f(theta*) is known, such as 0.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace the full gradient norm in Polyak's step size with the hard-thresholded gradient norm | IHT for high-dimensional sparse logistic regression · Synthetic logistic regression with increasing dimension | iterations to reach near-optimal statistical precision | Helped |
| Use the classical Polyak step size based on the full gradient norm instead of the hard-thresholded gradient norm | IHT for high-dimensional M-estimation · Synthetic problems with increasing dimension | iterations to reach near-optimal statistical precision | Hurt |
| Use the adaptive Sparse Polyak step size instead of the fixed step size | IHT · Synthetic linear regression | convergence speed | Helped |
| Use the adaptive Sparse Polyak step size instead of the fixed step size | IHT · Synthetic logistic regression | convergence speed | Helped |
| Change the target function value used by Sparse Polyak | Sparse Polyak · Synthetic experiments with different target values | achievable accuracy | Mixed |
Surprising findings
- Classical Polyak step size degrades with dimension even when restricted condition number and statistical precision are held constant.
- Lipschitz-based adaptive step-size rules are argued to scale as O(d) in high dimensions and therefore fail to achieve rate invariance.
Limitations
- Theory requires the restricted condition number and sparsity conditions such as s >= (240 kappa)^2 s* which can be demanding.
- Guaranteed convergence to optimal precision requires knowledge of f(theta*) or a lower bound; the adaptive variant needs a double loop.
- Analysis is for Polyak-type step sizes only; the authors conjecture other adaptive rules suffer similarly without proof.
Experimental setup
Datasets: synthetic sparse linear regression data synthetic sparse logistic regression data real-world datasets (Appendix D)
Benchmarks: synthetic sparse linear regression synthetic sparse logistic regression real data experiments (Appendix D)
Metrics: iterations to statistical precision estimation error ||theta_t - theta*||^2 objective suboptimality
Baselines: IHT with fixed step size 2/(3L) IHT with classical Polyak step size
Builds on: Polyak step size iterative hard thresholding restricted strong convexity and smoothness
Closest papers by meaning
- New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative Results (NeurIPS 2025 · similarity 0.85)
- The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements (NeurIPS 2025 · similarity 0.84)
- A Subquadratic Time Algorithm for Robust Sparse Mean Estimation (ICML 2024 · similarity 0.84)
- Generalized Smooth Variational Inequalities: Methods with Adaptive Stepsizes (ICML 2024 · similarity 0.84)
- Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination (ICML 2024 · similarity 0.83)
- Exact Recovery of Sparse Binary Vectors from Generalized Linear Measurements (ICML 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.