Validation analysis of mirror descent stochastic approximation method

By Guanghui Lan, Arkadi Nemirovski, Alexander Shapiro. 2012

156 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Management Science and Operations Research, Numerical Analysis

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 Numerical Analysis

Citations in the corpus

Communication-efficient algorithms for decentralized and stochastic optimization (2017, neutral): “i ,x ∗− ut−1,k i i} 1≤i≤m,1≤t≤T k,k≥1 is a martingale-diﬀerence sequence. Denoting γk,t := Pθ kλ t T k t=1λt , and using the large-deviation theorem for martingale-diﬀerence sequence (e.g. Lemma 2 of [25]) and the fact that E[exp{γ2 k,thδ t−1,k i,x ∗ i − u 1,ki2/(2γ2 k,t V¯ i(x ∗ i )σ 2)}] ≤ E[exp{k”
Training Quantized Nets: A Deeper Understanding (2017, neutral): “, the large-deviation estimates in [22]).”
Algorithms for stochastic optimization with expectation constraints (2016, background): “Lan, Nemirovski and Shapiro (see [21] Section 4.”
Group-Based Alternating Direction Method of Multipliers for Distributed Linear Classification (2017, methodology): “, gradient method [3]–[5], mirror descent [6], and dual averaging method [7].”
Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization (2016, methodology): “Other SA methods with provable complexities for solving convex stochastic optimization problems were also studied in [19, 26, 27, 28, 29, 30, 2, 13, 1, 51, 54].”
Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization, II: Shrinking Procedures and Optimal Algorithms (2013, methodology): “…et al. [13] demonstrated that a properly modiﬁed SA method based on iterate averaging, namely, the mirror-descent SA, can be competitive and even signiﬁcantly outperform the Sample Average Approximation (see, e.g., [7, 10, 22]) method for a certain class of stochastic optimization problems.”
Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization (2014, methodology): “In the analysis, we used the following well-known martingale inequality, a restatement of Lemma 2 of Lan et al. [2012]. Here, Et[·] denotes the expectation at time t conditioned on all the randomness till time t− 1.”
Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization I: A Generic Algorithmic Framework (2012, background): “A proof of this result can be found, for example, in [21].”
Monte Carlo sampling-based methods for stochastic optimization (2014, methodology): “[142] develop a lower bound for the mirror descent SA algorithm using the gradient estimates obtained throughout the algorithm.”