Problem Complexity and Method Efficiency in Optimization

By J. Seidler. 1984

How researchers see this paper

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

Citations in the corpus

A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, neutral): “If ¯ σ 2 > 0 the convergence rate is asymptotically dominated by the ﬁrst term, which cannot be further improved for stochastic methods (Nemirovsky & Yudin, 1983).”
Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming (2013, neutral): “On the other hand, these developments, motivated by complexity theory in convex optimization [24], concerned the convergence properties of SA methods during a ﬁnite number of iterations.”
Practical Recommendations for Gradient-Based Training of Deep Architectures (2012, neutral): “Note however that in the pure online case (stream of examples) and under some assumptions, the sublinear rate of convergence of stochastic gradient descent with O (1 /t ) decrease of learning rate is an optimal rate, at least for convex problems (Nemirovski and Yudin, 1983).”
SGD: General Analysis and Improved Rates (2019, neutral): “Stochastic gradient descent (SGD) (Robbins & Monro, 1951; Nemirovski & Yudin, 1978; 1983; Shalev-Shwartz et al., 2007; Nemirovski et al., 2009; Hardt et al., 2016), has become the workhorse for training supervised machine learning problems which have the generic form (1).”
The importance of better models in stochastic optimization (2019, background): “Finding global minima of nonconvex functions is computationally infeasible (28), so we follow established practice and consider convergence to stationary points via the Moreau envelope (5, 29).”
Accelerated gradient methods for nonconvex nonlinear and stochastic programming (2013, neutral): “Moreover, in view of the classic complexity theory for convex optimization by Nemirovski and Yudin [22], the above O(1/ √ ) iteration complexity bound is not improvable for smooth convex optimization when n is sufficiently large.”
On the Computation and Communication Complexity of Parallel SGD with Dynamic Batch Sizes for Stochastic Non-Convex Optimization (2019, background): “Recall that O(1/T ) convergence is optimal for stochastic strongly convex optimization (Nemirovsky & Yudin, 1983; Rakhlin et al., 2012) over single node.”
Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization (2013, methodology): “Motivated by the complexity theory in convex optimization [24], these studies focus on the convergence properties of SA-type algorithms in a finite number of iterations.”