A Stochastic Subgradient Method for Nonsmooth Nonconvex Multilevel Composition Optimization

DOI10.1137/20M1312952zbMATH Open1470.90096arXiv2001.10669OpenAlexW3174976469MaRDI QIDQ4995000FDOQ4995000

Andrzej Ruszczyński

Publication date: 22 June 2021

Published in: SIAM Journal on Control and Optimization (Search for Journal in Brave)

Abstract: We propose a single time-scale stochastic subgradient method for constrained optimization of a composition of several nonsmooth and nonconvex functions. The functions are assumed to be locally Lipschitz and differentiable in a generalized sense. Only stochastic estimates of the values and generalized derivatives of the functions are used. The method is parameter-free. We prove convergence with probability one of the method, by associating with it a system of differential inclusions and devising a nondifferentiable Lyapunov function for this system. For problems with functions having Lipschitz continuous derivatives, the method finds a point satisfying an optimality measure with error of order $1/sqrtN$, after executing $N$ iterations with constant stepsize.

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

zbMATH Keywords

stochastic approximationnonsmooth optimizationstochastic variational inequalityrisk-averse optimizationstochastic composition optimization

Mathematics Subject Classification ID

Stochastic approximation (62L20) Nonconvex programming, global optimization (90C26) Nonsmooth analysis (49J52)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Coherent measures of risk
• Stochastic approximation methods for constrained and unconstrained systems
• From stochastic dominance to mean-risk models: Semideviations as risk measures
• Clarke Subgradients of Stratifiable Functions
• Semismooth and Semiconvex Functions in Constrained Optimization
• Stochastic finance. An introduction in discrete time
• On consistency of stochastic dominance and mean-semideviation models
• Lectures on Stochastic Programming
• Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming
• Analysis of recursive stochastic algorithms
• Generalized Gradients and Applications
• Generalized gradients of Lipschitz functionals
• Regularized Iterative Stochastic Approximation Methods for Stochastic Variational Inequality Problems
• Stochastic Approximations and Differential Inclusions
• Stochastic Approximations and Differential Inclusions, Part II: Applications
• Stochastic Methods for Composite and Weakly Convex Optimization Problems
• Sample Average Approximation Method for Compound Stochastic Optimization Problems
• Statistical estimation of composite risk functionals and risk optimization problems
• Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions
• A Linearization Method for Nonsmooth Stochastic Programming Problems
• Curves of descent
• Accelerating Stochastic Composition Optimization
• Extragradient Method with Variance Reduction for Stochastic Variational Inequalities
• Stochastic Model-Based Minimization of Weakly Convex Functions
• Stochastic subgradient method converges on tame functions
• A Single Timescale Stochastic Approximation Method for Nested Stochastic Optimization
• Convergence of a stochastic subgradient method with averaging for nonsmooth nonconvex constrained optimization
• Multilevel Stochastic Gradient Methods for Nested Composition Optimization

Cited In (10)

• Mini-Batch Risk Forms
• Hybrid SGD algorithms to solve stochastic composite optimization problems with application in sparse portfolio selection problems
• Subgradient Sampling for Nonsmooth Nonconvex Minimization
• Distributed stochastic compositional optimization problems over directed networks
• A functional model method for nonconvex nonsmooth conditional stochastic optimization
• Stochastic nested primal-dual method for nonconvex constrained composition optimization
• Zeroth-order Riemannian averaging stochastic approximation algorithms
• A stochastic subgradient method for distributionally robust non-convex and non-smooth learning
• Stochastic Multilevel Composition Optimization Algorithms with Level-Independent Convergence Rates
• Stochastic composition optimization of functions without Lipschitz continuous gradient

Recommendations

• Title not available (Why is that?) 👍 👎
• A hybrid stochastic optimization framework for composite nonconvex optimization 👍 👎
• Stochastic subgradient method for quasi-convex optimization problems 👍 👎
• A Multilevel Proximal Gradient Algorithm for a Class of Composite Optimization Problems 👍 👎
• Stochastic Multilevel Composition Optimization Algorithms with Level-Independent Convergence Rates 👍 👎
• A stochastic Nesterov's smoothing accelerated method for general nonsmooth constrained stochastic composite convex optimization 👍 👎
• MultiLevel Composite Stochastic Optimization via Nested Variance Reduction 👍 👎
• Multilevel Stochastic Gradient Methods for Nested Composition Optimization 👍 👎
• Subregular recourse in nonlinear multistage stochastic optimization 👍 👎
• A multistep stochastic ϵ-subgradient method of minimizing a convex function 👍 👎

This page was built for publication: A Stochastic Subgradient Method for Nonsmooth Nonconvex Multilevel Composition Optimization

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