Confidence level solutions for stochastic programming

By Yu. N. Nesterov, Jean-Philippe Vial. 2000

87 citations recorded by the source corpus.

We propose an alternative approach to stochastic programming based on Monte-Carlo sampling and stochastic gradient optimization. The procedure is by essence probabilistic and the computed solution is a random variable. We propose a solution concept in which the probability that the random algorithm produces a solution with an expected objective value departing from the optimal one by more than @e is small enough. We derive complexity bounds on the number of iterations of this process. We show that by repeating the basic process on independent samples, one can significantly reduce the number of iterations.

Subfields: Computational Theory and Mathematics, Management Science and Operations Research, Statistics and Probability

How researchers see this paper

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

In Computational Theory and Mathematics

In Management Science and Operations Research

In Statistics and Probability

Citations in the corpus

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).”
Towards closing the gap between the theory and practice of SVRG (2019, methodology): “This is why, inspired by [20], we use the weighted averaging in Free-SVRG given in (10), which gives more importance to recent iterates compared to old ones.”
Dual Averaging Methods for Regularized Stochastic Learning and Online Optimization (2009, methodology): “The SGD method belongs to the general scheme of stochastic approximation, which can be traced back to Robbins and Monro (1951) and Kiefer and Wolfowitz (1952).”
Exponential convergence of testing error for stochastic gradient methods (2017, unknown): “…steps n typically as O (1 / √ n ) , or O (1 /n ) depending on the assumptions which are made on the problem (see, e.g., Polyak and Juditsky, 1992; Nesterov and Vial, 2008; Nemirovski et al., 2009; Shalev-Shwartz et al., 2007; Xiao, 2010; Bach and Moulines, 2011, 2013; Dieuleveut et al.,…”
Bridging the gap between constant step size stochastic gradient descent and Markov chains (2017, background): “This key methodological problem has raised interest in different communities: in large-scale machine learning [9, 53, 54], optimization [44, 46], and stochastic approximation [30, 48, 52].”
AdaBatch: Efficient Gradient Aggregation Rules for Sequential and Parallel Stochastic Gradient Methods (2017, background): “It is different but equivalent to using a decreasing step size (see [22] just before Corollary 1).”
Primal-dual subgradient methods for convex problems (2009, methodology): “In [ 14 ] this transformation was justified for a stochastic version of subgradient method (1.3 )( which is known to possess the feature (6.2)).”
Sharp Minima Can Generalize For Deep Nets (2017, background): “For example, Duchi et al. (2011); Nesterov & Vial (2008); Hardt et al. (2016); Bottou et al. (2016); Gonen & Shalev-Shwartz (2017) rely on the concept of stochastic approximation or uniform stability (Bousquet & Elisseeff, 2002).”
Statistical inference for model parameters in stochastic gradient descent (2016, methodology): “Note that the strong convexity of F (x) was adopted by Polyak and Juditsky (1992) (see Assumption 4.1 in Polyak and Juditsky (1992)) to derive the limiting distribution of averaged SGD, which serves as the basis of our work.”