Optimality of Convergence Rate: Acceleration in Gradient Descent

This lecture covers the optimality of convergence rate in gradient descent, acceleration techniques, and the stochastic gradient descent algorithm. It discusses the convergence rate of gradient descent for convex functions, information theoretic lower bounds, accelerated gradient descent algorithms, global convergence properties, adaptive first-order methods, and variable metric gradient descent algorithms. The lecture also explores adaptive gradient methods, AdaGrad, convergence rates for AdaGrad, AcceleGrad, and the performance comparison of optimization algorithms for convex and non-convex problems.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related lectures (40)

Related concepts (32)

EE-556: Mathematics of data: from theory to computation

This course provides an overview of key advances in continuous optimization and statistical analysis for machine learning. We review recent learning formulations and models as well as their guarantees

Stochastic gradient descent

Stochastic gradient descent (often abbreviated SGD) is an iterative method for optimizing an objective function with suitable smoothness properties (e.g. differentiable or subdifferentiable). It can be regarded as a stochastic approximation of gradient descent optimization, since it replaces the actual gradient (calculated from the entire data set) by an estimate thereof (calculated from a randomly selected subset of the data).

Series acceleration

In mathematics, series acceleration is one of a collection of sequence transformations for improving the rate of convergence of a series. Techniques for series acceleration are often applied in numerical analysis, where they are used to improve the speed of numerical integration. Series acceleration techniques may also be used, for example, to obtain a variety of identities on special functions. Thus, the Euler transform applied to the hypergeometric series gives some of the classic, well-known hypergeometric series identities.

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.

Mathematics

Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics with the major subdisciplines of number theory, algebra, geometry, and analysis, respectively. There is no general consensus among mathematicians about a common definition for their academic discipline. Most mathematical activity involves the discovery of properties of abstract objects and the use of pure reason to prove them.

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.

Optimality of Convergence Rates: Accelerated Gradient Descent EE-556: Mathematics of data: from theory to computation

Explores the optimality of convergence rates in convex optimization, focusing on accelerated gradient descent and adaptive methods.

Optimality of Convergence Rates: Accelerated/Stochastic Gradient Descent EE-556: Mathematics of data: from theory to computation

Covers the optimality of convergence rates in accelerated and stochastic gradient descent methods for non-convex optimization problems.

Primal-dual Optimization: Extra-Gradient Method EE-556: Mathematics of data: from theory to computation

Explores the Extra-Gradient method for Primal-dual optimization, covering nonconvex-concave problems, convergence rates, and practical performance.

Optimization Methods: Convergence and Trade-offs EE-556: Mathematics of data: from theory to computation

Covers optimization methods, convergence guarantees, trade-offs, and variance reduction techniques in numerical optimization.

Gradient Descent Methods: Theory and Computation EE-556: Mathematics of data: from theory to computation

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