



op·ti·mi·za·tion
/ˌäptəməˈzāSHən,ˌäptəˌmīˈzāSHən/ · noun
optimization / optimisation · plural: optimizations / optimisations
The action of making the best or most effective use of a situation or resource.
Google Dictionary · definition reproduced from the original slide
op·ti·mi·za·tion
/ˌäptəməˈzāSHən,ˌäptəˌmīˈzāSHən/ · noun
optimization / optimisation · plural: optimizations / optimisations
The action of making the best or most effective use of a situation or resource.
Google Dictionary · definition reproduced from the original slide
Mathematical optimization
Mathematical optimization or mathematical programming is the selection of a best element from some set of available alternatives.
Wikipedia · definition reproduced from the original slide
Mathematical optimization (alternatively spelled optimisation) or mathematical programming is the selection of a best element (with regard to some criterion) from some set of available alternatives.[1]
Optimization problems of sorts arise in all quantitative disciplines from computer science and engineering to operations research and economics, and the development of solution methods has been of interest in mathematics for centuries.[2]
Wikipedia · original excerpt
[1] The Nature of Mathematical Programming. Mathematical Programming Glossary, INFORMS Computing Society.
[2] Du, Pardalos & Wu (2008), History of Optimization. Encyclopedia of Optimization, pp. 1538–1542.
Choose feasible decisions to make a specified objective as good as possible.
In practice: find a good solution within the available time, evaluations and memory.



1.
2. Neighbourhoods/similarity defined by a distance
3. A black-box function
1.
2. Neighbourhoods/similarity defined by a distance
3. A black-box function
Topographic description:
1.
2. Neighbourhoods/similarity defined by a distance
3. A black-box function
Topographic description:
1.
2. Neighbourhoods/similarity defined by a distance
3. A black-box function
Topographic description:
Visualizing the Loss Landscape of Neural Nets
ResNet-56 loss surfaces with and without skip connections. The source uses filter normalization to compare sharpness/flatness in the two figures.
Wu, Zhu & E · 2017
Wu, Zhu & E · 2017
Fort & Jastrzębski · 2019
Wu, Zhu & E · 2017
Fort & Jastrzębski · 2019
Li, Xu, Taylor, Studer & Goldstein · 2018
Wu, Zhu & E · 2017
Fort & Jastrzębski · 2019
Li, Xu, Taylor, Studer & Goldstein · 2018
Venturi, Bandeira & Bruna · 2019
Visualizing the Loss Landscape of Neural Nets
ResNet-56 loss surfaces with and without skip connections. The source uses filter normalization to compare sharpness/flatness in the two figures.
Philip A. Romero, Andreas Krause & Frances H. Arnold · 2013
Enzyme to be optimized

Network representation
and distance definition

Measured fitness
modeled as a GP

Philip A. Romero, Andreas Krause & Frances H. Arnold · 2013
Enzyme to be optimized

Network representation
and distance definition

Measured fitness
modeled as a GP

Philip A. Romero, Andreas Krause & Frances H. Arnold · 2013
Enzyme to be optimized

Network representation
and distance definition

Measured fitness
modeled as a GP

Philip A. Romero, Andreas Krause & Frances H. Arnold · 2013
Enzyme to be optimized

Network representation
and distance definition

Measured fitness
modeled as a GP

Philip A. Romero, Andreas Krause & Frances H. Arnold · 2013
Enzyme to be optimized

Network representation
and distance definition

Measured fitness
modeled as a GP

Philip A. Romero, Andreas Krause & Frances H. Arnold · 2013
Enzyme to be optimized

Network representation
and distance definition

Measured fitness
modeled as a GP

Philip A. Romero, Andreas Krause & Frances H. Arnold · 2013
Enzyme to be optimized

Network representation
and distance definition

Measured fitness
modeled as a GP

The entire field of evolutionary computation, a subfield of continuous optimization, is based on this idea (>100k publications).
Keywords: Genetic algorithms, genetic programs, Evolution Strategies
The transition process from gas to liquid to solid can be seen as an optimization process.
The transition process from gas to liquid to solid can be seen as an optimization process.
Ingredients:
The transition process from gas to liquid to solid can be seen as an optimization process.
Ingredients:
David J. Wales & Jonathan P. K. Doye · 1997
David J. Wales & Jonathan P. K. Doye · 1997
Ingredients:
David J. Wales & Jonathan P. K. Doye · 1997
Ingredients:

Solid: original energy. Dashed: energy after local minimization.


Build a single-funnel energy landscape approximation
Gradient descent on landscape
Group Q&A
Optimization Landscapes



















Question: how would you spend
First choose the information you can afford: dimension, cost per evaluation, budget and noise.




When and why is this design useful?
What are the underlying assumptions on \(f(\mathbf x)\)?



Random Search for Hyper-Parameter Optimization
James Bergstra & Yoshua Bengio
JMLR · 2012
19,624 citations · Google Scholar
Count checked 18 November 2026
Jones, Perttunen & Stuckman · 1993
Jones, Schonlau & Welch · 1998
Only the black-dot function values are available to the algorithm. The colors show the illustrative landscape.
Question: Which boxes deserve the next evaluations?
A low center value is promising; a large box still leaves room for improvement.

Useful tutorial: Distill: Bayesian optimization

Useful tutorial: Distill: Bayesian optimization
Snoek, Larochelle & Adams · 2012
Deterministic observations
GP surrogate prediction:
Expected improvement
Minimize the loss; maximize the acquisition.
Fit → acquire → evaluate → update.
Deterministic observations
GP surrogate prediction:
Expected improvement
Minimize the loss; maximize the acquisition.
Fit → acquire → evaluate → update.
Deterministic observations
GP surrogate prediction:
Expected improvement
Minimize the loss; maximize the acquisition.
Fit → acquire → evaluate → update.
Use (uniform) samples in the landscape domain and estimate topographical features of the landscape.
Use (uniform) samples in the landscape domain and estimate topographical features of the landscape.
Use (uniform) samples in the landscape domain and estimate topographical features of the landscape.
Use (uniform) samples in the landscape domain and estimate topographical features of the landscape.
Fitness-distance correlation
Fitness-distance correlation
Function dispersion
Fitness-distance correlation
Function dispersion
Separability/interaction
Fitness-distance correlation
Function dispersion
Separability/interaction
Landscape ruggedness
How would you construct an iterative optimization scheme?
You can evaluate
How should earlier evaluations influence the next samples?
How would you construct an iterative optimization scheme?
You can evaluate
How should earlier evaluations influence the next samples?
One possible iterative scheme
1. Sample and evaluate
Maintain a search state
One possible iterative scheme
1. Sample and evaluate
Maintain a search state
2. Select
Compare the evaluated candidates. Keep useful candidates or rank them:
For example: accept an improving candidate, or select several highly ranked candidates.
One possible iterative scheme
1. Sample and evaluate
Maintain a search state
2. Select
Compare the evaluated candidates. Keep useful candidates or rank them:
For example: accept an improving candidate, or select several highly ranked candidates.
3. Update the search
Use the observations and selection to update
Move the search center? Change the sampling radius? Learn promising directions?
One possible iterative scheme
1. Sample and evaluate
Maintain a search state
2. Select
Compare the evaluated candidates. Keep useful candidates or rank them:
For example: accept an improving candidate, or select several highly ranked candidates.
3. Update the search
Use the observations and selection to update
Move the search center? Change the sampling radius? Learn promising directions?
4. Repeat within the budget
Repeat while evaluations remain. Retain the best evaluated point and its value.
What properties should our iterative scheme have?
These are design goals. Their guarantees depend on the particular algorithm.
How can successful samples change the next search?
These are random search directions learned from function values; derivatives are not required.
Gaussian adaptation (GaA): learn a Gaussian search region from accepted candidates.
Gaussian adaptation (GaA): learn a Gaussian search region from accepted candidates.
Acceptance region
Gaussian adaptation (GaA): learn a Gaussian search region from accepted candidates.
Acceptance region
Accepted candidate: learn from its direction
Accepted candidate: learn from its direction
Rejected candidate: reduce the search scale
Accepted candidate: learn from its direction
Rejected candidate: reduce the search scale
Why does this follow the landscape? Directions that repeatedly produce acceptable losses influence the Gaussian’s orientation and spread.
The threshold and scale control how selective the search is. Detailed updates and parameter choices remain in the reference slides.
Sample
Sample
Evaluate and rank by increasing loss.
Sample
Evaluate and rank by increasing loss.
Move the mean toward the best
Sample
Evaluate and rank by increasing loss.
Move the mean toward the best
Learn directions: covariance adaptation uses successful displacements and their accumulated history.
Sample
Evaluate and rank by increasing loss.
Move the mean toward the best
Learn directions: covariance adaptation uses successful displacements and their accumulated history.
Adapt scale:
GaA: one candidate and an acceptance threshold. CMA-ES: a ranked population and weighted recombination. Neither needs gradients.

Explore more than one basin.
Parallel runs can reduce wall-clock time when resources are available. They still consume evaluations.

Explore more than one basin.
Parallel runs can reduce wall-clock time when resources are available. They still consume evaluations.

A black-box evaluation trains a network and returns its validation error.

Search coordinates are transformed into training hyperparameters.
Logarithmic scales span orders of magnitude. Adam and Adadelta rows are alternatives.



Higher reward and lower KL divergence are better.
Blue: ES Pareto front; black: GRPO Pareto front.
Gradient: local slope
\(-\nabla f(\mathbf x)\): steepest local decrease.
\(f(\mathbf x+\mathbf s)\approx f(\mathbf x)+\nabla f(\mathbf x)^\top\mathbf s+\tfrac12\mathbf s^\top\mathbf H(\mathbf x)\mathbf s.\)
Gradient: local slope
\(-\nabla f(\mathbf x)\): steepest local decrease.
\(f(\mathbf x+\mathbf s)\approx f(\mathbf x)+\nabla f(\mathbf x)^\top\mathbf s+\tfrac12\mathbf s^\top\mathbf H(\mathbf x)\mathbf s.\)
Gradient: local slope
\(-\nabla f(\mathbf x)\): steepest local decrease.
\(f(\mathbf x+\mathbf s)\approx f(\mathbf x)+\nabla f(\mathbf x)^\top\mathbf s+\tfrac12\mathbf s^\top\mathbf H(\mathbf x)\mathbf s.\)
Gradient: local slope
\(-\nabla f(\mathbf x)\): steepest local decrease.
\(f(\mathbf x+\mathbf s)\approx f(\mathbf x)+\nabla f(\mathbf x)^\top\mathbf s+\tfrac12\mathbf s^\top\mathbf H(\mathbf x)\mathbf s.\)
Hessian: local curvature
Eigenvectors: principal directions.
Eigenvalues: curvature in these directions.
\(f(\mathbf x+\mathbf s)\approx f(\mathbf x)+\nabla f(\mathbf x)^\top\mathbf s+\tfrac12\mathbf s^\top\mathbf H(\mathbf x)\mathbf s.\)
Goal: find \(\mathbf x\in\mathbb R^p\) such that \(f(\mathbf x)-f^\star\le\varepsilon\).
Here \(f^\star=\inf_{\mathbf x} f(\mathbf x)\), and \(\varepsilon>0\) is the desired accuracy.
Iterative algorithm: start from \(\mathbf x_0\) and update
\(\mathbf x_{t+1}=\mathbf x_t-\eta_t\nabla f(\mathbf x_t).\)
For \(t=0,1,\ldots\), with step size \(\eta_t>0\).
Goal: find \(\mathbf x\in\mathbb R^p\) such that \(f(\mathbf x)-f^\star\le\varepsilon\).
Here \(f^\star=\inf_{\mathbf x} f(\mathbf x)\), and \(\varepsilon>0\) is the desired accuracy.
Iterative algorithm: start from \(\mathbf x_0\) and update
\(\mathbf x_{t+1}=\mathbf x_t-\eta_t\nabla f(\mathbf x_t).\)
For \(t=0,1,\ldots\), with step size \(\eta_t>0\).
Goal: find \(\mathbf x\in\mathbb R^p\) such that \(f(\mathbf x)-f^\star\le\varepsilon\).
Here \(f^\star=\inf_{\mathbf x} f(\mathbf x)\), and \(\varepsilon>0\) is the desired accuracy.
Iterative algorithm: start from \(\mathbf x_0\) and update
\(\mathbf x_{t+1}=\mathbf x_t-\eta_t\nabla f(\mathbf x_t).\)
For \(t=0,1,\ldots\), with step size \(\eta_t>0\).
Newton–Raphson in one dimension
Goal: find a zero of a differentiable scalar function
The tangent intercept gives the next iterate; require a nonzero denominator.
Newton–Raphson in one dimension
Goal: find a zero of a differentiable scalar function
The tangent intercept gives the next iterate; require a nonzero denominator.
To minimize
Apply Newton’s root-finding step to
A zero of
In several dimensions: solve
Nonzero curvature is required for the scalar step. Damping and curvature safeguards are needed for reliable minimization.
Find a zero of the gradient using local curvature.
Linearize the gradient and set it to zero:
Next: compare this curvature-scaled step with gradient descent.
Find a zero of the gradient using local curvature.
Linearize the gradient and set it to zero:
Next: compare this curvature-scaled step with gradient descent.

Can we learn curvature from gradients alone?
A dense Hessian costs
What information do two successive gradients give us?
Approximate Newton–Raphson in one dimension
Replace the derivative by the finite difference
to obtain the secant method
Two distinct previous points and a nonzero function difference are required.
A derivative-free root solver becomes a second-derivative-free optimization method by applying it to
First derivatives are still required. The method approximates curvature from changes in the gradient.
Can we generalize this to
In one dimension, approximate curvature from two gradients:
In several dimensions, define the secant pair
The Hessian approximation must satisfy
At the current step, solve
Newton uses
Positive-definite updates and line-search conditions provide descent safeguards.
Write
All denominators must be nonzero. BFGS preserves positive definiteness under the curvature condition
Write
All denominators must be nonzero. BFGS preserves positive definiteness under the curvature condition
Search direction: \(\mathbf d_t=-\mathbf A_t\mathbf g_t\).
Storage and direction computation: \(O(mp)\).
Low-rank correction; generally full-rank \(\mathbf A_t\).
Curvature information from gradient differences.
Limited storage of the most recent correction pairs.
| Problem | Newton / Newton-type | BFGS | L-BFGS |
|---|---|---|---|
| Likelihood fitting | Logistic regression: likelihood Hessian or score equations. | Smooth likelihoods with available gradients and costly Hessians. | Many coefficients; retain a short history of gradient differences. |
| Scientific parameter estimation | Model calibration with reliable second derivatives; Gauss–Newton for least squares. | Fit ODE or physical-model parameters without second derivatives. | Large inverse problems using adjoint gradients. |
| Molecular energy minimization | Refine structures near minima using energy curvature. | Learn curvature from energies and forces. | Relax large molecular systems with limited memory. |
Newton also solves nonlinear equilibrium and discretized PDE equations, using the residual Jacobian rather than an objective Hessian.
Choose using derivative access, dimension and memory. For nonconvex objectives these are local methods; safeguards matter.
David J. Wales & Jonathan P. K. Doye · 1997
David J. Wales & Jonathan P. K. Doye · 1997
Ingredients:
David J. Wales & Jonathan P. K. Doye · 1997
Ingredients:

Solid: original energy. Dashed: energy after local minimization.
Ingredients:
Goal: \(f(\mathbf x)-f^\star\le\varepsilon\).
How should we choose the step sizes
for different classes of functions?
Convex with bounded gradients → smooth and convex → strongly convex
Which step sizes give progress, and how quickly?
Goal: \(f(\mathbf x)-f^\star\le\varepsilon\).
How should we choose the step sizes
for different classes of functions?
Convex with bounded gradients → smooth and convex → strongly convex
Which step sizes give progress, and how quickly?
Goal: \(f(\mathbf x)-f^\star\le\varepsilon\).
How should we choose the step sizes
for different classes of functions?
Convex with bounded gradients → smooth and convex → strongly convex
Which step sizes give progress, and how quickly?
Goal: \(f(\mathbf x)-f^\star\le\varepsilon\).
How should we choose the step sizes
for different classes of functions?
Convex with bounded gradients → smooth and convex → strongly convex
Which step sizes give progress, and how quickly?
What properties of a function make optimization easier?
A convex optimization problem has the standard form
A convex optimization problem has the standard form
A set
A function is convex if
A convex optimization problem has the standard form
A set
A function is convex if
Convex set
Convex function
A convex optimization problem has the standard form
A set
A function is convex if
Every local minimizer is a global minimizer.
Convex set
Convex function
For differentiable
The gradient is a column vector:
Proof direction: apply convexity to
Can we use convexity and additional properties of the functions to derive (at least theoretically) how to set the step size?
Can we use convexity and additional properties of the functions to derive (at least theoretically) how to set the step size?
Yes
Fix a convex differentiable function with a minimizer \(\mathbf x^\star\).
Track two quantities throughout:
We want to bound the objective error: \(e_t=f(\mathbf x_t)-f^\star\le\varepsilon\), for a given accuracy \(\varepsilon>0\).
Let \(R^2=D_0\).
Depending on the assumptions about the function, we will be able to bound the error and the distances in different ways.

Convex, differentiable \(f,\) with minimizer \(\mathbf x^\star\).
Squared-norm expansion:
\[\|\mathbf a-\mathbf b\|_2^2=\|\mathbf a\|_2^2-2\mathbf a^\top\mathbf b+\|\mathbf b\|_2^2.\]Use \(\mathbf a=\mathbf x_t-\mathbf x^\star\) and \(\mathbf b=\eta\mathbf g_t\).
First-order condition for convexity:
\[f(\mathbf x^\star)\ge f(\mathbf x_t)+\mathbf g_t^\top(\mathbf x^\star-\mathbf x_t)\quad\Longrightarrow\quad e_t\le\mathbf g_t^\top(\mathbf x_t-\mathbf x^\star).\]
Convex, differentiable \(f,\) with minimizer \(\mathbf x^\star\).
Squared-norm expansion:
\[\|\mathbf a-\mathbf b\|_2^2=\|\mathbf a\|_2^2-2\mathbf a^\top\mathbf b+\|\mathbf b\|_2^2.\]Use \(\mathbf a=\mathbf x_t-\mathbf x^\star\) and \(\mathbf b=\eta\mathbf g_t\).
First-order condition for convexity:
\[f(\mathbf x^\star)\ge f(\mathbf x_t)+\mathbf g_t^\top(\mathbf x^\star-\mathbf x_t)\quad\Longrightarrow\quad e_t\le\mathbf g_t^\top(\mathbf x_t-\mathbf x^\star).\]
Convex, differentiable \(f,\) with minimizer \(\mathbf x^\star\).
Squared-norm expansion:
\[\|\mathbf a-\mathbf b\|_2^2=\|\mathbf a\|_2^2-2\mathbf a^\top\mathbf b+\|\mathbf b\|_2^2.\]Use \(\mathbf a=\mathbf x_t-\mathbf x^\star\) and \(\mathbf b=\eta\mathbf g_t\).
First-order condition for convexity:
\[f(\mathbf x^\star)\ge f(\mathbf x_t)+\mathbf g_t^\top(\mathbf x^\star-\mathbf x_t)\quad\Longrightarrow\quad e_t\le\mathbf g_t^\top(\mathbf x_t-\mathbf x^\star).\]
Convex, differentiable \(f,\) with minimizer \(\mathbf x^\star\).
Squared-norm expansion:
\[\|\mathbf a-\mathbf b\|_2^2=\|\mathbf a\|_2^2-2\mathbf a^\top\mathbf b+\|\mathbf b\|_2^2.\]Use \(\mathbf a=\mathbf x_t-\mathbf x^\star\) and \(\mathbf b=\eta\mathbf g_t\).
First-order condition for convexity:
\[f(\mathbf x^\star)\ge f(\mathbf x_t)+\mathbf g_t^\top(\mathbf x^\star-\mathbf x_t)\quad\Longrightarrow\quad e_t\le\mathbf g_t^\top(\mathbf x_t-\mathbf x^\star).\]Sum the same inequality over
Assume a gradient-norm bound G:
Sum the same inequality over
Assume a gradient-norm bound G:
Sum the same inequality over
Assume a gradient-norm bound G:
Smoothness means that the gradient is Lipschitz:
It implies the quadratic upper model
This implication does not require convexity. For differentiable convex functions on \(\mathbb R^p,\) the upper-model condition is also equivalent to a Lipschitz gradient.

For differentiable convex \(f:\mathbb R^p\to\mathbb R,\) the gradient condition is equivalent to
Keep \(G\) and \(L\) distinct.
Assume \(\nabla f\) is \(L\)-Lipschitz continuous. For a gradient step, the quadratic upper bound gives
Choose \(\eta=1/L\). Then
This decrease follows from smoothness; convexity is not needed here.
Theorem: suppose \(f:\mathbb R^p\to\mathbb R\) is convex, \(L\)-smooth and has a minimizer.
This time the guarantee is for the last iterate.
Assume convexity and an \(L\)-Lipschitz gradient. Choose \(\eta=1/L\).
The squared-distance expansion and convexity gave
Smoothness gives \(\eta^2\|\mathbf g_t\|_2^2\le2\eta(e_t-e_{t+1})\). Substitute:
The \(e_t\) terms cancel. We can now bound the next objective error using only the change in squared distance.
Sum \(2\eta e_{t+1}\le D_t-D_{t+1}\) over \(t=0,\ldots,T-1\):
The intermediate distances cancel. Smoothness also gives \(e_1\ge\cdots\ge e_T,\) so
For fixed \(L,R,\) this is \(O(\varepsilon^{-1})\) iterations.
This gives objective error \(O(T^{-1}),\) or \(O(\varepsilon^{-1})\) iterations for accuracy \(\varepsilon,\) for fixed \(L,R\).
So far, we have bounded the objective error by
Could the error decrease exponentially in \(T\)?
On \(f(x)=x^2,\) the exact smoothness constant is \(L=2\).
One step reaches the minimizer.
The same function is also smooth with the looser bound \(L=4\).
Geometric decrease, even with the conservative step.
On \(f(x)=x^2,\) the exact smoothness constant is \(L=2\).
One step reaches the minimizer.
The same function is also smooth with the looser bound \(L=4\).
Geometric decrease, even with the conservative step.
What is the right characterization to obtain this in general?
Strong convexity — “not too flat”
For \(\mu>0\) on a convex domain,
Strong convexity implies strict convexity and at most one minimizer. Existence still needs an assumption; for a finite differentiable strongly convex function on all of \(\mathbb R^p,\) it is attained.

For smooth, strongly convex functions, gradient descent can decrease the objective error geometrically.
To obtain \(e_T\le\varepsilon\), we will need \(O(\kappa\log(1/\varepsilon))\) iterations, for fixed \(L,R\).
Assume convexity, \(L\)-smoothness and \(\mu\)-strong convexity.
Choose \(\eta=1/L;\) keep the same \(e_t,D_t,R\).
Assume convexity, \(L\)-smoothness and \(\mu\)-strong convexity.
Choose \(\eta=1/L;\) keep the same \(e_t,D_t,R\).
Assume convexity, \(L\)-smoothness and \(\mu\)-strong convexity.
Choose \(\eta=1/L;\) keep the same \(e_t,D_t,R\).
Assume convexity, \(L\)-smoothness and \(\mu\)-strong convexity.
Choose \(\eta=1/L;\) keep the same \(e_t,D_t,R\).
Let \(\kappa=L/\mu\ge1\) be the condition number. Repeated contraction gives
At an unconstrained differentiable minimizer, \(\nabla f(\mathbf x^\star)=0\). The smooth upper model then gives
Combining the two bounds:
To make the objective error at most \(\varepsilon,\) it is sufficient that
Solve this scalar inequality for the number of updates:
If \(LR^2/2\le\varepsilon,\) the initial point already meets this sufficient bound.
The starting calculation was always the change in squared distance.
The assumptions change what we can do with the same identity.
Here \(\eta_t\) is one scalar for the whole gradient.
| Convex, bounded gradients | Convex, \(L\)-smooth | \(\mu\)-strongly convex | \((\mu,L)\) well conditioned | |
|---|---|---|---|---|
| Error | \(1/\sqrt T\) | \(L/T\) | \(1/(\mu T)\) | \(e^{-\mu T/L}\) |
| Step size | \(1/\sqrt T\) | \(1/L\) | \(1/(\mu T)\) | \(1/L\) |
Rates suppress problem-dependent constants; the stated gradient and curvature assumptions are required.
GD with the Polyak step size
Input: horizon \(T,\) initial iterate \(\mathbf x_0\).
For \(t=0,\ldots,T-1\). Return the best evaluated iterate.
\(\mathbf x^\star\): a minimizer
\(f(\mathbf x_t)-f^\star\): objective error
\(\|\mathbf x_t-\mathbf x^\star\|_2\): iterate distance
The displayed step uses the optimum value; its denominator must be nonzero.


Figure 2: cosine and warmup–stable–decay schedules (left); predicted objective-error bounds (right).
Write \(\eta_t=\eta_{\mathrm{base}}s_t\): choose both the schedule shape \(s_t\) and its scale \(\eta_{\mathrm{base}}\).


The shaded domain is the feasible set \(\mathcal X\).
A gradient step may leave \(\mathcal X\). How can we modify it?

The shaded domain is the feasible set \(\mathcal X\).
A gradient step may leave \(\mathcal X\). How can we modify it?

The shaded domain is the feasible set \(\mathcal X\).
A gradient step may leave \(\mathcal X\). How can we modify it?
We minimize the same objective, over a restricted domain:

We minimize the same objective, over a restricted domain:

The constrained optimum may lie on the boundary.

We can no longer assume \(\nabla f(\mathbf x^\star)=\mathbf0\).

In the source figure, \(X\) is our \(\mathcal X\), \(d=p\), and the red arrow represents \(-\eta_t\mathbf g_t\).
Let \(\mathbf g_t=\nabla f(\mathbf x_t)\). The update has two steps:
The Euclidean projection is
Use the same \(e_t=f(\mathbf x_t)-f^\star\) and \(D_t=\|\mathbf x_t-\mathbf x^\star\|_2^2\).
Projection cannot increase distances:
Convexity gives the same one-step bound as before:
The earlier rate arguments extend, but each iteration now also requires a projection.
With the corresponding assumptions and step sizes: bounded subgradients give \(O(\varepsilon^{-2})\) for the averaged iterate; smooth convex objectives give \(O(\varepsilon^{-1})\); smooth strongly convex objectives give \(O(\kappa\log(1/\varepsilon))\), with \(\kappa=L/\mu\).
Use the same \(e_t=f(\mathbf x_t)-f^\star\) and \(D_t=\|\mathbf x_t-\mathbf x^\star\|_2^2\).
Projection cannot increase distances:
Convexity gives the same one-step bound as before:
The earlier rate arguments extend, but each iteration now also requires a projection.
With the corresponding assumptions and step sizes: bounded subgradients give \(O(\varepsilon^{-2})\) for the averaged iterate; smooth convex objectives give \(O(\varepsilon^{-1})\); smooth strongly convex objectives give \(O(\kappa\log(1/\varepsilon))\), with \(\kappa=L/\mu\).

The corners of the feasible set favor solutions with zero coordinates.
Given \(\mathbf v\), find its nearest feasible point:
A sorting-based implementation costs \(O(p\log p)\). The threshold depends on the vector and the radius.

We approximate the smooth term and keep \(r\) unchanged.
Here \(\mathbf A\in\mathbb R^{n\times p}\), \(\mathbf y\in\mathbb R^n\), and \(\lambda\ge0\).
At \(\mathbf x_t\), use the same quadratic model as for gradient descent:
Complete the square and drop terms independent of \(\mathbf u\):
For \(0<\eta_t\le1/L\), the quadratic model is an upper bound.
The proximal operator is
Take a gradient step on the smooth term, then apply the proximal operator:
A fixed point satisfies \(\mathbf0\in\nabla f_{\rm sm}(\mathbf x)+\partial r(\mathbf x)\).
Represent the constraint by its convex indicator:
For \(r(\mathbf x)=\lambda\|\mathbf x\|_1\), the proximal step acts on each coordinate:
For convex \(f_{\rm sm}+r\), with \(\eta=1/L\) and \(R^2=\|\mathbf x_0-\mathbf x^\star\|_2^2\):
We again need \(O(\varepsilon^{-1})\) iterations for objective error at most \(\varepsilon\).
Marguerite Frank & Philip Wolfe · 1956
Martin Jaggi · 2013

Can we also do constrained optimization
without leaving the constraint set?

Large-scale optimization
Christian L. Müller
Helmholtz Munich
Department of Statistics, LMU
Flatiron Institute
23/11/2026

Christian L. Müller
Helmholtz Munich
Department of Statistics, LMU
Flatiron Institute
23/11/2026

Christian L. Müller
Helmholtz Munich
Department of Statistics, LMU
Flatiron Institute
23/11/2026

17,810 citations · Google Scholar, 18 Nov 2026

9,579 citations · Google Scholar, 18 Nov 2026
RCV1: 781,265 training documents and 47,152 sparse features.

Test performance levels off before very high optimization accuracy becomes useful.
ALPHA: squared hinge loss; 100,000 examples and 500 variables.

ASGD averages successive parameter vectors. In this experiment, it approaches its best test performance after one pass.
CoNLL-2000: conditional random field for sequence labeling.

SGDQN performs best here; averaging is not uniformly better across these experiments.
Many learning objectives are finite sums:
Here
Fix the dataset and write
Choose
Convexity applies to the full gradient:
It need not hold for every realization of the stochastic gradient. But independent uniform sampling gives
Condition on the history before drawing the example:
Now use the tower property:
Thus the deterministic distance calculation carries over after taking expectations. No finite-support assumption about the random iterate is needed.
Assume convexity, an attained minimum,
Choose the constant step
The proof uses the same telescoping recursion, now with expectations. Convexity gives the same bound for the expected error of the averaged iterate.
At a fixed parameter vector, compare
The left-hand side is the squared full-gradient norm; the right-hand side is the second moment of a uniformly sampled single-example gradient.
We bound them by
Larger mini-batches reduce sampling variance.
Draw
Fixed batch size:
For conditionally independent sample-gradient errors with zero mean and second moment at most
Cross terms vanish by conditional independence and zero mean. This controls variance, not the squared norm of the mean gradient.
For a uniform batch without replacement, multiply the single-example variance by



265,349 citations · Google Scholar, 18 Nov 2026
Initialize
Original defaults:

Logistic-regression training loss on MNIST and IMDB bag-of-words data.
Kingma & Ba (2015), Adam: A Method for Stochastic Optimization. These are the paper’s reported experiments.

Neural-network training on MNIST, comparing stochastic dropout and deterministic objectives.
Kingma & Ba (2015), Adam: A Method for Stochastic Optimization. These are the paper’s reported experiments.
Keep Adam’s loss-gradient moments and bias correction:
Adam
AdamW also shrinks the previous parameters by \(1-\eta_t\lambda_{\rm wd}\).
The decay is separate from the adaptive gradient step.
Keep Adam’s loss-gradient moments and bias correction:
Adam
AdamW also shrinks the previous parameters by \(1-\eta_t\lambda_{\rm wd}\).
The decay is separate from the adaptive gradient step.
Keep Adam’s loss-gradient moments and bias correction:
Adam
AdamW also shrinks the previous parameters by \(1-\eta_t\lambda_{\rm wd}\).
The decay is separate from the adaptive gradient step.
In each column, \(\mathbf g_t=\widehat{\nabla f}(\mathbf x_{t-1})\). Start with zero moments; \(t\ge1\).
Adam
Apply the adaptive gradient step.
AdamW: decoupled weight decay
Apply the same rule, with separate decay.
The moment rules are identical. Setting \(\lambda_{\rm wd}=0\) recovers Adam. All operations are coordinatewise.

Exactness concerns the reformulation and its minima; finite training still has numerical tolerances.
Is AdamW the best we have?
A GPT-style LLM predicts the next token from the preceding text.
Apply a scalar adaptive rule to each weight entry.
Equivalent view:
Transform a hidden-layer update using its matrix structure.
A GPT-style LLM predicts the next token from the preceding text.
Apply a scalar adaptive rule to each weight entry.
Equivalent view:
Transform a hidden-layer update using its matrix structure.
A GPT-style LLM predicts the next token from the preceding text.
Apply a scalar adaptive rule to each weight entry.
Equivalent view:
Transform a hidden-layer update using its matrix structure.
LLMs contain large matrices that map one representation to another.
LLMs contain large matrices that map one representation to another.
One matrix block;
Teaching variant: plain momentum and exact polar factor; omit decay and shape scaling.
What changes when all nonzero singular values become 1?
One matrix block;
Teaching variant: plain momentum and exact polar factor; omit decay and shape scaling.
Approximate the polar factor using matrix products, without an SVD at each update.
Polar Express chooses a new polynomial for each inner iteration, using a spectral interval.
Start with
How can a scalar polynomial transform an entire matrix spectrum?
The classical cubic uses fixed coefficients; Polar Express adapts its quintic coefficients.
Approximate the polar factor using matrix products, without an SVD at each update.
Polar Express chooses a new polynomial for each inner iteration, using a spectral interval.
Start with
GPT-2-Large · 774M parameters · FineWeb, 1 billion training tokens
Practical Muon also specifies Nesterov momentum, weight decay, shape scaling and parameter groups.
Marin “Mochi” 535B-A23B
Open pre-training checkpoints · Open Athena · 17 November 2026
Different parameter groups use Muon- and Adam-family updates.
What makes optimization work at this scale?
Marin “Mochi” 535B-A23B
Open pre-training checkpoints · Open Athena · 17 November 2026
Different parameter groups use Muon- and Adam-family updates.
What makes optimization work at this scale?
Geometry of trained neural networks
How are solutions connected in parameter space?
Architecture · basins · permutation symmetry
Wu, Zhu & E · 2017
Wu, Zhu & E · 2017
Fort & Jastrzębski · 2019
Wu, Zhu & E · 2017
Fort & Jastrzębski · 2019
Li, Xu, Taylor, Studer & Goldstein · 2018
Wu, Zhu & E · 2017
Fort & Jastrzębski · 2019
Li, Xu, Taylor, Studer & Goldstein · 2018
Venturi, Bandeira & Bruna · 2019
Visualizing the Loss Landscape of Neural Nets
ResNet-56 loss surfaces with and without skip connections. The source uses filter normalization to compare sharpness/flatness in the two figures.
Learn permutations of hidden units while preserving the network’s function.

Remember LJ clusters?

LJ\(_{13}\)
Permuting hidden units can align two solutions before interpolation.
A common training loop for optimizers in torch.optim.
import torch optimizer = torch.optim.Adam(model.parameters(), lr=1e-3) optimizer.zero_grad() loss = loss_fn(model(inputs), targets) loss.backward() optimizer.step()
params = model.parameters() optimizer = torch.optim.SGD(params, lr=1e-2) # Or choose one of the following: optimizer = torch.optim.SGD(params, lr=1e-2, momentum=0.9) optimizer = torch.optim.Adam(params, lr=1e-3) optimizer = torch.optim.AdamW(params, lr=1e-3, weight_decay=1e-2)
Use the same gradient-computation loop; change the optimizer.
Some methods may reevaluate the objective and gradient within one optimizer step.
optimizer = torch.optim.LBFGS(model.parameters(), lr=1.0)
def closure():
optimizer.zero_grad()
loss = loss_fn(model(inputs), targets)
loss.backward()
return loss
optimizer.step(closure)Here the closure uses the same full batch on each reevaluation.
JAX provides automatic differentiation and array operations.
Describe a convex optimization problem in a modeling language.
cvx_begin
variable x(p)
minimize(norm(A*x - b, 2))
subject to
C*x == d
norm(x, Inf) <= alpha
cvx_endMatch the method to the available information and the cost of using it.
There is much more to optimization than we can cover in one day.
LP: linear · QP: quadratic · SOCP: second-order cone · SDP: semidefinite · CP: cone · GFP: graph-form program
Narendra Karmarkar · 1984


Claude
“Using these lecture notes, help me understand [topic]. State the assumptions, explain the main idea, and work through one example in the course notation. Suggest three further readings with verifiable links.”
Codex
“Using these lecture notes, build a small reproducible experiment comparing [methods] on [problem]. Match the formulas and notation, plot objective value against iterations and evaluations, and explain the results.”
Gemini
“Find primary sources on [topic] that extend these lecture notes. Compare their assumptions, results and limitations. Give links and publication dates; distinguish established results from open questions.”