Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization

DOI10.1007/s10107-014-0846-1zbMath1332.90196arXiv1308.6594OpenAlexW2029463628MaRDI QIDQ5962719

Saeed Ghadimi, Guanghui Lan, Hongchao Zhang

Publication date: 23 February 2016

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

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

zbMATH Keywords

stochastic programmingstochastic approximationnonconvex optimizationfirst-order methodconstrained stochastic programmingmini-batch of sampleszeroth-order method

Mathematics Subject Classification ID

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

Related Items

On inexact stochastic splitting methods for a class of nonconvex composite optimization problems with relative error ⋮ Asynchronous variance-reduced block schemes for composite non-convex stochastic optimization: block-specific steplengths and adapted batch-sizes ⋮ Understanding generalization error of SGD in nonconvex optimization ⋮ Block coordinate type methods for optimization and learning ⋮ A stochastic extra-step quasi-Newton method for nonsmooth nonconvex optimization ⋮ Zeroth-order algorithms for stochastic distributed nonconvex optimization ⋮ Zeroth-Order Stochastic Compositional Algorithms for Risk-Aware Learning ⋮ Stochastic Multilevel Composition Optimization Algorithms with Level-Independent Convergence Rates ⋮ Distributed Variable Sample-Size Gradient-Response and Best-Response Schemes for Stochastic Nash Equilibrium Problems ⋮ An interior stochastic gradient method for a class of non-Lipschitz optimization problems ⋮ Zeroth-order methods for noisy Hölder-gradient functions ⋮ Graphical Convergence of Subgradients in Nonconvex Optimization and Learning ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Stochastic Trust-Region Methods with Trust-Region Radius Depending on Probabilistic Models ⋮ An Accelerated Method for Derivative-Free Smooth Stochastic Convex Optimization ⋮ On the information-adaptive variants of the ADMM: an iteration complexity perspective ⋮ Block Stochastic Gradient Iteration for Convex and Nonconvex Optimization ⋮ Stochastic gradient descent with noise of machine learning type. I: Discrete time analysis ⋮ Convergence analysis of a subsampled Levenberg-Marquardt algorithm ⋮ A dual-based stochastic inexact algorithm for a class of stochastic nonsmooth convex composite problems ⋮ Momentum-based variance-reduced proximal stochastic gradient method for composite nonconvex stochastic optimization ⋮ Stochastic Block Mirror Descent Methods for Nonsmooth and Stochastic Optimization ⋮ A unified analysis of stochastic gradient‐free Frank–Wolfe methods ⋮ Variance reduction on general adaptive stochastic mirror descent ⋮ A framework of convergence analysis of mini-batch stochastic projected gradient methods ⋮ Stochastic composition optimization of functions without Lipschitz continuous gradient ⋮ Complexity analysis of a stochastic variant of generalized alternating direction method of multipliers ⋮ Trimmed Statistical Estimation via Variance Reduction ⋮ Unnamed Item ⋮ 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 ⋮ Mini-batch learning of exponential family finite mixture models ⋮ Robust High-Dimensional Regression with Coefficient Thresholding and Its Application to Imaging Data Analysis ⋮ Accelerating stochastic sequential quadratic programming for equality constrained optimization using predictive variance reduction ⋮ Stochastic variable metric proximal gradient with variance reduction for non-convex composite optimization ⋮ Open Problem—Iterative Schemes for Stochastic Optimization: Convergence Statements and Limit Theorems ⋮ 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 ⋮ Random-reshuffled SARAH does not need full gradient computations ⋮ Complexity guarantees for an implicit smoothing-enabled method for stochastic MPECs ⋮ On the computation of equilibria in monotone and potential stochastic hierarchical games ⋮ Penalty methods with stochastic approximation for stochastic nonlinear programming ⋮ Primal-dual optimization algorithms over Riemannian manifolds: an iteration complexity analysis ⋮ Optimization-Based Calibration of Simulation Input Models ⋮ Two stochastic optimization algorithms for convex optimization with fixed point constraints ⋮ Conditional gradient type methods for composite nonlinear and stochastic optimization ⋮ Stochastic Model-Based Minimization of Weakly Convex Functions ⋮ A Unified Adaptive Tensor Approximation Scheme to Accelerate Composite Convex Optimization ⋮ Numerical solution of inverse problems by weak adversarial networks ⋮ Inexact proximal stochastic second-order methods for nonconvex composite optimization ⋮ Recent Theoretical Advances in Non-Convex Optimization ⋮ Unnamed Item ⋮ Asynchronous Schemes for Stochastic and Misspecified Potential Games and Nonconvex Optimization ⋮ Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysis ⋮ Stochastic Conditional Gradient++: (Non)Convex Minimization and Continuous Submodular Maximization ⋮ Unnamed Item ⋮ Extragradient Method with Variance Reduction for Stochastic Variational Inequalities ⋮ Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization ⋮ Dynamic stochastic approximation for multi-stage stochastic optimization ⋮ Stochastic proximal gradient methods for nonconvex problems in Hilbert spaces ⋮ An accelerated directional derivative method for smooth stochastic convex optimization ⋮ Stochastic proximal quasi-Newton methods for non-convex composite optimization ⋮ Unnamed Item ⋮ A unified convergence analysis of stochastic Bregman proximal gradient and extragradient methods ⋮ Stochastic polynomial optimization ⋮ Conditional Gradient Sliding for Convex Optimization ⋮ Robust and sparse regression in generalized linear model by stochastic optimization ⋮ A Single Timescale Stochastic Approximation Method for Nested Stochastic Optimization ⋮ A stochastic approximation method for approximating the efficient frontier of chance-constrained nonlinear programs ⋮ Proximally Guided Stochastic Subgradient Method for Nonsmooth, Nonconvex Problems ⋮ Generalized uniformly optimal methods for nonlinear programming ⋮ Accelerated Stochastic Algorithms for Nonconvex Finite-Sum and Multiblock Optimization ⋮ A Stochastic Semismooth Newton Method for Nonsmooth Nonconvex Optimization ⋮ On the local convergence of a stochastic semismooth Newton method for nonsmooth nonconvex optimization ⋮ Stochastic relaxed inertial forward-backward-forward splitting for monotone inclusions in Hilbert spaces ⋮ Variable metric proximal stochastic variance reduced gradient methods for nonconvex nonsmooth optimization ⋮ Stopping criteria for, and strong convergence of, stochastic gradient descent on Bottou-Curtis-Nocedal functions ⋮ A stochastic Nesterov's smoothing accelerated method for general nonsmooth constrained stochastic composite convex optimization ⋮ Stochastic Approximation Methods for the Two-Stage Stochastic Linear Complementarity Problem ⋮ Stochastic Difference-of-Convex-Functions Algorithms for Nonconvex Programming ⋮ Hölderian Error Bounds and Kurdyka-Łojasiewicz Inequality for the Trust Region Subproblem ⋮ On stochastic accelerated gradient with convergence rate ⋮ A hybrid stochastic optimization framework for composite nonconvex optimization ⋮ Accelerated gradient methods for nonconvex nonlinear and stochastic programming

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Accelerated gradient methods for nonconvex nonlinear and stochastic programming
• An optimal method for stochastic composite optimization
• Erratum to: ``Minimizing finite sums with the stochastic average gradient
• Validation analysis of mirror descent stochastic approximation method
• Introductory lectures on convex optimization. A basic course.
• Random gradient-free minimization of convex functions
• The Ordered Subsets Mirror Descent Optimization Method with Applications to Tomography
• Feature Article: Optimization for simulation: Theory vs. Practice
• Randomized Smoothing for Stochastic Optimization
• On the Complexity of Steepest Descent, Newton's and Regularized Newton's Methods for Nonconvex Unconstrained Optimization Problems
• A Unified View of the IPA, SF, and LR Gradient Estimation Techniques
• Robust Stochastic Approximation Approach to Stochastic Programming
• Acceleration of Stochastic Approximation by Averaging
• Variational Analysis
• Convergence of Proximal-Like Algorithms
• Introduction to Stochastic Search and Optimization
• Bregman Monotone Optimization 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
• Interior Gradient and Proximal Methods for Convex and Conic Optimization
• A Stochastic Approximation Method