Optimization for machine learning

Tam Le, Université Paris Cité - LPSM

Overview

Content. (1) Theoretical study of optimization algorithms. (2) Implementation

with automatic differentiation. (3) Machine learning aspects.

1
Prerequisite. basics in differential calculus, linear algebra, probability, python

Assessment.
• Homework (math exercises + coding): 1/4
• Final exam: 3/4 (math exercises, guided proofs from class and small coding
questions)

Contact.
• email: tamle@[Link].
• Office 5005 at Sophie Germain building.
• Course content on moodle.

1 For other languages (R, Julia), it has to be with autodiff library; ask me first. Exam

questions will be on python/pytorch.

2 / 23
Homework rules

• For homework feel free to use your favorite LLM for help, but remember: the
best is figuring it out yourself. HW are safe spaces to learn and make
mistakes.
• Do not trust LLMs outputs blindly.
• Presentation and redaction will be part of the evaluation.
• Delivery in LateX will be appreciated.
• For the code, you may provide a commented jupyter notebook.

3 / 23
Optimization

(Mathematical) Optimization aims to solve problems formulated as

Minimize F (x)
x∈C

Many applications.
Anytime you want the “best” solution under constraints (time, cost, risk,
resources, etc.), optimization is involved. - ChatGPT

• Planning, logistics: the best allocation?

• Signal processing: the best estimate of the true signal? The smallest one?
• Finance: the best portfolio? The less risky?
• Robotics, control: the best trajectory? the best reaction?
...
• Machine learning, deep learning, LLM: the best prediction? the best answer?

4 / 23
Brief History
1950s – Birth of modern optimization. Linear optimization - George Dantzig
(simplex method), applications to logistics - Kantorovich, duality principle - Von
Neumann.

1960s–Late 20th Century – Focus on convex optimization:

• Efficient algorithms for convex problems: first-order oracles (gradients) ⇒
polynomial complexity.
• Theoretical foundations of convex analysis: Moreau: “How to deal with
physical problems without compromising nonlinearities?”, Fenchel,
Rockafellar . . .
• Development of solvers for canonical convex problems (e.g. CVX) in the
2000s.

2010s–Present – Machine Learning era

• Stochastic gradient methods for large-scale problems
• Take roots in seminals works, stochastic method (Robbins and Monro, 1951),
inertial methods (Polyak 1964, Nesterov 1983 . . . )
• Adaptivity: update deep learning models on-the-fly.
• Greatly driven by automatic differentiation and GPU acceleration.
5 / 23
Opt for ML? Linear regression example

Why optimization in machine learning?

Assume we have data points (ϕi , yi )i=1,...,n . ϕi are called features or inputs yi are
called targets or outputs. We want to find the “best” x∗ ∈ Rd such that

yi ≈ ⟨x∗ , ϕi ⟩
Statistical standpoint offers log-likelihood maximization to estimate such a x∗ .

Assuming the variance is σ 2 , x∗ is selected as

n
(⟨x, ϕi ⟩ − yi )2
Y  
x∗ ∈ argmax exp −
x∈Rp i=1
2σ 2
n
1X
= argmin (⟨x, ϕi ⟩ − yi )2
x∈Rp n i=1

6 / 23
Empirical risk framework

We see a general learning principle here: empirical risk minimization (ERM).

Assume we have couples of input output (ϕi , yi )i=1,...,n . Then we can fit a model
h(x∗ , ·) by ERM.

n
1X
min ℓ(h(x, ϕi ), yi )
x∈Rp n i=1

ℓ is a dissimilarity measure.

Classical examples . . .

Least square regression. ℓ(h, y) = (h − y)2 , h(x, ϕ) = ⟨x, ϕ⟩

Least absolute deviation ℓ(h(x, ϕ), y) = |⟨x, ϕ⟩ − y|.
1
Logistic regression. ℓ(h, y) = −(1 − y) log(h) − y log(h), h(x, ϕ) = 1+exp(−⟨x,ϕ⟩)

7 / 23
Application to image classification

• Inputs: pixel arrays (images), ϕi ∈ Rd×d

• Outputs: labels yi ∈ {cat, dog} = {0, 1}
• ℓ(h, y) = −(1 − y) log(h) − y log(h).
• Prediction function: neural net

h(x, ϕ) = σ(WL σ(WL−1 σ(. . . σ(W1 ϕ + b1 ) . . .) + bL−1 ) + bL )

σ is an activation function (for instance reLU = max(0, ·)), and x is the

concatenation of the (Wi , bi )i=1,...,L .

8 / 23
Direct methods?

Linear regression can be solved by a linear system.

n
1X 1
(⟨x, ϕi ⟩ − yi )2 = ∥Φx − y∥22
2 i=1 2

Exercise. Specify the matrix Φ ∈ Rn×d and the vector y ∈ Rn . Write the linear
system satisfied by the solution

Here, a solution can be obtained exactly.

QR factorization. Φ can be decomposed as Φ = QR where QT Q = In

(orthogonal matrix) and R of size d × d is upper triangular. Solving the previous
system then is equivalent to

Rx = QT y
Overall complexity is O(d3 ) for d = n (due to computation of QR decomposition).

9 / 23
Exactness vs. complexity vs. predictive performance
Do we really need theoretically exact solutions?
→ Numerician says: we are limited by numerical precision in practice (see e.g.
conjugate gradient method).

Machine learner’s standpoint. when training by iterative method:

• Good predictive performance is sufficient.

• Statistical noise overcome numerical accuracy.
• Approximate solutions are obtained faster, better scaling with problem size.
10 / 23
First-order algorithms

Approximate solutions are often given by iterative methods, which update a

sequence according to some map H.

xk+1 = H(xk )

It aims for an optimality condition 0 = G(x∗ ) (e.g. 0 = ∇F (x∗ )).

In this course we will be interested in general algorithms using gradient, called

first-order methods. Some examples:

Gradient method

xk+1 = xk − αk ∇F (xk )
Interpretation: −∇F is a local descent direction.
F (x + h) = F (x) + ⟨∇F (x), h⟩ + o(∥h∥)

Heavy ball method: gradient method with inertia

xk+1 = xk − αk ∇F (xk ) + βk (xk − xk−1 )

11 / 23
Automatic differentiation, build and optimize
Gradient based algorithms offers a general framework for model fitting. This is
greatly enabled by automatic differentiation.

“Plug new model and optimize”

12 / 23
Mechanisms behind?

13 / 23
Built-in optimizers

14 / 23
Theoretical study: the role of regularity

At which rate, as k → ∞, do these algorithms converge?

Regularity and good geometry will be key.

Exercise. Study the convergence of gradient method on linear regression

assuming ΦT Φ has eigenvalues in [µ, L] for some 0 < µ < L.

15 / 23
Conditioning
L
Here the conditioning µ seems crucial.
Well-conditioned: f(x, y) = x2 + y2 Poorly-conditioned: f(x, y) = x2 + 100y2
Condition number = 1 Condition number = 100
10.0 10.0

7.5 7.5

5.0 5.0

2.5 2.5

0.0 0.0
y

y
2.5 2.5

5.0 5.0

7.5 7.5

10.0 10.0
10.0 7.5 5.0 2.5 0.0 2.5 5.0 7.5 10.0 10.0 7.5 5.0 2.5 0.0 2.5 5.0 7.5 10.0
x x

In general, what do we have to know about the regularity? Do the algorithm

adapts to the regularity?
16 / 23
 10000
9500
Inertia vs. conditioning
9000
8500
8000
7500
7000
6500
6000
5500
5000 Heavy Ball Method
4500 vs Gradient Descent
on Poorly Conditioned Function: f(x, y) = x4000
2 + 100y 2
3500
3000
2500
2000
4 1500
1000

500
2

Gradient Descent
0 Heavy Ball (Momentum)
y

Minimum

2 500

1000
1500
4
2000
2500
3000
3500
10.0 7.5 5.0 4000 2.5 0.0 2.5 5.0 7.5 10.0
4500
x 5000
5500
6000
6500
7000
7500
8000
8500
9000 17 / 23
Leveraging problem’s structure
Algorithmic choices are driven by problem’s structure and/or computational
limitations.

Example 1: Nonsmooth regularization (e.g. variable selection).

1
min ∥Ax − b∥22 + λ∥x∥1
x∈Rp 2
∥ · ∥1 √
is not differentiable at some points. General method (subgradient) gives
O(1/ k) rate. Little tweak in this case gives O(1/k) (proximal gradient).
12

11

10

6
4 3 2 1 0 1 2 3 4 18 / 23
Leveraging problem’s structure

Example 2: How to deal with ERM when n is large (e.g. deep learning)?
n
1X
minp F (x) = fi (x)
x∈R n i=1
Can we have an algorithm with only access to each ∇fi ? When is this problem
easy/difficult? Stochastic gradient descent

19 / 23
Little disclaimer

ERM is more a goal than a solution!

Modelling often introduces challenging objective functions:

Robust learning. Uncertainty level ϵ > 0, min-max problem:

n
( )
1X
minp max f (x, ϕi + ei , yi )
x∈R e1 ,...,en ∈B(0,ϵ)n n i=1

Generative modelling, sampling. Distribution (of images) PY , Gaussian noise Ξ, neural network
h(x, ·).

min d(PY , Ph(x,ϕ) )

x∈Rp
where d is some “distance” between probability distributions (cf. optimal transport).

Risk averse optimization, nested problem.

min Eϕ [f (x, ϕ) + κ(f (x, ϕ) − Eϕ [f (x, ϕ)])+ ]

x∈Rp

Optimization is everywhere, but a “nice” formulation of the problem helps

to build good/simple algorithms.
20 / 23
Rough table of content

min F (x)
x∈Rp

What are the existing algorithms to solve this problem when F is . . .

convex? differentiable? not differentiable? nonconvex? a large sum?
• Classical gradient method
• How to compute gradients? Automatic differentiation, computational graph
• Inertia and acceleration techniques
• Leveraging structure: nonsmooth penalty, subgradient, proximal operator
• Stochastic gradient method: finite sum.

What kind guarantees do we have for these algorithms?

Do I have... convergence in F (xk )? in xk ? in ∥∇F (xk )∥?
• Descent vs. regularity vs. stepsize
• The best we can hope for? Lower bounds
• Gradient variance.

21 / 23
References to learn more
Optimization for Machine Learning
• Learning Theory from First Principles
Bach
• First-order and Stochastic Optimization Methods for Machine Learning
Guanghui Lan
• Handbook of Convergence Theorems for (Stochastic) Gradient Methods
Garrigos, Gower (online)
• Optimization Methods for Large-Scale ML
Bottou, Curtis, Nocedal

Optimization in general
• Convex Optimization
Boyd, Vandenberghe (Beginner-friendly)
• Variational Analysis
Rockafellar, Wets (Theoretical and dense book)
• Lectures on Convex Optimization
Nesterov
• Convex Optimization: Algorithms and Complexity
Bubeck
22 / 23
Thanks for your attention!

23 / 23