mlsanityData to 7 Oct 2026

Optimal Black-Box Reductions Between Optimization Objectives

arXiv 1603.05642 ↗First posted 17 Mar 2016math.OC cs.DS cs.LGcited by 21

Not on the map. Why?

Abstract (arXiv)

The diverse world of machine learning applications has given rise to a plethora of algorithms and optimization methods, finely tuned to the specific regression or classification task at hand. We reduce the complexity of algorithm design for machine learning by reductions: we develop reductions that take a method developed for one setting and apply it to the entire spectrum of smoothness and strong-convexity in applications. Furthermore, unlike existing results, our new reductions are OPTIMAL and more PRACTICAL. We show how these new reductions give rise to new and faster running times on training linear classifiers for various families of loss functions, and conclude with experiments showing their successes also in practice.

Key facts. Cited by 21 papers in the map (data through 7 Oct 2026). First posted on arXiv 17 Mar 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 8; 2022: 3; 2023: 2; 2024: 3; 2025: 3; 2026: 2.

21 papers.

Sort:

  1. 2024Smooth Tchebycheff Scalarization for Multi-Objective Optimizationcited by 50
  2. 2021Oracle Complexity in Nonsmooth Nonconvex Optimizationcited by 38
  3. 2021Robust Regression Revisited: Acceleration and Improved Estimation Ratescited by 15
  4. 2022Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methodscited by 14
  5. 2021Acceleration via Fractal Learning Rate Schedulescited by 13
  6. 2021Variance Reduction via Primal-Dual Accelerated Dual Averaging for Nonsmooth Convex Finite-Sumscited by 10
  7. 2021An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learningcited by 10
  8. 2022Accelerated SGD for Non-Strongly-Convex Least Squarescited by 9
  9. 2021First-Order Methods for Convex Optimizationcited by 4
  10. 2025SAPPHIRE: Preconditioned Stochastic Variance Reduction for Faster Large-Scale Statistical Learningcited by 4
  11. 2023Optimal Guarantees for Algorithmic Reproducibility and Gradient Complexity in Convex Optimizationcited by 3
  12. 2024Quantum Algorithms and Lower Bounds for Finite-Sum Optimizationcited by 3
9 more
  1. 2021Delayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applicationscited by 2
  2. 2025On the Condition Number Dependency in Bilevel Optimizationcited by 2
  3. 2025Safety in the Face of Adversity: Achieving Zero Constraint Violation in Online Learning with Slowly Changing Constraintscited by 1
  4. 2026Towards Universal Convergence of Backward Error in Linear System Solverscited by 1
  5. 2021Utilizing Redundancy in Cost Functions for Resilience in Distributed Optimization and Learningcited by 0
  6. 2022Impact of Redundancy on Resilience in Distributed Optimization and Learningcited by 0
  7. 2023Accelerated Doubly Stochastic Gradient Algorithm for Large-scale Empirical Risk Minimizationcited by 0
  8. 2024Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithmscited by 0
  9. 2026Halpern Iteration Achieves tildeO(ε-1/p) pth-Order Oracle Complexity for Monotone Variational Inequalitiescited by 0