Stochastic Approximation approach to Stochastic Programming

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

1,732 citations recorded by the source corpus.

How researchers see this paper

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

In Optimization & Training

Citations in the corpus

Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity (2021, methodology): “In particular for the analysis of stochastic algorithms, papers assume either bounded operators [Nemirovski et al., 2009, Abernethy et al., 2021] or bounded variance [Juditsky et al., 2011, Yang et al., 2020, Lin et al., 2020a, Luo et al., 2020, Tran Dinh et al., 2020] and growth condition [Lin et…”
Stochastic Hamiltonian Gradient Methods for Smooth Games (2020, background): “Stochastic gradient descent (SGD) (Robbins & Monro, 1951; Nemirovski & Yudin, 1978; 1983; Nemirovski et al., 2009; Hardt et al., 2016; Gower et al., 2019; 2020; Loizou et al., 2020) is the workhorse for training supervised machine learning problems.”
Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence (2020, methodology): “Stochastic gradient descent (SGD) (Robbins and Monro, 1951; Nemirovski and Yudin, 1978, 1983; Shalev-Shwartz et al., 2007; Nemirovski et al., 2009; Hardt et al., 2016), is the workhorse for training supervised machine learning problems that have the generic form (1).”
Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates (2019, background): “Starting from L-smoothness of f , Taking expectations with respect to ik and noting that η k is independent of ∇ f ik ( w k ) , 1 ≤ 0 and we may lower bound η k using Equation 2, Taking expectation w.r.t η k and w k , Summing over iterations, We can extend this result to obtain a linear convergence ”
Quantifying Learning Guarantees for Convex but Inconsistent Surrogates (2018, methodology): “The constants R and Qmax come from the kernel ASGD setup and, importantly, depend only on the data distribution, but not on the loss L or score matrix F .”
On Structured Prediction Theory with Calibrated Convex Surrogate Losses (2017, background): “Theorem 5 is a straight-forward extension of classical results [33, 36].”
Hogwild: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent (2011, methodology): “In contrast, Nemirovski et al demonstrate that when the stepsize is inversely proportional to the iteration counter, an overestimate of c can result in exponential slow-down [21]! Robust 1/k rates.”
Optimization Methods for Large-Scale Machine Learning (2016, methodology): “ect to the same upper bound (4.20), but the stepsize parameter must be larger than 1=(c). This additional requirement is critical to ensure the O(1=k) convergence rate. How critical? Consider, e.g., [105] in which the authors provide a simple example (with unbiased gradient estimates and = 1) involv”
Train faster, generalize better: Stability of stochastic gradient descent (2015, methodology): “We can combine our bounds on the generalization error of stochastic gradient method with optimization bounds quantifying the convergence of the empirical loss achieved by SGM.”
Minimizing finite sums with the stochastic average gradient (2013, background): “The randomly chosen gradient f ′ ik (x k) yields an unbiased estimate of the true gradient g′(xk) and one can show under standard assumptions (see [40]) that, for a suitably”
Communication trade-offs for synchronized distributed SGD with large step size (2019, background): “This problem has received attention from various communities over the last fifty years in optimization, stochastic approximation, and machine learning (Polyak and Juditsky, 1992; Ruppert, 1988; Fabian, 1968; Nesterov and Vial, 2008; Nemirovski et al., 2009; Shalev-Shwartz et al., 2009; Zhang, 2004).”
Protection Against Reconstruction and Its Applications in Private Federated Learning (2018, methodology): “In these cases, mirror-descent-based methods [60, 14] have convergence rates for stochastic optimization problems that scale as √ , where M ∞ denotes the (cid:96) ∞ -radius of the gradients ∇ (cid:96) and R 1 the (cid:96) 1 -radius of the constraint set Θ in the problem (3).”
D2: Decentralized Training over Decentralized Data (2018, background): “The SGD approahces [Ghadimi and Lan, 2013, Moulines and Bach, 2011, Nemirovski et al., 2009] is quite powerful for solving large-scale machine learning problems.”
Asynchronous Decentralized Parallel Stochastic Gradient Descent (2017, methodology): “Note that if T = 0 and n = 1 the proposed AD-PSGD reduces to the vanilla SGD algorithm (Nemirovski et al., 2009; Moulines and Bach, 2011; Ghadimi and Lan, 2013).”
Better Mini-Batch Algorithms via Accelerated Gradient Methods (2011, methodology): “These methods are characterized by incremental updates based on subgradients ∂(cid:96) ( w , z i ) of individual instances, and enjoy the advantages of being highly scalable and simple to implement.”