Lecture

Gradient Descent: Proximal Operator and Step-Size Strategies

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.

In course

EE-566: Adaptation and learning

In this course, students learn to design and master algorithms and core concepts related to inference and learning from data and the foundations of adaptation and learning theories with applications.

Description

This lecture covers the concepts of proximal operator, gradient descent, and step-size strategies in the context of minimizing risk functions. It explains the derivation of the gradient-descent algorithm, the use of constant step-sizes, and the transition to iteration-dependent step-sizes. The lecture also discusses the convergence analysis under different step-size conditions, such as constant and vanishing step-sizes, and their impact on the convergence rate of the algorithm.

Instructor

Ali H. Sayed

Ali H. Sayed is Dean of Engineering at EPFL, Switzerland, where he also leads the Adaptive Systems Laboratory. He has also served as Distinguished Professor and Chairman of Electrical Engineering at UCLA. He is recognized as a Highly Cited Researcher and is a member of the US National Academy of Engineering. He is also a member of the World Academy of Sciences and served as President of the IEEE Signal Processing Society during 2018 and 2019. Dr. Sayed is an author/co-author of over 570 scholarly publications and six books. His research involves several areas including adaptation and learning theories, data and network sciences, statistical inference, and multiagent systems. His work has been recognized with several major awards including the 2022 IEEE Fourier Award, the 2020 Norbert Wiener Society Award and the 2015 Education Award from the IEEE Signal Processing Society, the 2014 Papoulis Award from the European Association for Signal Processing, the 2013 Meritorious Service Award and the 2012 Technical Achievement Award from the IEEE Signal Processing Society, the 2005 Terman Award from the American Society for Engineering Education, the 2005 Distinguished Lecturer from the IEEE Signal Processing Society, the 2003 Kuwait Prize, and the 1996 IEEE Donald G. Fink Prize. His publications have been awarded several Best Paper Awards from the IEEE (2002, 2005, 2012, 2014) and EURASIP (2015). He is a Fellow of IEEE, EURASIP, and the American Association for the Advancement of Science (AAAS); the publisher of the journal Science.

Official source

Related concepts (18)

Risk management

Risk management is the identification, evaluation, and prioritization of risks (defined in ISO 31000 as the effect of uncertainty on objectives) followed by coordinated and economical application of resources to minimize, monitor, and control the probability or impact of unfortunate events or to maximize the realization of opportunities.

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.

Uniform convergence

In the mathematical field of analysis, uniform convergence is a mode of convergence of functions stronger than pointwise convergence. A sequence of functions converges uniformly to a limiting function on a set as the function domain if, given any arbitrarily small positive number , a number can be found such that each of the functions differs from by no more than at every point in .

Lanczos algorithm

The Lanczos algorithm is an iterative method devised by Cornelius Lanczos that is an adaptation of power methods to find the "most useful" (tending towards extreme highest/lowest) eigenvalues and eigenvectors of an Hermitian matrix, where is often but not necessarily much smaller than . Although computationally efficient in principle, the method as initially formulated was not useful, due to its numerical instability. In 1970, Ojalvo and Newman showed how to make the method numerically stable and applied it to the solution of very large engineering structures subjected to dynamic loading.

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

Related lectures (42)

2024 Lecture 4, PHYS-467 Machine learning for physicists | Friday | Fall 24

Optimization Methods in Machine Learning

Explores optimization methods in machine learning, emphasizing gradients, costs, and computational efforts for efficient model training.

Linear Systems: Convergence and Methods

Explores linear systems, convergence, and solving methods with a focus on CPU time and memory requirements.

Criteria for the convergence of series

Covers the squeeze theorem, examples, and the Leibniz criterion for series convergence.

Gradient Descent