stochastic approximation

Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear (Sometimes Sublinear) Running Time

  • Mengdi Wang
    • Categories Dynamic Programming, Linear Programming Tags , , , , , ,

    We propose a randomized linear programming algorithm for approximating the optimal policy of the discounted Markov decision problem. By leveraging the value-policy duality, the algorithm adaptively samples state transitions and makes exponentiated primal-dual updates. We show that it finds an ε-optimal policy using nearly-linear running time in the worst case. For Markov decision processes that … Read more

    Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization

  • Donald Goldfarb
  • Wei Liu
  • Shiqian Ma
  • Xiao Wang
    • Categories Nonlinear Optimization Tags , , , , ,

    In this paper we study stochastic quasi-Newton methods for nonconvex stochastic optimization, where we assume that noisy information about the gradients of the objective function is available via a stochastic first-order oracle ($\SFO$). We propose a general framework for such methods, for which we prove almost sure convergence to stationary points and analyze its worst-case … Read more

    A Stochastic Majorize-Minimize Subspace Algorithm for Online Penalized Least Squares Estimation

  • Émilie Chouzenoux
  • Jean-Christophe Pesquet
    • Categories Convex Optimization, Unconstrained Optimization Tags , , , , , , , , , , ,

    Stochastic approximation techniques play an important role in solving many problems encountered in machine learning or adaptive signal processing. In these contexts, the statistics of the data are often unknown a priori or their direct computation is too intensive, and they have thus to be estimated online from the observed signals. For batch optimization of … Read more

    Stochastic Approximations and Perturbations in Forward-Backward Splitting for Monotone Operators

  • Patrick L. Combettes
  • Jean-Christophe Pesquet
    • Categories Infinite Dimensional Optimization, Stochastic Programming Tags , , , , ,

    We investigate the asymptotic behavior of a stochastic version of the forward-backward splitting algorithm for finding a zero of the sum of a maximally monotone set-valued operator and a cocoercive operator in Hilbert spaces. Our general setting features stochastic approximations of the cocoercive operator and stochastic perturbations in the evaluation of the resolvents of the … Read more

    Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization

  • Wei Liu
  • Shiqian Ma
  • Xiao Wang
    • Categories Nonlinear Optimization, Stochastic Programming Tags , , , , , ,

    In this paper we study stochastic quasi-Newton methods for nonconvex stochastic optimization, where we assume that only stochastic information of the gradients of the objective function is available via a stochastic first-order oracle (SFO). Firstly, we propose a general framework of stochastic quasi-Newton methods for solving nonconvex stochastic optimization. The proposed framework extends the classic … Read more

    On the Information-Adaptive Variants of the ADMM: an Iteration Complexity Perspective

  • Xiang Gao
  • Bo Jiang
  • Shuzhong Zhang
    • Categories Convex Optimization Tags , , , ,

    Designing algorithms for an optimization model often amounts to maintaining a balance between the degree of information to request from the model on the one hand, and the computational speed to expect on the other hand. Naturally, the more information is available, the faster one can expect the algorithm to converge. The popular algorithm of … Read more

    Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization

  • Saeed Ghadimi
  • Guanghui Lan
  • Hongchao Zhang
    • Categories Constrained Nonlinear Optimization, Convex and Nonsmooth Optimization Tags , , , , , ,

    This paper considers a class of constrained stochastic composite optimization problems whose objective function is given by the summation of a differentiable (possibly nonconvex) component, together with a certain non-differentiable (but convex) component. In order to solve these problems, we propose a randomized stochastic projected gradient (RSPG) algorithm, in which proper mini-batch of samples are … Read more

    Tail bounds for stochastic approximation

  • Michael P. Friedlander
  • Gabriel Goh
    • Categories Convex Optimization, Stochastic Programming Tags , , ,

    Stochastic-approximation gradient methods are attractive for large-scale convex optimization because they offer inexpensive iterations. They are especially popular in data-fitting and machine-learning applications where the data arrives in a continuous stream, or it is necessary to minimize large sums of functions. It is known that by appropriately decreasing the variance of the error at each … Read more

    Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization, II: Shrinking Procedures and Optimal Algorithms

  • Saeed Ghadimi
  • Guanghui Lan
    • Categories Convex Optimization, Nonlinear Optimization, Stochastic Programming Tags , , , , ,

    In this paper we study new stochastic approximation (SA) type algorithms, namely, the accelerated SA (AC-SA), for solving strongly convex stochastic composite optimization (SCO) problems. Specifically, by introducing a domain shrinking procedure, we significantly improve the large-deviation results associated with the convergence rate of a nearly optimal AC-SA algorithm presented by the authors. Moreover, we … Read more

    Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming

  • Saeed Ghadimi
  • Guanghui Lan
    • Categories Convex and Nonsmooth Optimization, Stochastic Programming, Unconstrained Optimization Tags , , , ,

    In this paper, we introduce a new stochastic approximation (SA) type algorithm, namely the randomized stochastic gradient (RSG) method, for solving an important class of nonlinear (possibly nonconvex) stochastic programming (SP) problems. We establish the complexity of this method for computing an approximate stationary point of a nonlinear programming problem. We also show that this … Read more