Optimal Black-Box Reductions Between Optimization Objectives
arXiv:1603.05642
Abstract
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.
arXiv commentnew applications of our optimal reductions are obtained in this version 3
Cited by in corpus (16)
- Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling
- Tight Complexity Bounds for Optimizing Composite Objectives
- On the Adaptivity of Stochastic Gradient-Based Optimization
- Fast Stochastic Variance Reduced Gradient Method with Momentum Acceleration for Machine Learning
- Convergence Rates Analysis of The Quadratic Penalty Method and Its Applications to Decentralized Distributed Optimization
- Higher-Order Accelerated Methods for Faster Non-Smooth Optimization
- Katyusha Acceleration for Convex Finite-Sum Compositional Optimization
- Global Riemannian Acceleration in Hyperbolic and Spherical Spaces
- An adaptive proximal point algorithm framework and application to large-scale optimization
- The Minimax Complexity of Distributed Optimization
- Dual Averaging is Surprisingly Effective for Deep Learning Optimization
- Delayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applications
- Variance Reduction via Primal-Dual Accelerated Dual Averaging for Nonsmooth Convex Finite-Sums
- An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learning
- Larger is Better: The Effect of Learning Rates Enjoyed by Stochastic Optimization with Progressive Variance Reduction
- The Lingering of Gradients: Theory and Applications