Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Momentum methods and nonlinear CG

In course

MATH-512: Optimization on manifolds

We develop, analyze and implement numerical algorithms to solve optimization problems of the form min f(x) where x is a point on a smooth manifold. To this end, we first study differential and Riemannian geometry (with a focus dictated by computational con ...

Description

This lecture covers gradient descent with memory in R2, introducing momentum methods to improve convergence speed. It then delves into conjugate gradients with momentum, exploring the use of different beta rules and their impact on performance. The instructor also discusses nonlinear CG on manifolds, specifically Riemannian CG, highlighting the rich family of algorithms it yields and the delicate theory behind it.

Instructor

Nicolas Boumal

Official source

Related concepts (32)

Conjugate gradient method

In mathematics, the conjugate gradient method is an algorithm for the numerical solution of particular systems of linear equations, namely those whose matrix is positive-definite. The conjugate gradient method is often implemented as an iterative algorithm, applicable to sparse systems that are too large to be handled by a direct implementation or other direct methods such as the Cholesky decomposition. Large sparse systems often arise when numerically solving partial differential equations or optimization problems.

Gradient descent

In mathematics, gradient descent (also often called steepest descent) is a iterative optimization algorithm for finding a local minimum of a differentiable function. The idea is to take repeated steps in the opposite direction of the gradient (or approximate gradient) of the function at the current point, because this is the direction of steepest descent. Conversely, stepping in the direction of the gradient will lead to a local maximum of that function; the procedure is then known as gradient ascent.

Manifold

In mathematics, a manifold is a topological space that locally resembles Euclidean space near each point. More precisely, an -dimensional manifold, or -manifold for short, is a topological space with the property that each point has a neighborhood that is homeomorphic to an open subset of -dimensional Euclidean space. One-dimensional manifolds include lines and circles, but not lemniscates. Two-dimensional manifolds are also called surfaces. Examples include the plane, the sphere, and the torus, and also the Klein bottle and real projective plane.

Mathematical optimization

Mathematical optimization (alternatively spelled optimisation) or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfields: discrete optimization and continuous optimization. Optimization problems arise in all quantitative disciplines from computer science and engineering to operations research and economics, and the development of solution methods has been of interest in mathematics for centuries.

Differentiable manifold

In mathematics, a differentiable manifold (also differential manifold) is a type of manifold that is locally similar enough to a vector space to allow one to apply calculus. Any manifold can be described by a collection of charts (atlas). One may then apply ideas from calculus while working within the individual charts, since each chart lies within a vector space to which the usual rules of calculus apply. If the charts are suitably compatible (namely, the transition from one chart to another is differentiable), then computations done in one chart are valid in any other differentiable chart.

Related lectures (52)

Transporters: a proxy for parallel transport

Explores transporters as a practical alternative to parallel transport, discussing minimal requirements, examples with matrices, pragmatic choices, and optimization algorithms.

Optimization on Manifolds: Context and Applications MOOC: Introduction to optimization on smooth manifolds: first order methods

Introduces optimization on manifolds, covering classical and modern techniques in the field.

Choosing a Step Size MOOC: Introduction to optimization on smooth manifolds: first order methods

Explores choosing a step size in optimization on manifolds, including backtracking line-search and the Armijo method.

Comparing Tangent Vectors: Three Reasons Why

Explores the importance of comparing tangent vectors at different points using algorithms and finite differences.

Taylor Expansions: First Order MOOC: Introduction to optimization on smooth manifolds: first order methods