Tight Complexity Bounds for Optimizing Composite Objectives

By Blake E. Woodworth, Nati Srebro. 2016

199 citations recorded by the source corpus.

We provide tight upper and lower bounds on the complexity of minimizing the average of $m$ convex functions using gradient and prox oracles of the component functions. We show a significant gap between the complexity of deterministic vs randomized optimization. For smooth functions, we show that accelerated gradient descent (AGD) and an accelerated variant of SVRG are optimal in the deterministic and randomized settings respectively, and that a gradient oracle is sufficient for the optimal rate. For non-smooth functions, having access to prox oracles reduces the complexity and we present optimal methods based on smoothing that improve over methods using just gradient accesses.

Subfields: Artificial Intelligence, Computational Mechanics, Optimization & Training, Mathematical Optimization

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

In Optimization & Training

In Mathematical Optimization

Citations in the corpus

Semi-Cyclic Stochastic Gradient Descent (2019, background): “…a composite objective to within , even if we could optimize each component separately, requires alternating between the two components at least Ω(B/ ) times (Woodworth & Srebro, 2016), establishing a lower bound on the number of required cycles, independent of the number of iterations per cycle.”
Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization (2018, methodology): “For the prox case, we construct two functions inspired by previous lower bounds for round-based and finite sum optimization [3, 27].”
Byzantine Stochastic Gradient Descent (2018, neutral): “(See for instance Woodworth and Srebro [37].)”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, background): “Recently, lower and upper bounds for complexity of stochastic methods on problems of the form (1) were recently obtained in [99].”
Katyusha: the first direct acceleration of stochastic gradient methods (2016, methodology): “This will make the algorithm statement less clean so we refrain from doing so in this paper. if the objective is σ -strongly convex— and this was achieved by his celebrated accelerated (full) gradient descent method [26].”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, background): “he need to tune additional parameter makes the method rather impractical. Recently, lower and upper bounds for complexity of stochastic methods on problems of the form (6.1) were recently obtained in [185]. 6.2.3 Distributed Setting In this section we review the literature concerning algorithms for ”
Accelerating Stochastic Gradient Descent (2017, background): “Zhu, 2016) that provide accelerated rates for ofﬂine stochastic optimization which deal with minimizing sums of convex functions; these results are almost tight owing to nearly matching lower bounds (Woodworth and Srebro, 2016). These results do not immediately translate into rates on the generaliza”
Less than a Single Pass: Stochastically Controlled Stochastic Gradient (2016, background): “Recently, Woodworth and Srebro (2016) establish a lower bound for the computational cost of randomized algorithms in minimizing the ﬁnite sums.”
Lower bounds for finding stationary points I (2017, methodology): “Following Woodworth and Srebro [45], we consider random rotations of our deterministic construction, and show that for any algorithm such a randomly rotated function is, with high probability, difficult.”
Lower Bound for Randomized First Order Convex Optimization (2017, methodology): “To do so, we use a technique we recently developed in order to analyze finite sum structured optimization problems [3].”
Minibatch vs Local SGD for Heterogeneous Distributed Learning (2020, unknown): “This is proven in Appendix G using techniques similar to those of Woodworth and Srebro [24] and Arjevani and Shamir [1].”
Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice (2017, background): “Moreover, the resulting convergence rates are near-optimal up to logarithmic constants according to the first-order lower bound (Woodworth and Srebro, 2016; Arjevani and Shamir, 2016).”
On the Randomized Complexity of Minimizing a Convex Quadratic Function (2018, background): “Woodworth and Srebro [2016] proved truly lower bounds against randomized ﬁrst-order algorithms for ﬁnite-sum optimization of convex functions, but their constructions require non-quadratic objectives.”
How To Make the Gradients Small Stochastically (2018, methodology): “In both cases, the offline stochastic method is no slower than the full-gradient ones (such as AGD), and known to be optimal [20].”
SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator (2018, methodology): “…with d ≥ 2 max(9n3K2, 12n2KR2) log ( 2n3K2 p ) + n2K ∼ O ( n2∆2L2 4 log ( n2∆2L2 4p )) , from Lemma 2 of Carmon et al. (2017b) (or similarly Lemma 7 of Woodworth & Srebro (2016) and Theorem 3 of Woodworth & Srebro (2017), also refer to Lemma 12 in the end of the paper), with probability at…”