An optimal method for stochastic composite optimization
From MaRDI portal
The stochastic composite optimization problem under consideration consists in minimizing the sum \(f+h\) of two convex functions \(f,h\) defined on a compact convex set \(X\subset \mathbb{R}^{n}\), assuming that \(\nabla f\) and \(h\) are globally Lipschitz. The author proposes two subgradient-type methods, namely, a modified version of the mirror-descent SA method due to \textit{A. Nemirovski, A. Juditsky, G. Lan} and \textit{A. Shapiro} [SIAM J. Optim. 19, No. 4, 1574--1609 (2009; Zbl 1189.90109)], which substantially improves the rate of convergence, and an accelerated stochastic approximation method, which can achieve an optimal rate of convergence. He illustrates the advantages of the latter method over other existing methods by discussing its performance for a particular class of stochastic optimization problems.
Recommendations
- Universal method for stochastic composite optimization problems
- Stochastic Methods for Composite and Weakly Convex Optimization Problems
- Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization I: A Generic Algorithmic Framework
- scientific article; zbMATH DE number 1045614
- A smoothing stochastic gradient method for composite optimization
- Stochastic primal dual fixed point method for composite optimization
- A hybrid stochastic optimization framework for composite nonconvex optimization
- scientific article; zbMATH DE number 5281595
- scientific article; zbMATH DE number 4055383
- A stochastic Bregman primal-dual splitting algorithm for composite optimization
Cites work
- A method of aggregate stochastic subgradients with on-line stepsize rules for convex stochastic programming problems
- A Stochastic Approximation Method
- Acceleration of Stochastic Approximation by Averaging
- Bregman Monotone Optimization Algorithms
- Convergence of Proximal-Like Algorithms
- Convex Analysis
- Convex optimization methods for dimension reduction and coefficient estimation in multivariate linear regression
- First-Order Methods for Sparse Covariance Selection
- scientific article; zbMATH DE number 1818892 (Why is no real title available?)
- scientific article; zbMATH DE number 1005357 (Why is no real title available?)
- scientific article; zbMATH DE number 1972910 (Why is no real title available?)
- scientific article; zbMATH DE number 3296905 (Why is no real title available?)
- Interior Gradient and Proximal Methods for Convex and Conic Optimization
- Introduction to Stochastic Search and Optimization
- Introductory lectures on convex optimization. A basic course.
- Iteration-complexity of first-order augmented Lagrangian methods for convex programming
- Iteration-complexity of first-order penalty methods for convex programming
- Large-scale semidefinite programming via a saddle point mirror-prox algorithm
- Learning by mirror averaging
- Monte Carlo bounding techniques for determinig solution quality in stochastic programs
- Monte Carlo sampling approach to stochastic programming
- Non-Euclidean restricted memory level method for large-scale convex optimization
- On complexity of stochastic programming problems
- On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean
- Primal-dual subgradient methods for convex problems
- Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
- Proximal Minimization Methods with Generalized Bregman Functions
- Recursive aggregation of estimators by the mirror descent algorithm with averaging
- Robust Stochastic Approximation Approach to Stochastic Programming
- Smooth minimization of non-smooth functions
- Smooth Optimization Approach for Sparse Covariance Selection
- Smooth Optimization with Approximate Gradient
- Smoothing technique and its applications in semidefinite optimization
- stochastic quasigradient methods and their application to system optimization†
- The empirical behavior of sampling methods for stochastic programming
- The Existence of Probability Measures with Given Marginals
- The sample average approximation method applied to stochastic routing problems: a computational study
- The sample average approximation method for stochastic discrete optimization
Cited in
(only showing first 100 items - show all)- Stochastic optimization using a trust-region method and random models
- On the information-adaptive variants of the ADMM: an iteration complexity perspective
- Accelerated schemes for a class of variational inequalities
- Inexact proximal stochastic gradient method for convex composite optimization
- Stochastic heavy ball
- Inexact SA method for constrained stochastic convex SDP and application in Chinese stock market
- On variance reduction for stochastic smooth convex optimization with multiplicative noise
- Universal method for stochastic composite optimization problems
- Approximation algorithms from inexact solutions to semidefinite programming relaxations of combinatorial optimization problems
- An optimal randomized incremental gradient method
- Convergence of stochastic proximal gradient algorithm
- Dynamic stochastic approximation for multi-stage stochastic optimization
- An accelerated directional derivative method for smooth stochastic convex optimization
- General convergence analysis of stochastic first-order methods for composite optimization
- A stochastic Nesterov's smoothing accelerated method for general nonsmooth constrained stochastic composite convex optimization
- On stochastic accelerated gradient with convergence rate
- A multi-step doubly stabilized bundle method for nonsmooth convex optimization
- ASD+M: automatic parameter tuning in stochastic optimization and on-line learning
- Algorithms for stochastic optimization with function or expectation constraints
- Bridging the gap between constant step size stochastic gradient descent and Markov chains
- A heuristic adaptive fast gradient method in stochastic optimization problems
- Algorithms of robust stochastic optimization based on mirror descent method
- A modular analysis of adaptive (non-)convex optimization: optimism, composite objectives, variance reduction, and variational bounds
- Communication-efficient algorithms for decentralized and stochastic optimization
- Accelerated first-order methods for large-scale convex optimization: nearly optimal complexity under strong convexity
- Generalized uniformly optimal methods for nonlinear programming
- An efficient primal dual prox method for non-smooth optimization
- On the convergence properties of non-Euclidean extragradient methods for variational inequalities with generalized monotone operators
- \(O(1/t)\) complexity analysis of the generalized alternating direction method of multipliers
- The million-variable ``march for stochastic combinatorial optimization
- Bundle-level type methods uniformly optimal for smooth and nonsmooth convex optimization
- An optimal trade-off model for portfolio selection with sensitivity of parameters
- Accelerated gradient methods for nonconvex nonlinear and stochastic programming
- Accelerated stochastic variance reduction for a class of convex optimization problems
- Conditional gradient sliding for convex optimization
- A family of subgradient-based methods for convex optimization problems in a unifying framework
- On the solution of stochastic optimization and variational problems in imperfect information regimes
- Stochastic forward-backward splitting for monotone inclusions
- A smoothing stochastic gradient method for composite optimization
- Block stochastic gradient iteration for convex and nonconvex optimization
- Stochastic block mirror descent methods for nonsmooth and stochastic optimization
- Penalty methods with stochastic approximation for stochastic nonlinear programming
- Gradient sliding for composite optimization
- On the global convergence rate of the gradient descent method for functions with Hölder continuous gradients
- New results on subgradient methods for strongly convex optimization problems with a unified analysis
- A smoothing direct search method for Monte Carlo-based bound constrained composite nonsmooth optimization
- First-order methods of smooth convex optimization with inexact oracle
- Katyusha: the first direct acceleration of stochastic gradient methods
- A sparsity preserving stochastic gradient methods for sparse regression
- Optimization with reference-based robust preference constraints
- Convergence rate analysis of projected stochastic subgradient method using conjugate gradient-like direction
- Portfolio selection with the effect of systematic risk diversification: formulation and accelerated gradient algorithm
- Utilizing second order information in minibatch stochastic variance reduced proximal iterations
- Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression
- Accelerating Stochastic Composition Optimization
- Linear coupling: an ultimate unification of gradient and mirror descent
- Random gradient extrapolation for distributed and stochastic optimization
- Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization I: A Generic Algorithmic Framework
- Conditional gradient algorithms for norm-regularized smooth convex optimization
- Graph-dependent implicit regularisation for distributed stochastic subgradient descent
- A data efficient and feasible level set method for stochastic convex optimization with expectation constraints
- Accelerated first-order primal-dual proximal methods for linearly constrained composite convex programming
- Accelerated extra-gradient descent: a novel accelerated first-order method
- An optimal high-order tensor method for convex optimization
- An accelerated method for derivative-free smooth stochastic convex optimization
- Accelerated stochastic algorithms for convex-concave saddle-point problems
- Scheduled restart momentum for accelerated stochastic gradient descent
- On stochastic accelerated gradient with convergence rate of regression learning
- Open problem: Iterative schemes for stochastic optimization: convergence statements and limit theorems
- On the adaptivity of stochastic gradient-based optimization
- Estimate sequences for stochastic composite optimization: variance reduction, acceleration, and robustness to noise
- Conditional Gradient Methods for Convex Optimization with General Affine and Nonlinear Constraints
- Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity
- Computing the best approximation over the intersection of a polyhedral set and the doubly nonnegative cone
- Incremental majorization-minimization optimization with application to large-scale machine learning
- A multilevel proximal gradient algorithm for a class of composite optimization problems
- Two stochastic optimization algorithms for convex optimization with fixed point constraints
- Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization. II: Shrinking procedures and optimal algorithms
- Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization
- Robust accelerated gradient methods for smooth strongly convex functions
- Inexact model: a framework for optimization and variational inequalities
- Universal intermediate gradient method for convex problems with inexact oracle
- Smoothed Variable Sample-Size Accelerated Proximal Methods for Nonsmooth Stochastic Convex Programs
- Research on three-step accelerated gradient algorithm in deep learning
- A new randomized primal-dual algorithm for convex optimization with fast last iterate convergence rates
- Block coordinate type methods for optimization and learning
- Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization
- Subgradient ellipsoid method for nonsmooth convex problems
- Unifying mirror descent and dual averaging
- Semi-discrete optimal transport: hardness, regularization and numerical solution
- A dual-based stochastic inexact algorithm for a class of stochastic nonsmooth convex composite problems
- Nonconvex optimization with inertial proximal stochastic variance reduction gradient
- Gradient-free federated learning methods with l₁ and l₂-randomization for non-smooth convex stochastic optimization problems
- Automatic, dynamic, and nearly optimal learning rate specification via local quadratic approximation
- An overview of stochastic quasi-Newton methods for large-scale machine learning
- A mini-batch proximal stochastic recursive gradient algorithm with diagonal Barzilai-Borwein stepsize
- Stochastic composition optimization of functions without Lipschitz continuous gradient
- Complexity analysis of a stochastic variant of generalized alternating direction method of multipliers
- Optimal Algorithms for Stochastic Complementary Composite Minimization
- Regularized quasi-monotone method for stochastic optimization
This page was built for publication: An optimal method for stochastic composite optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q431018)
