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

Lecture

Generalized Optimistic Methods for Convex-Concave Saddle Point Problems

Description

This lecture introduces a generalized optimistic framework for solving convex-concave saddle point problems, extending to higher-order methods. The method covers composite settings, complexity bounds, and line search schemes. The instructor discusses the convergence rates, stepsize selection, and the implementation of the algorithm.

Official source

Related concepts (22)

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., ).

Numerical methods for ordinary differential equations

Numerical methods for ordinary differential equations are methods used to find numerical approximations to the solutions of ordinary differential equations (ODEs). Their use is also known as "numerical integration", although this term can also refer to the computation of integrals. Many differential equations cannot be solved exactly. For practical purposes, however – such as in engineering – a numeric approximation to the solution is often sufficient. The algorithms studied here can be used to compute such an approximation.

Convex optimization

Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets (or, equivalently, maximizing concave functions over convex sets). Many classes of convex optimization problems admit polynomial-time algorithms, whereas mathematical optimization is in general NP-hard.

Convex function

In mathematics, a real-valued function is called convex if the line segment between any two distinct points on the graph of the function lies above the graph between the two points. Equivalently, a function is convex if its epigraph (the set of points on or above the graph of the function) is a convex set. A twice-differentiable function of a single variable is convex if and only if its second derivative is nonnegative on its entire domain.

Euler method

In mathematics and computational science, the Euler method (also called the forward Euler method) is a first-order numerical procedure for solving ordinary differential equations (ODEs) with a given initial value. It is the most basic explicit method for numerical integration of ordinary differential equations and is the simplest Runge–Kutta method. The Euler method is named after Leonhard Euler, who first proposed it in his book Institutionum calculi integralis (published 1768–1870).

Related lectures (42)

Optimization Basics

Introduces optimization basics, covering logistic regression, derivatives, convex functions, gradient descent, and second-order methods.

Optimality of Convergence Rates: Accelerated Gradient Descent

Explores the optimality of convergence rates in convex minimization problems using accelerated gradient descent methods.

Proximal and Subgradient Descent: Optimization Techniques

Discusses proximal and subgradient descent methods for optimization in machine learning.

Gradient Descent Methods: Theory and Computation

Explores gradient descent methods for smooth convex and non-convex problems, covering iterative strategies, convergence rates, and challenges in optimization.

Optimization Techniques: Convexity in Machine Learning