Local convergence of the heavy-ball method and iPiano for non-convex optimization

DOI10.1007/S10957-018-1272-YzbMATH Open1404.90105arXiv1606.09070OpenAlexW2962834223WikidataQ130051349 ScholiaQ130051349MaRDI QIDQ1637355FDOQ1637355

Authors: Peter Ochs 

Publication date: 8 June 2018

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

Abstract: A local convergence result for abstract descent methods is proved. The sequence of iterates is attracted by a local (or global) minimum, stays in its neighborhood and converges within this neighborhood. This result allows algorithms to exploit local properties of the objective function. In particular, the abstract theory in this paper applies to the inertial forward--backward splitting method: iPiano---a generalization of the Heavy-ball method. Moreover, it reveals an equivalence between iPiano and inertial averaged/alternating proximal minimization and projection methods. Key for this equivalence is the attraction to a local minimum within a neighborhood and the fact that, for a prox-regular function, the gradient of the Moreau envelope is locally Lipschitz continuous and expressible in terms of the proximal mapping. In a numerical feasibility problem, the inertial alternating projection method significantly outperforms its non-inertial variants.

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

Recommendations

• Convergence rates of the heavy ball method for quasi-strongly convex optimization
• From global to local convergence of interior methods for nonlinear optimization
• Local convergence of the interior-point Newton method for general nonlinear programming
• Local convexification of the Lagrangian function for nonlinear nonconvex optimization
• Convergence rates for the heavy-ball continuous dynamics for non-convex optimization, under Polyak-Łojasiewicz condition
• On the local convergence of a stochastic semismooth Newton method for nonsmooth nonconvex optimization
• Local saddle point and a class of convexification methods for nonconvex optimization problems
• Locally optimal and heavy ball GMRES methods
• Local convergence of the affine-scaling interior-point algorithm for nonlinear programming
• Local convexification of the Lagrangian function in nonconvex optimization

zbMATH Keywords

non-convex optimizationinertial forward-backward splitting

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30) Nonsmooth analysis (49J52)

Cites Work

• iPiano: inertial proximal algorithm for nonconvex optimization
• Variational Analysis
• Convex analysis and monotone operator theory in Hilbert spaces
• Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
• Proximal alternating linearized minimization for nonconvex and nonsmooth problems
• Convergence of non-smooth descent methods using the Kurdyka-Łojasiewicz inequality
• Differential properties of the Moreau envelope
• A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion
• Clarke Subgradients of Stratifiable Functions
• Integration of subdifferentials of nonconvex functions
• Title not available (Why is that?)
• Local differentiability of distance functions
• Prox-regular functions in variational analysis
• Convergence of the Iterates of Descent Methods for Analytic Cost Functions
• On semi- and subanalytic geometry
• Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
• An inertial forward-backward algorithm for the minimization of the sum of two nonconvex functions
• Title not available (Why is that?)
• Title not available (Why is that?)
• New fractional error bounds for polynomial systems with applications to Hölderian stability in optimization and spectral theory of tensors
• On gradients of functions definable in o-minimal structures
• The Łojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical Systems
• Splitting methods with variable metric for Kurdyka-Łojasiewicz functions and general convergence rates
• An inertial Tseng's type proximal algorithm for nonsmooth and nonconvex optimization problems
• Prox-regularity of spectral functions and spectral sets
• Characterizations of Łojasiewicz inequalities: Subgradient flows, talweg, convexity
• Variable metric forward-backward algorithm for minimizing the sum of a differentiable function and a convex function
• Alternating Projections on Manifolds
• Local linear convergence for alternating and averaged nonconvex projections
• On the convergence of the proximal algorithm for nonsmooth functions involving analytic features
• Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems
• On iteratively reweighted algorithms for nonsmooth nonconvex optimization in computer vision
• Some methods of speeding up the convergence of iteration methods
• A generalized inexact proximal point method for nonsmooth functions that satisfies Kurdyka Łojasiewicz inequality
• Heavy-ball method in nonconvex optimization problems
• Convergence to equilibrium for the backward Euler scheme and applications
• A nonsmooth Morse--Sard theorem for subanalytic functions
• From error bounds to the complexity of first-order descent methods for convex functions
• Global convergence of splitting methods for nonconvex composite optimization
• Peaceman-Rachford splitting for a class of nonconvex optimization problems
• A globally convergent algorithm for nonconvex optimization based on block coordinate update
• A block coordinate variable metric forward-backward algorithm
• Inertial proximal alternating linearized minimization (iPALM) for nonconvex and nonsmooth problems
• Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods
• Error bounds for parametric polynomial systems with applications to higher-order stability analysis and convergence rates
• Forward-backward quasi-Newton methods for nonsmooth optimization problems
• Majorization-minimization procedures and convergence of SQP methods for semi-algebraic and tame programs
• On the convergence of a linesearch based proximal-gradient method for nonconvex optimization

Cited In (16)

• Convergence Analysis of the Proximal Gradient Method in the Presence of the Kurdyka–Łojasiewicz Property Without Global Lipschitz Assumptions
• Inertial Newton algorithms avoiding strict saddle points
• A Regularized Newton Method for \({\boldsymbol{\ell}}_{q}\) -Norm Composite Optimization Problems
• Convex-concave backtracking for inertial Bregman proximal gradient algorithms in nonconvex optimization
• Convergence of non-smooth descent methods using the Kurdyka-Łojasiewicz inequality
• Convergence rates for the heavy-ball continuous dynamics for non-convex optimization, under Polyak-Łojasiewicz condition
• Distributed stochastic inertial-accelerated methods with delayed derivatives for nonconvex problems
• Convergence of the Momentum Method for Semialgebraic Functions with Locally Lipschitz Gradients
• Unifying abstract inexact convergence theorems and block coordinate variable metric iPiano
• Convergence rates for an inertial algorithm of gradient type associated to a smooth non-convex minimization
• Non-monotone Behavior of the Heavy Ball Method
• An abstract convergence framework with application to inertial inexact forward-backward methods
• Bregman proximal mappings and Bregman-Moreau envelopes under relative prox-regularity
• Learning weakly convex regularizers for convergent image-reconstruction algorithms
• Inertial proximal incremental aggregated gradient method with linear convergence guarantees
• A forward-backward algorithm with different inertial terms for structured non-convex minimization problems

Uses Software

• iPiano

This page was built for publication: Local convergence of the heavy-ball method and iPiano for non-convex optimization

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