Optimal Black-Box Reductions Between Optimization Objectives

By Zeyuan Allen-Zhu, Elad Hazan. 2016

98 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

Citations in the corpus

How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD (2018, background): “To the best of our knowledge, the analysis in [4] (and the references therein) cannot be applied to this paper.”
Introduction to Online Convex Optimization (2016, background): “3 can be removed with a more careful reduction and analysis, for details see (9).”
Tight Complexity Bounds for Optimizing Composite Objectives (2016, methodology): “The log-factor in the second term can be removed using the more delicate reduction of Allen-Zhu and Hazan [4], which involves optimizing F (x) for progressively smaller values of , yielding the upper bound in the table.”
L-SVRG and L-Katyusha with Arbitrary Sampling (2019, methodology): “(23) The following property can be found in (Allen-Zhu and Hazan, 2016).”
Optimization Methods for Large-Scale Machine Learning (2016, result): “can be derived as extensions of the results presented here [3], making our analyses a starting point for deriving a more general theory.”
Guaranteed Sufficient Decrease for Stochastic Variance Reduced Gradient Optimization (2018, methodology): “, support vector machine), we can use the proximal operator oracle [40] or the Nesterov’s smoothing [41] technique to smoothen them, and thereby obtain the smoothed approximations of the functions fi(x).”
How To Make the Gradients Small Stochastically (2018, background): “For instance, when reducing weakly-convex optimization to strongly-convex optimization (both in terms of convergence in objective value), one can keep halving the value of σ for a logarithmic number of rounds [3].”