1,720,987 research outputs found
Accelerated And Inexact Forward-Backward Algorithms
Full text linkWe propose a convergence analysis of accelerated forward-backward splitting methods for composite function minimization, when the proximity operator is not available in closed form, and can only be computed up to a certain precision. We prove that the 1/k(2) convergence rate for the function values can be achieved if the admissible errors are of a certain type and satisfy a sufficiently fast decay condition. Our analysis is based on the machinery of estimate sequences first introduced by Nesterov for the study of accelerated gradient descent algorithms. Furthermore, we give a global complexity analysis, taking into account the cost of computing admissible approximations of the proximal point. An experimental analysis is also presented.LION
Convergence of an Asynchronous Block-Coordinate Forward-Backward Algorithm for Convex Composite Optimization
Full text linkIn this paper, we study the convergence properties of a randomized
block-coordinate descent algorithm for the minimization of a composite convex
objective function, where the block-coordinates are updated asynchronously and
randomly according to an arbitrary probability distribution. We prove that the
iterates generated by the algorithm form a stochastic quasi-Fej\'er sequence
and thus converge almost surely to a minimizer of the objective function.
Moreover, we prove a general sublinear rate of convergence in expectation for
the function values and a linear rate of convergence in expectation under an
error bound condition of Tseng type
Bilevel Optimization with a Lower-level Contraction: Optimal Sample Complexity without Warm-start
Full text linkWe analyse a general class of bilevel problems, in which the upper-level
problem consists in the minimization of a smooth objective function and the
lower-level problem is to find the fixed point of a smooth contraction map.
This type of problems include instances of meta-learning, equilibrium models,
hyperparameter optimization and data poisoning adversarial attacks. Several
recent works have proposed algorithms which warm-start the lower-level problem,
i.e.~they use the previous lower-level approximate solution as a staring point
for the lower-level solver. This warm-start procedure allows one to improve the
sample complexity in both the stochastic and deterministic settings, achieving
in some cases the order-wise optimal sample complexity. However, there are
situations, e.g., meta learning and equilibrium models, in which the warm-start
procedure is not well-suited or ineffective. In this work we show that without
warm-start, it is still possible to achieve order-wise (near) optimal sample
complexity. In particular, we propose a simple method which uses (stochastic)
fixed point iterations at the lower-level and projected inexact gradient
descent at the upper-level, that reaches an -stationary point using
and samples for the stochastic
and the deterministic setting, respectively. Finally, compared to methods using
warm-start, our approach yields a simpler analysis that does not need to study
the coupled interactions between the upper-level and lower-level iterates.Comment: Corrected Remark 18 + other small edits. Code at
https://github.com/CSML-IIT-UCL/bioptexp
Proximal Gradient Methods for Machine Learning and Imaging
No full textConvex optimization plays a key role in data science and image processing. Indeed, from one hand it provides theoretical frameworks, such as duality theory and the theory of nonexpansive operators, which are indispensable to formally analyze many problems arising in those fields. On the other hand, convex optimization supplies a plethora of algorithmic solutions covering a broad range of applications. In particular, the last decades witnessed an unprecedented development of optimization methods which are now capable of addressing structured and large-scale problems effectively. An important class of such methods, which are at the core of modern nonlinear convex optimization, is that of proximal gradient splitting algorithms. They are first-order methods which are tailored to optimization problems having a composite structure given by the sum of smooth and nonsmooth terms. These methods are splitting algorithms, in the sense that along the iterations they process each term separately by exploiting gradient information when available and the so-called proximity operator for nonsmooth terms. Even though there is a rich literature on proximal gradient algorithms, in this contribution, we paid particular attention to presenting a self-contained and unifying analysis for the various algorithms, unveiling common theoretical basis. We give state-of-the-art results treating both convergence of the iterates and of objective functions values in infinite-dimensional setting. This work is based on the lecture notes written for the PhD course “Introduction to Convex Optimization” that was given by the authors at the University of Genoa during the last 5 years
- …
