Lecture

Stochastic Optimization: Algorithms and Methods

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 stochastic optimization and adaptive gradient methods, examining algorithms like gradient descent, coordinate descent, subgradient, proximal gradient, projection gradient, and mirror descent. It explores the solution of convex optimization problems with and without constraints, for both smooth and nonsmooth risks. The lecture delves into exploiting the structure of the risk function and the challenges posed by large datasets and unknown statistics. Various stochastic algorithms are discussed, including stochastic gradient, subgradient, and proximal gradient methods, highlighting their convergence properties and the impact of step sizes on convergence.

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 (32)

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.

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.

Sampling (statistics)

In statistics, quality assurance, and survey methodology, sampling is the selection of a subset or a statistical sample (termed sample for short) of individuals from within a statistical population to estimate characteristics of the whole population. Statisticians attempt to collect samples that are representative of the population. Sampling has lower costs and faster data collection compared to recording data from the entire population, and thus, it can provide insights in cases where it is infeasible to measure an entire population.

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.

Randomness

In common usage, randomness is the apparent or actual lack of definite pattern or predictability in information. A random sequence of events, symbols or steps often has no order and does not follow an intelligible pattern or combination. Individual random events are, by definition, unpredictable, but if the probability distribution is known, the frequency of different outcomes over repeated events (or "trials") is predictable. For example, when throwing two dice, the outcome of any particular roll is unpredictable, but a sum of 7 will tend to occur twice as often as 4.

Related lectures (64)

Stochastic Gradient Descent: Non-convex Optimization Techniques

Discusses Stochastic Gradient Descent and its application in non-convex optimization, focusing on convergence rates and challenges in machine learning.

Optimization Techniques: Convexity in Machine Learning

Covers optimization techniques in machine learning, focusing on convexity and its implications for efficient problem-solving.

Optimization Methods in Machine Learning

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

Optimization: Gradient Descent and Subgradients

Explores optimization methods like gradient descent and subgradients for training machine learning models, including advanced techniques like Adam optimization.

Explicit Stabilised Methods: Applications to Bayesian Inverse Problems