Lecture

Descent methods and line search: Inexact line search

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 covers the concept of descent methods and line search, focusing on the idea of updating a point based on a step direction to minimize a function. Examples in one dimension are provided to illustrate the process, along with the intuition that descent direction assumes small steps. The lecture also discusses the importance of maintaining small steps for Taylor's theorem to apply and how even ascent directions can decrease the function with long steps.

In MOOC

Optimization: principles and algorithms - Unconstrained nonlinear optimization

What you'll learn Formulation: you will learn from simple examples how to formulate, transform and characterize an optimization problem. Objective function: you will review the mathematical properties of the objective function that are important in optimization. Optimality conditions: you will learn sufficient and necessary conditions for an optimal solution. Solving equations, Newton: this is a reminder about Newton's method to solve nonlinear equations. Newton's local method: you will see how to interpret

Official source

Related concepts (15)

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.

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

Dimension

In physics and mathematics, the dimension of a mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any point within it. Thus, a line has a dimension of one (1D) because only one coordinate is needed to specify a point on it - for example, the point at 5 on a number line. A surface, such as the boundary of a cylinder or sphere, has a dimension of two (2D) because two coordinates are needed to specify a point on it - for example, both a latitude and longitude are required to locate a point on the surface of a sphere.

One-dimensional space

In physics and mathematics, a sequence of n numbers can specify a location in n-dimensional space. When n = 1, the set of all such locations is called a one-dimensional space. An example of a one-dimensional space is the number line, where the position of each point on it can be described by a single number. In algebraic geometry there are several structures that are technically one-dimensional spaces but referred to in other terms. A field k is a one-dimensional vector space over itself.

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.

Related lectures (64)

Optimization: Gradient Descent and Subgradients

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

Optimization Techniques: Convexity in Machine Learning

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

Optimization without Constraints: Gradient Method

Covers optimization without constraints using the gradient method to find the function's minimum.

Optimization methods

Covers optimization methods, focusing on gradient methods and line search techniques.

Optimization Basics