Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization I: A Generic Algorithmic Framework

By Saeed Ghadimi, Guanghui Lan. 2012

398 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research, 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 Management Science and Operations Research

In Optimization & Training

In Mathematical Optimization

Citations in the corpus

Optimal Distributed Online Prediction Using Mini-Batches (2010, background): “…expected optimality bound of ¯ ψ ( σ 2 , m ) = 4 D 2 L / m 2 + 4 Dσ / √ m , which translates into the following bound for the DMB algorithm: Most recently, Ghadimi and Lan (2010) developed accelerated stochastic gradient methods for strongly convex functions that have the convergence rate ¯ ψ (…”
How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD (2018, background): “1(b) is recorded for the accelerated version of SGD [15], but with a”
Variance-based Regularization with Convex Objectives (2016, background): “ √ n with high probability, as long as the growth of R away from its optima scales appropriately. For example, when γ = 2, which corresponds to the usual strong convexity conditions in the literature [17, 15] (though ours is easier to satisfy, as it is a more local notion of strong convexity), we ob”
A reliable effective terascale linear learning system (2011, background): “o reach an -error is at least (Nemirovski and Yudin, 1983) T batch = p log 1 ; (6) where = L=. For the hybrid approach, the rst online pass over the n samples guarantees an error of O(=n) (Lan and Ghadimi, 2010). Then the total number of passes over data needed by the hybrid approach in the batch”
Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning (2014, background): “Based on their ﬁndings, we do not include in our ﬁgures other variants of SGD, e.g., [17, 23, 25, 49].”
Non-Uniform Stochastic Average Gradient Method for Training Conditional Random Fields (2015, methodology): “On these datasets we compared the performance of a set of competitive methods, including ﬁve variants on classic stochastic gradient methods: Pegasos which is a standard stochastic gradient method with a step-size of α = η/λt on iteration t [Shalev-Shwartz et al., 2011], 6 a basic stochastic gradien”
Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization (2013, background): “See for example [10, 9, 4] and the references therein.”
On the rates of convergence of parallelized averaged stochastic gradient algorithms (2017, background): “Among the studied cases, two of them attract a lot of attention: globally strongly convex objectives [11,12], and locally strongly convex ones [13–16].”
Accelerated gradient methods for nonconvex nonlinear and stochastic programming (2013, methodology): “48) and using some existing results on prox-mapping discussed in [10].”
Stochastic Approximation of Smooth and Strongly Convex Functions: Beyond the O(1/T) Convergence Rate (2019, methodology): “COMPARISONS WITH PREVIOUS RESULTS In the following, we compare our Theorem 1 and Corollary 2 with related work in SA (Ghadimi and Lan, 2012; Dieuleveut et al., 2017; Jain et al., 2018; Moulines and Bach, 2011; Needell et al., 2014) and SAA (Zhang et al.”
Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variants (2014, methodology): “ging). In the last decade, there has been a surge of interest in the development of techniques for stochastic convex optimization with a focus on optimal constant steplengths [34], composite problems [35,36] and nonconvexity [37,38]. However, in the context of stochastic variational inequality probl”
Stochastic Gradient Methods for Distributionally Robust Optimization with f-divergences (2016, background): “(This is not just a theoretical issue: in extensive simulations that we omit because they are a bit boring, SGD and other heuristic approaches that impose shrinking bounds of the form c > at each iteration t all fail to optimize the objective (5).)”
Algorithms for stochastic optimization with expectation constraints (2016, background): “It should be noted, however, that none of these SA algorithms are applicable to expectation constrained problems, since each iteration of these algorithms requires the projection over the feasible set { x ∈ X g ( x ) ≤ 0 , which is computationally prohibitive as g is given in the form of…”
Statistical inference for model parameters in stochastic gradient descent (2016, methodology): “, Ghadimi and Lan (2012) and references therein). However, due to the proximal operator (i.e., the soft-thresholding operator for `1-regularized problem), the distribution of the average iterate x̄n no longer converges to a multivariate normal distribution. To address this challenge, we use the rece”
Accelerated schemes for a class of variational inequalities (2014, methodology): “, e.g., when H = 0 or H is linear. In particular, when H = 0, SVI(Z,F) is equivalent to the stochastic minimization problem ofminu∈Z G(u)+J(u), Lan ﬁrst presented in [16] (see more general results in [11, 12]) an accelerated stochastic approximation method and showed that the iteration complexity of”