Bregman Finito/MISO for nonconvex regularized finite sum minimization without Lipschitz gradient continuity
From MaRDI portal
(Redirected from Publication:5869813)
Abstract: We introduce two algorithms for nonconvex regularized finite sum minimization, where typical Lipschitz differentiability assumptions are relaxed to the notion of relative smoothness. The first one is a Bregman extension of Finito/MISO, studied for fully nonconvex problems when the sampling is randomized, or under convexity of the nonsmooth term when it is essentially cyclic. The second algorithm is a low-memory variant, in the spirit of SVRG and SARAH, that also allows for fully nonconvex formulations. Our analysis is made remarkably simple by employing a Bregman Moreau envelope as Lyapunov function. In the randomized case, linear convergence is established when the cost function is strongly convex, yet with no convexity requirements on the individual functions in the sum. For the essentially cyclic and low-memory variants, global and linear convergence results are established when the cost function satisfies the Kurdyka-L ojasiewicz property.
Recommendations
- Block-coordinate and incremental aggregated proximal gradient methods for nonsmooth nonconvex problems
- A Bregman stochastic method for nonconvex nonsmooth problem beyond global Lipschitz gradient continuity
- Inertial proximal gradient methods with Bregman regularization for a class of nonconvex optimization problems
- Non-smooth non-convex Bregman minimization: unification and new algorithms
- First order methods beyond convexity and Lipschitz gradient continuity with applications to quadratic inverse problems
Cites work
- A Bregman forward-backward linesearch algorithm for nonconvex composite optimization: superlinear convergence to nonisolated local minima
- A Convergent Incremental Gradient Method with a Constant Step Size
- A coordinate gradient descent method for nonsmooth separable minimization
- A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications
- A geometric analysis of phase retrieval
- A globally convergent algorithm for nonconvex optimization based on block coordinate update
- A proximal stochastic gradient method with progressive variance reduction
- A simplified view of first order methods for optimization
- An inexact hybrid generalized proximal point algorithm and some new results on the theory of Bregman functions
- Block-coordinate and incremental aggregated proximal gradient methods for nonsmooth nonconvex problems
- Clarke Subgradients of Stratifiable Functions
- Convergence Analysis of a Proximal-Like Minimization Algorithm Using Bregman Functions
- Convergence of a block coordinate descent method for nondifferentiable minimization
- Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
- Convex Analysis
- Convex optimization theory.
- Cyclic coordinate-update algorithms for fixed-point problems: analysis and applications
- Efficiency of coordinate descent methods on huge-scale optimization problems
- ESSENTIAL SMOOTHNESS, ESSENTIAL STRICT CONVEXITY, AND LEGENDRE FUNCTIONS IN BANACH SPACES
- Fastest rates for stochastic mirror descent methods
- First order methods beyond convexity and Lipschitz gradient continuity with applications to quadratic inverse problems
- First-order methods in optimization
- Global convergence rate of proximal incremental aggregated gradient methods
- Gradient Convergence in Gradient methods with Errors
- scientific article; zbMATH DE number 1046019 (Why is no real title available?)
- Incremental majorization-minimization optimization with application to large-scale machine learning
- Incremental proximal methods for large scale convex optimization
- Incrementally updated gradient methods for constrained and regularized optimization
- Iteration complexity analysis of block coordinate descent methods
- Kurdyka-Łojasiewicz exponent via inf-projection
- Minimizing finite sums with the stochastic average gradient
- Mirror descent and nonlinear projected subgradient methods for convex optimization.
- Non-smooth non-convex Bregman minimization: unification and new algorithms
- On gradients of functions definable in o-minimal structures
- On linear convergence of non-Euclidean gradient methods without strong convexity and Lipschitz gradient continuity
- On semi- and subanalytic geometry
- On stochastic subgradient mirror-descent algorithm with weighted averaging
- On the convergence of block coordinate descent type methods
- On the convergence of the proximal algorithm for nonsmooth functions involving analytic features
- Optical Wavefront Reconstruction: Theory and Numerical Methods
- Phase retrieval via Wirtinger flow: theory and algorithms
- Proximal alternating linearized minimization for nonconvex and nonsmooth problems
- Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
- Proximal-like incremental aggregated gradient method with linear convergence under Bregman distance growth conditions
- Relatively smooth convex optimization by first-order methods, and applications
- Relaxation methods for problems with strictly convex separable costs and linear constraints
- Robust Stochastic Approximation Approach to Stochastic Programming
- Saga
- Solving (most) of a set of quadratic equalities: composite optimization for robust phase retrieval
- Surpassing gradient descent provably: a cyclic incremental method with linear convergence rate
- The elements of statistical learning. Data mining, inference, and prediction
- The Moreau envelope function and proximal mapping in the sense of the Bregman distance
- The nonsmooth landscape of phase retrieval
- The Łojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical Systems
Cited in
(13)- Inertial proximal incremental aggregated gradient method with linear convergence guarantees
- A telescopic Bregmanian proximal gradient method without the global Lipschitz continuity assumption
- A Bregman forward-backward linesearch algorithm for nonconvex composite optimization: superlinear convergence to nonisolated local minima
- SPIRAL: a superlinearly convergent incremental proximal algorithm for nonconvex finite sum minimization
- An interior proximal gradient method for nonconvex optimization
- Convergence properties of proximal (sub)gradient methods without convexity or smoothness of any of the functions
- Smoothing proximal gradient block-coordinate algorithms for group sparse _0 regularized nonsmooth convex regression problem
- A fast computational Gauss-Seidel type iPALM algorithm using an incremental aggregated gradient strategy for weakly convex composite optimization problems with application in image processing
- Adaptive proximal algorithms for convex optimization under local Lipschitz continuity of the gradient
- Smoothing randomized block-coordinate proximal gradient algorithms for nonsmooth nonconvex composite optimization
- Nonconvex stochastic Bregman proximal gradient method with application to deep learning
- Inertial accelerated stochastic mirror descent for large-scale generalized tensor CP decomposition
- A normal map-based proximal stochastic gradient method: convergence and identification properties
This page was built for publication: Bregman Finito/MISO for nonconvex regularized finite sum minimization without Lipschitz gradient continuity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5869813)
