Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization

DOI10.1007/S10107-014-0846-1zbMATH Open1332.90196arXiv1308.6594OpenAlexW2029463628MaRDI QIDQ5962719FDOQ5962719

Authors: Saeed Ghadimi, Guanghui Lan, Hongchao Zhang 

Publication date: 23 February 2016

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Abstract: 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 taken at each iteration depending on the total budget of stochastic samples allowed. The RSPG algorithm also employs a general distance function to allow taking advantage of the geometry of the feasible region. Complexity of this algorithm is established in a unified setting, which shows nearly optimal complexity of the algorithm for convex stochastic programming. A post-optimization phase is also proposed to significantly reduce the variance of the solutions returned by the algorithm. In addition, based on the RSPG algorithm, a stochastic gradient free algorithm, which only uses the stochastic zeroth-order information, has been also discussed. Some preliminary numerical results are also provided.

Full work available at URL: https://arxiv.org/abs/1308.6594

Recommendations

• Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming
• A hybrid stochastic optimization framework for composite nonconvex optimization
• A stochastic Nesterov's smoothing accelerated method for general nonsmooth constrained stochastic composite convex optimization
• Random gradient-free minimization of convex functions
• Momentum-based variance-reduced proximal stochastic gradient method for composite nonconvex stochastic optimization

zbMATH Keywords

nonconvex optimizationstochastic approximationstochastic programmingfirst-order methodmini-batch of sampleszeroth-order methodconstrained stochastic programming

Mathematics Subject Classification ID

Convex programming (90C25) Large-scale problems in mathematical programming (90C06) Numerical methods based on nonlinear programming (49M37) Semidefinite programming (90C22)

Cites Work

• Variational Analysis
• Introductory lectures on convex optimization. A basic course.
• Title not available (Why is that?)
• Acceleration of Stochastic Approximation by Averaging
• A Stochastic Approximation Method
• Title not available (Why is that?)
• The ordered subsets mirror descent optimization method with applications to tomography
• Robust Stochastic Approximation Approach to Stochastic Programming
• Title not available (Why is that?)
• Introduction to Stochastic Search and Optimization
• Bregman Monotone Optimization Algorithms
• Random gradient-free minimization of convex functions
• Accelerated gradient methods for nonconvex nonlinear and stochastic programming
• Optimization for simulation: theory vs. practice
• Online learning for matrix factorization and sparse coding
• Online convex optimization in the bandit setting: gradient descent without a gradient
• On the complexity of steepest descent, Newton's and regularized Newton's methods for nonconvex unconstrained optimization problems
• Optimization techniques for semi-supervised support vector machines
• A Unified View of the IPA, SF, and LR Gradient Estimation Techniques
• An optimal method for stochastic composite optimization
• Convergence of Proximal-Like Algorithms
• Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization I: A Generic Algorithmic Framework
• Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization, II: Shrinking Procedures and Optimal Algorithms
• Erratum to: ``Minimizing finite sums with the stochastic average gradient
• Validation analysis of mirror descent stochastic approximation method
• Interior Gradient and Proximal Methods for Convex and Conic Optimization
• Title not available (Why is that?)
• Randomized smoothing for stochastic optimization

Cited In (only showing first 100 items - show all)

• Momentum-based accelerated mirror descent stochastic approximation for robust topology optimization under stochastic loads
• Title not available (Why is that?)
• Robust High-Dimensional Regression with Coefficient Thresholding and Its Application to Imaging Data Analysis
• Dissipative imitation learning for discrete dynamic output feedback control with sparse data sets
• Convergence analysis of a subsampled Levenberg-Marquardt algorithm
• A dual-based stochastic inexact algorithm for a class of stochastic nonsmooth convex composite problems
• Accelerating stochastic sequential quadratic programming for equality constrained optimization using predictive variance reduction
• On inexact stochastic splitting methods for a class of nonconvex composite optimization problems with relative error
• An accelerated stochastic mirror descent method
• Almost sure convergence rates of stochastic proximal gradient descent algorithm
• Complexity of a projected Newton-CG method for optimization with bounds
• Stochastic linearized generalized alternating direction method of multipliers: expected convergence rates and large deviation properties
• Two stochastic optimization algorithms for convex optimization with fixed point constraints
• Proximal stochastic recursive momentum algorithm for nonsmooth nonconvex optimization problems
• Gradient complexity and non-stationary views of differentially private empirical risk minimization
• Unifying framework for accelerated randomized methods in convex optimization
• Title not available (Why is that?)
• Random-reshuffled SARAH does not need full gradient computations
• Stochastic augmented Lagrangian method in Riemannian shape manifolds
• A semismooth Newton stochastic proximal point algorithm with variance reduction
• A framework of convergence analysis of mini-batch stochastic projected gradient methods
• SPIRAL: a superlinearly convergent incremental proximal algorithm for nonconvex finite sum minimization
• Title not available (Why is that?)
• Stochastic composition optimization of functions without Lipschitz continuous gradient
• A stochastic Bregman golden ratio algorithm for non-Lipschitz stochastic mixed variational inequalities with application to resource share problems
• Stochastic gradient methods with preconditioned updates
• Zeroth-Order Stochastic Compositional Algorithms for Risk-Aware Learning
• Graphical Convergence of Subgradients in Nonconvex Optimization and Learning
• Open Problem—Iterative Schemes for Stochastic Optimization: Convergence Statements and Limit Theorems
• A unified analysis of stochastic gradient‐free Frank–Wolfe methods
• Proximal variable smoothing method for three-composite nonconvex nonsmooth minimization with a linear operator
• Worst-case complexity of an SQP method for nonlinear equality constrained stochastic optimization
• Variable sample-size operator extrapolation algorithm for stochastic mixed variational inequalities
• Stochastic Conditional Gradient++: (Non)Convex Minimization and Continuous Submodular Maximization
• Stochastic Trust-Region Methods with Trust-Region Radius Depending on Probabilistic Models
• Accelerated gradient methods for nonconvex nonlinear and stochastic programming
• Stochastic polynomial optimization
• On stochastic accelerated gradient with convergence rate
• Proximally Guided Stochastic Subgradient Method for Nonsmooth, Nonconvex Problems
• An Asynchronous Mini-Batch Algorithm for Regularized Stochastic Optimization
• Robust and sparse regression in generalized linear model by stochastic optimization
• Title not available (Why is that?)
• Zeroth-order methods for noisy Hölder-gradient functions
• On the information-adaptive variants of the ADMM: an iteration complexity perspective
• Variable metric proximal stochastic variance reduced gradient methods for nonconvex nonsmooth optimization
• A Stochastic Semismooth Newton Method for Nonsmooth Nonconvex Optimization
• Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysis
• Understanding generalization error of SGD in nonconvex optimization
• Variance reduction on general adaptive stochastic mirror descent
• Primal-dual optimization algorithms over Riemannian manifolds: an iteration complexity analysis
• Dynamic stochastic approximation for multi-stage stochastic optimization
• Stochastic variable metric proximal gradient with variance reduction for non-convex composite optimization
• Stochastic Difference-of-Convex-Functions Algorithms for Nonconvex Programming
• An accelerated directional derivative method for smooth stochastic convex optimization
• A unified convergence analysis of stochastic Bregman proximal gradient and extragradient methods
• Stochastic gradient descent with noise of machine learning type. I: Discrete time analysis
• Distributed Variable Sample-Size Gradient-Response and Best-Response Schemes for Stochastic Nash Equilibrium Problems
• A stochastic Nesterov's smoothing accelerated method for general nonsmooth constrained stochastic composite convex optimization
• A Unified Adaptive Tensor Approximation Scheme to Accelerate Composite Convex Optimization
• Block coordinate type methods for optimization and learning
• Inexact proximal stochastic second-order methods for nonconvex composite optimization
• Stochastic proximal quasi-Newton methods for non-convex composite optimization
• Trimmed Statistical Estimation via Variance Reduction
• A Single Timescale Stochastic Approximation Method for Nested Stochastic Optimization
• Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization
• An interior stochastic gradient method for a class of non-Lipschitz optimization problems
• Penalty methods with stochastic approximation for stochastic nonlinear programming
• Complexity analysis of a stochastic variant of generalized alternating direction method of multipliers
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Block Stochastic Gradient Iteration for Convex and Nonconvex Optimization
• Zeroth-order algorithms for stochastic distributed nonconvex optimization
• Stochastic relaxed inertial forward-backward-forward splitting for monotone inclusions in Hilbert spaces
• A hybrid stochastic optimization framework for composite nonconvex optimization
• Stochastic Block Mirror Descent Methods for Nonsmooth and Stochastic Optimization
• A stochastic approximation method for approximating the efficient frontier of chance-constrained nonlinear programs
• Title not available (Why is that?)
• Stochastic Multilevel Composition Optimization Algorithms with Level-Independent Convergence Rates
• Extragradient Method with Variance Reduction for Stochastic Variational Inequalities
• Mini-batch learning of exponential family finite mixture models
• Title not available (Why is that?)
• Momentum-based variance-reduced proximal stochastic gradient method for composite nonconvex stochastic optimization
• Generalized uniformly optimal methods for nonlinear programming
• Hölderian Error Bounds and Kurdyka-Łojasiewicz Inequality for the Trust Region Subproblem
• Stochastic proximal gradient methods for nonconvex problems in Hilbert spaces
• Stochastic Approximation Methods for the Two-Stage Stochastic Linear Complementarity Problem
• Recent Theoretical Advances in Non-Convex Optimization
• Stochastic Model-Based Minimization of Weakly Convex Functions
• Complexity guarantees for an implicit smoothing-enabled method for stochastic MPECs
• Optimization-Based Calibration of Simulation Input Models
• Conditional gradient sliding for convex optimization
• Numerical solution of inverse problems by weak adversarial networks
• A stochastic extra-step quasi-Newton method for nonsmooth nonconvex optimization
• On the local convergence of a stochastic semismooth Newton method for nonsmooth nonconvex optimization
• Stopping criteria for, and strong convergence of, stochastic gradient descent on Bottou-Curtis-Nocedal functions
• On the computation of equilibria in monotone and potential stochastic hierarchical games
• Asynchronous Schemes for Stochastic and Misspecified Potential Games and Nonconvex Optimization
• Asynchronous variance-reduced block schemes for composite non-convex stochastic optimization: block-specific steplengths and adapted batch-sizes
• An Accelerated Method for Derivative-Free Smooth Stochastic Convex Optimization

This page was built for publication: Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5962719)