Lecture

Accelerated Algorithms for Monotone Inclusions

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Description

This lecture by Quoc Tran-Dinh presents Halpern-type accelerated and splitting algorithms for monotone inclusions, focusing on optimization models and applications in various fields like convex optimization, nonlinear analysis, economics, and machine learning. The talk covers the motivation behind monotone inclusions, the optimization model, the challenges in developing accelerated methods, and the derivation of new algorithms like Halpern fixed-point iteration and splitting extra-gradient methods. The lecture also discusses the properties of maximally monotone operators, Lipschitz continuity, resolvent and proximal operators, convergence rates, and complexity analysis tools. The presentation concludes with the comparison of different methods and the convergence analysis of the proposed accelerated algorithms.

Official source

Related concepts (32)

Monotonic function

In mathematics, a monotonic function (or monotone function) is a function between ordered sets that preserves or reverses the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of order theory. In calculus, a function defined on a subset of the real numbers with real values is called monotonic if and only if it is either entirely non-increasing, or entirely non-decreasing. That is, as per Fig. 1, a function that increases monotonically does not exclusively have to increase, it simply must not decrease.

Resolvent formalism

In mathematics, the resolvent formalism is a technique for applying concepts from complex analysis to the study of the spectrum of operators on Banach spaces and more general spaces. Formal justification for the manipulations can be found in the framework of holomorphic functional calculus. The resolvent captures the spectral properties of an operator in the analytic structure of the functional.

Resolvent set

In linear algebra and operator theory, the resolvent set of a linear operator is a set of complex numbers for which the operator is in some sense "well-behaved". The resolvent set plays an important role in the resolvent formalism. Let X be a Banach space and let be a linear operator with domain . Let id denote the identity operator on X. For any , let A complex number is said to be a regular value if the following three statements are true: is injective, that is, the corestriction of to its image has an inverse ; is a bounded linear operator; is defined on a dense subspace of X, that is, has dense range.

Rate of convergence

In numerical analysis, the order of convergence and the rate of convergence of a convergent sequence are quantities that represent how quickly the sequence approaches its limit. A sequence that converges to is said to have order of convergence and rate of convergence if The rate of convergence is also called the asymptotic error constant. Note that this terminology is not standardized and some authors will use rate where this article uses order (e.g., ).

Iterative method

In computational mathematics, an iterative method is a mathematical procedure that uses an initial value to generate a sequence of improving approximate solutions for a class of problems, in which the n-th approximation is derived from the previous ones. A specific implementation with termination criteria for a given iterative method like gradient descent, hill climbing, Newton's method, or quasi-Newton methods like BFGS, is an algorithm of the iterative method.

Related lectures (64)

Optimization Methods

Covers optimization methods without constraints, including gradient and line search in the quadratic case.

Newton Method: Convergence and Quadratic Care

Covers the Newton method and its convergence properties near the optimal point.

Gradient Descent: Principles and Applications

Covers gradient descent, its principles, applications, and convergence rates in optimization for machine learning.

Optimization without Constraints: Gradient Method

Covers optimization without constraints using the gradient method to find the function's minimum.

Proximal and Subgradient Descent: Optimization Techniques