stochastic approximation – Page 3

A randomized Mirror-Prox method for solving structured large-scale matrix saddle-point problems

Published: 2011/12/06

In this paper, we derive a randomized version of the Mirror-Prox method for solving some structured matrix saddle-point problems, such as the maximal eigenvalue minimization problem. Deterministic first-order schemes, such as Nesterov’s Smoothing Techniques or standard Mirror-Prox methods, require the exact computation of a matrix exponential at every iteration, limiting the size of the problems … Read more

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

Published: 2010/07/03, Updated: 2012/06/18

Saeed Ghadimi

Guanghui Lan

Convex Optimization, Data-Mining, Stochastic Programming complexity, convex optimization, large deviation, optimal method, stochastic approximation, stochastic programming

In this paper we present a generic algorithmic framework, namely, the accelerated stochastic approximation (AC-SA) algorithm, for solving strongly convex stochastic composite optimization (SCO) problems. While the classical stochastic approximation (SA) algorithms are asymptotically optimal for solving differentiable and strongly convex problems, the AC-SA algorithm, when employed with proper stepsize policies, can achieve optimal or … Read more

Efficient Methods for Stochastic Composite Optimization

Published: 2008/08/05

Guanghui Lan

Convex and Nonsmooth Optimization, Stochastic Programming complexity, convex optimization, optimal method, stochastic approximation, stochastic programming

This paper considers an important class of convex programming problems whose objective function $\Psi$ is given by the summation of a smooth and non-smooth component. Further, it is assumed that the only information available for the numerical scheme to solve these problems is the subgradient of $\Psi$ contaminated by stochastic noise. Our contribution mainly consists … Read more

Validation Analysis of Robust Stochastic Approximation Method

Published: 2008/05/20, Updated: 2009/05/25

Guanghui Lan

Arkadi Nemirovski

Alexander Shapiro

Stochastic Programming asset allocation problem, conditional-value-at-risk, large deviations estimates, mirror descent algorithm, monte carlo sampling, optimality bounds, prox mapping, sample average approximation method, stochastic approximation, stochastic programming

The main goal of this paper is to develop accuracy estimates for stochastic programming problems by employing robust stochastic approximation (SA) type algorithms. To this end we show that while running a Robust Mirror Descent Stochastic Approximation procedure one can compute, with a small additional effort, lower and upper statistical bounds for the optimal objective … Read more

Stochastic Approximation approach to Stochastic Programming

Published: 2007/09/26, Updated: 2007/10/03

Convex and Nonsmooth Optimization, Stochastic Programming complexity, minimax problems, mirror descent algorithms, monte carlo sampling, saddle point problem, sample average approximation method, stochastic approximation, stochastic programming

In this paper we consider optimization problems where the objective function is given in a form of the expectation. A basic difficulty of solving such stochastic optimization problems is that the involved multidimensional integrals (expectations) cannot be computed with high accuracy. The aim of this paper is to compare two computational approaches based on Monte … Read more