Lecture

Gradient Descent Convergence

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

MGT-448: Statistical inference and machine learning

This course aims to provide graduate students a thorough grounding in the methods, theory, mathematics and algorithms needed to do research and applications in machine learning. The course covers topics from machine learning, classical statistics, and data ...

Description

This lecture presents a stronger result about gradient descent, assuming a convex function with a minimum. It explains how the algorithm converges to the function's minimum at a rate of 1 over k, providing a detailed proof of the convergence. The instructor also discusses the importance of choosing the proper step size for convergence and highlights the challenges of determining the Lipschitz constant. Additionally, the lecture introduces the concept of strong convexity and how it can lead to even stronger convergence results, emphasizing the significance of understanding the properties of the function for optimization.

Instructor

Negar Kiyavash

Teaching & PhD PhD Students Mohammad Shahverdikondori, Badri Mohammad Reza, Arefe Boushehrian, Sepehr Elahi, Mohammadsadegh Khorasani, Mohammadsaeed Masiha, Amir Mohammad Aboueimehrizi Past EPFL PhD Students Sina Akbari, Ehsan Mokhtarian, Yaroslav Kivva, Fateme Jamshidi Courses Causal inference MGT-416 Students will learn the core concepts and techniques of network analysis with emphasis on causal inference. Theory andapplication will be balanced, with students working directly with networ

Official source

Related concepts (30)

Convex function

In mathematics, a real-valued function is called convex if the line segment between any two distinct points on the graph of the function lies above the graph between the two points. Equivalently, a function is convex if its epigraph (the set of points on or above the graph of the function) is a convex set. A twice-differentiable function of a single variable is convex if and only if its second derivative is nonnegative on its entire domain.

Lipschitz continuity

In mathematical analysis, Lipschitz continuity, named after German mathematician Rudolf Lipschitz, is a strong form of uniform continuity for functions. Intuitively, a Lipschitz continuous function is limited in how fast it can change: there exists a real number such that, for every pair of points on the graph of this function, the absolute value of the slope of the line connecting them is not greater than this real number; the smallest such bound is called the Lipschitz constant of the function (and is related to the modulus of uniform continuity).

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.

Quasiconvex function

In mathematics, a quasiconvex function is a real-valued function defined on an interval or on a convex subset of a real vector space such that the of any set of the form is a convex set. For a function of a single variable, along any stretch of the curve the highest point is one of the endpoints. The negative of a quasiconvex function is said to be quasiconcave. All convex functions are also quasiconvex, but not all quasiconvex functions are convex, so quasiconvexity is a generalization of convexity.

Modulus of continuity

In mathematical analysis, a modulus of continuity is a function ω : [0, ∞] → [0, ∞] used to measure quantitatively the uniform continuity of functions. So, a function f : I → R admits ω as a modulus of continuity if and only if for all x and y in the domain of f. Since moduli of continuity are required to be infinitesimal at 0, a function turns out to be uniformly continuous if and only if it admits a modulus of continuity. Moreover, relevance to the notion is given by the fact that sets of functions sharing the same modulus of continuity are exactly equicontinuous families.

Related lectures (64)

Optimization Methods in Machine Learning

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

Convex Optimization: Gradient Descent

Explores VC dimension, gradient descent, convex sets, and Lipschitz functions in convex optimization.

Primal-dual Optimization: Algorithms and Convergence

Explores primal-dual optimization algorithms for convex-concave minimax problems, discussing convergence properties and applications.

Proximal and Subgradient Descent: Optimization Techniques

Discusses proximal and subgradient descent methods for optimization in machine learning.

Stochastic Gradient Descent