Robust Stochastic Approximation Approach to Stochastic Programming

By Arkadi Nemirovski, Anatoli B. Juditsky, Guanghui Lan, Alexander Shapiro. 2008

932 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Management Science and Operations Research, Statistics and Probability, Optimization & Training

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 Management Science and Operations Research

In Statistics and Probability

In Optimization & Training

Citations in the corpus

Dynamics of SGD with Stochastic Polyak Stepsizes: Truly Adaptive Variants and Convergence to Exact Solution (2022, methodology): “That is, we consider � k = min We note that, in the SGD case, simply picking e.g. k = � 0 / p k + 1 would guarantee convergence of f ( x k ) to f ( x ⇤ ) , in expectation and with high probability [20, 23].”
A Variational Inequality Perspective on Generative Adversarial Networks (2018, background): “1) with a constant step-size gives, Thm. 2 uses a similar proof as (Nemirovski et al., 2009).”
Qsparse-Local-SGD: Distributed SGD With Quantization, Sparsification, and Local Computations (2019, neutral): “This is a standard assumption in [SSS07, NJLS09, RRWN11, HK14, RSS12, SCJ18, Sti19, YYZ18, KSJ19, AHJ + 18].”
Fast Convergence of Stochastic Gradient Descent under a Strong Growth Condition (2013, neutral): “For strongly convex objective functions, the stochastic gradient method with a decreasing sequence of step sizes has an error of O (1 /k ) [Nemirovski et al., 2009, § 2.1] while the deterministic method with a constant step size has an linear convergence rate.”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “3 is inspired by gradient-free optimization, a topic extensively studied since [118, 147] — see [31, 67, 138, 140] for recent accounts on this theory.”
An asynchronous mini-batch algorithm for regularized stochastic optimization (2015, positive): “[7] demonstrated that a modified stochastic approximation method, the mirror descent, has an optimal expected iteration complexity of O(1/ (2)) for stochastic non-smooth convex problems.”
Finite-Sample Analysis of Proximal Gradient TD Algorithms (2015, methodology): “, 2008, 2009; Maei, 2011] and those made in the analysis of SG algorithms [Nemirovski et al., 2009].”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, background): “We refer the reader to [120, 124, 125, 20] for a recent theoretical and practical assessment of SGD.”
Semi-stochastic coordinate descent (2014, neutral): “Stochastic gradient descent (SGD) in each iteration computes the gradient of a single randomly chosen function fi only—this constitutes an unbiased (but noisy) estimate of the gradient of f —and makes a step in that direction [8,16,20,23].”
AUC Maximization in the Era of Big Data and AI: A Survey (2022, background): “The existing works consider two learning settings: online setting similar to stochastic approximation in conventional literature [130], and offline setting similar to stochastic average approximation in conventional literature [108].”
Decentralized Federated Averaging (2021, methodology): “The convergence rate in Proposition 1 coincides with existing results of the optimal rate of SGD with respect to T under the strong convexity assumption [51], [52].”
Communication-efficient algorithms for statistical optimization (2012, neutral): “Consequently, performing stochastic gradient descent on F1 for O(log2(mn)/ρ2) iterations yields an approximate minimizer that falls within Bρ(θ1) with high probability (e.g. Nemirovski et al., 2009, Proposition 2.1).”
ODE Analysis of Stochastic Gradient Methods with Optimism and Anchoring for Minimax Problems and GANs (2019, neutral): “Classical literature analyze convergence of the Polyak-averaged iterates (which assigns less weight to newer iterates) when solving convex-concave saddle point problems using stochastic subgradients [47, 46, 24, 17].”
Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression (2013, methodology): “In this section, we review existing results for Lipschitz-continuous non-strongly convex problems (Nesterov and Vial, 2008; Nemirovski et al., 2009; Shalev-Shwartz et al., 2009; Duchi and Singer, 2009; Xiao, 2010).”
Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization, II: Shrinking Procedures and Optimal Algorithms (2013, methodology): “We compare the single-stage AC-SA algorithms, the multi-stage AC-SA algorithms, the classic SA (see, e.g., [13]), the mirror descent SA ([9]) and the batch-learning approach in the following way.”
Bayesian inference with optimal maps (2011, positive): “In this sense, the present scheme bears strong similarities to the SAA (sample average approximation) approach to stochastic programming [49].”
Theoretical properties of the global optimizer of two layer neural network (2017, methodology): “So we can implement many procedures developed in the Stochastic optimization literature to get the convergence to optimal value [19].”