Optimization for AI

Contents

• Introduction and overview
• 0. Refresher: convexity and duality
• 1. Optimization inside the AI loop
• 2. Gradient descent: convergence proved
• 3. Conditioning and Nesterov acceleration
• 4. Proximal methods: ISTA and FISTA
• 5. Stochastic gradient descent
• 6. Variance reduction: SAGA and SVRG
• 7. Newton and quasi-Newton
• 8. Constraints in machine learning
• 9. Hyperparameter optimization
• 10. Optimizing the training of networks
• 11. Course research notes — CMAP (Chamon, Dieuleveut)
• Exercises
• Projects and assessment
• References

Introduction and overview

Audience: an engineer who already runs Adam or SGD and wants to know why it converges (or not). Empirical first: each topic starts from a symptom — a loss that oscillates because the step is too large, a plateau on an ill-conditioned problem — and only then names the concepts that explain it: convexity, conditioning, acceleration, proximal operators, convergence rates.

The module is the theoretical backbone reused wherever a model is trained in the program.

What you will be able to do

• Prove the convergence of gradient descent and its acceleration under convexity and strong convexity assumptions.
• Explain the role of conditioning and that of Nesterov acceleration.
• Handle non-smooth objectives with proximal methods (ISTA, FISTA).
• Analyze stochastic gradient descent and the effect of variance reduction (SAGA, SVRG).
• Choose between first-order and quasi-Newton methods according to the problem and its dimension.
• Formulate constraints in learning via duality, projections and penalties.
• Optimize hyperparameters in a reasoned way rather than blindly.
• Connect these theoretical results to the actual training of neural networks.

Official objectives and syllabus (2026-2027 catalog)

According to the APM_52067_EP — “Optimization for AI” sheet: the course introduces the fundamentals of optimization for machine learning and AI. Rather than a panorama of existing algorithms, it is organized around the workhorse of modern ML/AI — stochastic gradient descent (SGD) — and studies its extensions, such as variance reduction and adaptive methods, deriving convergence guarantees in convex and non-convex settings.

It also explores minimax optimization, in particular in the context of constrained optimization and duality, non-smooth optimization, and saddle-point methods, with an emphasis on theoretical foundations and practical applications.

The sheet publishes no session-by-session programme and no prerequisites. The LLGA section of its assessment tab gives only the exam format: a written final exam without calculator, with one handwritten A4 sheet allowed (to be handed in with the exam). The table maps every element of this description to the section that teaches it.

Complement to the official description — chapters of these materials that go beyond it: Nesterov acceleration (ch. 3), Newton and quasi-Newton (ch. 7), hyperparameter optimization (ch. 9) and the research of the course instructors (ch. 11, self-study).

Where this course fits in the program

An option of period 2 of M1, outside the recommended track. It sits in the Choose-1 group of Period 2, next to Multimodal Generative AI, Deep Learning (P2 variant), Computational Optimal Transport, Advanced Deep Learning and Image Synthesis. A student who takes it takes none of these, so this page cites their notes only as optional reading. Official prerequisites: not communicated (the “Prerequisites” tab of the SynapseS sheet is empty).

What the module assumes:

• the mandatory P1 Machine Learning course, whose gradient descent (0.2) and Lagrangian duality (0.4) are recalled in chapter 0;
• the P1 Deep Learning course, which every student of this option has taken: Deep Learning is required once, and its P2 variant sits in this same group. Its Adam and schedules (3.3–3.4) are recalled in chapter 10;
• if you took it in P1, Emerging Subjects in ML & Collaborative Learning (SGD review in ch. 0, distributed SGD in ch. 2) is a first draft of chapters 5–6; it is not required.

What it feeds: the mandatory Reinforcement Learning course, which runs in parallel, rests on the stochastic approximation of its section 0.2, and chapter 11 here carries duality over to constrained reinforcement learning. In Year 2, the training runs of Large Language Models (ch. 3–4) are the SGD, AdamW and schedules of chapters 5 and 10. The end-of-year projects Y1.3 (exposure constraint by stochastic primal–dual) and Y2.4 use the constraint tools of chapter 8.

Course outline

• Refresher: convexity and duality — the essentials of convex analysis reloaded for the rest of the module.
• Optimization inside the AI loop — why modern learning is first an optimization problem, and what that imposes.
• Gradient descent: convergence proved — the founding theorem, its assumptions and its rate, proved in detail.
• Conditioning and Nesterov acceleration — what the geometry of the problem does to speed, and the acceleration that answers it.
• Proximal methods: ISTA and FISTA — handling non-differentiabilities (regularizations, constraints) cleanly, and the subgradient method when no prox is available.
• Stochastic gradient descent — the workhorse algorithm of machine learning, analyzed as such, in the convex and the non-convex settings.
• Variance reduction: SAGA and SVRG — keeping the best of both worlds: the cost of the stochastic, the accuracy of the deterministic.
• Newton and quasi-Newton — exploiting curvature, and doing so at a controlled cost.
• Constraints in machine learning — duality, projections and penalties to encode what the model must respect, and the minimax and saddle-point methods that solve the resulting games.
• Hyperparameter optimization — optimizing the level above: methods, costs and pitfalls.
• Optimizing the training of networks — the junction with practice: adaptive methods (AdaGrad, Adam) and what theory really illuminates in heavy training runs.
• Course research notes — CMAP (Chamon, Dieuleveut) — the instructors’ papers, read with the module’s tools.
• Exercises — proofs and implementations for each family of algorithms.
• Projects and assessment — solo and group project subjects, a written-exam proposal and a grading rubric.
• References — the theoretical sources of each chapter.

Session plan

36 h in class = 12 sessions of 3 h. The SynapseS 2026–2027 sheet displays no volume (and the volume column of the LLGA track page is empty for this unit), but the LLGA curriculum page of the programme wiki (msct.dix.polytechnique.fr/llga, last modified on 9 September 2026 by the programme director) states that “all subsequent M1 courses are 36h and will credit 4.5 ECTS”; since no session-by-session programme is published, the split below is our proposal for covering these notes in that time.

Level 1 = foundations (reviews, definitions, first worked examples), 2 = core theorems and algorithms, 3 = advanced or open questions; the level never goes down from one session to the next.

Self-study, outside the 36 h (about 3 h in total): ch. 11 Course research notes — CMAP (Chamon, Dieuleveut) (≈ 3 h, with the two cross-cutting readings it proposes).

How to study this module

• Redo every proof on the board, without the notes: convergence rates are the heart of the exam as of the module.
• Never separate an algorithm from its assumptions: convexity, L-Lipschitz continuity and strong convexity change everything.
• Implement each method on simple problems where the exact solution is known, and check the observed rates against the proven rates.
• Keep chapter 0 at hand: convexity and duality return at every turn.
• Connect every result to the P1 machine learning module: regularization, SVM and regression become concrete examples.
• Prepare the exercises in a small group, but write the proofs alone: it is the writing that reveals the gaps.

Notation

The page follows the site-wide notation conventions:

• the step (learning rate) is \eta in every chapter, deterministic or stochastic;
• a momentum coefficient is \beta, and Nesterov’s is \beta_k;
• L is a smoothness constant, \mu a strong-convexity constant and \kappa = L/\mu;
• a loss is written \ell(\hat y, y), prediction first.

Deviations, as in optimization textbooks.

• From chapter 2 on, the variable of an algorithm is written x: it is the parameter \theta of definition 1.1, never a data point. In chapters 5–6, data enter only through the per-sample losses f_i, with f = \frac{1}{n}\sum_i f_i.
• Where chapter 8 writes a learning problem with its data (definition 8.1, adversarial training, the SVM of example 8.5), the parameter is again \theta (or w) and x_i is an input.
• In the FISTA proof (chapter 4), t_k is the momentum sequence of Beck and Teboulle, not a step.
• With a sample index, y_i is the label of sample i. Otherwise y is an auxiliary vector: a comparison point in proofs, the look-ahead point y_k of Nesterov and FISTA (chapters 3–4), the gradient difference of BFGS (chapter 7), or the maximizing player of a game (chapter 8).
• The Lagrangian \mathcal{L}(x, \lambda) is minimized in x and maximized in \lambda.

0. Refresher: convexity and duality

1. Optimization inside the AI loop

A fine-tuning run that “stops descending” while the gradient is not zero is usually a problem of conditioning, not a bug. Before any algorithm, this chapter writes training as an optimization problem, fixes the vocabulary, and collects the examples on which every later method is tested.

The practitioner’s main enemy is conditioning; the main ally is structure (convexity, separability, sparsity).

2. Gradient descent: convergence proved

This chapter answers the first question of the module: under which assumptions does gradient descent converge, and how fast? The algorithm is the most widely used one in machine learning:

x_{k+1} = x_k - \eta\, \nabla f(x_k), \qquad \eta > 0 \text{ the step (learning rate).}

import numpy as np

def gradient_descent(grad, x0, step, n_iter=200):
    x, traj = x0.copy(), [x0.copy()]
    for _ in range(n_iter):
        x = x - step * grad(x)
        traj.append(x.copy())
    return np.array(traj)

kappa = 200.0
A = np.diag([1.0, kappa])          # L = kappa, mu = 1, condition number = kappa
grad = lambda x: A @ x
x0 = np.array([9.0, 0.0])          # start on the flat axis: the worst case
traj = gradient_descent(grad, x0, step=1.0/kappa)
err = 0.5 * np.sum(traj**2 * np.array([1.0, kappa]), axis=1)
print(err[-1] / err[0])   # (1 - 1/kappa)**400 ~ 0.135: slow!
# optimal step for a quadratic: 2/(mu + L)
traj_opt = gradient_descent(grad, x0, step=2.0/(1.0+kappa))
err_opt = 0.5 * np.sum(traj_opt**2 * np.array([1.0, kappa]), axis=1)
print(err_opt[-1] / err_opt[0])    # ((kappa-1)/(kappa+1))**400 ~ 0.018: better
# from (9, 9) instead, step 1/L kills the steep coordinate (which carries
# almost all of the initial error) in one step: the ratio then looks tiny
# (~7e-4) although the flat coordinate is just as slow

3. Conditioning and Nesterov acceleration

Gradient descent pays a factor \kappa in iterations; this chapter asks whether another first-order method can pay less. Can we go faster without second-order information (no Hessian)? Nesterov’s answer (1983): yes, by a factor \sqrt{\kappa} — and this is optimal: no first-order algorithm can do better on the class of smooth convex functions. This is one of the rare results of the discipline where optimality is known and achieved by a usable algorithm.

4. Proximal methods: ISTA and FISTA

This chapter extends gradient descent to objectives with a non-differentiable part. Gradient descent requires a gradient — impossible for F = f + \lambda\|\theta\|_1 at the points where a coordinate is zero. The proximal trick: handle the smooth part with a gradient step, the non-smooth part with an explicit operation.

import numpy as np
rng = np.random.default_rng(0)
n, d, s = 60, 200, 8                       # underdetermined, sparse support
X = rng.normal(size=(n, d)); X /= np.sqrt(n)
theta_true = np.zeros(d); theta_true[:s] = rng.normal(size=s)
y = X @ theta_true + 0.05 * rng.normal(size=n)

L = np.linalg.norm(X, 2) ** 2              # Lipschitz constant of f = 0.5||Xt-y||^2
lam = 0.1 * np.linalg.norm(X.T @ y, np.inf)

def soft(v, t): return np.sign(v) * np.maximum(np.abs(v) - t, 0)

def ista(x, iters):
    for _ in range(iters):
        x = soft(x - (1/L) * X.T @ (X @ x - y), lam/L)
    return x

def fista(x, iters):
    z, t = x.copy(), 1.0
    for k in range(1, iters+1):
        xn = soft(z - (1/L) * X.T @ (X @ z - y), lam/L)
        t_next = (1 + np.sqrt(1 + 4*t*t)) / 2
        z = xn + ((t-1)/t_next) * (xn - x)   # Nesterov momentum
        x, t = xn, t_next
    return x

F = lambda th: 0.5*np.sum((X@th - y)**2) + lam*np.abs(th).sum()
x0 = np.zeros(d)
F_ref = F(fista(x0.copy(), 5000))          # reference optimal value
for it in (20, 100):
    print(it, "ISTA gap:", F(ista(x0.copy(), it)) - F_ref,
              "FISTA gap:", F(fista(x0.copy(), it)) - F_ref)
# observed: FISTA's gap is ~50x smaller at 20 iterations, ~270x at 100;
# by 1000 iterations both reach machine precision

Non-smooth objectives without a prox: the subgradient method

The proximal methods above need g to have a computable prox. When the whole objective is non-smooth and has no easy prox — a hinge loss summed over many points, a maximum of many affine functions — the only first-order information left is a subgradient (definition 1.2). The subgradient method simply follows it: x_{k+1} = x_k - \eta_k v_k \quad \text{with} \quad v_k \in \partial F(x_k). It is not a descent method, since a subgradient step can increase F, so the analysis tracks the distance to the solution instead of the function value.

5. Stochastic gradient descent

This chapter analyses what happens when the gradient is replaced by a cheap, noisy estimate. When n = 10^9, computing \nabla f costs 10^9 evaluations — per iteration. The founding gesture of modern learning (Robbins–Monro, 1951): accept a noisy but cheap gradient.

import numpy as np
rng = np.random.default_rng(1)
n, d = 20_000, 50
X = rng.normal(size=(n, d)) / np.sqrt(d)
y = (X @ rng.normal(size=d) + 0.3*rng.normal(size=n) > 0).astype(float)  # labels in {0, 1}

def sgd_logreg(eta, epochs=20, b=32):
    w = np.zeros(d); losses = []
    sig = lambda z: 1/(1+np.exp(-z))
    for ep in range(epochs):
        idx = rng.permutation(n)
        for s in range(0, n, b):
            B = idx[s:s+b]
            p = sig(X[B] @ w)
            g = X[B].T @ (p - y[B]) / b      # mini-batch gradient
            w = w - eta * g
        losses.append(np.mean(np.logaddexp(0, -(2*y-1)*(X@w))))  # full training risk
    return losses

# here L ~ 0.005 (features scaled by 1/sqrt(d)): all three steps are below 1/L
for eta in (0.1, 1.0, 100.0):
    print(eta, "->", sgd_logreg(eta)[-1])
# observed (optimal risk 0.200): 0.255 (too small, still descending),
# 0.201 (near the optimum), 0.26 (noisy plateau: the eta*sigma^2 term)

SGD without convexity: approximate stationary points

Neural network losses are not convex, so the convex rates above do not apply to them. What remains provable is weaker but useful: SGD finds a point where the gradient is small. The inequality of theorem 5.2 never used convexity — only L-smoothness, unbiasedness and bounded variance — so it can be summed directly.

6. Variance reduction: SAGA and SVRG

This chapter removes the plateau of constant-step SGD without paying a full gradient at every step. Between the “complete but expensive” and the “stochastic but noisy” gradient, a third way: keep memory of past gradients to build an unbiased estimator whose variance vanishes by itself.

7. Newton and quasi-Newton

First-order methods pay for the condition number \kappa; this chapter buys second-order information (the Hessian) to remove it. The reward is quadratic local convergence — the number of correct digits doubles at every iteration — and the price is the cost of each iteration.

8. Constraints in machine learning

This chapter shows how to train a model that must satisfy requirements, not only minimize an average loss. A real specification reads “error rate \leq 5\,\% and demographic disparity \leq \delta and latency \leq 100 ms”. The average loss alone cannot express such requirements; constraints are needed — and hence the duality of ch. 0, applied.

Minimax optimization and saddle-point methods

The Lagrangian of definition 8.1 turns a constrained problem into a game: the learner minimizes over \theta while the multiplier maximizes over \lambda \geq 0. The same min–max structure appears elsewhere in AI: generative adversarial networks (\min over the generator, \max over the discriminator) and adversarial training: \min_\theta \mathbb{E}\max_{\|\delta\| \leq \epsilon}\ell(h_\theta(x + \delta), y). This section studies the algorithms for such problems and shows that they need more care than plain gradient descent.

9. Hyperparameter optimization

This chapter optimizes the quantities that the previous chapters took as given. The step \eta, the penalty \lambda, the batch size, the learning rate schedule: so many hyperparameters that the module has so far treated as given. Yet experience shows they are often worth more performance points than the choice of algorithm itself. The task is to optimize the optimizer itself.

import numpy as np
rng = np.random.default_rng(0)
def train_score(lr, lam, epochs=30):          # proxy: linear reg model
    # ... real training replaced by a rugged function
    peak = 0.92 - 0.4*np.abs(np.log10(lr) + 1.5) - 0.15*np.log10(1+lam)
    return peak + 0.02*np.sin(10*lr) + 0.01*rng.standard_normal()

best_grid = max(train_score(10**e, 10**-l)
                for e in np.linspace(-4, -1, 8) for l in np.linspace(0, 3, 8))
best_rand = max(train_score(10**rng.uniform(-4, -1), 10**-rng.uniform(0, 3))
                for _ in range(64))           # same budget: 64 trials
print("grid:", round(best_grid, 4), "random:", round(best_rand, 4))
# on this type of landscape (few sensitive parameters), random almost always wins

10. Optimizing the training of networks

This chapter confronts the module with its main application. Almost everything so far assumed convexity, and training a network is not convex. Yet the recipes of deep learning are literally the objects of the previous chapters, transplanted — with adaptations that non-convexity demands.

Adaptive methods: AdaGrad, and what Adam changes

Recall 10.1 presented Adam as a recipe. Its theoretical ancestor is AdaGrad, for which a clean guarantee exists, and comparing the two shows what is gained and what is lost when the step adapts to the observed gradients.

Lab: diagnosing a diverging run

The reflex sheet above, tested on a small network. The code below trains a one-hidden-layer tanh network by full-batch gradient descent. It also measures the sharpness, the largest eigenvalue of the Hessian, by power iteration on gradient differences, without ever forming the Hessian.

import numpy as np
rng = np.random.default_rng(0)
n, d, h = 512, 10, 32                       # one-hidden-layer tanh network
X = rng.normal(size=(n, d))
y = np.tanh(X @ rng.normal(size=d) / 2)[:, None] + 0.1 * rng.normal(size=(n, 1))

def init():
    r = np.random.default_rng(1)
    return [r.normal(size=(d, h)) / np.sqrt(d), r.normal(size=(h, 1)) / np.sqrt(h)]

def loss_grad(P):
    W1, W2 = P
    H = np.tanh(X @ W1); err = H @ W2 - y
    g1 = X.T @ ((err @ W2.T) * (1 - H**2)) / n
    return 0.5 * np.mean(err**2), [g1, H.T @ err / n]

def sharpness(P, iters=50, eps=1e-4):
    """top Hessian eigenvalue by power iteration on gradient differences"""
    v = [np.random.default_rng(2).normal(size=p.shape) for p in P]
    g0 = loss_grad(P)[1]
    for _ in range(iters):
        nv = np.sqrt(sum((a**2).sum() for a in v)); v = [a / nv for a in v]
        g = loss_grad([p + eps * a for p, a in zip(P, v)])[1]
        Hv = [(a - b) / eps for a, b in zip(g, g0)]
        lam = sum((a * b).sum() for a, b in zip(Hv, v)); v = Hv
    return lam

def train(eta, steps=500, clip=None, warmup=0):
    P = init()
    for k in range(steps):
        loss, g = loss_grad(P)
        if not loss < 1e3:
            return f"diverged at step {k}"
        gn = np.sqrt(sum((a**2).sum() for a in g))
        if clip and gn > clip:                 # clipping = projection onto a ball (ch. 8)
            g = [a * clip / gn for a in g]
        lr = eta * min(1.0, (k + 1) / warmup) if warmup else eta
        P = [p - lr * a for p, a in zip(P, g)]
    return f"loss {loss:.4f}, sharpness {sharpness(P):.2f}"

print("threshold 2/sharpness at init:", round(2 / sharpness(init()), 2))   # 0.74
for eta in (0.5, 1.0, 1.5, 2.0):
    print(eta, "plain:", train(eta), "| clip:", train(eta, clip=1.0),
          "| warmup:", train(eta, warmup=100))

11. Course research notes — CMAP (Chamon, Dieuleveut)

The module’s two instructors are among the players in optimization theory for learning. Three axes: learning under constraints (Chamon), acceleration and the fine behavior of SGD (Dieuleveut).

Exercises

1. ★ Valley. For f(u,v)=\tfrac12(u^2+\kappa v^2), \kappa = 100, x_0 = (10, 1): compute the first three iterates of descent at step 1/L, plot the trajectory, and verify that the steep direction is canceled in one step while the flat direction decreases by 1 - 1/\kappa per step.

   Solution: \nabla f = (u, \kappa v), hence (10, 1) \to (9.9,\, 0) \to (9.801,\, 0) \to (9.703,\, 0) — v_1 = 0 but u_k = 10\,(1-1/\kappa)^k; to compare with Nesterov (\beta = \tfrac{1-1/\sqrt\kappa}{1+1/\sqrt\kappa}) which reaches the target accuracy in \sqrt\kappa steps.

2. ★ ISTA/FISTA in practice. Take up the code of ch. 4: plot F(x_k)-F(x^\star) (reference: 5,000 FISTA iterations, as in the code) on a log scale for ISTA, FISTA and FISTA+adaptive restart (reset the momentum to zero when F(x_{k+1}) > F(x_k)). Measure the experimental slopes and compare with 1/k and 1/k^2.

   Expected: FISTA+restart beats FISTA as soon as the solution is sparse (local strong convexity).

3. ★ Random search. Reproduce proposition 9.2: build a dummy function in d = 6 dimensions of which only p = 2 matter, compare a truncated exhaustive 8^6 grid at equal budget vs random draws, over 20 repetitions; plot the distribution of the best score.

   Then test skopt.gp_minimize (GP-EI) at small budget: when does it beat random?

4. ★★ Optimal step on a quadratic. Show that for f(x) = \tfrac12 x^\top A x with eigenvalues in [\mu, L], the constant step minimizing the contraction factor \rho(\eta) = \max_i |1 - \eta\lambda_i| equals \eta = 2/(\mu+L) and gives \rho = \frac{\kappa-1}{\kappa+1} — in x, hence \big(\tfrac{\kappa-1}{\kappa+1}\big)^2 on the values of f.

   Verify that this factor equals 1 - \frac{2}{\kappa+1} and conclude that descent cannot beat O(\kappa) on this class.

5. ★★ Soft thresholding. Prove the formula (use example 1.4) \mathrm{prox}_{\lambda|\cdot|}(z) = \mathrm{sign}(z)\max(|z|-\lambda, 0), then compute the \mathrm{prox} of the indicator of [a,b], of the \ell_2 ball, and of the probability simplex (algorithm of Duchi et al., 2008).

6. ★★ SGD neighborhood. Prove consequence 2 of theorem 5.2: at constant step \eta, under strong convexity, \limsup \mathbb{E}[f(x_k)] - f^\star \leq \frac{\eta L\sigma^2}{2\mu}.

   Hint: combine theorem 5.2 with the Polyak–Łojasiewicz inequality f - f^\star \leq \frac{1}{2\mu}\|\nabla f\|^2 to get \mathbb{E}[f(x_{k+1})] - f^\star \leq (1 - \eta\mu)\big(\mathbb{E}[f(x_k)] - f^\star\big) + \frac{\eta^2 L\sigma^2}{2}, then take the fixed point of this recursion. Check the bound against the exact computation of example 5.3. Simulate with the code of ch. 5, at its steps \eta \in \{0.1; 1; 100\}.

7. ★★ Minimum viable SAGA. Implement SAGA (table of n gradients) for \ell_2-regularized logistic regression, n = 1\,000, d = 50, \mu chosen so that \kappa = 100.

   Plot the variance of the estimator \|g_k - \nabla f(x_k)\|^2 along the iterations and compare it with that of SGD; verify the linear convergence of theorem 6.3 (slope in log).

   Pitfall: the average \bar\phi must be maintained incrementally, not recomputed.

8. ★★ Quadratic Newton. For f(x) = \frac{x^4}{4} (convex, f'(x) = x^3, f''(x) = 3x^2): show that x_{k+1} = x_k - \tfrac{x_k}{3} = \tfrac23 x_k , a linear convergence, not a quadratic one — which assumption of theorem 7.1 fails at x^\star = 0?

   Then show that for f(x)=\frac{x^2}{2}+e^{-x} (minimizer x^\star \approx 0.567, the solution of x = e^{-x}) the convergence is quadratic once the iterate is close to x^\star.

   Compare scipy.optimize.minimize (Newton-CG, BFGS, L-BFGS-B) on the smoothed LASSO of ch. 4 in d = 200: iteration count, time, final accuracy.

9. ★★ Constraints: penalty vs duality. Solve \min \tfrac12\|x\|^2 subject to Ax = b in two ways, then compare them.

   • 1. Quadratic penalty \tfrac{\rho}{2}\|Ax-b\|^2, \rho \to \infty.
   • 2. Uzawa \lambda_{k+1} = \lambda_k + \rho(Ax_{k+1}-b) with x_{k+1} minimizing the Lagrangian.
   • 3. Show that the penalized problem has Hessian I + \rho A^\top A, whose condition number is 1 + \rho\|A\|^2 when A has more columns than rows, while its violation \|Ax_\rho - b\| only decreases like O(1/\rho).
   • 4. Show that the dual function is concave with a \|A\|^2-Lipschitz gradient, so that Uzawa converges for 0 < \rho < 2/\|A\|^2 (example 8.4 is essentially the case A = 1, b = 1).

   Conclude on the superiority of the multiplier (which “remembers” the constraint) over the penalty (which forgets it).

Projects and assessment

The assessment tab (“Acquisition de l’UE”) of the SynapseS 2026–2027 sheet APM_52067_EP gives, in its section for the LLGA track, a single line: a “written final exam without calculator, one handwritten A4 sheet allowed and to be handed in with the exam” (our translation). That section shows no duration, resit rule, pass threshold or ECTS value; the sheet states resit rules only for other degrees. The unit’s grade format is a numerical mark out of 20. The exam proposal below keeps the stated format; its duration and questions are ours.

The projects are proposals of these notes, for practice or for a continuous-assessment part if the instructors choose to add one; they replace nothing on the sheet. They exercise objective O1 (ML and DL foundations) throughout and O7 (hands-on practice) in every subject, with O8 (trustworthy AI) and O4 (graphs) in group project 1 and O3 (large language models) in group project 2. Group project 1 rehearses, on a classifier, the stochastic primal–dual method that the optimization option of the end-of-year project Y1.3 applies to an exposure constraint on a ranking.

Solo projects

1. [Solo · ≈ 20 h] Rates in the wild. Do the proved rates predict what one measures, and where do the gaps come from?
   • Implement: in NumPy, gradient descent, Nesterov with adaptive restart, ISTA, FISTA, the subgradient method, SGD, SAGA and SVRG; L-BFGS from scipy.optimize. The instances are ridge regressions with \kappa \in \{10, 10^2, 10^4\}, set by rescaling the features, a LASSO, and an \ell_2-regularized logistic regression.
   • Data: synthetic Gaussian designs, and the a9a version of UCI Adult (Kohavi, 1996) in the LIBSVM collection: 32,561 samples, 123 binary features.
   • Deliverables: code with a test that each method decreases its objective, a 5-page report with one log-scale plot per theorem tested, a 10-minute talk.
   • Chapters: ch. 2–7.
   • Success: the iterations needed to divide the error by 10^6 grow like \kappa for gradient descent and like \sqrt{\kappa} for Nesterov (log-log slopes 1 and 1/2, within 10 %); the gaps of ISTA and FISTA stay below the bounds of theorem 4.4 at every iteration; each other deviation (local strong convexity, constants, noise floor) is explained by a named result.
2. [Solo · ≈ 20 h] Paper study: the non-convergence of Adam (Reddi, Kale & Kumar, ICLR 2018). When does an adaptive method fail on a convex problem, and does the fix matter in practice?
   • Paper: S. J. Reddi, S. Kale, S. Kumar, On the Convergence of Adam and Beyond, ICLR 2018.
   • Implement: AdaGrad (definition 10.3), RMSProp, Adam and AMSGrad from scratch. Reproduce the online counter-example of the paper’s theorem 1: on [-1, 1], a linear loss pays Cx once every three steps and -x otherwise, with C > 2, and Adam uses the theorem’s hyperparameters, \beta_1 = 0 and \beta_2 = 1/(1 + C^2). Then compare the four methods on the logistic regression of solo project 1 and on a small CNN trained on CIFAR-10 (Krizhevsky, 2009).
   • Deliverables: code, a 4-page report, a 10-minute talk.
   • Chapters: ch. 5, 10 (theorem 10.4, example 10.5).
   • Success: on the counter-example, Adam’s iterate goes to the worst point x = +1 while AdaGrad and AMSGrad reach the minimizer x = -1, with an average regret that vanishes only for them; a measured answer, over 3 seeds, on whether AMSGrad changes the test accuracy of the two real tasks.
3. [Solo · ≈ 20 h] Games that spiral: gradient descent–ascent versus extragradient. When does a saddle-point method converge, and should one output the last iterate or the average?
   • Implement: simultaneous and alternating GDA, extragradient and optimistic GDA on the bilinear game of example 8.7 (unconstrained, then restricted to [-1, 1]^2 by projection), on the Lagrangian game of example 8.4, and on a 2-D GAN fitting a mixture of 8 Gaussians on a circle.
   • Paper: G. Gidel, H. Berard, G. Vignoud, P. Vincent, S. Lacoste-Julien, A Variational Inequality Perspective on Generative Adversarial Networks, ICLR 2019. The student reproduces its bilinear experiment, then applies its extragradient and averaging methods to the mixture.
   • Deliverables: code, a 4-page report with phase portraits, a 10-minute talk.
   • Chapters: ch. 0, 8 (definition 8.6, example 8.7, proposition 8.8).
   • Success: the measured growth factors on the bilinear game match 1 + \eta^2 and 1 - \eta^2 + \eta^4 to three digits; on the box, the duality gap |\bar x_K| + |\bar y_K| of the averaged GDA iterate decays at least like 1/\sqrt{K} (proposition 8.8) while the last iterate keeps cycling; the number of modes each method covers, over 5 seeds.

Group projects

1. [Group of 3 · ≈ 30 h each] Fair classifiers by duality. Does a fairness constraint satisfied on the training set still hold on the test set, and which of penalty, Uzawa and stochastic primal–dual gets there best?
   • Implement: a classifier under a demographic-parity constraint, a gap of positive-prediction rates between two groups at most \delta (with a smooth surrogate of the rates), solved three ways (proposition 8.2): quadratic penalty, Uzawa with an exact inner minimization, and stochastic primal–dual with one SGD step per dual step.
   • Data: UCI Adult (sensitive attribute: sex) for logistic regression, and the Pokec-z social graph of Dai & Wang (WSDM 2021; sensitive attribute: region) for a GNN node classifier.
   • Paper: L. F. O. Chamon, A. Ribeiro, Probably Approximately Correct Constrained Learning, NeurIPS 2020 (ch. 11). The group measures the empirical duality gap and the train–test gap of the constraint that the paper bounds.
   • Split: member A the penalty and Uzawa solvers, with the duality-gap measurement; member B the stochastic primal–dual method and the train–test study; member C the GNN variant, built on Graph ML, ch. 5.
   • Deliverables: a repository, a 6-page report, a 15-minute talk.
   • Chapters: ch. 0, 5, 8, 11.
   • Success: a table of accuracy, train and test violation and empirical duality gap per method over 5 seeds; the multiplier \lambda^\star read as a price, the training loss saved per unit increase of \delta, and checked against a finite difference in \delta as in example 8.4.
2. [Group of 3 · ≈ 30 h each] Anatomy of a transformer training run. Which results of the module explain the plateaus, the divergences and the noise floor of a real training run?
   • Implement: a decoder-only transformer of about 10 M parameters, trained on TinyStories (Eldan & Li, 2023) at a fixed token budget on a free GPU tier, with SGD + momentum, AdaGrad, Adam and AdamW (recall 10.1). The sweeps cover warmup length and cosine decay, batch size with the linear scaling rule, and gradient clipping; the sharpness of example 10.6 is logged along training.
   • Split: member A the optimizers and the weight-decay study; member B the schedules, batch sizes and clipping; member C a hyperparameter search, random search against Hyperband (ch. 9) at equal compute.
   • Deliverables: a repository with tracked runs, a 6-page report, a 15-minute talk, and an evidence-backed version of the reflex sheet of ch. 10.
   • Chapters: ch. 3, 5, 9, 10. It builds on Deep Learning, ch. 3 and 6 and prepares the pre-training chapter of Large Language Models.
   • Success: every reflex of the sheet is backed by one run that triggers the problem and one that cures it; the loss noise floor shrinks when the step decays, as theorem 5.2 predicts; random search and Hyperband are compared over at least 3 seeds.

Written exam (proposal)

Format: as in the LLGA section of the sheet’s assessment tab, a written final exam without calculator, with one handwritten A4 sheet allowed and handed in with the copy; the duration is not displayed, and 2 hours are proposed. Four exercises, 20 points.

1. Question (5 points). Duality. (a) For \min f(x) subject to g_i(x) \leq 0, define the Lagrangian and the dual function, and prove weak duality. (b) State Slater’s condition and the KKT conditions. (c) For \min \tfrac12 x^2 subject to x \geq 1, compute the dual function and the optimal multiplier, and check the zero gap and complementary slackness.

   Expected:

   • (a) \mathcal{L} = f + \sum_i \lambda_i g_i and d(\lambda) = \inf_x \mathcal{L}(x, \lambda); for feasible x and \lambda \geq 0, \mathcal{L}(x, \lambda) \leq f(x), then take the infimum and the supremum (proposition 0.1) (2 points).
   • (b) A convex problem with a strictly feasible point has a zero gap and an attained dual (theorem 0.2); KKT: primal and dual feasibility, stationarity, complementary slackness (1.5 points).
   • (c) \mathcal{L} is minimized at x = \lambda, so the dual function is d(\lambda) = \lambda - \tfrac12\lambda^2, maximized at \lambda^\star = 1. Then d(\lambda^\star) = \tfrac12 = f(1): zero gap. The constraint is active at the solution, so complementary slackness holds with a positive multiplier (1.5 points).

2. Question (6 points). Take f(u, v) = \tfrac12(u^2 + 25 v^2). (a) Give the constants of smoothness and strong convexity, and the condition number. (b) Run two steps of gradient descent at step 1/L from (1, 1). (c) Which constant step minimizes the contraction factor of exercise 4, and what is the factor? (d) Give the momentum coefficient \beta of definition 3.2. (e) About how many iterations divide the error by e^{10}, for gradient descent (theorem 2.3) and for the accelerated scheme?

   Expected:

   • (a) L = 25, \mu = 1, \kappa = 25 (1 point).
   • (b) With \nabla f = (u, 25v), the iterates are (0.96, 0), then (0.9216, 0): the steep direction is gone after one step (1.5 points).
   • (c) \eta = 2/(\mu + L) = 1/13, with factor (\kappa - 1)/(\kappa + 1) = 12/13 on both eigen-directions (1.5 points).
   • (d) \beta = (1 - 1/5)/(1 + 1/5) = 2/3 (1 point).
   • (e) e^{-k/\kappa} \leq e^{-10} gives k = 250; with the factor 1 - 1/\sqrt{\kappa} \leq e^{-1/5}, k = 50 is enough (1 point).

3. Question (5 points). Let F be convex with subgradients bounded by G, x^\star a minimizer and R = \|x_0 - x^\star\|. Prove that the subgradient method at constant step \eta satisfies \min_{k < K} F(x_k) - F(x^\star) \leq \frac{R^2 + K\eta^2 G^2}{2\eta K}, choose \eta to get a 1/\sqrt{K} rate, and explain example 4.7.

   Expected:

   • Expand \|x_{k+1} - x^\star\|^2 and use the subgradient inequality, as in theorem 4.6 (2 points).
   • Telescope over k < K, drop the last distance, and bound the minimum by the average (1.5 points).
   • \eta = R/(G\sqrt{K}) gives RG/\sqrt{K} (1 point).
   • For a fixed step the bound tends to \eta G^2/2, here 0.15 for |x| with \eta = 0.3. The iterates of example 4.7 cycle at a minimum value of 0.1, under that floor, and never reach 0 (0.5 point).

4. Question (4 points). Take \mathcal{L}(x, y) = xy. (a) Give its saddle point. (b) Show that simultaneous GDA multiplies x^2 + y^2 by 1 + \eta^2. (c) Show that extragradient multiplies it by 1 - \eta^2 + \eta^4, and give the steps for which it converges. (d) What does averaging change for GDA?

   Expected:

   • (a) (0, 0), since \mathcal{L}(0, y) = 0 = \mathcal{L}(x, 0) (0.5 point).
   • (b) With x_{k+1} = x_k - \eta y_k and y_{k+1} = y_k + \eta x_k, the cross terms cancel (1 point).
   • (c) The update of example 8.7 gives (1 - \eta^2)^2 + \eta^2, which is below 1 exactly when 0 < \eta < 1 (1.5 points).
   • (d) On compact sets, with a step of order 1/\sqrt{K}, the averaged iterates reach a duality gap O(1/\sqrt{K}) (proposition 8.8), although the last iterate spirals out (1 point).

Grading rubric (proposal)

References

• Y. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, Kluwer, 2004 — the reference for ch. 2–3 (lower bounds, acceleration).
• S. Bubeck, Convex Optimization: Algorithms and Complexity, Foundations and Trends in ML, 2015 — the reference panorama, compact proofs.
• A. Beck, First-Order Methods in Optimization, SIAM, 2017 — the proximal treatise (ch. 4).
• A. Beck, M. Teboulle, A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems (FISTA), SIAM J. Imaging Sciences, 2009.
• I. Daubechies, M. Defrise, C. De Mol, An Iterative Thresholding Algorithm for Linear Inverse Problems with a Sparsity Constraint (ISTA), Comm. Pure Appl. Math., 2004.
• H. Robbins, S. Monro, A Stochastic Approximation Method, Annals of Mathematical Statistics, 1951 — the birth certificate of SGD.
• L. Bottou, F. E. Curtis, J. Nocedal, Optimization Methods for Large-Scale Machine Learning, SIAM Review, 2018 — the modern synthesis of ch. 5–6.
• R. Johnson, T. Zhang, Accelerating Stochastic Gradient Descent using Predictive Variance Reduction (SVRG), NeurIPS 2013.
• A. Defazio, F. Bach, S. Lacoste-Julien, SAGA: A Fast Incremental Gradient Method with Support for Non-Strongly Convex Composite Objectives, NeurIPS 2014.
• W. Su, S. Boyd, E. J. Candès, A Differential Equation for Modeling Nesterov’s Accelerated Gradient Method, JMLR, 2016 — the ODE of theorem 3.4.
• B. O’Donoghue, E. Candès, Adaptive Restart for Accelerated Gradient Schemes, Foundations of Computational Mathematics, 2015.
• J. Nocedal, S. Wright, Numerical Optimization, 2nd ed., Springer, 2006 — Newton, BFGS, L-BFGS (ch. 7).
• D. P. Kingma, J. Ba, Adam: A Method for Stochastic Optimization, ICLR 2015.
• J. Duchi, E. Hazan, Y. Singer, Adaptive Subgradient Methods for Online Learning and Stochastic Optimization (AdaGrad), JMLR, 2011.
• S. J. Reddi, S. Kale, S. Kumar, On the Convergence of Adam and Beyond (AMSGrad), ICLR 2018.
• J. Cohen, S. Kaur, Y. Li, J. Z. Kolter, A. Talwalkar, Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability, ICLR 2021 — the sharpness of example 10.6.
• I. Loshchilov, F. Hutter, Decoupled Weight Decay Regularization (AdamW), ICLR 2019.
• Z. You, I. Gitman, B. Ginsburg, Large Batch Training of Convolutional Networks (LARS), 2017.
• J. Bergstra, Y. Bengio, Random Search for Hyper-Parameter Optimization, JMLR, 2012.
• B. Shahriari et al., Taking the Human Out of the Loop: A Review of Bayesian Optimization, Proceedings of the IEEE, 2016.
• K. Li et al., Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization, ICLR 2017.
• G. Gidel, H. Berard, G. Vignoud, P. Vincent, S. Lacoste-Julien, A Variational Inequality Perspective on Generative Adversarial Networks, ICLR 2019 — extragradient for games (ch. 8).
• Research group (CMAP, École Polytechnique): L. F. O. Chamon, A. Ribeiro, Probably Approximately Correct Constrained Learning, NeurIPS 2020; L. F. O. Chamon, S. Paternain, M. Calvo-Fullana, A. Ribeiro, The empirical duality gap of constrained statistical learning, 2020; S. Paternain, L. Chamon, M. Calvo-Fullana, A. Ribeiro, Constrained Reinforcement Learning Has Zero Duality Gap, NeurIPS 2019; A. Dieuleveut, N. Flammarion, F. Bach, Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression, ICML 2017; A. Dieuleveut, A. Durmus, F. Bach, Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains, Annals of Statistics, 2020.
• SciPy (L-BFGS, Newton-CG) and scikit-optimize (GP-EI) — the tools of the labs.