iPiano: Inertial Proximal Algorithm for Nonconvex Optimization

By Peter Ochs, Yunjin Chen, Thomas Brox, Thomas Pock. SIAM Journal of Imaging Sciences, 2014

481 citations recorded by the source corpus.

In this paper we study an algorithm for solving a minimization problem composed of a differentiable (possibly nonconvex) and a convex (possibly nondifferentiable) function. The algorithm iPiano combines forward-backward splitting with an inertial force. It can be seen as a nonsmooth split version of the Heavy-ball method from Polyak. A rigorous analysis of the algorithm for the proposed class of problems yields global convergence of the function values and the arguments. This makes the algorithm robust for usage on nonconvex problems. The convergence result is obtained based on the Kurdyka--Łojasiewicz inequality. This is a very weak restriction, which was used to prove convergence for several other gradient methods. First, an abstract convergence theorem for a generic algorithm is proved, and then iPiano is shown to satisfy the requirements of this theorem. Furthermore, a convergence rate is established for the general problem class. We demonstrate iPiano on computer vision problems---image denoising wit...

Subfields: Computational Mechanics, Computational Theory and Mathematics, Mathematical Physics

View Paper: https://www.semanticscholar.org/paper/f30e8a13330f04e8ec8dc08a65fed92ed65512f2

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computational Theory and Mathematics

In Mathematical Physics

Citations in the corpus

Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, methodology): “Extensions of the heavy ball method have been recently proposed in the proximal setting [145], non-convex setting [146, 210] and for distributed optimization [63].”
Accelerated quadratic proxy for geometric optimization (2016, methodology): “Moreover, proximal gradient with line search typically requires computing additional solutions of the linear system (8), one for each value of t to be tested in backtracking [Beck and Teboulle 2009; Parikh and Boyd 2014; Ochs et al. 2014].”
Convergence Analysis of a Momentum Algorithm with Adaptive Step Size for Non Convex Optimization (2019, methodology): “We recall the conditions satisﬁed by α n and β n in Ochs et al. (2014) in order to traduce them in terms of the algorithm (2) at stake.”
Unified Convergence Analysis of Stochastic Momentum Methods for Convex and Non-convex Optimization (2016, background): “Although the convergence analysis of HB has been recently extended to smooth functions for both convex (Ghadimi et al., 2014; Ochs et al., 2015) and non-convex optimization (Ochs et al., 2014), it is still under-explored for stochastic optimization, specially stochastic non-convex optimization.”
Accelerated Proximal Gradient Methods for Nonconvex Programming (2015, methodology): “Method name Assumption Accelerate (CP) converge (NCP) GD [16, 17] f + g: KL No Yes iPiano [18] nonconvex f , convex g No Yes GIST [19] nonconvex f , g = g1 − g2, g1, g2 convex No Yes GDPA [20] nonconvex f , g = g1 − g2, g1, g2 convex No Yes IR [8, 21] special f and g No Yes IFB [22] nonconvex f , no”
An introduction to continuous optimization for imaging (2016, methodology): “A common way to extend accelerated methods of this kind to more general problems is to consider problems 236 A. Chambolle and T. Pock Algorithm 11 ‘iPiano’ algorithm (Ochs et al. 2014).”
A Unified Analysis of Stochastic Momentum Methods for Deep Learning (2018, background): “The convergence analysis of HB has been recently extended to smooth functions for both convex [Ghadimi et al. , 2014; Ochs et al. , 2015] and non-convex deterministic optimization [Ochs et al. , 2014; Ochs, 2016].”
Optical flow modeling and computation: A survey (2015, result): “When appropriate minimization strategy is available, like graph cuts or the recent work of [192], this kind of penalty functions has proven to yield improvements compared to the TV model.”
On learning optimized reaction diffusion processes for effective image restoration (2015, methodology): “t the variational model (8) using the proximal gradient method [33], which reads as”
Modern regularization methods for inverse problems (2018, background): “It is important to emphasize that even for nonsmooth, nonconvex optimization there is a vast amount of recent publications, ranging from forward-backward, respectively proximaltype, schemes [8, 9, 10, 49, 50], over linearized proximal schemes [365, 47, 366, 298], to inertial methods [299, 309], prim”
Trainable Nonlinear Reaction Diffusion: A Flexible Framework for Fast and Effective Image Restoration (2015, methodology): “where ProxGtðûÞ is the proximal mapping operation [44] related to the non-differentiable function Gt, given as 1258 IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL.”
Calculus of the Exponent of Kurdyka–Łojasiewicz Inequality and Its Applications to Linear Convergence of First-Order Methods (2016, methodology): “ppose that fx kgis bounded. Then fxkgconverges locally linearly to a stationary point of f. The next algorithm we consider is the inertial proximal algorithm, known as iPiano, proposed and studied in [34]. The algorithm can be applied to minimizing (26) when domh= Rn and rhis globally Lipschitz cont”
Forward–backward quasi-Newton methods for nonsmooth optimization problems (2016, methodology): “This assumption was used to prove convergence of many other algorithms [7–11].”
Bilevel Optimization with Nonsmooth Lower Level Problems (2015, background): “With iPiano [24] we found the exact optimum; see also Figure 3.”