Lecture

Coordinate Descent: Optimization 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.

Description

This lecture delves into the concept of coordinate descent optimization strategies, focusing on simplifying the optimization process by updating one coordinate at a time. The instructor explains the transition from gradient methods to second-order methods, emphasizing the trade-off between complexity and simplicity in optimization. Through examples and theoretical analysis, the lecture explores the benefits and limitations of coordinate-based approaches, discussing the importance of selecting the right step size and coordinate for efficient optimization. The instructor also covers the implications of different strategies, such as random coordinate descent, steepest coordinate descent, and importance sampling, highlighting their relevance in machine learning applications. Additionally, the lecture touches on the challenges posed by non-smooth functions and provides insights into overcoming them in practical scenarios.

This video is available exclusively on Mediaspace for a restricted audience. Please log in to MediaSpace to access it if you have the necessary permissions.

Watch on Mediaspace

Official source

Related concepts (32)

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

Coordinate descent

Coordinate descent is an optimization algorithm that successively minimizes along coordinate directions to find the minimum of a function. At each iteration, the algorithm determines a coordinate or coordinate block via a coordinate selection rule, then exactly or inexactly minimizes over the corresponding coordinate hyperplane while fixing all other coordinates or coordinate blocks. A line search along the coordinate direction can be performed at the current iterate to determine the appropriate step size.

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.

Non-analytic smooth function

In mathematics, smooth functions (also called infinitely differentiable functions) and analytic functions are two very important types of functions. One can easily prove that any analytic function of a real argument is smooth. The converse is not true, as demonstrated with the counterexample below. One of the most important applications of smooth functions with compact support is the construction of so-called mollifiers, which are important in theories of generalized functions, such as Laurent Schwartz's theory of distributions.

Machine learning

Machine learning (ML) is an umbrella term for solving problems for which development of algorithms by human programmers would be cost-prohibitive, and instead the problems are solved by helping machines 'discover' their 'own' algorithms, without needing to be explicitly told what to do by any human-developed algorithms. Recently, generative artificial neural networks have been able to surpass results of many previous approaches.

Related lectures (64)

Coordinate Descent: Efficient Optimization Techniques

Covers coordinate descent, a method for optimizing functions by updating one coordinate at a time.

Optimization: Gradient Descent and Subgradients

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

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.

Gradient Descent: Principles and Applications