Stochastic composition optimization of functions without Lipschitz continuous gradient

DOI10.1007/S10957-023-02180-WMaRDI QIDQ6108982zbMATH OpenOpenAlexFDO

Authors

Publication date 26 July 2023

Published in Journal of Optimization Theory and Applications (Search for Journal in Brave)

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

zbMATH Keywords

Bregman subproblemcomposition optimizationstochastic optimization algorithm

Mathematics Subject Classification ID

Stochastic programming (90C15)

Abstract: In this paper, we study stochastic optimization of two-level composition of functions without Lipschitz continuous gradient. The smoothness property is generalized by the notion of relative smoothness which provokes the Bregman gradient method. We propose three Stochastic Composition Bregman Gradient algorithms for the three possible relatively smooth compositional scenarios and provide their sample complexities to achieve an $epsilon$-approximate stationary point. For the smooth of relatively smooth composition, the first algorithm requires $O(epsilo{n}^{-2})$ calls to the stochastic oracles of the inner function value and gradient as well as the outer function gradient. When both functions are relatively smooth, the second algorithm requires $O(epsilo{n}^{-3})$ calls to the inner function value stochastic oracle and $O(epsilo{n}^{-2})$ calls to the inner and outer functions gradients stochastic oracles. We further improve the second algorithm by variance reduction for the setting where just the inner function is smooth. The resulting algorithm requires $O(epsilo{n}^{-5/2})$ calls to the inner function value stochastic oracle, $O(epsilo{n}^{-3/2})$ calls to the inner function gradient and $O(epsilo{n}^{-2})$ calls to the outer function gradient stochastic oracles. Finally, we numerically evaluate the performance of these three algorithms over two different examples.

Recommendations

• Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions
• Riemannian gradient methods for stochastic composition problems
• Gradient-free methods for non-smooth convex stochastic optimization with heavy-tailed noise on convex compact
• A smoothing stochastic gradient method for composite optimization
• Stochastic Methods for Composite and Weakly Convex Optimization Problems
• An optimal method for stochastic composite optimization
• A hybrid stochastic optimization framework for composite nonconvex optimization
• A Stochastic Subgradient Method for Nonsmooth Nonconvex Multilevel Composition Optimization
• Optimization by stochastic continuation
• Conditional gradient type methods for composite nonlinear and stochastic optimization

Cites work

• A Bregman forward-backward linesearch algorithm for nonconvex composite optimization: superlinear convergence to nonisolated local minima
• A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications
• A simplified view of first order methods for optimization
• A Single Timescale Stochastic Approximation Method for Nested Stochastic Optimization
• A Stochastic Subgradient Method for Nonsmooth Nonconvex Multilevel Composition Optimization
• Accelerated Bregman proximal gradient methods for relatively smooth convex optimization
• Algorithms and applications for approximate nonnegative matrix factorization
• Analysis of biased stochastic gradient descent using sequential semidefinite programs
• Convergence Analysis of a Proximal-Like Minimization Algorithm Using Bregman Functions
• Convex optimization: algorithms and complexity
• Convex-concave backtracking for inertial Bregman proximal gradient algorithms in nonconvex optimization
• Fastest rates for stochastic mirror descent methods
• First order methods beyond convexity and Lipschitz gradient continuity with applications to quadratic inverse problems
• scientific article; zbMATH DE number 3761782 (Why is no real title available?)
• scientific article; zbMATH DE number 3790208 (Why is no real title available?)
• Independent Component Analysis and Blind Signal Separation
• Learning the parts of objects by non-negative matrix factorization
• Mean-variance risk-averse optimal control of systems governed by PDEs with random parameter fields using quadratic approximations
• Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization
• Mirror descent and nonlinear projected subgradient methods for convex optimization.
• Multigrid Methods and Sparse-Grid Collocation Techniques for Parabolic Optimal Control Problems with Random Coefficients
• Multilevel composite stochastic optimization via nested variance reduction
• Multilevel stochastic gradient methods for nested composition optimization
• On linear convergence of non-Euclidean gradient methods without strong convexity and Lipschitz gradient continuity
• Optimal complexity and certification of Bregman first-order methods
• Policy evaluation with temporal differences: a survey and comparison
• Projected subgradient methods with non-Euclidean distances for non-differentiable convex minimization and variational inequalities
• Reinforcement learning. An introduction
• Relatively smooth convex optimization by first-order methods, and applications
• Robust Stochastic Approximation Approach to Stochastic Programming
• Sample average approximation method for compound stochastic optimization problems
• Solving Stochastic Compositional Optimization is Nearly as Easy as Solving Stochastic Optimization
• Statistical estimation of composite risk functionals and risk optimization problems
• Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions
• Stochastic multilevel composition optimization algorithms with level-independent convergence rates
• Stochastic variance-reduced prox-linear algorithms for nonconvex composite optimization
• The ordered subsets mirror descent optimization method with applications to tomography
• Why least squares and maximum entropy? An axiomatic approach to inference for linear inverse problems

Cited in

(1)

• Some unified theory for variance reduced prox-linear methods

This page was built for publication: Stochastic composition optimization of functions without Lipschitz continuous gradient

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