Research map / Optimization / Nonconvex and smooth optimization
Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use sampling probabilities proportional to the square root of coordinate smoothness instead of proportional to coordinate smoothness | Accelerated coordinate descent · Euclidean norm, strongly convex and convex objectives | iteration complexity: √(n P_i Li) -> P_i √Li | Helped |
| Use sampling probabilities proportional to L_i^((1−β)/2) instead of L_i^(1−β) | Accelerated coordinate descent in the Lβ norm · Lβ norm, strongly convex and convex objectives | iteration complexity: √(nS1−β) -> S(1−β)/2 | Helped |
| Use square-root-smoothness sampling rather than ACDM sampling | NU ACDM on ridge regression · news20, w8a, and covtype | theoretical speed-up factor over ACDM: 1.56772; 1.30740; 1.05110; 1.11060; 1.04897; 1.00373; 1.04266; 1.02787; 1.00362 | Helped |
| Sample linear-system rows proportional to their Euclidean norms rather than using ACDM sampling | NU ACDM for solving linear systems · Linear systems with non-uniform row norms | theoretical speed-up factor over ACDM: 1.0992; 1.2464; 1.4025; 1.6243; 1.7379 | Helped |
| Use square-root-norm row sampling rather than ACDM sampling | NU ACDM for solving linear systems · Linear systems with uniform row norms (r = 100%) | theoretical speed-up factor over ACDM: 1 | No clear effect |
| Choose smaller β values rather than larger β values (ablation) | NU ACDMns · ℓ2−ℓ1 Penalty Regression | convergence performance | Helped |
| Use β values between 0 and 0.8 rather than β = 1 (ablation) | NU ACDMns · ℓ2−ℓ1 Penalty Regression | convergence performance | Helped |
| Use non-uniform square-root sampling rather than uniform sampling (ablation) | NU ACDMns · ℓ2−ℓ1 Penalty Regression on covtype | convergence performance | No clear effect |
Closest papers by meaning
- Adaptive Sampling Probabilities for Non-Smooth Optimization (ICML 2017 · similarity 0.90)
- Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent (ICML 2025 · similarity 0.88)
- Tighter Convergence Bounds for Shuffled SGD via Primal-Dual Perspective (NeurIPS 2024 · similarity 0.87)
- Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems (ICML 2025 · similarity 0.87)
- The Sample Complexity of Gradient Descent in Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.86)
- Block Acceleration Without Momentum: On Optimal Stepsizes of Block Gradient Descent for Least-Squares (ICML 2024 · similarity 0.86)
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.