Part 1, original PDF page 1MUDS course optimization Part I1.1
Part 1, original PDF page 1Optimization and landscapesChristian L. MüllerInstitute of Computational Biology, Helmholtz MunichDepartment of Statistics, Ludwig-Maximilians-UniversitätCenter for Computational Mathematics, Flatiron Institute, New Yorkch.mueller@lmu.de23/11/2026
Part 1, original PDF page 2Optimization1.2
Part 1, original PDF page 2
Part 1, original PDF page 3Optimization1.2
Part 1, original PDF page 3tion äptäptnounnoun: optimization; plural noun: optimizations; noun: optimisation; plural noun: optimisations1. the action of making the best or most effective use of a situation or resource.

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

Part 1, original PDF page 4Optimization1.2
Part 1, original PDF page 4tion äptäptnounnoun: optimization; plural noun: optimizations; noun: optimisation; plural noun: optimisations1. the action of making the best or most effective use of a situation or resource.Mathematical optimizationDiscipline Description Mathematical optimization or mathematical programming is the selection of a best element from some set of available alternatives. Wikipedia

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

Part 1, original PDF page 5Optimization1.3
Part 1, original PDF page 5Mathematical optimization (alternatively spelled optimisationmathematical 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 operations research and economics, and the development of solution methods has been of interest in mathematics for centuries.[2]1. The Nature of Mathematical Programming Archived 2014-03-05 at the Wayback MachineMathematical Programming Glossary, INFORMS Computing Society.2. Du, D. Z.; Pardalos, P. M.; Wu, W. (2008). "History of Optimization". In Floudas, C.; Pardalos, P. (eds.). Encyclopedia of Optimization. Boston: Springer. pp. 1538–1542.

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.

Part 1, original PDF page 5What is optimization?1.4

Choose feasible decisions to make a specified objective as good as possible.

minx∈Xf(x),X⊆Rp.
  • Decisions: x contains the quantities we can change.
  • Objective: f(x) measures loss, cost or energy; here, smaller is better.
  • Constraints: X contains the allowed choices.

In practice: find a good solution within the available time, evaluations and memory.

Part 1, original PDF page 6Optimization1.5
Part 1, original PDF page 6Group discussion - introduce yourself and tell us one example of an optimization problem you encountered
Part 1, original PDF page 7Optimizing a black-box1.6
Part 1, original PDF page 7Black-box systemInput Output
Part 1, original PDF page 8Optimizing a black-box1.6
Part 1, original PDF page 8Black-box systemInput Output
Mathematical model
Computer simulation
Real-world experiment
Part 1, original PDF page 9Black-box optimization1.7
Part 1, original PDF page 9
Input
x∈Rp
Output / loss
f(x)∈R
Black-box system
x1
x2
xj
xp
⋯
⋯
Part 1, original PDF page 10Black-box optimization1.7
Part 1, original PDF page 10
Input
x∈Rp
Output / loss
f(x)∈R
Black-box system
Systems biology models
x1
x2
xj
xp
⋯
⋯
Original Systems biology models example
Part 1, original PDF page 11Black-box optimization1.7
Part 1, original PDF page 11
Input
x∈Rp
Output / loss
f(x)∈R
Black-box system
Analog circuit design
x1
x2
xj
xp
⋯
⋯
Original Analog circuit design example
Part 1, original PDF page 12Black-box optimization1.7
Part 1, original PDF page 12
Input
x∈Rp
Output / loss
f(x)∈R
Black-box system
Hyper-parameters in DNN
x1
x2
xj
xp
⋯
⋯
Original Hyper-parameters in DNN example
Part 1, original PDF page 13Black-box optimization1.7
Part 1, original PDF page 13
Input
x∈Rp
Output / loss
f(x)∈R
Black-box system
x1
x2
xj
xp
⋯
⋯
Part 1, original PDF page 14Black-box optimization1.7
Part 1, original PDF page 14
Input
x∈Rp
Output / loss
f(x)∈R
Black-box system
x1
x2
xj
xp
⋯
⋯
Variables
Parameters
Configuration
Factors
Part 1, original PDF page 15Black-box optimization1.7
Part 1, original PDF page 15
Input
x∈Rp
Output / loss
f(x)∈R
Black-box system
x1
x2
xj
xp
⋯
⋯
Variables
Parameters
Configuration
Factors
Cost
Criterion
Objective
Energy
Fitness
Loss
Part 1, original PDF page 16Black-box optimization1.7
Part 1, original PDF page 16PARAMETERSCONFIGURATIONFind x* such that f(x*)
Input
x∈Rp
Output / loss
f(x)∈R
Black-box system
x1
x2
xj
xp
⋯
⋯
Variables
Parameters
Configuration
Factors
Cost
Criterion
Objective
Energy
Fitness
Loss
Find x⋆∈arg⁡minx∈Xf(x).
Part 1, original PDF page 17Optimization landscapes1.8
Part 1, original PDF page 17......
f(x)∈R
x1
x2
xj
xp
Part 1, original PDF page 18Optimization landscapes1.8
Part 1, original PDF page 185055050100020003000
f(x)∈R
Part 1, original PDF page 19Black-box landscapes1.9
Part 1, original PDF page 195055050100020003000
f(x)∈R
Part 1, original PDF page 20Black-box landscapes1.9
Part 1, original PDF page 205055050100020003000
f(x)∈R
Part 1, original PDF page 21Black-box landscapes1.9
Part 1, original PDF page 215055050100020003000

L=(X,ρ,f) consists of

1. X=∏j=1p[ℓj,uj]⊆Rp.

2. Neighbourhoods/similarity defined by a distance ρ.

3. A black-box function f:X→R.

f(x)∈R
Part 1, original PDF page 22Black-box landscapes1.9
Part 1, original PDF page 225055050100020003000

L=(X,ρ,f) consists of

1. X=∏j=1p[ℓj,uj]⊆Rp.

2. Neighbourhoods/similarity defined by a distance ρ.

3. A black-box function f:X→R.

Topographic description:

  • Peaks and valleys
  • Plateaus and basins
  • Ridges and funnels
f(x)∈R
Part 1, original PDF page 23Black-box landscapes1.9
Part 1, original PDF page 235055050100020003000

L=(X,ρ,f) consists of

1. X=∏j=1p[ℓj,uj]⊆Rp.

2. Neighbourhoods/similarity defined by a distance ρ.

3. A black-box function f:X→R.

Topographic description:

  • Peaks and valleys
  • Plateaus and basins
  • Ridges and funnels
f(x)∈R
Part 1, original PDF page 24Black-box landscapes1.9
Part 1, original PDF page 245055050100020003000Find the lowest point x* in the landscape!

L=(X,ρ,f) consists of

1. X=∏j=1p[ℓj,uj]⊆Rp.

2. Neighbourhoods/similarity defined by a distance ρ.

3. A black-box function f:X→R.

Topographic description:

  • Peaks and valleys
  • Plateaus and basins
  • Ridges and funnels
f(x)∈R
Part 1, original PDF page 25Landscapes in science1.10
Part 1, original PDF page 255055050100020003000
f(x)∈R
Part 1, original PDF page 26Landscapes in science1.10
Part 1, original PDF page 265055050100020003000Fitness landscape
f(x)∈R
Part 1, original PDF page 27Landscapes in science1.10
Part 1, original PDF page 275055050100020003000Fitness landscapePotential energy landscape
f(x)∈R
Part 1, original PDF page 28Landscapes in science1.10
Part 1, original PDF page 285055050100020003000Fitness landscapePotential energy landscapeEpigenetic landscape
f(x)∈R
Part 1, original PDF page 29Landscapes in science1.10
Part 1, original PDF page 295055050100020003000Fitness landscapePotential energy landscapeEpigenetic landscapeFolding funnel
f(x)∈R
Part 1, original PDF page 30Landscapes in science1.10
Part 1, original PDF page 305055050100020003000Fitness landscapePotential energy landscapeEpigenetic landscapeFolding funnel DNN landscape
f(x)∈R
Part 1, original PDF page 30Landscape of Thoughts1.11
Part 1, original PDF page 305055050100020003000
Part 1, original PDF page 31Landscapes are metaphors1.12
Part 1, original PDF page 31“The price of metaphor is eternal vigilance."Norbert WienerLa condition humaine, René Magritte
Part 1, original PDF page 32Deep neural network landscapes1.13
Part 1, original PDF page 32(a) without skip connections (b) with skip connectionsFigure 1: The loss surfaces of ResNet-56 with/without skip connections. The proposed filternormalization scheme is used to enable comparisons of sharpness/flatness between the two figures.Visualizing the Loss Landscape of Neural NetsHao Li, Zheng Xu, Gavin Taylor, Christoph Studer, Tom GoldsteinUniversity of Maryland, College Park United States Naval Academy Cornell University{haoli,xuzh,tomg}@cs.umd.edutaylor@usna.edustuder@cornell.edu

Visualizing the Loss Landscape of Neural Nets

Without skip connectionsWith skip connections

ResNet-56 loss surfaces with and without skip connections. The source uses filter normalization to compare sharpness/flatness in the two figures.

Part 1, original PDF page 33Deep neural network landscapes1.13
Part 1, original PDF page 33Towards Understanding Generalization of DeepLearning: Perspective of Loss LandscapesLei WuSchool of Mathematics, Peking UniversityBeijing, Chinaleiwu@pku.edu.cnZhanxing ZhuBeijing Institute of Big Data Research (BIBDR)Center for Data Science, Peking UniversityBeijing, Chinazhanxing.zhu@pku.edu.cnWeinan EBeijing Institute of Big Data Research (BIBDR)Center for Data Science and BICMR, Peking University, Beijing, ChinaDepartment of Mathematics and PACM, Princeton University, Princeton, NJ, USAweinan@math.princeton.edu
Towards Understanding Generalization of Deep Learning: Perspective of Loss Landscapes

Wu, Zhu & E · 2017

Part 1, original PDF page 34Deep neural network landscapes1.13
Part 1, original PDF page 34Towards Understanding Generalization of DeepLearning: Perspective of Loss LandscapesLei WuSchool of Mathematics, Peking UniversityBeijing, Chinaleiwu@pku.edu.cnZhanxing ZhuBeijing Institute of Big Data Research (BIBDR)Center for Data Science, Peking UniversityBeijing, Chinazhanxing.zhu@pku.edu.cnWeinan EBeijing Institute of Big Data Research (BIBDR)Center for Data Science and BICMR, Peking University, Beijing, ChinaDepartment of Mathematics and PACM, Princeton University, Princeton, NJ, USAweinan@math.princeton.eduLarge Scale Structure of Neural Network LossLandscapesStanislav FortGoogle ResearchZurich, Switzerlandstanislavfort@google.comStanislaw JastrzebskiNew York UniversityNew York, United StatesAbstractThere are many surprising and perhaps counter-intuitive properties of optimizationof deep neural networks. We propose and experimentally verify a unified phenomenological model of the loss landscape that incorporates many of them. Highdimensionality plays a key role in our model. Our core idea is to model the losslandscape as a set of high dimensional wedges that together form a large-scale,inter-connected structure and towards which optimization is drawn. We first showthat hyperparameter choices such as learning rate, network width and regularization, affect the path optimizer takes through the landscape in a similar ways,influencing the large scale curvature of the regions the optimizer explores. Finally,we predict and demonstrate new counter-intuitive properties of the loss-landscape.We show an existence of low loss subspaces connecting a set (not only a pair)of solutions, and verify it experimentally. Finally, we analyze recently popularensembling techniques for deep networks in the light of our model.
Towards Understanding Generalization of Deep Learning: Perspective of Loss Landscapes

Wu, Zhu & E · 2017

Large Scale Structure of Neural Network Loss Landscapes

Fort & Jastrzębski · 2019

Part 1, original PDF page 35Deep neural network landscapes1.13
Part 1, original PDF page 35Towards Understanding Generalization of DeepLearning: Perspective of Loss LandscapesLei WuSchool of Mathematics, Peking UniversityBeijing, Chinaleiwu@pku.edu.cnZhanxing ZhuBeijing Institute of Big Data Research (BIBDR)Center for Data Science, Peking UniversityBeijing, Chinazhanxing.zhu@pku.edu.cnWeinan EBeijing Institute of Big Data Research (BIBDR)Center for Data Science and BICMR, Peking University, Beijing, ChinaDepartment of Mathematics and PACM, Princeton University, Princeton, NJ, USAweinan@math.princeton.eduVisualizing the Loss Landscape of Neural NetsHao Li, Zheng Xu, Gavin Taylor, Christoph Studer, Tom GoldsteinUniversity of Maryland, College Park United States Naval Academy Cornell University{haoli,xuzh,tomg}@cs.umd.edutaylor@usna.edustuder@cornell.eduAbstractNeural network training relies on our ability to find “good” minimizers of highlynon-convex loss functions. It is well-known that certain network architecturedesigns (e.g., skip connections) produce loss functions that train easier, and wellchosen training parameters (batch size, learning rate, optimizer) produce minimizers that generalize better. However, the reasons for these differences, and theireffect on the underlying loss landscape, are not well understood. In this paper, weexplore the structure of neural loss functions, and the effect of loss landscapes ongeneralization, using a range of visualization methods. First, we introduce a simple“filter normalization” method that helps us visualize loss function curvature andmake meaningful side-by-side comparisons between loss functions. Then, usinga variety of visualizations, we explore how network architecture affects the losslandscape, and how training parameters affect the shape of minimizers.Large Scale Structure of Neural Network LossLandscapesStanislav FortGoogle ResearchZurich, Switzerlandstanislavfort@google.comStanislaw JastrzebskiNew York UniversityNew York, United StatesAbstractThere are many surprising and perhaps counter-intuitive properties of optimizationof deep neural networks. We propose and experimentally verify a unified phenomenological model of the loss landscape that incorporates many of them. Highdimensionality plays a key role in our model. Our core idea is to model the losslandscape as a set of high dimensional wedges that together form a large-scale,inter-connected structure and towards which optimization is drawn. We first showthat hyperparameter choices such as learning rate, network width and regularization, affect the path optimizer takes through the landscape in a similar ways,influencing the large scale curvature of the regions the optimizer explores. Finally,we predict and demonstrate new counter-intuitive properties of the loss-landscape.We show an existence of low loss subspaces connecting a set (not only a pair)of solutions, and verify it experimentally. Finally, we analyze recently popularensembling techniques for deep networks in the light of our model.
Towards Understanding Generalization of Deep Learning: Perspective of Loss Landscapes

Wu, Zhu & E · 2017

Large Scale Structure of Neural Network Loss Landscapes

Fort & Jastrzębski · 2019

Visualizing the Loss Landscape of Neural Nets

Li, Xu, Taylor, Studer & Goldstein · 2018

Part 1, original PDF page 36Deep neural network landscapes1.13
Part 1, original PDF page 36Towards Understanding Generalization of DeepLearning: Perspective of Loss LandscapesLei WuSchool of Mathematics, Peking UniversityBeijing, Chinaleiwu@pku.edu.cnZhanxing ZhuBeijing Institute of Big Data Research (BIBDR)Center for Data Science, Peking UniversityBeijing, Chinazhanxing.zhu@pku.edu.cnWeinan EBeijing Institute of Big Data Research (BIBDR)Center for Data Science and BICMR, Peking University, Beijing, ChinaDepartment of Mathematics and PACM, Princeton University, Princeton, NJ, USAweinan@math.princeton.eduVisualizing the Loss Landscape of Neural NetsHao Li, Zheng Xu, Gavin Taylor, Christoph Studer, Tom GoldsteinUniversity of Maryland, College Park United States Naval Academy Cornell University{haoli,xuzh,tomg}@cs.umd.edutaylor@usna.edustuder@cornell.eduAbstractNeural network training relies on our ability to find “good” minimizers of highlynon-convex loss functions. It is well-known that certain network architecturedesigns (e.g., skip connections) produce loss functions that train easier, and wellchosen training parameters (batch size, learning rate, optimizer) produce minimizers that generalize better. However, the reasons for these differences, and theireffect on the underlying loss landscape, are not well understood. In this paper, weexplore the structure of neural loss functions, and the effect of loss landscapes ongeneralization, using a range of visualization methods. First, we introduce a simple“filter normalization” method that helps us visualize loss function curvature andmake meaningful side-by-side comparisons between loss functions. Then, usinga variety of visualizations, we explore how network architecture affects the losslandscape, and how training parameters affect the shape of minimizers.Large Scale Structure of Neural Network LossLandscapesStanislav FortGoogle ResearchZurich, Switzerlandstanislavfort@google.comStanislaw JastrzebskiNew York UniversityNew York, United StatesAbstractThere are many surprising and perhaps counter-intuitive properties of optimizationof deep neural networks. We propose and experimentally verify a unified phenomenological model of the loss landscape that incorporates many of them. Highdimensionality plays a key role in our model. Our core idea is to model the losslandscape as a set of high dimensional wedges that together form a large-scale,inter-connected structure and towards which optimization is drawn. We first showthat hyperparameter choices such as learning rate, network width and regularization, affect the path optimizer takes through the landscape in a similar ways,influencing the large scale curvature of the regions the optimizer explores. Finally,we predict and demonstrate new counter-intuitive properties of the loss-landscape.We show an existence of low loss subspaces connecting a set (not only a pair)of solutions, and verify it experimentally. Finally, we analyze recently popularensembling techniques for deep networks in the light of our model.Journal of Machine Learning Research 20 (2019) 1-34 Submitted 9/18; Revised 7/19; Published 8/19Spurious Valleys in One-hidden-layer Neural NetworkOptimization LandscapesLuca Venturi venturi@cims.nyu.eduCourant Institute of Mathematical Sciences, 251 Mercer Street, New York, NY 10012Afonso S. Bandeira bandeira@cims.nyu.eduJoan Bruna bruna@cims.nyu.eduCourant Institute of Mathematical Sciences, 251 Mercer Street, New York, NY 10012Center for Data Science, 60 5th Avenue, New York, NY 10011Editor: Animashree Anandkumar
Towards Understanding Generalization of Deep Learning: Perspective of Loss Landscapes

Wu, Zhu & E · 2017

Large Scale Structure of Neural Network Loss Landscapes

Fort & Jastrzębski · 2019

Visualizing the Loss Landscape of Neural Nets

Li, Xu, Taylor, Studer & Goldstein · 2018

Spurious Valleys in One-hidden-layer Neural Network Optimization Landscapes

Venturi, Bandeira & Bruna · 2019

Part 1, original PDF page 37Deep neural network landscapes1.14
Part 1, original PDF page 37
A standard architecture
h₀F₀F₁F₂h₃
Residual-block schematic: He et al., Deep Residual Learning (2015). Layer activations: hℓ.
Part 1, original PDF page 38Deep neural network landscapes1.14
Part 1, original PDF page 38
A standard architecture
h₀F₀F₁F₂h₃
With skip connections
h₀F₀identityF₁identityF₂identityh₃
Residual-block schematic: He et al., Deep Residual Learning (2015). Layer activations: hℓ.
Part 1, original PDF page 39Deep neural network landscapes1.14
Part 1, original PDF page 39Visualizing the Loss Landscape of Neural NetsHao Li, Zheng Xu, Gavin Taylor, Christoph Studer, Tom GoldsteinUniversity of Maryland, College Park United States Naval Academy Cornell University{haoli,xuzh,tomg}@cs.umd.edutaylor@usna.edustuder@cornell.edu
A standard architecture
h₀F₀F₁F₂h₃
hℓ+1=Fℓ(hℓ)
With skip connections
h₀F₀identityF₁identityF₂identityh₃
hℓ+1=hℓ+Fℓ(hℓ)
Blue: unchanged input   ·   +: elementwise addition   ·   Matching feature dimensions
Residual-block schematic: He et al., Deep Residual Learning (2015). Layer activations: hℓ.
Part 1, original PDF page 40Deep neural network landscapes1.14
Part 1, original PDF page 40Visualizing the Loss Landscape of Neural NetsHao Li, Zheng Xu, Gavin Taylor, Christoph Studer, Tom GoldsteinUniversity of Maryland, College Park United States Naval Academy Cornell University{haoli,xuzh,tomg}@cs.umd.edutaylor@usna.edustuder@cornell.edu
A standard architecture
h₀F₀F₁F₂h₃
hℓ+1=Fℓ(hℓ)
With skip connections
h₀F₀identityF₁identityF₂identityh₃
hℓ+1=hℓ+Fℓ(hℓ)
Blue: unchanged input   ·   +: elementwise addition   ·   Matching feature dimensions
Learn a correction: Fℓ(hℓ)=0 recovers the identity map.
Residual-block schematic: He et al., Deep Residual Learning (2015). Layer activations: hℓ.
Part 1, original PDF page 40Deep neural network landscapes1.15
Part 1, original PDF page 40Visualizing the Loss Landscape of Neural NetsHao Li, Zheng Xu, Gavin Taylor, Christoph Studer, Tom GoldsteinUniversity of Maryland, College Park United States Naval Academy Cornell University{haoli,xuzh,tomg}@cs.umd.edutaylor@usna.edustuder@cornell.edu
Part 1, original PDF page 41Deep neural network landscapes1.16
Part 1, original PDF page 41(a) without skip connections (b) with skip connectionsFigure 1: The loss surfaces of ResNet-56 with/without skip connections. The proposed filternormalization scheme is used to enable comparisons of sharpness/flatness between the two figures.Visualizing the Loss Landscape of Neural NetsHao Li, Zheng Xu, Gavin Taylor, Christoph Studer, Tom GoldsteinUniversity of Maryland, College Park United States Naval Academy Cornell University{haoli,xuzh,tomg}@cs.umd.edutaylor@usna.edustuder@cornell.edu

Visualizing the Loss Landscape of Neural Nets

Without skip connectionsWith skip connections

ResNet-56 loss surfaces with and without skip connections. The source uses filter normalization to compare sharpness/flatness in the two figures.

Part 1, original PDF page 42Fitness landscapes1.17
Part 1, original PDF page 42Wright, S., “The Roles of Mutation, Inbreeding, Crossbreeding, and Selection in Evolution,” Proceedings of the Sixth International Congress on Genetics, 1932.
Part 1, original PDF page 43Fitness landscapes1.17
Part 1, original PDF page 43Wright, S., “The Roles of Mutation, Inbreeding, Crossbreeding, and Selection in Evolution,” Proceedings of the Sixth International Congress on Genetics, 1932. gene 1/ trait 1/…gene 2/trait 2/…
Part 1, original PDF page 44Fitness landscapes1.17
Part 1, original PDF page 44Wright, S., “The Roles of Mutation, Inbreeding, Crossbreeding, and Selection in Evolution,” Proceedings of the Sixth International Congress on Genetics, 1932. gene 1/ trait 1/…gene 2/trait 2/…
Part 1, original PDF page 45Fitness landscapes1.17
Part 1, original PDF page 45Wright, S., “The Roles of Mutation, Inbreeding, Crossbreeding, and Selection in Evolution,” Proceedings of the Sixth International Congress on Genetics, 1932. gene 1/ trait 1/…gene 2/trait 2/…
Part 1, original PDF page 46Fitness landscapes1.18
Part 1, original PDF page 46Exploring protein fitness landscapes by directed evolutionPhilip A. Romero and Frances H. ArnoldAbstract | Directed evolution circumvents our profound ignorance of how a protein’s sequence encodes its function by using iterative rounds of random mutation and artificial selection to discover new and useful proteins. Proteins can be tuned to adapt to new functions or environments by simple adaptive walks involving small numbers of mutations. Directed evolution studies have shown how rapidly some proteins can evolve under strong selection pressures and, because the entire ‘fossil record’ of evolutionary intermediates is available for detailed study, they have provided new insight into the relationship between sequence and function. Directed evolution has also shown how mutations that are functionally neutral can set the stage for further adaptation.FitnesSequenc
Part 1, original PDF page 47Fitness landscapes1.18
Part 1, original PDF page 47Exploring protein fitness landscapes by directed evolutionPhilip A. Romero and Frances H. ArnoldAbstract | Directed evolution circumvents our profound ignorance of how a protein’s sequence encodes its function by using iterative rounds of random mutation and artificial selection to discover new and useful proteins. Proteins can be tuned to adapt to new functions or environments by simple adaptive walks involving small numbers of mutations. Directed evolution studies have shown how rapidly some proteins can evolve under strong selection pressures and, because the entire ‘fossil record’ of evolutionary intermediates is available for detailed study, they have provided new insight into the relationship between sequence and function. Directed evolution has also shown how mutations that are functionally neutral can set the stage for further adaptation.FitnesSequencent section Best starting point orpoints out of naturynthetic sequencErrone PCRombination oromputer-guidedmutagenesisHigh-throughputscreen or selectionMedical, agriculturenvironmentalindustrial or energy usesSequence diversifictionunctional assaApplictionFittestsequenc
Part 1, original PDF page 48Fitness landscapes1.19
Part 1, original PDF page 48Navigating the protein tness landscape withGaussian processesPhilip A. Romero, Andreas Krause, and Frances H. ArnoldDivision of Chemistry and Chemical Engineering, California Institute of Technology, Pasadena, CA 91125; and Department of Computer Science, SwissFederal Institute of Technology, 8092 Zurich, SwitzerlandEdited by Michael Levitt, Stanford University School of Medicine, Stanford, CA, and approved November 28, 2012 (received for review September 9, 201PNAS PLUS
Navigating the protein fitness landscape
with Gaussian processes

Philip A. Romero, Andreas Krause & Frances H. Arnold · 2013

Enzyme to be optimized

Original protein fitness landscape figure, panel 1

Network representation
and distance definition

Original protein fitness landscape figure, panel 2

Measured fitness
modeled as a GP

Original protein fitness landscape figure, panel 3
Part 1, original PDF page 49Fitness landscapes1.19
Part 1, original PDF page 49Navigating the protein tness landscape withGaussian processesPhilip A. Romero, Andreas Krause, and Frances H. ArnoldDivision of Chemistry and Chemical Engineering, California Institute of Technology, Pasadena, CA 91125; and Department of Computer Science, SwissFederal Institute of Technology, 8092 Zurich, SwitzerlandEdited by Michael Levitt, Stanford University School of Medicine, Stanford, CA, and approved November 28, 2012 (received for review September 9, 201PNAS PLUS
Navigating the protein fitness landscape
with Gaussian processes

Philip A. Romero, Andreas Krause & Frances H. Arnold · 2013

Enzyme to be optimized

Original protein fitness landscape figure, panel 1

Network representation
and distance definition

Original protein fitness landscape figure, panel 2

Measured fitness
modeled as a GP

Original protein fitness landscape figure, panel 3
Part 1, original PDF page 50Fitness landscapes1.19
Part 1, original PDF page 50Navigating the protein tness landscape withGaussian processesPhilip A. Romero, Andreas Krause, and Frances H. ArnoldDivision of Chemistry and Chemical Engineering, California Institute of Technology, Pasadena, CA 91125; and Department of Computer Science, SwissFederal Institute of Technology, 8092 Zurich, SwitzerlandEdited by Michael Levitt, Stanford University School of Medicine, Stanford, CA, and approved November 28, 2012 (received for review September 9, 201PNAS PLUS
Navigating the protein fitness landscape
with Gaussian processes

Philip A. Romero, Andreas Krause & Frances H. Arnold · 2013

Enzyme to be optimized

Original protein fitness landscape figure, panel 1

Network representation
and distance definition

Original protein fitness landscape figure, panel 2

Measured fitness
modeled as a GP

Original protein fitness landscape figure, panel 3
Part 1, original PDF page 51Fitness landscapes1.19
Part 1, original PDF page 51Navigating the protein tness landscape withGaussian processesPhilip A. Romero, Andreas Krause, and Frances H. ArnoldDivision of Chemistry and Chemical Engineering, California Institute of Technology, Pasadena, CA 91125; and Department of Computer Science, SwissFederal Institute of Technology, 8092 Zurich, SwitzerlandEdited by Michael Levitt, Stanford University School of Medicine, Stanford, CA, and approved November 28, 2012 (received for review September 9, 201PNAS PLUS
Navigating the protein fitness landscape
with Gaussian processes

Philip A. Romero, Andreas Krause & Frances H. Arnold · 2013

Enzyme to be optimized

Original protein fitness landscape figure, panel 1

Network representation
and distance definition

Original protein fitness landscape figure, panel 2

Measured fitness
modeled as a GP

Original protein fitness landscape figure, panel 3
Part 1, original PDF page 52Fitness landscapes1.19
Part 1, original PDF page 52Navigating the protein tness landscape withGaussian processesPhilip A. Romero, Andreas Krause, and Frances H. ArnoldDivision of Chemistry and Chemical Engineering, California Institute of Technology, Pasadena, CA 91125; and Department of Computer Science, SwissFederal Institute of Technology, 8092 Zurich, SwitzerlandEdited by Michael Levitt, Stanford University School of Medicine, Stanford, CA, and approved November 28, 2012 (received for review September 9, 201PNAS PLUS
Navigating the protein fitness landscape
with Gaussian processes

Philip A. Romero, Andreas Krause & Frances H. Arnold · 2013

Enzyme to be optimized

Original protein fitness landscape figure, panel 1

Network representation
and distance definition

Original protein fitness landscape figure, panel 2

Measured fitness
modeled as a GP

Original protein fitness landscape figure, panel 3
Part 1, original PDF page 53Fitness landscapes1.19
Part 1, original PDF page 53Navigating the protein tness landscape withGaussian processesPhilip A. Romero, Andreas Krause, and Frances H. ArnoldDivision of Chemistry and Chemical Engineering, California Institute of Technology, Pasadena, CA 91125; and Department of Computer Science, SwissFederal Institute of Technology, 8092 Zurich, SwitzerlandEdited by Michael Levitt, Stanford University School of Medicine, Stanford, CA, and approved November 28, 2012 (received for review September 9, 201PNAS PLUS
Navigating the protein fitness landscape
with Gaussian processes

Philip A. Romero, Andreas Krause & Frances H. Arnold · 2013

Enzyme to be optimized

Original protein fitness landscape figure, panel 1

Network representation
and distance definition

Original protein fitness landscape figure, panel 2

Measured fitness
modeled as a GP

Original protein fitness landscape figure, panel 3
Part 1, original PDF page 54Fitness landscapes1.19
Part 1, original PDF page 54Navigating the protein tness landscape withGaussian processesPhilip A. Romero, Andreas Krause, and Frances H. ArnoldDivision of Chemistry and Chemical Engineering, California Institute of Technology, Pasadena, CA 91125; and Department of Computer Science, SwissFederal Institute of Technology, 8092 Zurich, SwitzerlandEdited by Michael Levitt, Stanford University School of Medicine, Stanford, CA, and approved November 28, 2012 (received for review September 9, 201PNAS PLUS
Navigating the protein fitness landscape
with Gaussian processes

Philip A. Romero, Andreas Krause & Frances H. Arnold · 2013

Enzyme to be optimized

Original protein fitness landscape figure, panel 1

Network representation
and distance definition

Original protein fitness landscape figure, panel 2

Measured fitness
modeled as a GP

Original protein fitness landscape figure, panel 3
Part 1, original PDF page 55Fitness landscapes and optimization1.20
Part 1, original PDF page 55
  • Evolution can be seen as an optimization process over a fitness landscape.
  • The optimization process is based on a population of individuals.
  • Key operations are mutation and selection.
Part 1, original PDF page 56Fitness landscapes and optimization1.20
Part 1, original PDF page 56evolutionary computation
  • Evolution can be seen as an optimization process over a fitness landscape.
  • The optimization process is based on a population of individuals.
  • Key operations are mutation and selection.

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

Part 1, original PDF page 57Energy landscapes1.21
Part 1, original PDF page 57Eyring, H, Polanyi, M., “Über einfache Gasreaktionen,” Zeitschrift für Physikalische Chemie B, Band 12, S. 279–311,1931London-eyring-polanyi potential energy surface
Part 1, original PDF page 58Energy landscapes1.21
Part 1, original PDF page 58Eyring, H, Polanyi, M., “Über einfache Gasreaktionen,” Zeitschrift für Physikalische Chemie B, Band 12, S. 279–311,19312 2 + H reaction for a collinear collision geometryLondon-eyring-polanyi potential energy surface
Part 1, original PDF page 59Energy landscapes1.21
Part 1, original PDF page 59Eyring, H, Polanyi, M., “Über einfache Gasreaktionen,” Zeitschrift für Physikalische Chemie B, Band 12, S. 279–311,19312 2 + H reaction for a collinear collision geometryLondon-eyring-polanyi potential energy surface
Part 1, original PDF page 60Energy landscapes1.21
Part 1, original PDF page 60Eyring, H, Polanyi, M., “Über einfache Gasreaktionen,” Zeitschrift für Physikalische Chemie B, Band 12, S. 279–311,19312 2 + H reaction for a collinear collision geometryLondon-eyring-polanyi potential energy surface
Part 1, original PDF page 61Energy landscapes1.21
Part 1, original PDF page 61Eyring, H, Polanyi, M., “Über einfache Gasreaktionen,” Zeitschrift für Physikalische Chemie B, Band 12, S. 279–311,19312 2 + H reaction for a collinear collision geometryLondon-eyring-polanyi potential energy surface distance between atom X and Ydistance between atom X and Z
Part 1, original PDF page 62Energy landscapes1.21
Part 1, original PDF page 62Eyring, H, Polanyi, M., “Über einfache Gasreaktionen,” Zeitschrift für Physikalische Chemie B, Band 12, S. 279–311,19312 2 + H reaction for a collinear collision geometryLondon-eyring-polanyi potential energy surface distance between atom X and Ydistance between atom X and Z
Part 1, original PDF page 63Energy landscapes1.21
Part 1, original PDF page 63Eyring, H, Polanyi, M., “Über einfache Gasreaktionen,” Zeitschrift für Physikalische Chemie B, Band 12, S. 279–311,19312 2 + H reaction for a collinear collision geometryLondon-eyring-polanyi potential energy surface distance between atom X and Ydistance between atom X and Z
Part 1, original PDF page 64Energy landscapes1.21
Part 1, original PDF page 64Eyring, H, Polanyi, M., “Über einfache Gasreaktionen,” Zeitschrift für Physikalische Chemie B, Band 12, S. 279–311,19312 2 + H reaction for a collinear collision geometryResonance energy as a function of distances (“resonance mountain”)London-eyring-polanyi potential energy surface distance between atom X and Ydistance between atom X and Z
Part 1, original PDF page 65Energy landscapes1.21
Part 1, original PDF page 65Packing Structures and Transitions Liquids and Solids Frank Stillinger and Thomas Weber September Volume Number SCIENCE Fig. Schematic representation the potential energy surface for N-atom system. Minima are shown filled circles and saddle points crosses. Potential energy constant along the continuous curves. Regions belonging different minima are indicated dashed curves.
Part 1, original PDF page 66Energy landscapes1.21
Part 1, original PDF page 66Packing Structures and Transitions Liquids and Solids Frank Stillinger and Thomas Weber September Volume Number SCIENCE Fig. Schematic representation the potential energy surface for N-atom system. Minima are shown filled circles and saddle points crosses. Potential energy constant along the continuous curves. Regions belonging different minima are indicated dashed curves. Gas LiquidSolidLearnThermo source (archived, 2024)
Part 1, original PDF page 67Energy landscapes and optimization1.22
Part 1, original PDF page 67SCIENCEMay Volume Number Optimization Simulated Annealing Kirkpatrick, Gelatt, Vecchi

The transition process from gas to liquid to solid can be seen as an optimization process.

Part 1, original PDF page 68Energy landscapes and optimization1.22
Part 1, original PDF page 68SCIENCEMay Volume Number Optimization Simulated Annealing Kirkpatrick, Gelatt, Vecchi

The transition process from gas to liquid to solid can be seen as an optimization process.

Ingredients:

  • A procedure to explore local configurations
  • A temperature-dependent acceptance criterion for new configurations
  • A temperature annealing schedule
Part 1, original PDF page 69Energy landscapes and optimization1.22
Part 1, original PDF page 69SCIENCEMay Volume Number Optimization Simulated Annealing Kirkpatrick, Gelatt, Vecchi

The transition process from gas to liquid to solid can be seen as an optimization process.

Ingredients:

  • A procedure to explore local configurations
  • A temperature-dependent acceptance criterion for new configurations
  • A temperature annealing schedule
Part 1, original PDF page 70Energy landscapes – Lennard-Jones clusters1.23
Part 1, original PDF page 70•Lennard-Jones potential as pair potential between noble gas atoms •What is the best (lowest potential energy) configuration at temperature T = 0? •How does the energy landscape look like for n number of atoms?rij
f(x)=4ϵLJ∑1≤a<b≤Nat[(σLJrab)12−(σLJrab)6]
  • Lennard–Jones potential as a pair potential between noble gas atoms
  • What is the lowest-energy configuration at temperature T=0?
  • How does the energy landscape look for Nat atoms?
Part 1, original PDF page 71Energy landscapes: basin hopping1.24
Part 1, original PDF page 71Global Optimization by Basin-Hopping and the Lowest Energy Structures of Lennard-JonesClusters Containing up to 110 AtomsDavid J. Wales*Uniersity Chemical Laboratories, Lensfield Road, Cambridge CB2 1EW, U.K.Jonathan P. K. DoyeFOM Institute for Atomic and Molecular Physics, Kruislaan 407, 1098 SJ Amsterdam, The NetherlandsReceied: March 19, 1997; In Final Form: April 29, 1997J. Phys. Chem. A
Global Optimization by Basin-Hopping and the Lowest Energy Structures of Lennard-Jones Clusters Containing up to 110 Atoms

David J. Wales & Jonathan P. K. Doye · 1997

Part 1, original PDF page 72Energy landscapes: basin hopping1.24
Part 1, original PDF page 72Global Optimization by Basin-Hopping and the Lowest Energy Structures of Lennard-JonesClusters Containing up to 110 AtomsDavid J. Wales*Uniersity Chemical Laboratories, Lensfield Road, Cambridge CB2 1EW, U.K.Jonathan P. K. DoyeFOM Institute for Atomic and Molecular Physics, Kruislaan 407, 1098 SJ Amsterdam, The NetherlandsReceied: March 19, 1997; In Final Form: April 29, 1997J. Phys. Chem. A
Global Optimization by Basin-Hopping and the Lowest Energy Structures of Lennard-Jones Clusters Containing up to 110 Atoms

David J. Wales & Jonathan P. K. Doye · 1997

Ingredients:

  • Local minimization, for example gradient descent.
  • Sampling moves and a simulated-annealing acceptance rule.
Part 1, original PDF page 73Energy landscapes: basin hopping1.24
Part 1, original PDF page 73Global Optimization by Basin-Hopping and the Lowest Energy Structures of Lennard-JonesClusters Containing up to 110 AtomsDavid J. Wales*Uniersity Chemical Laboratories, Lensfield Road, Cambridge CB2 1EW, U.K.Jonathan P. K. DoyeFOM Institute for Atomic and Molecular Physics, Kruislaan 407, 1098 SJ Amsterdam, The NetherlandsReceied: March 19, 1997; In Final Form: April 29, 1997J. Phys. Chem. A Figure 2. A schematic diagram illustrating the effects of our energytransformation for a one-dimensional example. The solid line is theenergy of the original surface and the dashed line is the transformedenergy
Global Optimization by Basin-Hopping and the Lowest Energy Structures of Lennard-Jones Clusters Containing up to 110 Atoms

David J. Wales & Jonathan P. K. Doye · 1997

Ingredients:

  • Local minimization, for example gradient descent.
  • Sampling moves and a simulated-annealing acceptance rule.
Original landscape and basin-hopping transformation

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

Part 1, original PDF page 74Energy landscapes - LJ cluster minima1.25
Part 1, original PDF page 74LJ 13
Part 1, original PDF page 75Energy landscapes - LJ cluster minima1.25
Part 1, original PDF page 75LJ 19LJ 13
Part 1, original PDF page 76Energy landscapes - LJ cluster minima1.25
Part 1, original PDF page 76LJ 19 LJ 31LJ 13
Part 1, original PDF page 77Energy landscapes - LJ cluster minima1.25
Part 1, original PDF page 77LJ 19 LJ 31 LJ 38LJ 13
Part 1, original PDF page 78Energy landscapes - LJ cluster minima1.25
Part 1, original PDF page 78LJ 19 LJ 31 LJ 38LJ 13 No!This face-centered cubic octahedron (fcc) structure is the global minimum.
Part 1, original PDF page 79Energy landscapes and the Simons foundation1.26
Part 1, original PDF page 79
Part 1, original PDF page 80Energy landscapes and protein folding1.27
Part 1, original PDF page 80
Part 1, original PDF page 81Energy landscapes and DeepMind’s AlphaFold1.28
Protein sequence to neural network, predicted distances and angles, energy score, gradient descent and structureNature: AI protein-folding algorithms solve structures faster than ever

Build a single-funnel energy landscape approximation

Gradient descent on landscape

Part 1, original PDF page 82Energy landscapes and DNNs1.29
Part 1, original PDF page 82Archetypal landscapes for deep neural networksPhilipp C. Verpoort, Alpha A. Lee, and David J. WalesDepartment of Physics, University of Cambridge, Cambridge CB3 0HE, United Kingdom; and Department of Chemistry, University of Cambridge,Cambridge CB2 1EW, United KingdomEdited by David L. Donoho, Stanford University, Stanford, CA, and approved July 7, 2020 (received for review November 15, 2019)Fig. 1. A DNN. Blue, input; red, output; green, hidden nodes.
Part 1, original PDF page 83Energy landscapes and the 2024 Nobel prize1.30
Part 1, original PDF page 83
Part 1, original PDF page 84Black box landscapes1.31
Part 1, original PDF page 84

Group Q&A

Optimization Landscapes

Part 1, original PDF page 85Want to know more?1.32
Richard Dawkins: Climbing Mount ImprobableDavid J. Wales: Energy LandscapesChristian L. Müller: Black-box Landscapes, PhD thesis (2010)
What we will cover in the rest of the course
Black-box optimization1.34
Only function values: where should we evaluate next?
Black boxInputLoss
\(\mathbf x\longmapsto f(\mathbf x)\)
  • We can evaluate \(f(\mathbf x)\), but have no derivatives.
  • Each evaluation may be expensive.
The input–output view of the same objective.
Black-box optimization1.35
Only function values: where should we evaluate next?
Black boxInputLoss
\(\mathbf x\longmapsto f(\mathbf x)\)
  • Sample points and compare their objective values.
  • Use a fixed design, or let earlier results guide the next samples.
  • Repeat: propose, evaluate, select and adapt.
The input–output view of the same objective.
Which evaluations are worth the remaining budget?
Black-box optimization1.35
Only function values: where should we evaluate next?
Black boxInputLoss
\(\mathbf x\longmapsto f(\mathbf x)\)
  • Sample points and compare their objective values.
  • Use a fixed design, or let earlier results guide the next samples.
  • Repeat: propose, evaluate, select and adapt.
The input–output view of the same objective.
Which evaluations are worth the remaining budget?
Black-box optimization1.35
Only function values: where should we evaluate next?
Black boxInputLoss
\(\mathbf x\longmapsto f(\mathbf x)\)
  • Sample points and compare their objective values.
  • Use a fixed design, or let earlier results guide the next samples.
  • Repeat: propose, evaluate, select and adapt.
The input–output view of the same objective.
Which evaluations are worth the remaining budget?
Gradients1.36
Now we have gradients. Does that make optimization easy?
Existing course example: initial
  • The gradient describes the local slope.
  • A local direction alone does not tell us how far to move.
Same rotated quadratic and starting point used later.
Gradients1.37
Now we have gradients. Does that make optimization easy?
Existing course example: gradient
  • Move in a local descent direction.
  • Choose a step size: too large can overshoot; too small can be slow.
  • Landscape geometry still matters: narrow valleys can slow progress.
Same rotated quadratic and starting point used later.
How much progress does one gradient evaluation buy?
Gradients1.37
Now we have gradients. Does that make optimization easy?
Existing course example: gradient
  • Move in a local descent direction.
  • Choose a step size: too large can overshoot; too small can be slow.
  • Landscape geometry still matters: narrow valleys can slow progress.
Same rotated quadratic and starting point used later.
How much progress does one gradient evaluation buy?
Gradients1.37
Now we have gradients. Does that make optimization easy?
Existing course example: gradient
  • Move in a local descent direction.
  • Choose a step size: too large can overshoot; too small can be slow.
  • Landscape geometry still matters: narrow valleys can slow progress.
Same rotated quadratic and starting point used later.
How much progress does one gradient evaluation buy?
Higher-order information1.38
Could curvature help us choose a better step?
Existing course example: gradient
  • The landscape may bend very differently in different directions.
  • Can local curvature tell us how to adjust the step?
Same quadratic, same start; only the information changes.
Higher-order information1.39
Could curvature help us choose a better step?
Existing course example: curvature
  • Use curvature to adjust the direction and scale of a step.
  • On this quadratic, exact curvature leads directly to the minimizer.
  • Obtaining, storing and using curvature can be expensive.
Same quadratic, same start; only the information changes.
Is the extra information worth its cost at dimension p?
Higher-order information1.39
Could curvature help us choose a better step?
Existing course example: curvature
  • Use curvature to adjust the direction and scale of a step.
  • On this quadratic, exact curvature leads directly to the minimizer.
  • Obtaining, storing and using curvature can be expensive.
Same quadratic, same start; only the information changes.
Is the extra information worth its cost at dimension p?
Higher-order information1.39
Could curvature help us choose a better step?
Existing course example: curvature
  • Use curvature to adjust the direction and scale of a step.
  • On this quadratic, exact curvature leads directly to the minimizer.
  • Obtaining, storing and using curvature can be expensive.
Same quadratic, same start; only the information changes.
Is the extra information worth its cost at dimension p?
Constraints1.40
What if a promising step leaves the feasible set?
Existing course example: proposal
  • The decision must lie in a feasible set \(\mathcal X\).
  • A lower objective value is useful only if the decision is allowed.
Original box-constrained example: proposal, then projection.
Constraints1.41
What if a promising step leaves the feasible set?
Existing course example: projected
  • Take a tentative step and project it back into the feasible set.
  • Or choose a direction and step that stay feasible.
  • The geometry and cost of the constraint operation matter.
Original box-constrained example: proposal, then projection.
Which feasible operations are cheap for this problem?
Constraints1.41
What if a promising step leaves the feasible set?
Existing course example: projected
  • Take a tentative step and project it back into the feasible set.
  • Or choose a direction and step that stay feasible.
  • The geometry and cost of the constraint operation matter.
Original box-constrained example: proposal, then projection.
Which feasible operations are cheap for this problem?
Constraints1.41
What if a promising step leaves the feasible set?
Existing course example: projected
  • Take a tentative step and project it back into the feasible set.
  • Or choose a direction and step that stay feasible.
  • The geometry and cost of the constraint operation matter.
Original box-constrained example: proposal, then projection.
Which feasible operations are cheap for this problem?
Large-scale optimization1.42
What if one full gradient is already too expensive?
Existing course example: initial
  • In learning, one full gradient can require all \(n\) training examples.
  • Could we make useful progress with much less work per update?
Illustrative noisy-gradient run on the same quadratic.
Large-scale optimization1.43
What if one full gradient is already too expensive?
Existing course example: noisy
  • Estimate the gradient from a mini-batch.
  • Use cheaper updates, accepting that their directions are noisy.
  • Balance progress, batch size, memory and total computation.
Illustrative noisy-gradient run on the same quadratic.
Optimize progress per unit of computation, not just per update.
Large-scale optimization1.43
What if one full gradient is already too expensive?
Existing course example: noisy
  • Estimate the gradient from a mini-batch.
  • Use cheaper updates, accepting that their directions are noisy.
  • Balance progress, batch size, memory and total computation.
Illustrative noisy-gradient run on the same quadratic.
Optimize progress per unit of computation, not just per update.
Large-scale optimization1.43
What if one full gradient is already too expensive?
Existing course example: noisy
  • Estimate the gradient from a mini-batch.
  • Use cheaper updates, accepting that their directions are noisy.
  • Balance progress, batch size, memory and total computation.
Illustrative noisy-gradient run on the same quadratic.
Optimize progress per unit of computation, not just per update.
Part 1, original PDF page 85Take-home messages1.44
  • Formulate the decisions x, objective f and feasible set X.
  • Landscapes connect energy, fitness, learning and other scientific problems.
  • Basins, barriers, symmetry and curvature help explain search behavior.
  • Choose a method using the available information, problem size and evaluation budget.
Part 1, original PDF page 85Take-home messages1.44
  • Formulate the decisions x, objective f and feasible set X.
  • Landscapes connect energy, fitness, learning and other scientific problems.
  • Basins, barriers, symmetry and curvature help explain search behavior.
  • Choose a method using the available information, problem size and evaluation budget.
Part 1, original PDF page 85Take-home messages1.44
  • Formulate the decisions x, objective f and feasible set X.
  • Landscapes connect energy, fitness, learning and other scientific problems.
  • Basins, barriers, symmetry and curvature help explain search behavior.
  • Choose a method using the available information, problem size and evaluation budget.
Part 1, original PDF page 85Take-home messages1.44
  • Formulate the decisions x, objective f and feasible set X.
  • Landscapes connect energy, fitness, learning and other scientific problems.
  • Basins, barriers, symmetry and curvature help explain search behavior.
  • Choose a method using the available information, problem size and evaluation budget.
Part 2, original PDF page 1MUDS course optimization Part II2.1
Part 2, original PDF page 1Black-box optimizationChristian L. MüllerInstitute of Computational Biology, Helmholtz MunichDepartment of Statistics, Ludwig-Maximilians-UniversitätCenter for Computational Mathematics, Flatiron Institute, New Yorkch.mueller@lmu.de23/11/2026
Part 2, original PDF page 2Black-box optimization2.2
Part 2, original PDF page 2InputOutputBlack-box system......
x1
x2
xj
xp
f(x)∈R
Part 2, original PDF page 3Black-box optimization2.2
Part 2, original PDF page 3InputOutputBlack-box system......
• Find the minimum of f(x)
•The function is deterministic but nothing is known about it •A finite budget of samples is available •The function is defined on a hypercube
x1
x2
xj
xp
  • Find a minimizer of f:X→R.
  • The objective is deterministic; only function values are supplied.
  • At most Beval function evaluations are available.
  • X=∏j=1p[ℓj,uj] is a box.
f(x)∈R
Part 2, original PDF page 3Black-box optimization2.3
Part 2, original PDF page 3
You can evaluate f(x), but have no gradients.
You have a limited number of function evaluations.
How would you solve this problem?
Where would you evaluate first?
How would you decide what to try next?
Part 2, original PDF page 4Black-box optimization: sampling and designs2.4

Question: how would you spend Beval evaluations?

X=∏j=1p[ℓj,uj],f:X→R
  • Random sampling: draw points independently from a fixed distribution, e.g. uniform sampling.
  • Design: choose points to cover the domain; no observed values are used.
  • Adaptive search: use observed values to decide where to sample next.
x(t,r)∼iidUnif(X),r=1,…,qt

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

Part 2, original PDF page 5Fixed and random designs2.4
Part 2, original PDF page 5Grid search
xp
  • Decide on a Sampling Design beforehand
  • Evaluate the function at the predetermined design Points
  • Collect the Minimum over all Function Evaluations
Part 2, original PDF page 6Grid designs2.5
Part 2, original PDF page 6Grid searchWhen/why is this design useful?
What are the underlying assumptions on f(x)?
xp
Latin hypercube design2.6
Latin hypercube design: progressive comparison of sampling designs
Latin hypercube design2.6
Latin hypercube design: progressive comparison of sampling designs
Latin hypercube design2.6
Latin hypercube design: progressive comparison of sampling designs
Latin hypercube design2.6
Latin hypercube design: progressive comparison of sampling designs

When and why is this design useful?

What are the underlying assumptions on \(f(\mathbf x)\)?

Part 2, original PDF page 11Pure random search2.7
Part 2, original PDF page 11
  • Requires access to “Good” Random Numbers
  • No explicit control of Coverage
Part 2, original PDF page 12Pure random search2.7
Part 2, original PDF page 12Grid Layout Random Layout Unimportant parameterImportant parameterUnimportant parameterImportant parameterJournal of Machine Learning Research 13 (2012) 281-305 Submitted 3/11; Revised 9/11; Published 2/12Random Search for Hyper-Parameter OptimizationJames Bergstra JAMESBERGSTRAUMONTREALYoshua Bengio YOSHUABENGIOUMONTREALepartement d’Informatique et de recherche op erationnelle Universite de Montr eal Montreal, QC, H3C 3J7, Canada Editor: Leon Bottou
Original samples figure
  • Requires good random numbers
  • No explicit control of coverage
Grid layout
Random layout
Original grid figureOriginal random figure

Random Search for Hyper-Parameter Optimization

James Bergstra & Yoshua Bengio
JMLR · 2012

19,624 citations · Google Scholar
Count checked 18 November 2026

Part 2, original PDF page 13Quasi-random search2.8
Part 2, original PDF page 13Quasi-random Pseudo-random
Part 2, original PDF page 14Quasi-random search2.8
Part 2, original PDF page 14Quasi-random Pseudo-random
Part 2, original PDF page 15Quasi-random search2.8
Part 2, original PDF page 15Quasi-random Pseudo-random
Part 2, original PDF page 16Quasi-random search2.8
Part 2, original PDF page 16Quasi-random Pseudo-random
Part 2, original PDF page 17Quasi-random search2.8
Part 2, original PDF page 17Quasi-random Pseudo-randomQuasi-random points Pseudo-random points
Part 2, original PDF page 18Quasi-random search2.8
Part 2, original PDF page 18Quasi-random Pseudo-randomQuasi-random points Pseudo-random points
  • Requires access to “good” low discrepancy sequences
  • Explicit control of coverage
  • Deteriorates in higher dimensions
Part 2, original PDF page 19Quasi-random search2.8
Part 2, original PDF page 1940-Dimensional sobol sequence in dimension 38 vs. 39 https://link.springer.com/book/10.1007/978-90-481-3100-6
Part 2, original PDF page 40Sequential designs2.9
Part 2, original PDF page 40Exploration vs. exploitation
  • Create a procedure that adapts the sampling design in the process
  • Key ingredient: A function that determines where to sample next
  • For optimization, the function needs to balance
Part 2, original PDF page 41Sequential designs2.9
Part 2, original PDF page 41Journal of Global Optimization Kluwer Academic Publishers. Printed in the Netherlands. Efficient Global Optimization of ExpensiveBlack-Box FunctionsDONALD R. JONES, MATTHIAS SCHONLAUand WILLIAM J.WELCHOperations Research Department, General Motors R&D Operations, Warren, MI, USA; NationalInstitute of Statistical Sciences, Research Triangle Park, NC, USA; Department of Statistics andActuarial Science and The Institute for Improvement in Quality and Productivity, University ofWaterloo, Waterloo, Ontario, CanadaJOURNAL OPTIMIZATION THEORY AND APPLICATION: Vol. OCTOBER Lipschitzian Optimization Without the Lipschitz Constant JONES, I~RTTUNEN, AND STUCKMAN Communicated Dixon
  • Adapt the sampling design after observing function values.
  • Decide where to evaluate next.
  • Balance exploration and exploitation.
  • Formulate minimal assumptions about the underlying function, e.g., how “wiggly” a function is.
Lipschitzian Optimization without the Lipschitz Constant

Jones, Perttunen & Stuckman · 1993

Efficient Global Optimization of Expensive Black-Box Functions

Jones, Schonlau & Welch · 1998

Part 2, original PDF page 41Lipschitz continuity2.10
Part 2, original PDF page 41Journal of Global Optimization Kluwer Academic Publishers. Printed in the Netherlands. Efficient Global Optimization of ExpensiveBlack-Box FunctionsDONALD R. JONES, MATTHIAS SCHONLAUand WILLIAM J.WELCHOperations Research Department, General Motors R&D Operations, Warren, MI, USA; NationalInstitute of Statistical Sciences, Research Triangle Park, NC, USA; Department of Statistics andActuarial Science and The Institute for Improvement in Quality and Productivity, University ofWaterloo, Waterloo, Ontario, CanadaJOURNAL OPTIMIZATION THEORY AND APPLICATION: Vol. OCTOBER Lipschitzian Optimization Without the Lipschitz Constant JONES, I~RTTUNEN, AND STUCKMAN Communicated Dixon
Part 2, original PDF page 42The DIRECT method2.11
Part 2, original PDF page 42initial Pointshttps://hosting.cs.vt.edu/hpcs2008/HPCS08DIRECTtut.pdfDIRECT (DIviding-RECTangles) Global Search Algorithm

Only the black-dot function values are available to the algorithm. The colors show the illustrative landscape.

Part 2, original PDF page 43The DIRECT method2.11
Part 2, original PDF page 43after 1 iterationinitial Pointshttps://hosting.cs.vt.edu/hpcs2008/HPCS08DIRECTtut.pdfDIRECT (DIviding-RECTangles) Global Search Algorithm

Question: Which boxes deserve the next evaluations?

A low center value is promising; a large box still leaves room for improvement.

Part 2, original PDF page 44The DIRECT method2.11
Part 2, original PDF page 44after 5 iterations after 1 iterationinitial Pointshttps://hosting.cs.vt.edu/hpcs2008/HPCS08DIRECTtut.pdfDIRECT (DIviding-RECTangles) Global Search Algorithm
Part 2, original PDF page 45The DIRECT method2.11
Part 2, original PDF page 45after 10 iterationsafter 5 iterations after 1 iterationinitial Pointshttps://hosting.cs.vt.edu/hpcs2008/HPCS08DIRECTtut.pdfDIRECT (DIviding-RECTangles) Global Search Algorithm
Part 2, original PDF page 48DIRECT: which boxes deserve refinement?2.12
Part 2, original PDF page 48https://hosting.cs.vt.edu/hpcs2008/HPCS08DIRECTtut.pdfrepresents a potentially optimal boxBox Center Function ValuesBox DiametersminBox selection rule: box is potentially optimal iffor some and (the total number of subdivided boxes)Lipschitz continuity is required in the domain.
Part 2, original PDF page 48DIRECT on the quadratic2.13
Part 2, original PDF page 48https://hosting.cs.vt.edu/hpcs2008/HPCS08DIRECTtut.pdfrepresents a potentially optimal boxBox Center Function ValuesBox DiametersminBox selection rule: box is potentially optimal iffor some and (the total number of subdivided boxes)Lipschitz continuity is required in the domain.
Part 2, original PDF page 51Bayesian optimization2.14
Part 2, original PDF page 51
  • Bayesian optimization is a type of sequential design scheme.
  • An acquisition function guides the next evaluation, balancing exploration and exploitation.
  • Build a surrogate model of the function, often using Gaussian processes (see the directed evolution example).
Jonas Mockus, Bayesian Approach to Global Optimization

Useful tutorial: Distill: Bayesian optimization

Part 2, original PDF page 52Bayesian optimization2.14
Part 2, original PDF page 52
  • Bayesian optimization is a type of sequential design scheme.
  • An acquisition function guides the next evaluation, balancing exploration and exploitation.
  • Build a surrogate model of the function, often using Gaussian processes (see the directed evolution example).
Jonas Mockus, Bayesian Approach to Global Optimization

Useful tutorial: Distill: Bayesian optimization

Practical Bayesian Optimization of Machine Learning Algorithms

Snoek, Larochelle & Adams · 2012

Part 2, original PDF page 53Bayesian optimization2.15
Part 2, original PDF page 53

Deterministic observations yi=f(xi).

Dk={(xi,yi)}i=1k
bk=min1≤i≤kyi

bk = best loss observed so far.

GP surrogate prediction:

F(x)∣Dk∼N(μk(x),sk2(x))

Expected improvement

ak(x)=E[(bk−F(x))+∣Dk]
xk+1∈arg⁡maxx∈Xak(x)

Minimize the loss; maximize the acquisition.

Fit → acquire → evaluate → update.

Minimization GP posterior and expected improvement, matching the course notation
Example p = 1 · Dashed: true loss · Black: GP mean · Dots: observations
Part 2, original PDF page 54Bayesian optimization2.15
Part 2, original PDF page 54

Deterministic observations yi=f(xi).

Dk={(xi,yi)}i=1k
bk=min1≤i≤kyi

bk = best loss observed so far.

GP surrogate prediction:

F(x)∣Dk∼N(μk(x),sk2(x))

Expected improvement

ak(x)=E[(bk−F(x))+∣Dk]
xk+1∈arg⁡maxx∈Xak(x)

Minimize the loss; maximize the acquisition.

Fit → acquire → evaluate → update.

Minimization GP posterior and expected improvement, matching the course notation
Example p = 1 · Dashed: true loss · Black: GP mean · Dots: observations
Part 2, original PDF page 55Bayesian optimization2.15
Part 2, original PDF page 55

Deterministic observations yi=f(xi).

Dk={(xi,yi)}i=1k
bk=min1≤i≤kyi

bk = best loss observed so far.

GP surrogate prediction:

F(x)∣Dk∼N(μk(x),sk2(x))

Expected improvement

ak(x)=E[(bk−F(x))+∣Dk]
xk+1∈arg⁡maxx∈Xak(x)

Minimize the loss; maximize the acquisition.

Fit → acquire → evaluate → update.

Minimization GP posterior and expected improvement, matching the course notation
Example p = 1 · Dashed: true loss · Black: GP mean · Dots: observations
Part 2, original PDF page 55Bayesian optimization on the quadratic2.16
Part 2, original PDF page 55Minimization GP posterior and expected improvement, matching the course notation
Example p = 1 · Dashed: true loss · Black: GP mean · Dots: observations
Part 2, original PDF page 55Landscape features from samples2.17
Part 2, original PDF page 55Minimization GP posterior and expected improvement, matching the course notation
Example p = 1 · Dashed: true loss · Black: GP mean · Dots: observations
DIRECT and Bayesian optimization are useful when the dimension and evaluation budget permit.
In higher dimensions, what can a first sample
tell us about the landscape?
Estimate useful characteristics of the function,
then use what we learn to guide further search.
Part 2, original PDF page 23Excursion: landscape analysis from samples2.18
Part 2, original PDF page 23Exploratory Landscape AnalysisOlaf MersmannTU Dortmund, Germanyolafm@statistik.tudortmund.deBernd BischlTU Dortmund, Germanybischl@statistik.tudortmund.deHeike TrautmannTU Dortmund, Germanytrautmann@statistik.tudortmund.deMike PreussTU Dortmund, Germanymike.preuss@tudortmund.deClaus WeihsTU Dortmund, Germanyweihs@statistik.tudortmund.deGünter RudolphTU Dortmund, Germanyguenter.rudolph@tudortmund.de
Part 2, original PDF page 24Landscape analysis2.19
Part 2, original PDF page 24

Use (uniform) samples in the landscape domain and estimate topographical features of the landscape.

x1
x2
Part 2, original PDF page 25Landscape analysis2.19
Part 2, original PDF page 25

Use (uniform) samples in the landscape domain and estimate topographical features of the landscape.

x1
x2
x(r)
Part 2, original PDF page 26Landscape analysis2.19
Part 2, original PDF page 26

Use (uniform) samples in the landscape domain and estimate topographical features of the landscape.

x1
x2
x(r)
Describe the landscape with a list of scalar landscape “fingerprints” or features.
Part 2, original PDF page 27Landscape analysis2.19
Part 2, original PDF page 27

Use (uniform) samples in the landscape domain and estimate topographical features of the landscape.

x1
x2
x(r)
Describe the landscape with a list of scalar landscape “fingerprints” or features.
Depending on the features, select an appropriate optimization algorithm in a second phase.
Part 2, original PDF page 28Landscape features2.20
Part 2, original PDF page 28
Part 2, original PDF page 29Landscape features2.20
Part 2, original PDF page 29

Fitness-distance correlation

  • Measures how distance to the optimum is related to fitness of candidate solutions
  • Scatter plots/correlation coefficient
Part 2, original PDF page 30Landscape features2.20
Part 2, original PDF page 30

Fitness-distance correlation

  • Measures how distance to the optimum is related to fitness of candidate solutions
  • Scatter plots/correlation coefficient

Function dispersion

  • Measures single- or multi-funnel character of the landscape
  • Threshold-dependent dispersion difference
Part 2, original PDF page 31Landscape features2.20
Part 2, original PDF page 31

Fitness-distance correlation

  • Measures how distance to the optimum is related to fitness of candidate solutions
  • Scatter plots/correlation coefficient

Function dispersion

  • Measures single- or multi-funnel character of the landscape
  • Threshold-dependent dispersion difference

Separability/interaction

  • Measures variable importance and interaction between variables
  • Morris’ sensitivity analysis used to identify elementary effects
Part 2, original PDF page 32Landscape features2.20
Part 2, original PDF page 32

Fitness-distance correlation

  • Measures how distance to the optimum is related to fitness of candidate solutions
  • Scatter plots/correlation coefficient

Function dispersion

  • Measures single- or multi-funnel character of the landscape
  • Threshold-dependent dispersion difference

Separability/interaction

  • Measures variable importance and interaction between variables
  • Morris’ sensitivity analysis used to identify elementary effects

Landscape ruggedness

  • Measures the roughness or ruggedness of the surface over the entire landscape domain
  • Random-walk autocorrelation
Part 2, original PDF page 33Fitness distance correlation2.21
Part 2, original PDF page 33(i) x xmin
Part 2, original PDF page 34Fitness distance correlation2.21
Part 2, original PDF page 34(i) (i) x xmind E
Part 2, original PDF page 35Fitness distance correlation2.21
Part 2, original PDF page 352202005 60011001200(i) (i) x xmind E
p=10
Part 2, original PDF page 36Fitness distance correlation2.21
Part 2, original PDF page 362202005 60011001200(i) (i) x xmind E
p=10
Part 2, original PDF page 37Fitness distance correlation2.21
Part 2, original PDF page 375 10 152802602402202005 10 15 600700800900100011001200(i) (i) x xmind E
p=10
Part 2, original PDF page 38Fitness distance correlation2.22
Part 2, original PDF page 38Single-funnel landscape? Double-funnel landscape?
Part 2, original PDF page 39Fitness distance correlation2.22
Part 2, original PDF page 39Single-funnel landscape? Double-funnel landscape?Are there algorithms that can exploit those features?
Part 2, original PDF page 58Constructing an iterative scheme2.23

How would you construct an iterative optimization scheme?

You can evaluate f(x), but no derivatives are available.
How should earlier evaluations influence the next samples?

Part 2, original PDF page 59Constructing an iterative scheme2.23

How would you construct an iterative optimization scheme?

You can evaluate f(x), but no derivatives are available.
How should earlier evaluations influence the next samples?

Where do we sample next?
Which candidates do we select?
What do we learn from success and failure?
When should we stop?
Part 2, original PDF page 59Constructing an iterative scheme2.24
Part 2, original PDF page 59

One possible iterative scheme

1. Sample and evaluate

Maintain a search state St and draw qt candidates from its sampling distribution Pt:

x(t,r)∼Pt,yt,r=f(x(t,r)),r=1,…,qt.
Part 2, original PDF page 59Constructing an iterative scheme2.24
Part 2, original PDF page 59

One possible iterative scheme

1. Sample and evaluate

Maintain a search state St and draw qt candidates from its sampling distribution Pt:

x(t,r)∼Pt,yt,r=f(x(t,r)),r=1,…,qt.

2. Select

Compare the evaluated candidates. Keep useful candidates or rank them:

yt,(1)≤⋯≤yt,(qt).

For example: accept an improving candidate, or select several highly ranked candidates.

Part 2, original PDF page 59Constructing an iterative scheme2.24
Part 2, original PDF page 59

One possible iterative scheme

1. Sample and evaluate

Maintain a search state St and draw qt candidates from its sampling distribution Pt:

x(t,r)∼Pt,yt,r=f(x(t,r)),r=1,…,qt.

2. Select

Compare the evaluated candidates. Keep useful candidates or rank them:

yt,(1)≤⋯≤yt,(qt).

For example: accept an improving candidate, or select several highly ranked candidates.

3. Update the search

Use the observations and selection to update St, then construct Pt+1.

Move the search center? Change the sampling radius? Learn promising directions?

Part 2, original PDF page 59Constructing an iterative scheme2.24
Part 2, original PDF page 59

One possible iterative scheme

1. Sample and evaluate

Maintain a search state St and draw qt candidates from its sampling distribution Pt:

x(t,r)∼Pt,yt,r=f(x(t,r)),r=1,…,qt.

2. Select

Compare the evaluated candidates. Keep useful candidates or rank them:

yt,(1)≤⋯≤yt,(qt).

For example: accept an improving candidate, or select several highly ranked candidates.

3. Update the search

Use the observations and selection to update St, then construct Pt+1.

Move the search center? Change the sampling radius? Learn promising directions?

4. Repeat within the budget

kt+1=kt+qt,qt≤Beval−kt.

Repeat while evaluations remain. Retain the best evaluated point and its value.

Part 2, original PDF page 60Designing the search2.25

What properties should our iterative scheme have?

  • Generate candidates cheaply and respect the feasible domain.
  • Make fast progress on easy functions; retain exploration on difficult ones.
  • Use rankings when only relative performance matters: strictly increasing transformations of the objective preserve rankings.
  • Adapt directions and scales to the geometry of the problem.
  • Account for dimension, evaluation cost, noise and the remaining budget.

These are design goals. Their guarantees depend on the particular algorithm.

Part 2, original PDF page 61Normal distribution as search operator2.26
Part 2, original PDF page 61•completely described by a mean vector and a covariance matrix (which is positive definite) •Convenient geometric interpretation•Following Jaynes’ Maximum Entropy Principle it is the least biased choice among all distributions for fi xed fi rst and second moment•Easily extendible to convex domains via the truncated multivariate normal distribution
  • N(mt,Ct) is specified by a mean mt∈Rp and positive-definite covariance Ct∈Rp×p.
  • Its level sets have an ellipsoidal interpretation.
  • For a fixed mean and covariance, the Gaussian maximizes differential entropy.
  • On constrained domains, a truncated Gaussian can be used; its moments require care.
Figure: μj=(mt)j;λj=covariance eigenvalue
Part 2, original PDF page 62Adaptive directional sampling2.27

How can successful samples change the next search?

z(t,r)∼N(0,Ip),x(t,r)=mt+Ltz(t,r)
Ct=LtLt⊤,r=1,…,qt,kt+1=kt+qt
  • The mean mt controls where we search.
  • The covariance Ct controls which directions and scales we explore.
  • Evaluate, compare, adapt; repeat until the evaluation budget is spent.

These are random search directions learned from function values; derivatives are not required.

Part 2, original PDF page 62Local improvement: (1+1)-ES2.28
Part 2, original PDF page 62
Part 2, original PDF page 62Learning search directions2.29
Part 2, original PDF page 62
Part 2, original PDF page 68Gaussian adaptation2.30

Gaussian adaptation (GaA): learn a Gaussian search region from accepted candidates.

x(t,1)=mt+rtQtzt,zt∼N(0,Ip),detQt=1

rt sets the scale; Qt sets shape and orientation; qt=1.

Part 2, original PDF page 69Gaussian adaptation2.30

Gaussian adaptation (GaA): learn a Gaussian search region from accepted candidates.

x(t,1)=mt+rtQtzt,zt∼N(0,Ip),detQt=1

rt sets the scale; Qt sets shape and orientation; qt=1.

Acceptance region

At={x∈X:f(x)<ct}

ct is a moving loss threshold. Evaluate the candidate once.

Part 2, original PDF page 70Gaussian adaptation2.30

Gaussian adaptation (GaA): learn a Gaussian search region from accepted candidates.

x(t,1)=mt+rtQtzt,zt∼N(0,Ip),detQt=1

rt sets the scale; Qt sets shape and orientation; qt=1.

Acceptance region

At={x∈X:f(x)<ct}

ct is a moving loss threshold. Evaluate the candidate once.

  • Accepted: move the mean toward the candidate, adapt the shape, and expand.
  • Rejected: retain mean and shape, and contract.
Part 2, original PDF page 71Gaussian adaptation: learn from success2.31

Accepted candidate: learn from its direction

mt+1=(1−1τm)mt+1τmx(t,1),τm≥1

τm controls mean-update memory. Update the shape toward successful displacements and increase rt.

Part 2, original PDF page 72Gaussian adaptation: learn from success2.31

Accepted candidate: learn from its direction

mt+1=(1−1τm)mt+1τmx(t,1),τm≥1

τm controls mean-update memory. Update the shape toward successful displacements and increase rt.

Rejected candidate: reduce the search scale

mt+1=mt,Qt+1=Qt,rt+1<rt
Part 2, original PDF page 73Gaussian adaptation: learn from success2.31

Accepted candidate: learn from its direction

mt+1=(1−1τm)mt+1τmx(t,1),τm≥1

τm controls mean-update memory. Update the shape toward successful displacements and increase rt.

Rejected candidate: reduce the search scale

mt+1=mt,Qt+1=Qt,rt+1<rt

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.

Part 2, original PDF page 74Gaussian adaptation2.32
Part 2, original PDF page 74
Part 2, original PDF page 78Example: Rosenbrock’s function in 20 dimensions2.33
Part 2, original PDF page 78
Part 2, original PDF page 79Example: Rosenbrock’s function in 20 dimensions2.33
Part 2, original PDF page 79
Part 2, original PDF page 84Gradient-free optimization with CMA-ES2.34
Part 2, original PDF page 84
Part 2, original PDF page 83Gradient-free optimization with CMA-ES2.34
Part 2, original PDF page 83
Part 2, original PDF page 85Gradient-free optimization with CMA-ES2.34
Part 2, original PDF page 85
Part 2, original PDF page 86Gradient-free optimization with CMA-ES2.34
Part 2, original PDF page 86
Part 2, original PDF page 87CMA-ES: sample, rank, adapt2.35

Sample qt candidates from the current search distribution.

x(t,r)∼iidN(mt,σt2Ct),r=1,…,qt
Part 2, original PDF page 88CMA-ES: sample, rank, adapt2.35

Sample qt candidates from the current search distribution.

x(t,r)∼iidN(mt,σt2Ct),r=1,…,qt

Evaluate and rank by increasing loss. kt+1=kt+qt.

Part 2, original PDF page 89CMA-ES: sample, rank, adapt2.35

Sample qt candidates from the current search distribution.

x(t,r)∼iidN(mt,σt2Ct),r=1,…,qt

Evaluate and rank by increasing loss. kt+1=kt+qt.

Move the mean toward the best msel candidates:

mt+1=∑r=1mselwrx(t,r:qt),wr>0,∑rwr=1
Part 2, original PDF page 90CMA-ES: sample, rank, adapt2.35

Sample qt candidates from the current search distribution.

x(t,r)∼iidN(mt,σt2Ct),r=1,…,qt

Evaluate and rank by increasing loss. kt+1=kt+qt.

Move the mean toward the best msel candidates:

mt+1=∑r=1mselwrx(t,r:qt),wr>0,∑rwr=1

Learn directions: covariance adaptation uses successful displacements and their accumulated history.

Part 2, original PDF page 91CMA-ES: sample, rank, adapt2.35

Sample qt candidates from the current search distribution.

x(t,r)∼iidN(mt,σt2Ct),r=1,…,qt

Evaluate and rank by increasing loss. kt+1=kt+qt.

Move the mean toward the best msel candidates:

mt+1=∑r=1mselwrx(t,r:qt),wr>0,∑rwr=1

Learn directions: covariance adaptation uses successful displacements and their accumulated history.

Adapt scale: σt controls the overall step size; Ct controls shape and orientation.

GaA: one candidate and an acceptance threshold. CMA-ES: a ranked population and weighted recombination. Neither needs gradients.

Part 2, original PDF page 92CMA-ES on Rastrigin function2.36
Part 2, original PDF page 92
f(x)=10p+∑j=1p[xj2−10cos⁡(2πxj)]
Part 2, original PDF page 93CMA-ES on Rastrigin function2.36
Part 2, original PDF page 93
f(x)=10p+∑j=1p[xj2−10cos⁡(2πxj)]
Part 2, original PDF page 94CMA-ES on Rastrigin’s function2.37
Part 2, original PDF page 94
Part 2, original PDF page 94Multiple funnels2.38
Part 2, original PDF page 94
What if one adaptive search
concentrates in the wrong funnel?
Learning a useful local search distribution
does not guarantee that we have found the best basin.
Part 2, original PDF page 94Parallel searches and restarts2.39
Part 2, original PDF page 94
Original course illustration of several search populations in different regions

Explore more than one basin.

  • Run several searches from different starting points.
  • Or restart a search with a new initialization.
  • Share the total evaluation budget across runs; compare their best observed values.

Parallel runs can reduce wall-clock time when resources are available. They still consume evaluations.

Part 2, original PDF page 94Parallel searches and restarts2.39
Part 2, original PDF page 94
Original course illustration of several search populations in different regions

Explore more than one basin.

  • Run several searches from different starting points.
  • Or restart a search with a new initialization.
  • Share the total evaluation budget across runs; compare their best observed values.

Parallel runs can reduce wall-clock time when resources are available. They still consume evaluations.

Part 2, original PDF page 94IPOP-CMA-ES: increasing populations2.40
Part 2, original PDF page 94
CMA-ES for hyperparameter tuning
Original Loshchilov and Hutter paper header and abstract

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

2.41
The hyperparameter search space2.42
Table 1: hyperparameters, transformations and ranges

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

CMA-ES for hyperparameter tuning2.43
Original MNIST hyperparameter benchmark, Figure 2
  • Tune a CNN on MNIST; the parallel experiment uses 30 GPUs.
  • Compare validation error against evaluations and training budget. The two panels use different evaluation budgets.
ES at scale2.44
Evolution Strategies at Scale: paper title and authors
Original Figure 1, reward versus KL divergence

Higher reward and lower KL divergence are better.
Blue: ES Pareto front; black: GRPO Pareto front.

  • Gaussian ES fine-tunes billion-parameter LLMs without backpropagation.
  • Reasoning runs use 30 candidates; regenerate perturbations from random seeds.
  • Figure 1: ES improves the reward–KL trade-off in this comparison.
Part 2, original PDF page 94Take-home messages2.45
  • Choose designs, DIRECT or Bayesian optimization with dimension and evaluation cost in mind.
  • Use a first sample to estimate landscape characteristics, then adapt further search.
  • GaA and CMA-ES learn useful sampling scales and directions.
  • Explore multiple basins using parallel searches or restarts under one total budget.
Part 2, original PDF page 94Take-home messages2.45
  • Choose designs, DIRECT or Bayesian optimization with dimension and evaluation cost in mind.
  • Use a first sample to estimate landscape characteristics, then adapt further search.
  • GaA and CMA-ES learn useful sampling scales and directions.
  • Explore multiple basins using parallel searches or restarts under one total budget.
Part 2, original PDF page 94Take-home messages2.45
  • Choose designs, DIRECT or Bayesian optimization with dimension and evaluation cost in mind.
  • Use a first sample to estimate landscape characteristics, then adapt further search.
  • GaA and CMA-ES learn useful sampling scales and directions.
  • Explore multiple basins using parallel searches or restarts under one total budget.
Part 2, original PDF page 94Take-home messages2.45
  • Choose designs, DIRECT or Bayesian optimization with dimension and evaluation cost in mind.
  • Use a first sample to estimate landscape characteristics, then adapt further search.
  • GaA and CMA-ES learn useful sampling scales and directions.
  • Explore multiple basins using parallel searches or restarts under one total budget.
Part 3, original PDF page 1MUDS course optimization Part III3.1
Part 3, original PDF page 1Gradients and curvatureChristian L. MüllerInstitute of Computational Biology, Helmholtz MunichDepartment of Statistics, Ludwig-Maximilians-UniversitätCenter for Computational Mathematics, Flatiron Institute, New Yorkch.mueller@lmu.de23/11/2026
Part 3, original PDF page 2MUDS course optimization Part III3.1
Part 3, original PDF page 2Christian L. MüllerInstitute of Computational Biology, Helmholtz MunichDepartment of Statistics, Ludwig-Maximilians-UniversitätCenter for Computational Mathematics, Flatiron Institute, New Yorkch.mueller@lmu.de23/11/2026
Part 3, original PDF page 5Gradient and curvature3.2
  • The gradient of the function is available.
  • The function can be high-dimensional.
  • Higher-order information may also be available.
\(f(\mathbf x)=(1-x_1)^2+100(x_2-x_1^2)^2,\qquad \mathbf x\in\mathbb R^2.\)

Gradient: local slope

\[\nabla f(\mathbf x)=\begin{pmatrix}\frac{\partial f}{\partial x_1}\\[3pt]\frac{\partial f}{\partial x_2}\end{pmatrix}=\begin{pmatrix}2(x_1-1)-400x_1(x_2-x_1^2)\\200(x_2-x_1^2)\end{pmatrix}.\]

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

Part 3, original PDF page 5Gradient and curvature3.2
  • The gradient of the function is available.
  • The function can be high-dimensional.
  • Higher-order information may also be available.
\(f(\mathbf x)=(1-x_1)^2+100(x_2-x_1^2)^2,\qquad \mathbf x\in\mathbb R^2.\)

Gradient: local slope

\[\nabla f(\mathbf x)=\begin{pmatrix}\frac{\partial f}{\partial x_1}\\[3pt]\frac{\partial f}{\partial x_2}\end{pmatrix}=\begin{pmatrix}2(x_1-1)-400x_1(x_2-x_1^2)\\200(x_2-x_1^2)\end{pmatrix}.\]

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

Part 3, original PDF page 5Gradient and curvature3.2
  • The gradient of the function is available.
  • The function can be high-dimensional.
  • Higher-order information may also be available.
\(f(\mathbf x)=(1-x_1)^2+100(x_2-x_1^2)^2,\qquad \mathbf x\in\mathbb R^2.\)

Gradient: local slope

\[\nabla f(\mathbf x)=\begin{pmatrix}\frac{\partial f}{\partial x_1}\\[3pt]\frac{\partial f}{\partial x_2}\end{pmatrix}=\begin{pmatrix}2(x_1-1)-400x_1(x_2-x_1^2)\\200(x_2-x_1^2)\end{pmatrix}.\]

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

Part 3, original PDF page 5Gradient and curvature3.2
  • The gradient of the function is available.
  • The function can be high-dimensional.
  • Higher-order information may also be available.
\(f(\mathbf x)=(1-x_1)^2+100(x_2-x_1^2)^2,\qquad \mathbf x\in\mathbb R^2.\)

Gradient: local slope

\[\nabla f(\mathbf x)=\begin{pmatrix}\frac{\partial f}{\partial x_1}\\[3pt]\frac{\partial f}{\partial x_2}\end{pmatrix}=\begin{pmatrix}2(x_1-1)-400x_1(x_2-x_1^2)\\200(x_2-x_1^2)\end{pmatrix}.\]

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

Part 3, original PDF page 5Gradient and curvature3.2
  • The gradient of the function is available.
  • The function can be high-dimensional.
  • Higher-order information may also be available.
\(f(\mathbf x)=(1-x_1)^2+100(x_2-x_1^2)^2,\qquad \mathbf x\in\mathbb R^2.\)

Hessian: local curvature

\[\mathbf H(\mathbf x)=\nabla^2f(\mathbf x)=\left[\frac{\partial^2 f}{\partial x_i\partial x_j}\right]_{i,j=1}^2\]\[=\begin{pmatrix}1200x_1^2-400x_2+2&-400x_1\\-400x_1&200\end{pmatrix}.\]
At \(\mathbf x=(-0.8,\,0.5)^\top\):\[\mathbf H(\mathbf x)=\begin{pmatrix}570&320\\320&200\end{pmatrix}.\]

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

First-order optimization3.3
  • The gradient \(\nabla f(\mathbf x)\) is available.
  • Assume \(f\) has an \(L\)-Lipschitz continuous gradient.
\(f(\mathbf y)\le f(\mathbf x)+\nabla f(\mathbf x)^\top(\mathbf y-\mathbf x)+\frac L2\|\mathbf y-\mathbf x\|_2^2.\)

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

First-order optimization3.3
First-order optimization3.3
  • The gradient \(\nabla f(\mathbf x)\) is available.
  • Assume \(f\) has an \(L\)-Lipschitz continuous gradient.
\(f(\mathbf y)\le f(\mathbf x)+\nabla f(\mathbf x)^\top(\mathbf y-\mathbf x)+\frac L2\|\mathbf y-\mathbf x\|_2^2.\)

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

First-order optimization3.3
  • The gradient \(\nabla f(\mathbf x)\) is available.
  • Assume \(f\) has an \(L\)-Lipschitz continuous gradient.
\(f(\mathbf y)\le f(\mathbf x)+\nabla f(\mathbf x)^\top(\mathbf y-\mathbf x)+\frac L2\|\mathbf y-\mathbf x\|_2^2.\)

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

First-order optimization3.3
  • The gradient \(\nabla f(\mathbf x)\) is available.
  • Assume \(f\) has an \(L\)-Lipschitz continuous gradient.
Part 3, original PDF page 9Gradient descent step sizes3.4
Part 3, original PDF page 9
·····   Level sets of f
⟶   Gradient update
ηηηη
Part 3, original PDF page 10Gradient descent step sizes3.4
Part 3, original PDF page 10
·····   Level sets of f
⟶   Gradient update
ηηηη
Part 3, original PDF page 11Second-order optimization (on smooth functions)3.5
Part 3, original PDF page 11
  • The gradient gives a good local direction
  • Invariance principles from black-box optimization are also desirable here
  • Maybe higher-order information is available, i.e. the function is twice differentiable
Part 3, original PDF page 17Let’s consider smooth functions3.6
Part 3, original PDF page 17Newton’s method: finding a zero

Newton–Raphson in one dimension

Goal: find a zero of a differentiable scalar function r:R→R.

xt+1=xt−r(xt)r′(xt)
r(xt)+r′(xt)(x−xt)=0

The tangent intercept gives the next iterate; require a nonzero denominator.

r(x)
r(xt)+r′(xt)(x−xt)
Part 3, original PDF page 20Let’s consider smooth functions3.6
Part 3, original PDF page 20Newton’s method: finding a zero

Newton–Raphson in one dimension

Goal: find a zero of a differentiable scalar function r:R→R.

xt+1=xt−r(xt)r′(xt)
r(xt)+r′(xt)(x−xt)=0

The tangent intercept gives the next iterate; require a nonzero denominator.

r(x)
r(xt)+r′(xt)(x−xt)
Part 3, original PDF page 21From roots to optimization3.7

To minimize f, look for a zero of its derivative.

r(x)=f′(x),r′(x)=f″(x).

Apply Newton’s root-finding step to r=f′:

xt+1=xt−r(xt)r′(xt)=xt−f′(xt)f″(xt).

A zero of f′ is a stationary point. If f″(x⋆)>0, it is a strict local minimum.

In several dimensions: solve ∇f(x)=0; the Hessian is the derivative of the gradient.

Nonzero curvature is required for the scalar step. Damping and curvature safeguards are needed for reliable minimization.

Second-order optimization3.8
  • The gradient and Hessian of \(f\) are available, giving local slope and curvature information.
  • The function is moderately high-dimensional.
  • The gradient is Lipschitz continuous with constant \(L\).
Newton’s method3.8

Find a zero of the gradient using local curvature.

\[\mathbf g_t=\nabla f(\mathbf x_t),\qquad\mathbf H_t=\nabla^2f(\mathbf x_t).\]

Linearize the gradient and set it to zero:

\[\mathbf0\approx\mathbf g_t+\mathbf H_t\mathbf d_t,\qquad\mathbf H_t\mathbf d_t=-\mathbf g_t.\]
\[\mathbf x_{t+1}=\mathbf x_t+\eta_t\mathbf d_t,\qquad\eta_t>0.\]
  • Solve a linear system; an explicit inverse is unnecessary.
  • For positive-definite \(\mathbf H_t\) and nonzero \(\mathbf g_t\), \(\mathbf d_t\) is a descent direction.
  • Choose a suitable step length; safeguard indefinite or singular curvature.

Next: compare this curvature-scaled step with gradient descent.

Newton’s method3.8

Find a zero of the gradient using local curvature.

\[\mathbf g_t=\nabla f(\mathbf x_t),\qquad\mathbf H_t=\nabla^2f(\mathbf x_t).\]

Linearize the gradient and set it to zero:

\[\mathbf0\approx\mathbf g_t+\mathbf H_t\mathbf d_t,\qquad\mathbf H_t\mathbf d_t=-\mathbf g_t.\]
\[\mathbf x_{t+1}=\mathbf x_t+\eta_t\mathbf d_t,\qquad\eta_t>0.\]
  • Solve a linear system; an explicit inverse is unnecessary.
  • For positive-definite \(\mathbf H_t\) and nonzero \(\mathbf g_t\), \(\mathbf d_t\) is a descent direction.
  • Choose a suitable step length; safeguard indefinite or singular curvature.

Next: compare this curvature-scaled step with gradient descent.

Part 3, original PDF page 14Newton’s method3.9
Part 3, original PDF page 14
Part 3, original PDF page 15Second-order optimization and approximations3.10
  • Dense Hessian storage costs O(p2).
  • Indefinite curvature and saddle points require safeguards.
  • Variable-metric methods approximate curvature using gradient information.
Complete Davidon paper header, abstract, keywords and classification
Part 3, original PDF page 16Quasi-Newton methods3.11

Can we learn curvature from gradients alone?

A dense Hessian costs O(p2) storage and may be expensive to form.

What information do two successive gradients give us?

Part 3, original PDF page 22Quasi-Newton methods3.12

Approximate Newton–Raphson in one dimension

xt+1=xt−r(xt)r′(xt)

Replace the derivative by the finite difference

r′(xt)≈r(xt)−r(xt−1)xt−xt−1

to obtain the secant method

xt+1=xt−r(xt)xt−xt−1r(xt)−r(xt−1)

Two distinct previous points and a nonzero function difference are required.

Part 3, original PDF page 23Quasi-Newton methods3.13
Part 3, original PDF page 23
r(x)
  • Construct the line through (xt−1,r(xt−1)) and (xt,r(xt)).
  • The next iterate xt+1 is its horizontal-axis intercept.
Part 3, original PDF page 24Quasi-Newton methods3.14

A derivative-free root solver becomes a second-derivative-free optimization method by applying it to r=f′.

xt+1=xt−f′(xt)xt−xt−1f′(xt)−f′(xt−1)

First derivatives are still required. The method approximates curvature from changes in the gradient.

Can we generalize this to p dimensions without evaluating a Hessian?

Part 3, original PDF page 25Quasi-Newton methods3.15

In one dimension, approximate curvature from two gradients:

Bt+1=f′(xt+1)−f′(xt)xt+1−xt,Bt+1st=Δgt.

In several dimensions, define the secant pair

st=xt+1−xt,qt=gt+1−gt

The Hessian approximation must satisfy

Bt+1st=qt,Bt∈Rp×p

At the current step, solve Btdt=−gt and set xt+1=xt+ηtdt.

Part 3, original PDF page 26Quasi-Newton methods3.16

Newton uses Ht=∇2f(xt); quasi-Newton uses an approximation Bt.

qt≈Htst,Bt+1st=qt
  • p=1: the secant equation determines one scalar curvature when st≠0.
  • p>1: it generally leaves many possible symmetric matrices; additional update rules are needed.
  • Use At for an inverse-Hessian approximation: At+1qt=st.
dt=−Atgt,xt+1=xt+ηtdt

Positive-definite updates and line-search conditions provide descent safeguards.

Part 3, original PDF page 27Quasi-Newton updates: Hessian3.17
Part 3, original PDF page 27
st=xt+1−xt,qt=gt+1−gt,r=(q⊤s)−1.

Write B,A,s,q for the current quantities; A approximates the inverse Hessian. Suppress the step index in the updates below.

BFGS
B−Bss⊤Bs⊤Bs+qq⊤q⊤s
Broyden
B+(q−Bs)s⊤s⊤s
DFP
(I−rqs⊤)B(I−rsq⊤)+rqq⊤
SR1
B+(q−Bs)(q−Bs)⊤(q−Bs)⊤s

All denominators must be nonzero. BFGS preserves positive definiteness under the curvature condition q⊤s>0; Broyden’s general rank-one update need not preserve symmetry.

Symmetric Broyden class: Bt+1=(1−ϕt)Bt+1BFGS+ϕtBt+1DFP,ϕt∈[0,1].
Part 3, original PDF page 27Quasi-Newton updates: inverse Hessian3.18
Part 3, original PDF page 27
st=xt+1−xt,qt=gt+1−gt,r=(q⊤s)−1.

Write B,A,s,q for the current quantities; A approximates the inverse Hessian. Suppress the step index in the updates below.

BFGS
(I−rsq⊤)A(I−rqs⊤)+rss⊤
Broyden
A+(s−Aq)s⊤As⊤Aq
DFP
A+ss⊤s⊤q−Aqq⊤Aq⊤Aq
SR1
A+(s−Aq)(s−Aq)⊤(s−Aq)⊤q

All denominators must be nonzero. BFGS preserves positive definiteness under the curvature condition q⊤s>0; Broyden’s general rank-one update need not preserve symmetry.

Symmetric Broyden class: Bt+1=(1−ϕt)Bt+1BFGS+ϕtBt+1DFP,ϕt∈[0,1].
Part 3, original PDF page 27BFGS3.19
Part 3, original PDF page 27
L-BFGS: limited memory3.20
  • BFGS stores a dense \(\mathbf A_t\in\mathbb R^{p\times p}\): \(O(p^2)\) memory.
  • L-BFGS keeps only the latest \(m\) displacement–gradient pairs:
\[\mathbf s_i=\mathbf x_{i+1}-\mathbf x_i,\qquad\mathbf y_i=\nabla f(\mathbf x_{i+1})-\nabla f(\mathbf x_i).\]
  • Discard the oldest pair when the memory is full.
  • Compute \(\mathbf d_t=-\mathbf A_t\mathbf g_t\) without forming \(\mathbf A_t\).
Storage and direction computation: \(O(mp)\), with \(m\ll p\).
L-BFGS: a low-rank correction3.21
  • Store the latest \(m\) pairs \((\mathbf s_i,\mathbf y_i)\).
  • Approximate the inverse Hessian by a scaled identity plus a correction of rank at most \(2m\).
Aₜ =+=δₜ IUₜMₜUₜᵀAₜscaled identitylow-rank correctionimplicit full matrix
\(\mathbf A_t=\delta_t\mathbf I+\mathbf U_t\mathbf M_t\mathbf U_t^\top,\qquad\mathbf U_t\in\mathbb R^{p\times r},\quad r\le2m.\)

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

L-BFGS in practice3.22
  • Useful for large, smooth problems when gradients are reliable and a dense BFGS matrix is too expensive.
  • Choose the step length \(\eta_t\) with a line search; Wolfe conditions support positive curvature pairs.
  • Skip or safeguard pairs when \(\mathbf s_i^\top\mathbf y_i\le0\).
  • Limited memory trades older curvature information for lower storage and computation.
  • For box constraints, use a suitable extension such as L-BFGS-B.

Curvature information from gradient differences.
Limited storage of the most recent correction pairs.

Newton, BFGS and L-BFGS in science3.23
ProblemNewton / Newton-typeBFGSL-BFGS
Likelihood fittingLogistic 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 estimationModel 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 minimizationRefine 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.

Part 3, original PDF page 28Combine first-order methods with sampling3.24
Part 3, original PDF page 28Global Optimization by Basin-Hopping and the Lowest Energy Structures of Lennard-JonesClusters Containing up to 110 AtomsDavid J. Wales*Uniersity Chemical Laboratories, Lensfield Road, Cambridge CB2 1EW, U.K.Jonathan P. K. DoyeFOM Institute for Atomic and Molecular Physics, Kruislaan 407, 1098 SJ Amsterdam, The NetherlandsReceied: March 19, 1997; In Final Form: April 29, 1997J. Phys. Chem. A
Global Optimization by Basin-Hopping and the Lowest Energy Structures of Lennard-Jones Clusters Containing up to 110 Atoms

David J. Wales & Jonathan P. K. Doye · 1997

Part 3, original PDF page 29Combine first-order methods with sampling3.24
Part 3, original PDF page 29Global Optimization by Basin-Hopping and the Lowest Energy Structures of Lennard-JonesClusters Containing up to 110 AtomsDavid J. Wales*Uniersity Chemical Laboratories, Lensfield Road, Cambridge CB2 1EW, U.K.Jonathan P. K. DoyeFOM Institute for Atomic and Molecular Physics, Kruislaan 407, 1098 SJ Amsterdam, The NetherlandsReceied: March 19, 1997; In Final Form: April 29, 1997J. Phys. Chem. A
Global Optimization by Basin-Hopping and the Lowest Energy Structures of Lennard-Jones Clusters Containing up to 110 Atoms

David J. Wales & Jonathan P. K. Doye · 1997

Ingredients:

  • Local minimization, for example gradient descent.
  • Sampling moves and a simulated-annealing acceptance rule.
Part 3, original PDF page 30Combine first-order methods with sampling3.24
Part 3, original PDF page 30Global Optimization by Basin-Hopping and the Lowest Energy Structures of Lennard-JonesClusters Containing up to 110 AtomsDavid J. Wales*Uniersity Chemical Laboratories, Lensfield Road, Cambridge CB2 1EW, U.K.Jonathan P. K. DoyeFOM Institute for Atomic and Molecular Physics, Kruislaan 407, 1098 SJ Amsterdam, The NetherlandsReceied: March 19, 1997; In Final Form: April 29, 1997J. Phys. Chem. A Figure 2. A schematic diagram illustrating the effects of our energytransformation for a one-dimensional example. The solid line is theenergy of the original surface and the dashed line is the transformedenergy
Global Optimization by Basin-Hopping and the Lowest Energy Structures of Lennard-Jones Clusters Containing up to 110 Atoms

David J. Wales & Jonathan P. K. Doye · 1997

Ingredients:

  • Local minimization, for example gradient descent.
  • Sampling moves and a simulated-annealing acceptance rule.
Original landscape and basin-hopping transformation

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

Memetic algorithms3.25

Ingredients:

  • A local optimizer, such as gradient descent, BFGS or Newton.
  • An evolutionary search procedure.
Memetic algorithms3.25

Ingredients:

  • A local optimizer, such as gradient descent, BFGS or Newton.
  • An evolutionary search procedure.
Neri and Cotta (2012), complete original paper header
Part 3, original PDF page 33“Memetic algorithms”3.26
Part 3, original PDF page 33Guided evolutionary strategies:Augmenting random search with surrogate gradientsNiru Maheswaranathan Luke Metz George Tucker Dami Choi Jascha Sohl-Dickstein Guided evolutionary strategies: Augmenting random search with surrogate gradientsFigure 1. (a) Schematic of guided evolutionary strategies. We perform a random search using a distribution (white contours) elongatedalong a subspace (white arrow) which we are given instead of the true gradient (blue arrow). (b) Comparison of different algorithms on aquadratic loss, where a bias is explicitly added to the gradient to mimic situations where the true gradient is unknown. The loss (left) andcorrelation between surrogate and true gradient (right) are shown during optimization. See for experimental details.Guided evolutionary search
Part 3, original PDF page 34Take-home messages3.27
  • Gradient descent uses first-order information; the step size matters.
  • Newton solves Htdt=−gt; curvature and step safeguards matter.
  • Quasi-Newton methods learn curvature from changes in positions and gradients.
  • Local methods can be combined with sampling to explore multiple basins.
Part 3, original PDF page 34Take-home messages3.27
  • Gradient descent uses first-order information; the step size matters.
  • Newton solves Htdt=−gt; curvature and step safeguards matter.
  • Quasi-Newton methods learn curvature from changes in positions and gradients.
  • Local methods can be combined with sampling to explore multiple basins.
Part 3, original PDF page 34Take-home messages3.27
  • Gradient descent uses first-order information; the step size matters.
  • Newton solves Htdt=−gt; curvature and step safeguards matter.
  • Quasi-Newton methods learn curvature from changes in positions and gradients.
  • Local methods can be combined with sampling to explore multiple basins.
Part 3, original PDF page 34Take-home messages3.27
  • Gradient descent uses first-order information; the step size matters.
  • Newton solves Htdt=−gt; curvature and step safeguards matter.
  • Quasi-Newton methods learn curvature from changes in positions and gradients.
  • Local methods can be combined with sampling to explore multiple basins.
Part 4, original PDF page 1MUDS course optimization Part IV4.1
Part 4, original PDF page 1Convergence of gradient methodsChristian L. MüllerInstitute of Computational Biology, Helmholtz MunichDepartment of Statistics, Ludwig-Maximilians-UniversitätCenter for Computational Mathematics, Flatiron Institute, New Yorkch.mueller@lmu.de23/11/2026
Part 4, original PDF page 2MUDS course optimization Part IV4.1
Part 4, original PDF page 2Convergence of gradient methodsChristian L. MüllerInstitute of Computational Biology, Helmholtz MunichDepartment of Statistics, Ludwig-Maximilians-UniversitätCenter for Computational Mathematics, Flatiron Institute, New Yorkch.mueller@lmu.de23/11/2026
Gradient-based optimization4.2
  • The gradient \(\nabla f(\mathbf x)\) is available.
  • The function can be high-dimensional.
  • The available assumptions determine which step sizes we can justify.
\(\mathbf x_{t+1}=\mathbf x_t-\eta_t\nabla f(\mathbf x_t)\)

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?

Gradient-based optimization4.2
  • The gradient \(\nabla f(\mathbf x)\) is available.
  • The function can be high-dimensional.
  • The available assumptions determine which step sizes we can justify.
\(\mathbf x_{t+1}=\mathbf x_t-\eta_t\nabla f(\mathbf x_t)\)

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?

Gradient-based optimization4.2
  • The gradient \(\nabla f(\mathbf x)\) is available.
  • The function can be high-dimensional.
  • The available assumptions determine which step sizes we can justify.
\(\mathbf x_{t+1}=\mathbf x_t-\eta_t\nabla f(\mathbf x_t)\)

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?

Gradient-based optimization4.2
  • The gradient \(\nabla f(\mathbf x)\) is available.
  • The function can be high-dimensional.
  • The available assumptions determine which step sizes we can justify.
\(\mathbf x_{t+1}=\mathbf x_t-\eta_t\nabla f(\mathbf x_t)\)

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?

Part 4, original PDF page 9What are good functions?4.3
Part 4, original PDF page 9Stochastic Methods for Single Objective Global Optimization, Christian L. Müller, in: Computational Intelligence in Aerospace Sciences - Fundamental Concepts and Methods (2015) https://doi.org/10.2514/5.9781624102714.0063.0112Nice!!Hard Hopeless?but doable?!Deceiving
Part 4, original PDF page 10What are good functions?4.3
Part 4, original PDF page 10Stochastic Methods for Single Objective Global Optimization, Christian L. Müller, in: Computational Intelligence in Aerospace Sciences - Fundamental Concepts and Methods (2015) https://doi.org/10.2514/5.9781624102714.0063.0112Nice!!Hard Hopeless?but doable?!Deceiving
What are good functions?4.3

What properties of a function make optimization easier?

Part 4, original PDF page 15Convex optimization4.4
Part 4, original PDF page 15

A convex optimization problem has the standard form

minimizex∈Rpf(x)subject toca(x)≤0, a=1,…,mineq,ha(x)=0, a=1,…,meq.

f,c1,…,cmineq are convex; h1,…,hmeq are affine.

Part 4, original PDF page 16Convex optimization4.4
Part 4, original PDF page 16

A convex optimization problem has the standard form

minimizex∈Rpf(x)subject toca(x)≤0, a=1,…,mineq,ha(x)=0, a=1,…,meq.

f,c1,…,cmineq are convex; h1,…,hmeq are affine.

A set X is convex if (1−θ)x+θy∈X for x,y∈X, θ∈[0,1].

A function is convex if

f((1−θ)x+θy)≤(1−θ)f(x)+θf(y).
Part 4, original PDF page 17Convex optimization4.4
Part 4, original PDF page 17Convex setConvex function

A convex optimization problem has the standard form

minimizex∈Rpf(x)subject toca(x)≤0, a=1,…,mineq,ha(x)=0, a=1,…,meq.

f,c1,…,cmineq are convex; h1,…,hmeq are affine.

A set X is convex if (1−θ)x+θy∈X for x,y∈X, θ∈[0,1].

A function is convex if

f((1−θ)x+θy)≤(1−θ)f(x)+θf(y).

Convex set

Convex function

Part 4, original PDF page 18Convex optimization4.4
Part 4, original PDF page 18Convex setConvex functionEvery local minimum is a global minimum!

A convex optimization problem has the standard form

minimizex∈Rpf(x)subject toca(x)≤0, a=1,…,mineq,ha(x)=0, a=1,…,meq.

f,c1,…,cmineq are convex; h1,…,hmeq are affine.

A set X is convex if (1−θ)x+θy∈X for x,y∈X, θ∈[0,1].

A function is convex if

f((1−θ)x+θy)≤(1−θ)f(x)+θf(y).

Every local minimizer is a global minimizer.

Convex set

Convex function

Part 4, original PDF page 19Convexity4.5
Part 4, original PDF page 19Lemma 1.11 Suppose that is open and that is differentiable; in particular, the gradient (vector of partial derivatives)exists at every point . Then is convex if and only if convex andholds for all Geometrically, this means that for all , the graph of liesabove its tangent hyperplane at the point ; see Figure 1.5.Figure 1.5: First-order characterization of convexity

For differentiable f on an open convex domain in Rp, convexity is equivalent to

f(y)≥f(x)+∇f(x)⊤(y−x).

The gradient is a column vector:

∇f(x)=(∂f∂x1(x),…,∂f∂xp(x))⊤

Proof direction: apply convexity to x+θ(y−x), subtract f(x), divide by θ>0 and let θ↓0.

Part 4, original PDF page 21What can go wrong?4.6
Part 4, original PDF page 21(with with exact line search and starting point Gradient method is slow even with exact line search
Part 4, original PDF page 22Fixed step size: too big4.7
Part 4, original PDF page 2220 10 0 10 2020100 10 20
Part 4, original PDF page 23Fixed step size: too small4.8
Part 4, original PDF page 2320 10 0 10 2020100 10 20
Part 4, original PDF page 24Fixed step size: just right4.9
Part 4, original PDF page 2420 10 0 10 2020100 10 20
Part 4, original PDF page 25The magic of convexity and gradient descent4.10
Part 4, original PDF page 25

Can we use convexity and additional properties of the functions to derive (at least theoretically) how to set the step size?

Part 4, original PDF page 26The magic of convexity and gradient descent4.10
Part 4, original PDF page 26

Can we use convexity and additional properties of the functions to derive (at least theoretically) how to set the step size?

Yes

Gradient descent: what will we prove?4.11

Fix a convex differentiable function with a minimizer \(\mathbf x^\star\).

\[\mathbf x_{t+1}=\mathbf x_t-\eta\mathbf g_t,\qquad\mathbf g_t=\nabla f(\mathbf x_t).\]

Track two quantities throughout:

\[e_t=f(\mathbf x_t)-f(\mathbf x^\star)\ge0,\qquad D_t=\|\mathbf x_t-\mathbf x^\star\|_2^2.\]

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.

One gradient step4.12
Original gradient descent example
\(\mathbf x^\star\)
\(\mathbf x_t\)
\(\mathbf x_{t+1}\)
\(\sqrt{D_t}\)
\(\sqrt{D_{t+1}}\)
\(-\eta\mathbf g_t\)

Convex, differentiable \(f,\) with minimizer \(\mathbf x^\star\).

\[\begin{aligned}\mathbf g_t&=\nabla f(\mathbf x_t),&\mathbf x_{t+1}&=\mathbf x_t-\eta\mathbf g_t,\\e_t&=f(\mathbf x_t)-f^\star,&D_t&=\|\mathbf x_t-\mathbf x^\star\|_2^2.\end{aligned}\]
\[\begin{aligned}D_{t+1}&=\|\mathbf x_{t+1}-\mathbf x^\star\|_2^2\\[6pt]&=\|(\mathbf x_t-\mathbf x^\star)-\eta\mathbf g_t\|_2^2\\[6pt]&=D_t-2\eta\mathbf g_t^\top(\mathbf x_t-\mathbf x^\star)+\eta^2\|\mathbf g_t\|_2^2.\end{aligned}\]

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).\]
\[\begin{aligned}2\eta e_t&\le 2\eta\mathbf g_t^\top(\mathbf x_t-\mathbf x^\star)\\[5pt]&=D_t-D_{t+1}+\eta^2\|\mathbf g_t\|_2^2.\end{aligned}\]
One gradient step4.12
Original gradient descent example
\(\mathbf x^\star\)
\(\mathbf x_t\)
\(\mathbf x_{t+1}\)
\(\sqrt{D_t}\)
\(\sqrt{D_{t+1}}\)
\(-\eta\mathbf g_t\)

Convex, differentiable \(f,\) with minimizer \(\mathbf x^\star\).

\[\begin{aligned}\mathbf g_t&=\nabla f(\mathbf x_t),&\mathbf x_{t+1}&=\mathbf x_t-\eta\mathbf g_t,\\e_t&=f(\mathbf x_t)-f^\star,&D_t&=\|\mathbf x_t-\mathbf x^\star\|_2^2.\end{aligned}\]
\[\begin{aligned}D_{t+1}&=\|\mathbf x_{t+1}-\mathbf x^\star\|_2^2\\[6pt]&=\|(\mathbf x_t-\mathbf x^\star)-\eta\mathbf g_t\|_2^2\\[6pt]&=D_t-2\eta\mathbf g_t^\top(\mathbf x_t-\mathbf x^\star)+\eta^2\|\mathbf g_t\|_2^2.\end{aligned}\]

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).\]
\[\begin{aligned}2\eta e_t&\le 2\eta\mathbf g_t^\top(\mathbf x_t-\mathbf x^\star)\\[5pt]&=D_t-D_{t+1}+\eta^2\|\mathbf g_t\|_2^2.\end{aligned}\]
One gradient step4.12
Original gradient descent example
\(\mathbf x^\star\)
\(\mathbf x_t\)
\(\mathbf x_{t+1}\)
\(\sqrt{D_t}\)
\(\sqrt{D_{t+1}}\)
\(-\eta\mathbf g_t\)

Convex, differentiable \(f,\) with minimizer \(\mathbf x^\star\).

\[\begin{aligned}\mathbf g_t&=\nabla f(\mathbf x_t),&\mathbf x_{t+1}&=\mathbf x_t-\eta\mathbf g_t,\\e_t&=f(\mathbf x_t)-f^\star,&D_t&=\|\mathbf x_t-\mathbf x^\star\|_2^2.\end{aligned}\]
\[\begin{aligned}D_{t+1}&=\|\mathbf x_{t+1}-\mathbf x^\star\|_2^2\\[6pt]&=\|(\mathbf x_t-\mathbf x^\star)-\eta\mathbf g_t\|_2^2\\[6pt]&=D_t-2\eta\mathbf g_t^\top(\mathbf x_t-\mathbf x^\star)+\eta^2\|\mathbf g_t\|_2^2.\end{aligned}\]

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).\]
\[\begin{aligned}2\eta e_t&\le 2\eta\mathbf g_t^\top(\mathbf x_t-\mathbf x^\star)\\[5pt]&=D_t-D_{t+1}+\eta^2\|\mathbf g_t\|_2^2.\end{aligned}\]
One gradient step4.12
Original gradient descent example
\(\mathbf x^\star\)
\(\mathbf x_t\)
\(\mathbf x_{t+1}\)
\(\sqrt{D_t}\)
\(\sqrt{D_{t+1}}\)
\(-\eta\mathbf g_t\)

Convex, differentiable \(f,\) with minimizer \(\mathbf x^\star\).

\[\begin{aligned}\mathbf g_t&=\nabla f(\mathbf x_t),&\mathbf x_{t+1}&=\mathbf x_t-\eta\mathbf g_t,\\e_t&=f(\mathbf x_t)-f^\star,&D_t&=\|\mathbf x_t-\mathbf x^\star\|_2^2.\end{aligned}\]
\[\begin{aligned}D_{t+1}&=\|\mathbf x_{t+1}-\mathbf x^\star\|_2^2\\[6pt]&=\|(\mathbf x_t-\mathbf x^\star)-\eta\mathbf g_t\|_2^2\\[6pt]&=D_t-2\eta\mathbf g_t^\top(\mathbf x_t-\mathbf x^\star)+\eta^2\|\mathbf g_t\|_2^2.\end{aligned}\]

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).\]
\[\begin{aligned}2\eta e_t&\le 2\eta\mathbf g_t^\top(\mathbf x_t-\mathbf x^\star)\\[5pt]&=D_t-D_{t+1}+\eta^2\|\mathbf g_t\|_2^2.\end{aligned}\]
Part 4, original PDF page 31Vanilla analysis: sum and balance4.13
Part 4, original PDF page 31

Sum the same inequality over t=0,…,T−1.

D0 − D1
D1 − D2
D2 − D3
⋯ − ⋯
DT−1 − DT
2η∑t=0T−1et≤D0−DT⏟≤R2+η2∑t=0T−1‖gt‖22,R2=D0.

Assume a gradient-norm bound G: ‖gt‖2≤G. Divide by 2ηT:

1T∑t=0T−1et≤R22ηT⏟smaller for larger η+ηG22⏟larger for larger η.
Part 4, original PDF page 32Vanilla analysis: sum and balance4.13
Part 4, original PDF page 32

Sum the same inequality over t=0,…,T−1.

D0 − D1
D1 − D2
D2 − D3
⋯ − ⋯
DT−1 − DT
2η∑t=0T−1et≤D0−DT⏟≤R2+η2∑t=0T−1‖gt‖22,R2=D0.

Assume a gradient-norm bound G: ‖gt‖2≤G. Divide by 2ηT:

1T∑t=0T−1et≤R22ηT⏟smaller for larger η+ηG22⏟larger for larger η.
Part 4, original PDF page 33Vanilla analysis: sum and balance4.13
Part 4, original PDF page 33

Sum the same inequality over t=0,…,T−1.

D0 − D1
D1 − D2
D2 − D3
⋯ − ⋯
DT−1 − DT
2η∑t=0T−1et≤D0−DT⏟≤R2+η2∑t=0T−1‖gt‖22,R2=D0.

Assume a gradient-norm bound G: ‖gt‖2≤G. Divide by 2ηT:

1T∑t=0T−1et≤R22ηT⏟smaller for larger η+ηG22⏟larger for larger η.
η=RGT⟹f(x―T)−f⋆≤1T∑t=0T−1et≤RGT.

x―T=T−1∑t=0T−1xt: convexity turns the average error into an output guarantee. Thus T≥R2G2/ϵ2 suffices.

To obtain \(f(\overline{\mathbf x}_T)-f^\star\le\varepsilon,\) choose \(T\ge(RG/\varepsilon)^2\): \(O(\varepsilon^{-2})\) iterations for fixed \(R,G\).
Part 4, original PDF page 33Vanilla analysis: proof ideas4.14
Part 4, original PDF page 33
Smooth functions4.15

Smoothness means that the gradient is Lipschitz:

\[\|\nabla f({\mathbf{x}})-\nabla f({\mathbf{y}})\|_2\leq L\|{\mathbf{x}}-{\mathbf{y}}\|_2.\]

It implies the quadratic upper model

\[f({\mathbf{y}})\leq f({\mathbf{x}})+\nabla f({\mathbf{x}})^\top({\mathbf{y}}-{\mathbf{x}})+\frac L2\|{\mathbf{y}}-{\mathbf{x}}\|_2^2\]

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.

Smooth functions4.16
Original function and quadratic bounds, with source text removed
An L-Lipschitz gradient gives a quadratic upper bound.
\(f(\mathbf x)+\nabla f(\mathbf x)^\top(\mathbf y-\mathbf x)+\frac L2\|\mathbf y-\mathbf x\|_2^2\)
\(f(\mathbf y)\)
\(f(\mathbf x)+\nabla f(\mathbf x)^\top(\mathbf y-\mathbf x)\)
\(\mathbf x\)
\(\mathbf y\)
Smooth vs lipschitz4.17
  • Bounded gradients: \(\|\nabla f({\mathbf{x}})\|_2\leq G\) controls changes in \(f\).
  • Lipschitz gradients: \(\|\nabla f({\mathbf{x}})-\nabla f({\mathbf{y}})\|_2\leq L\|{\mathbf{x}}-{\mathbf{y}}\|_2\) controls curvature.

For differentiable convex \(f:\mathbb R^p\to\mathbb R,\) the gradient condition is equivalent to

\[f({\mathbf{y}})\leq f({\mathbf{x}})+\nabla f({\mathbf{x}})^\top({\mathbf{y}}-{\mathbf{x}})+\frac L2\|{\mathbf{y}}-{\mathbf{x}}\|_2^2\]

Keep \(G\) and \(L\) distinct.

Sufficient decrease4.18

Assume \(\nabla f\) is \(L\)-Lipschitz continuous. For a gradient step, the quadratic upper bound gives

\[\begin{aligned}f(\mathbf x_{t+1})&\le f(\mathbf x_t)+\mathbf g_t^\top(\mathbf x_{t+1}-\mathbf x_t)+\tfrac L2\|\mathbf x_{t+1}-\mathbf x_t\|_2^2\\&=f(\mathbf x_t)-\eta\|\mathbf g_t\|_2^2+\tfrac{L\eta^2}{2}\|\mathbf g_t\|_2^2.\end{aligned}\]

Choose \(\eta=1/L\). Then

\(f(\mathbf x_t)-f(\mathbf x_{t+1})\ge\frac1{2L}\|\mathbf g_t\|_2^2.\)

This decrease follows from smoothness; convexity is not needed here.

Smooth Convex functions i4.19

Theorem: suppose \(f:\mathbb R^p\to\mathbb R\) is convex, \(L\)-smooth and has a minimizer.

\[\eta=1/L,\qquad{\mathbf{x}}_{t+1}={\mathbf{x}}_t-\frac1L\nabla f({\mathbf{x}}_t).\]
\[e_T\leq\frac{LR^2}{2T},\qquad R^2=\|{\mathbf{x}}_0-{\mathbf{x}}^\star\|_2^2,\quad T\geq1.\]

This time the guarantee is for the last iterate.

Smooth Convex functions: one step4.20

Assume convexity and an \(L\)-Lipschitz gradient. Choose \(\eta=1/L\).

The squared-distance expansion and convexity gave

\[2\eta e_t\le D_t-D_{t+1}+\eta^2\|\mathbf g_t\|_2^2.\]

Smoothness gives \(\eta^2\|\mathbf g_t\|_2^2\le2\eta(e_t-e_{t+1})\). Substitute:

\[\begin{aligned}2\eta e_t&\le D_t-D_{t+1}+2\eta(e_t-e_{t+1}),\\2\eta e_{t+1}&\le D_t-D_{t+1}.\end{aligned}\]

The \(e_t\) terms cancel. We can now bound the next objective error using only the change in squared distance.

Smooth Convex functions: sum the steps4.21

Sum \(2\eta e_{t+1}\le D_t-D_{t+1}\) over \(t=0,\ldots,T-1\):

\[\begin{aligned}2\eta\sum_{t=0}^{T-1}e_{t+1}&\le(D_0-D_1)+(D_1-D_2)+\cdots+(D_{T-1}-D_T)\\&=D_0-D_T\\&\le R^2.\end{aligned}\]

The intermediate distances cancel. Smoothness also gives \(e_1\ge\cdots\ge e_T,\) so

\[Te_T\le e_1+\cdots+e_T\le\frac{R^2}{2\eta}.\]
\(e_T=f(\mathbf x_T)-f^\star\le\frac{LR^2}{2T}.\)
Smooth Convex functions: the rate4.22
\[e_T\le\frac{LR^2}{2T}\le\varepsilon\quad\text{when}\quad T\ge\frac{LR^2}{2\varepsilon}.\]

For fixed \(L,R,\) this is \(O(\varepsilon^{-1})\) iterations.

  • Convexity links objective error to the gradient.
  • Smoothness turns the gradient penalty into actual decrease.
  • Summing cancels intermediate distances.
  • Monotonicity gives a guarantee for the final iterate.

This gives objective error \(O(T^{-1}),\) or \(O(\varepsilon^{-1})\) iterations for accuracy \(\varepsilon,\) for fixed \(L,R\).

Recap so far…4.23

So far, we have bounded the objective error by

  • \(O(T^{-1/2})\) for convex functions with bounded gradients, using the averaged iterate.
  • \(O(T^{-1})\) for smooth convex functions, using the final iterate.

Could the error decrease exponentially in \(T\)?

Simple example4.24

On \(f(x)=x^2,\) the exact smoothness constant is \(L=2\).

\[\eta=\tfrac12:\quad x_{t+1}=x_t-\tfrac12(2x_t)=0.\]

One step reaches the minimizer.

The same function is also smooth with the looser bound \(L=4\).

\[\eta=\tfrac14:\quad x_{t+1}=\tfrac12x_t,\qquad f(x_T)=4^{-T}f(x_0).\]

Geometric decrease, even with the conservative step.

Simple example4.24

On \(f(x)=x^2,\) the exact smoothness constant is \(L=2\).

\[\eta=\tfrac12:\quad x_{t+1}=x_t-\tfrac12(2x_t)=0.\]

One step reaches the minimizer.

The same function is also smooth with the looser bound \(L=4\).

\[\eta=\tfrac14:\quad x_{t+1}=\tfrac12x_t,\qquad f(x_T)=4^{-T}f(x_0).\]

Geometric decrease, even with the conservative step.

What is the right characterization to obtain this in general?

Strongly Convex functions4.25

Strong convexity — “not too flat”

For \(\mu>0\) on a convex domain,

\[f({\mathbf{y}})\geq f({\mathbf{x}})+\nabla f({\mathbf{x}})^\top({\mathbf{y}}-{\mathbf{x}})+\frac\mu2\|{\mathbf{y}}-{\mathbf{x}}\|_2^2.\]

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.

Strongly Convex functions4.26
Original function and quadratic bounds, with source text removed
Strong convexity gives a quadratic lower bound; smoothness gives the upper bound.
\(f(\mathbf x)+\nabla f(\mathbf x)^\top(\mathbf y-\mathbf x)+\frac L2\|\mathbf y-\mathbf x\|_2^2\)
\(f(\mathbf y)\)
\(f(\mathbf x)+\nabla f(\mathbf x)^\top(\mathbf y-\mathbf x)+\frac\mu2\|\mathbf y-\mathbf x\|_2^2\)
\(\mathbf x\)
\(\mathbf y\)
Smooth and strongly Convex functions4.27

For smooth, strongly convex functions, gradient descent can decrease the objective error geometrically.

\[e_T\le\frac{LR^2}{2}e^{-T/\kappa},\qquad\kappa=\frac L\mu.\]

To obtain \(e_T\le\varepsilon\), we will need \(O(\kappa\log(1/\varepsilon))\) iterations, for fixed \(L,R\).

Strong convexity: contraction in one step4.27

Assume convexity, \(L\)-smoothness and \(\mu\)-strong convexity.
Choose \(\eta=1/L;\) keep the same \(e_t,D_t,R\).

1. Expand the squared distance
\[D_{t+1}=D_t-2\eta\mathbf g_t^\top(\mathbf x_t-\mathbf x^\star)+\eta^2\|\mathbf g_t\|_2^2.\]
Strong convexity: contraction in one step4.27

Assume convexity, \(L\)-smoothness and \(\mu\)-strong convexity.
Choose \(\eta=1/L;\) keep the same \(e_t,D_t,R\).

1. Expand the squared distance
\[D_{t+1}=D_t-2\eta\mathbf g_t^\top(\mathbf x_t-\mathbf x^\star)+\eta^2\|\mathbf g_t\|_2^2.\]
2. Use strong convexity
\[f(\mathbf x^\star)\ge f(\mathbf x_t)+\mathbf g_t^\top(\mathbf x^\star-\mathbf x_t)+\tfrac\mu2\|\mathbf x^\star-\mathbf x_t\|_2^2.\]
Strong convexity: contraction in one step4.27

Assume convexity, \(L\)-smoothness and \(\mu\)-strong convexity.
Choose \(\eta=1/L;\) keep the same \(e_t,D_t,R\).

1. Expand the squared distance
\[D_{t+1}=D_t-2\eta\mathbf g_t^\top(\mathbf x_t-\mathbf x^\star)+\eta^2\|\mathbf g_t\|_2^2.\]
2. Use strong convexity
\[f(\mathbf x^\star)\ge f(\mathbf x_t)+\mathbf g_t^\top(\mathbf x^\star-\mathbf x_t)+\tfrac\mu2\|\mathbf x^\star-\mathbf x_t\|_2^2.\]
\[\begin{aligned}\mathbf g_t^\top(\mathbf x_t-\mathbf x^\star)&\ge e_t+\tfrac\mu2D_t,\\[5pt]D_{t+1}&\le(1-\mu\eta)D_t-2\eta e_t+\eta^2\|\mathbf g_t\|_2^2.\end{aligned}\]
Strong convexity: contraction in one step4.27

Assume convexity, \(L\)-smoothness and \(\mu\)-strong convexity.
Choose \(\eta=1/L;\) keep the same \(e_t,D_t,R\).

1. Expand the squared distance
\[D_{t+1}=D_t-2\eta\mathbf g_t^\top(\mathbf x_t-\mathbf x^\star)+\eta^2\|\mathbf g_t\|_2^2.\]
2. Use strong convexity
\[f(\mathbf x^\star)\ge f(\mathbf x_t)+\mathbf g_t^\top(\mathbf x^\star-\mathbf x_t)+\tfrac\mu2\|\mathbf x^\star-\mathbf x_t\|_2^2.\]
\[\begin{aligned}\mathbf g_t^\top(\mathbf x_t-\mathbf x^\star)&\ge e_t+\tfrac\mu2D_t,\\[5pt]D_{t+1}&\le(1-\mu\eta)D_t-2\eta e_t+\eta^2\|\mathbf g_t\|_2^2.\end{aligned}\]
3. Use smoothness
\[\begin{aligned}\eta^2\|\mathbf g_t\|_2^2&\le2\eta(e_t-e_{t+1}),\\ -2\eta e_t+\eta^2\|\mathbf g_t\|_2^2&\le-2\eta e_{t+1}\le0.\end{aligned}\]
\(\boxed{D_{t+1}\le(1-\mu/L)D_t.}\)
Strong convexity: repeat the contraction4.28

Let \(\kappa=L/\mu\ge1\) be the condition number. Repeated contraction gives

\[D_T\le(1-1/\kappa)^TR^2\le e^{-T/\kappa}R^2.\]

At an unconstrained differentiable minimizer, \(\nabla f(\mathbf x^\star)=0\). The smooth upper model then gives

\[e_T\le\frac L2D_T.\]

Combining the two bounds:

\[\boxed{e_T\le\frac{LR^2}{2}e^{-T/\kappa}.}\]
Strong convexity: the rate4.29

To make the objective error at most \(\varepsilon,\) it is sufficient that

\[\frac{LR^2}{2}e^{-T/\kappa}\le\varepsilon.\]

Solve this scalar inequality for the number of updates:

\[T\ge\kappa\log\!\left(\frac{LR^2}{2\varepsilon}\right).\]
  • The error decreases geometrically with the update count.
  • The condition number \(\kappa=L/\mu\) controls the speed.
  • For fixed \(L,R,\) this requires \(O(\kappa\log(1/\varepsilon))\) iterations.

If \(LR^2/2\le\varepsilon,\) the initial point already meets this sufficient bound.

Three function classes: what changed?4.30

The starting calculation was always the change in squared distance.

  • Bounded gradients: bound the extra gradient term by a constant; balance the step size. Obtain an averaged-output bound \(O(T^{-1/2})\).
  • Smooth convex: replace that term by objective decrease. Sum and use monotonicity. Obtain a final-iterate bound \(O(T^{-1})\).
  • Smooth and strongly convex: the extra curvature contracts the distance every step. Obtain geometric convergence.

The assumptions change what we can do with the same identity.

Adaptive step sizes4.31
  • So far, we chose a constant step size using assumptions about the function.
  • We can instead choose a step size \(\eta_t\) at each iteration:
\[\mathbf x_{t+1}=\mathbf x_t-\eta_t\mathbf g_t,\qquad\mathbf g_t=\nabla f(\mathbf x_t).\]
  • A schedule specifies \(\eta_t\) in advance, for example a decreasing sequence.
  • An adaptive rule uses information from the current iteration, such as function values or the gradient.
  • Line search tests candidate step sizes. The Polyak rule uses the objective error and gradient norm.

Here \(\eta_t\) is one scalar for the whole gradient.

What about adaptive step sizes?4.32
Convex, bounded gradientsConvex, \(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\)
Revisiting the Polyak step size, Hazan and Kakade
What about adaptive step sizes?4.32
Convex, bounded gradientsConvex, \(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\).

\[\eta_t=\frac{f(\mathbf x_t)-f^\star}{\|\mathbf g_t\|_2^2},\qquad\mathbf g_t=\nabla f(\mathbf x_t).\]
\[\mathbf x_{t+1}=\mathbf x_t-\eta_t\mathbf g_t.\]

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.

Learning-rate schedules4.33
Schaipp, Hägele, Taylor, Şimşekli and Bach: paper headerFigure 2: cosine and warmup-stable-decay schedules and their theoretical bounds

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

Convex theory and model training4.34
Figure 1: measured validation loss for a 210M Llama model and theoretical convex suboptimality bounds
  • Left: validation loss of a 210M Llama model trained with AdamW. Right: a bound from convex optimization.
  • Both show a sharp improvement during the cooldown of the warmup–stable–decay schedule.
  • The agreement helps compare and tune schedules; it does not prove that LLM training is convex.
Part 4, original PDF page 55Take-home messages4.35
  • One distance calculation underlies the gradient-descent convergence proofs.
  • Convexity and bounded gradients give an averaged-output error of O(T−1/2).
  • Convexity and L-smoothness give a last-iterate error of O(T−1).
  • Add μ-strong convexity for geometric convergence; conditioning L/μ controls the rate.
Part 4, original PDF page 55Take-home messages4.35
  • One distance calculation underlies the gradient-descent convergence proofs.
  • Convexity and bounded gradients give an averaged-output error of O(T−1/2).
  • Convexity and L-smoothness give a last-iterate error of O(T−1).
  • Add μ-strong convexity for geometric convergence; conditioning L/μ controls the rate.
Part 4, original PDF page 55Take-home messages4.35
  • One distance calculation underlies the gradient-descent convergence proofs.
  • Convexity and bounded gradients give an averaged-output error of O(T−1/2).
  • Convexity and L-smoothness give a last-iterate error of O(T−1).
  • Add μ-strong convexity for geometric convergence; conditioning L/μ controls the rate.
Part 4, original PDF page 55Take-home messages4.35
  • One distance calculation underlies the gradient-descent convergence proofs.
  • Convexity and bounded gradients give an averaged-output error of O(T−1/2).
  • Convexity and L-smoothness give a last-iterate error of O(T−1).
  • Add μ-strong convexity for geometric convergence; conditioning L/μ controls the rate.
Part 5, original PDF page 1MUDS course optimization Part V5.1
Part 5, original PDF page 1Constrained optimizationChristian L. MüllerInstitute of Computational Biology, Helmholtz MunichDepartment of Statistics, Ludwig-Maximilians-UniversitätCenter for Computational Mathematics, Flatiron Institute, New Yorkch.mueller@lmu.de23/11/2026
X⊆Rp
Gradient descent with constraints5.2
  • The gradient \( \mathbf g_t=\nabla f(\mathbf x_t) \) is available.
  • Now we restrict \(\mathbf x\) to a feasible set \(\mathcal X\subseteq\mathbb R^p\).
  • Assume \(\mathcal X\) is nonempty, closed and convex; start with \(\mathbf x_0\in\mathcal X\).
Objective function above a restricted feasible domain
\(\mathcal X\subseteq\mathbb R^p\)

The shaded domain is the feasible set \(\mathcal X\).

\[\mathbf x_{t+1}=\mathbf x_t-\eta_t\mathbf g_t.\]

A gradient step may leave \(\mathcal X\). How can we modify it?

Gradient descent with constraints5.2
  • The gradient \( \mathbf g_t=\nabla f(\mathbf x_t) \) is available.
  • Now we restrict \(\mathbf x\) to a feasible set \(\mathcal X\subseteq\mathbb R^p\).
  • Assume \(\mathcal X\) is nonempty, closed and convex; start with \(\mathbf x_0\in\mathcal X\).
Objective function above a restricted feasible domain
\(\mathcal X\subseteq\mathbb R^p\)

The shaded domain is the feasible set \(\mathcal X\).

\[\mathbf x_{t+1}=\mathbf x_t-\eta_t\mathbf g_t.\]

A gradient step may leave \(\mathcal X\). How can we modify it?

Gradient descent with constraints5.2
  • The gradient \( \mathbf g_t=\nabla f(\mathbf x_t) \) is available.
  • Now we restrict \(\mathbf x\) to a feasible set \(\mathcal X\subseteq\mathbb R^p\).
  • Assume \(\mathcal X\) is nonempty, closed and convex; start with \(\mathbf x_0\in\mathcal X\).
Objective function above a restricted feasible domain
\(\mathcal X\subseteq\mathbb R^p\)

The shaded domain is the feasible set \(\mathcal X\).

\[\mathbf x_{t+1}=\mathbf x_t-\eta_t\mathbf g_t.\]

A gradient step may leave \(\mathcal X\). How can we modify it?

What about constraints?5.3
How can we keep each iterate
inside a convex feasible set?
Constrained optimization5.4

We minimize the same objective, over a restricted domain:

\[f^\star=\min_{\mathbf x\in\mathcal X}f(\mathbf x),\qquad\mathcal X\subseteq\mathbb R^p.\]
  • Assume \(\mathcal X\) is nonempty, closed and convex.
  • Start with \(\mathbf x_0\in\mathcal X\).
  • Project a gradient step back onto the set.
  • Or include the constraint in the objective.
Original course illustration
Constrained optimization5.4

We minimize the same objective, over a restricted domain:

\[f^\star=\min_{\mathbf x\in\mathcal X}f(\mathbf x),\qquad\mathcal X\subseteq\mathbb R^p.\]
  • Assume \(\mathcal X\) is nonempty, closed and convex.
  • Start with \(\mathbf x_0\in\mathcal X\).
  • Project a gradient step back onto the set.
  • Or include the constraint in the objective.
Original course illustration
Constrained optimization5.5

The constrained optimum may lie on the boundary.

\[\mathbf x^\star\in\arg\min_{\mathbf x\in\mathcal X}f(\mathbf x).\]
Original feasible-set and objective-contour illustration, cleanly cropped
\(\mathcal X\subseteq\mathbb R^p\)

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

Projected gradient descent5.6
  • First take a gradient step.
  • Then choose the nearest feasible point.
Original course illustration

In the source figure, \(X\) is our \(\mathcal X\), \(d=p\), and the red arrow represents \(-\eta_t\mathbf g_t\).

Projected gradient descent5.7

Let \(\mathbf g_t=\nabla f(\mathbf x_t)\). The update has two steps:

\[\begin{aligned}\mathbf y_{t+1}&=\mathbf x_t-\eta_t\mathbf g_t,\\\mathbf x_{t+1}&=\Pi_{\mathcal X}(\mathbf y_{t+1}).\end{aligned}\]

The Euclidean projection is

\[\Pi_{\mathcal X}(\mathbf y)=\arg\min_{\mathbf u\in\mathcal X}\tfrac12\|\mathbf u-\mathbf y\|_2^2.\]
  • For a nonempty closed convex set, this point is unique.
  • For box constraints, clip each coordinate to its allowed interval.
Part 5, original PDF page 10Projected gradient descent5.8
Part 5, original PDF page 10
Projected gradient descent: the same distance bound5.9

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:

\[\begin{aligned}D_{t+1}&\le\|\mathbf x_t-\mathbf x^\star-\eta_t\mathbf g_t\|_2^2\\&=D_t-2\eta_t\mathbf g_t^\top(\mathbf x_t-\mathbf x^\star)+\eta_t^2\|\mathbf g_t\|_2^2.\end{aligned}\]

Convexity gives the same one-step bound as before:

\(2\eta_t e_t\le D_t-D_{t+1}+\eta_t^2\|\mathbf g_t\|_2^2.\)

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

Projected gradient descent: the same distance bound5.9

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:

\[\begin{aligned}D_{t+1}&\le\|\mathbf x_t-\mathbf x^\star-\eta_t\mathbf g_t\|_2^2\\&=D_t-2\eta_t\mathbf g_t^\top(\mathbf x_t-\mathbf x^\star)+\eta_t^2\|\mathbf g_t\|_2^2.\end{aligned}\]

Convexity gives the same one-step bound as before:

\(2\eta_t e_t\le D_t-D_{t+1}+\eta_t^2\|\mathbf g_t\|_2^2.\)

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

Projection onto the ℓ₁ ball5.10
\[\mathcal X=\{\mathbf x\in\mathbb R^p:\|\mathbf x\|_1\le R_1\},\qquad R_1>0.\]
Original course illustration

The corners of the feasible set favor solutions with zero coordinates.

Projection onto the ℓ₁ ball5.11

Given \(\mathbf v\), find its nearest feasible point:

\[\Pi_{\mathcal X}(\mathbf v)=\arg\min_{\|\mathbf u\|_1\le R_1}\tfrac12\|\mathbf u-\mathbf v\|_2^2.\]
  • If \(\|\mathbf v\|_1\le R_1\), leave it unchanged.
  • Otherwise choose \(\tau\ge0\) so the projected point lies on the boundary.
\[u_j=\operatorname{sign}(v_j)\max\{|v_j|-\tau,0\},\qquad\sum_{j=1}^{p}|u_j|=R_1.\]

A sorting-based implementation costs \(O(p\log p)\). The threshold depends on the vector and the radius.

Part 5, original PDF page 14Lasso: the L1 constraint5.12
Part 5, original PDF page 14
Projection onto the L1 ball5.12
Original publication header
  • The threshold depends on the vector and the constraint radius.
  • A standard sorting-based implementation costs \(O(p\log p)\).
  • This differs from fixed-threshold soft thresholding.
Proximal algorithms5.13
Can we use the same idea
for a non-smooth convex term?
Smooth and non-smooth terms5.14
\[\min_{\mathbf x\in\mathbb R^p} f(\mathbf x),\qquad f=f_{\rm sm}+r.\]
  • \(f_{\rm sm}\) is convex with an \(L\)-Lipschitz gradient.
  • \(r\) is proper, closed and convex; it may be non-smooth.
  • Allowing \(r=+\infty\) outside \(\mathcal X\) also represents constraints.

We approximate the smooth term and keep \(r\) unchanged.

The Lasso5.15
\[\min_{\mathbf x\in\mathbb R^p}\underbrace{\tfrac1{2n}\|\mathbf A\mathbf x-\mathbf y\|_2^2}_{f_{\rm sm}(\mathbf x)}+\underbrace{\lambda\|\mathbf x\|_1}_{r(\mathbf x)}.\]

Here \(\mathbf A\in\mathbb R^{n\times p}\), \(\mathbf y\in\mathbb R^n\), and \(\lambda\ge0\).

How would you update the coefficients?
What happens at zero?
A quadratic model for the smooth term5.16

At \(\mathbf x_t\), use the same quadratic model as for gradient descent:

\[\begin{aligned}\mathbf x_{t+1}=\arg\min_{\mathbf u}\bigl\{&f_{\rm sm}(\mathbf x_t)+\nabla f_{\rm sm}(\mathbf x_t)^\top(\mathbf u-\mathbf x_t)\\&+\tfrac1{2\eta_t}\|\mathbf u-\mathbf x_t\|_2^2+r(\mathbf u)\bigr\}.\end{aligned}\]

Complete the square and drop terms independent of \(\mathbf u\):

\[\mathbf x_{t+1}=\arg\min_{\mathbf u}\left\{r(\mathbf u)+\frac{\|\mathbf u-(\mathbf x_t-\eta_t\nabla f_{\rm sm}(\mathbf x_t))\|_2^2}{2\eta_t}\right\}.\]

For \(0<\eta_t\le1/L\), the quadratic model is an upper bound.

Proximal gradient descent5.17

The proximal operator is

\[\operatorname{prox}_{\eta r}(\mathbf z)=\arg\min_{\mathbf u}\left\{r(\mathbf u)+\tfrac1{2\eta}\|\mathbf u-\mathbf z\|_2^2\right\}.\]

Take a gradient step on the smooth term, then apply the proximal operator:

\[\mathbf x_{t+1}=\operatorname{prox}_{\eta_t r}\!\left(\mathbf x_t-\eta_t\nabla f_{\rm sm}(\mathbf x_t)\right).\]
  • The gradient is evaluated only for \(f_{\rm sm}\).
  • The method is useful when the proximal operator is cheap to compute.

A fixed point satisfies \(\mathbf0\in\nabla f_{\rm sm}(\mathbf x)+\partial r(\mathbf x)\).

Projection is a proximal operator5.18

Represent the constraint by its convex indicator:

\[r(\mathbf x)=\iota_{\mathcal X}(\mathbf x)=\begin{cases}0,&\mathbf x\in\mathcal X,\\+\infty,&\mathbf x\notin\mathcal X.\end{cases}\]
\[\operatorname{prox}_{\eta\iota_{\mathcal X}}(\mathbf z)=\Pi_{\mathcal X}(\mathbf z).\]
  • \(r=0\): ordinary gradient descent.
  • \(r=\iota_{\mathcal X}\): projected gradient descent.
  • \(r=\lambda\|\cdot\|_1\): soft thresholding.
Proximal gradient descent for the Lasso5.19

For \(r(\mathbf x)=\lambda\|\mathbf x\|_1\), the proximal step acts on each coordinate:

\[[\operatorname{prox}_{\eta\lambda\|\cdot\|_1}(\mathbf z)]_j=\operatorname{sign}(z_j)\max\{|z_j|-\eta\lambda,0\}.\]
  • The fixed threshold \(\eta\lambda\) can set coefficients exactly to zero.
  • This step costs \(O(p)\), unlike sorting for an ℓ₁-ball projection.

For convex \(f_{\rm sm}+r\), with \(\eta=1/L\) and \(R^2=\|\mathbf x_0-\mathbf x^\star\|_2^2\):

\(f(\mathbf x_T)-f^\star\le\dfrac{LR^2}{2T}.\)

We again need \(O(\varepsilon^{-1})\) iterations for objective error at most \(\varepsilon\).

Part 5, original PDF page 25Excursion: current research5.20
Part 5, original PDF page 25Perspective M-estimationConstrained Lasso and friendshttps://github.com/bio-datascience/c-lassohttps://doi.org/10.1214/19-EJS1662
Further reading5.21
Combettes and Pesquet: Proximal Splitting Methods in Signal ProcessingParikh and Boyd: Proximal Algorithms
Part 5, original PDF page 24Further reading5.22
Part 5, original PDF page 24© ISTOCKPHOTO.COM/A2Y4NVolkan Cevher, Stephen Becker, and Mark SchmidtScalable, randomized, and parallel algorithms for big data analyticsConvex Optimization for Big Data
Part 6, original PDF page 54Projection-free algorithms5.23
Part 6, original PDF page 54
An Algorithm for Quadratic Programming

Marguerite Frank & Philip Wolfe · 1956

Revisiting Frank–Wolfe: Projection-Free Sparse Convex Optimization

Martin Jaggi · 2013

Original Frank–Wolfe linear minimization geometry
Constrained optimization

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

5.24
Part 5, original PDF page 22Vanilla Frank–Wolfe5.25
Part 5, original PDF page 22
Part 5, original PDF page 22Frank–Wolfe5.26
Part 5, original PDF page 22
Part 5, original PDF page 22Lasso with Frank–Wolfe5.27
Part 5, original PDF page 22
Part 5, original PDF page 25Take-home messages5.28
  • Constraints and non-smooth terms change the update, not the optimization goal.
  • Projected gradient descent takes a gradient step and projects onto the feasible set.
  • Proximal gradient keeps a non-smooth regularizer in a tractable subproblem.
  • Frank–Wolfe uses a linear minimization oracle and a feasible convex-combination step.
Part 5, original PDF page 25Take-home messages5.28
  • Constraints and non-smooth terms change the update, not the optimization goal.
  • Projected gradient descent takes a gradient step and projects onto the feasible set.
  • Proximal gradient keeps a non-smooth regularizer in a tractable subproblem.
  • Frank–Wolfe uses a linear minimization oracle and a feasible convex-combination step.
Part 5, original PDF page 25Take-home messages5.28
  • Constraints and non-smooth terms change the update, not the optimization goal.
  • Projected gradient descent takes a gradient step and projects onto the feasible set.
  • Proximal gradient keeps a non-smooth regularizer in a tractable subproblem.
  • Frank–Wolfe uses a linear minimization oracle and a feasible convex-combination step.
Part 5, original PDF page 25Take-home messages5.28
  • Constraints and non-smooth terms change the update, not the optimization goal.
  • Projected gradient descent takes a gradient step and projects onto the feasible set.
  • Proximal gradient keeps a non-smooth regularizer in a tractable subproblem.
  • Frank–Wolfe uses a linear minimization oracle and a feasible convex-combination step.
MUDS course optimization Part VI6.1
  • So far, we have used full gradients and proximal steps.
  • What changes when the data or the model are too large?
  • Adaptive and accelerated methods.
  • Stochastic gradients.
  • Distributed and parallel optimization.
Cevher, Becker and Schmidt: Convex Optimization for Big Data

Large-scale optimization

Christian L. Müller

Helmholtz Munich
Department of Statistics, LMU
Flatiron Institute

23/11/2026

Large-scale optimization6.1
  • So far, we have used full gradients and proximal steps.
  • What changes when the data or the model are too large?
  • Adaptive and accelerated methods.
  • Stochastic gradients.
  • Distributed and parallel optimization.
Cevher, Becker and Schmidt: Convex Optimization for Big Data

Christian L. Müller

Helmholtz Munich
Department of Statistics, LMU
Flatiron Institute

23/11/2026

Large-scale optimization6.1
  • So far, we have used full gradients and proximal steps.
  • What changes when the data or the model are too large?
  • Adaptive and accelerated methods.
  • Stochastic gradients.
  • Distributed and parallel optimization.
Cevher, Becker and Schmidt: Convex Optimization for Big Data

Christian L. Müller

Helmholtz Munich
Department of Statistics, LMU
Flatiron Institute

23/11/2026

Stochastic gradient descent6.2
Original publication title, authors and abstract

17,810 citations · Google Scholar, 18 Nov 2026

Stochastic gradient descent for machine learning6.3
Original publication title, authors and abstract

9,579 citations · Google Scholar, 18 Nov 2026

Linear SVMs: optimization and prediction

RCV1: 781,265 training documents and 47,152 sparse features.

Bottou 2010 Figure 1

Test performance levels off before very high optimization accuracy becomes useful.

6.4
Averaged SGD for a linear SVM

ALPHA: squared hinge loss; 100,000 examples and 500 variables.

Bottou 2010 Figure 2

ASGD averages successive parameter vectors. In this experiment, it approaches its best test performance after one pass.

6.5
Stochastic optimization beyond SVMs

CoNLL-2000: conditional random field for sequence labeling.

Bottou 2010 Figure 3

SGDQN performs best here; averaging is not uniformly better across these experiments.

6.6
Part 6, original PDF page 6Stochastic gradient descent - why?6.7

Many learning objectives are finite sums:

fn(x)=1n∑i=1nℓ(x;zi),x∈Rp.

Here n is the number of training examples and p the number of optimized parameters.

Fix the dataset and write f=fn. The full gradient requires all sample gradients:

∇f(x)=1n∑i=1n∇ℓ(x;zi).
Part 6, original PDF page 7SGD - the algorithm6.8

Choose x0∈Rp. At step t:

It∼Unif{1,…,n},g^t=∇ℓ(xt;zIt)
xt+1=xt−ηtg^t,ηt>0,t=0,1,….
  • Use one sample gradient instead of all n gradients.
  • This reduces the sample-gradient work per update; actual runtime depends on implementation.
  • The stochastic gradient g^t∈Rp is random; gt=∇f(xt) is the exact gradient.
Part 6, original PDF page 8SGD - unbiasedness6.9

Convexity applies to the full gradient:

et≤∇f(xt)⊤(xt−x⋆).

It need not hold for every realization of the stochastic gradient. But independent uniform sampling gives

E[g^t∣Ft]=1n∑i=1n∇ℓ(xt;zi)=∇f(xt).

Ft is the history before the new sample draw; xt is known given that history.

Part 6, original PDF page 9SGD - unbiasedness6.9

Condition on the history before drawing the example:

E[g^t⊤(xt−x⋆)∣Ft]=∇f(xt)⊤(xt−x⋆)≥et.

Now use the tower property:

E[g^t⊤(xt−x⋆)]≥E[et].

Thus the deterministic distance calculation carries over after taking expectations. No finite-support assumption about the random iterate is needed.

Part 6, original PDF page 10Bounded stochastic gradient6.10

Assume convexity, an attained minimum, ‖x0−x⋆‖2≤R, unbiased sample gradients and

E‖g^t‖22≤Gstoch2.

Choose the constant step

η=RGstochT.
1T∑t=0T−1E[et]≤RGstochT.

The proof uses the same telescoping recursion, now with expectations. Convexity gives the same bound for the expected error of the averaged iterate.

Part 6, original PDF page 11Gradient descent vs. SGD6.11

At a fixed parameter vector, compare

‖1n∑i=1n∇ℓ(x;zi)‖22≤1n∑i=1n‖∇ℓ(x;zi)‖22.

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 GGD2 and Gstoch2, respectively. Jensen’s inequality explains why stochastic-gradient bounds can be larger.

Larger mini-batches reduce sampling variance.

Part 6, original PDF page 12Mini-batch variant6.12

Draw bt training indices independently and uniformly with replacement:

it,r∼Unif{1,…,n},r=1,…,bt.
g^t=1bt∑r=1bt∇ℓ(xt;zit,r).
  • bt=1: ordinary single-example SGD.
  • Full GD: include every example exactly once. A with-replacement batch of size n is not necessarily the full gradient.
  • Sample gradients can be computed in parallel.

Fixed batch size: bt=b. Search populations use qt, not b.

Part 6, original PDF page 13Mini-batch variant6.12

For conditionally independent sample-gradient errors with zero mean and second moment at most σg2:

E[‖g^t−gt‖22∣Ft]=1btE[‖∇ℓ(xt;zI)−gt‖22∣Ft]≤σg2bt.

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 (n−bt)/(bt(n−1)) when n>1. At bt=n, this variance is zero.

Part 6, original PDF page 13Stochastic gradient descent6.13
Part 6, original PDF page 13
Part 6, original PDF page 13SGD on noisy Rastrigin6.13
Part 6, original PDF page 13
Part 6, original PDF page 13CMA-ES with noisy evaluations6.13
Part 6, original PDF page 13
Modern stochastic gradient descent6.14
  • For large training sets, evaluating the full gradient can be expensive.
  • Use stochastic or mini-batch gradients to reduce the work per update.
  • Momentum, AdaGrad and Adam adapt how gradient information is used.
Modern stochastic gradient descent6.14
  • For large training sets, evaluating the full gradient can be expensive.
  • Use stochastic or mini-batch gradients to reduce the work per update.
  • Momentum, AdaGrad and Adam adapt how gradient information is used.
Gradient methods at large scale6.14
  • At large scale, stochastic gradients can be much cheaper than full gradients.
  • Adaptive scaling and momentum modify the basic update.
  • Mini-batches trade gradient cost against sampling noise.
Original publication headerOriginal publication header
Adam6.15
Kingma and Ba: Adam, original title, authors and complete abstract

265,349 citations · Google Scholar, 18 Nov 2026

Part 6, original PDF page 18Adam6.16

Initialize m0=v0=0. For t=1,2,…, evaluate a stochastic gradient g^t at xt−1.

mt=β1mt−1+(1−β1)g^t,vt=β2vt−1+(1−β2)(g^t⊙g^t).
m^t=mt1−β1t,v^t=vt1−β2t.
xt=xt−1−ηtm^tv^t+ϵA.
  • All products, square roots and divisions are coordinatewise.
  • vt estimates the raw second moment, not the variance.
  • Bias correction compensates for initialization at zero.

Original defaults: η=10−3, β1=0.9, β2=0.999, ϵA=10−8.

Adam rules the world6.16
Original Adam paper experimental plots

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.

Adam rules the world6.16
Original Adam paper experimental plots

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.

Part 6, original PDF page 20Adam6.17
Part 6, original PDF page 20
Weight decay: Adam and AdamW6.18
Original snapshot of Fabian Schaipp’s Decay No More blog post
From Adam to AdamW6.19

Keep Adam’s loss-gradient moments and bias correction:

\[\mathbf a_t=\frac{\widehat{\mathbf m}_t}{\sqrt{\widehat{\mathbf v}_t}+\epsilon_A}.\]

Adam

\[\mathbf x_t=\mathbf x_{t-1}-\eta_t\mathbf a_t.\]

AdamW also shrinks the previous parameters by \(1-\eta_t\lambda_{\rm wd}\).

\[\mathbf x_t=(1-\eta_t\lambda_{\rm wd})\mathbf x_{t-1}-\eta_t\mathbf a_t.\]

The decay is separate from the adaptive gradient step.

From Adam to AdamW6.19

Keep Adam’s loss-gradient moments and bias correction:

\[\mathbf a_t=\frac{\widehat{\mathbf m}_t}{\sqrt{\widehat{\mathbf v}_t}+\epsilon_A}.\]

Adam

\[\mathbf x_t=\mathbf x_{t-1}-\eta_t\mathbf a_t.\]

AdamW also shrinks the previous parameters by \(1-\eta_t\lambda_{\rm wd}\).

\[\mathbf x_t=(1-\eta_t\lambda_{\rm wd})\mathbf x_{t-1}-\eta_t\mathbf a_t.\]

The decay is separate from the adaptive gradient step.

From Adam to AdamW6.19

Keep Adam’s loss-gradient moments and bias correction:

\[\mathbf a_t=\frac{\widehat{\mathbf m}_t}{\sqrt{\widehat{\mathbf v}_t}+\epsilon_A}.\]

Adam

\[\mathbf x_t=\mathbf x_{t-1}-\eta_t\mathbf a_t.\]

AdamW also shrinks the previous parameters by \(1-\eta_t\lambda_{\rm wd}\).

\[\mathbf x_t=(1-\eta_t\lambda_{\rm wd})\mathbf x_{t-1}-\eta_t\mathbf a_t.\]

The decay is separate from the adaptive gradient step.

Adam and AdamW: the recursions6.20

In each column, \(\mathbf g_t=\widehat{\nabla f}(\mathbf x_{t-1})\). Start with zero moments; \(t\ge1\).

Adam

\[\mathbf g_t=\widehat{\nabla f}(\mathbf x_{t-1})\]
\[\mathbf m_t=\beta_1\mathbf m_{t-1}+(1-\beta_1)\mathbf g_t\]
\[\mathbf v_t=\beta_2\mathbf v_{t-1}+(1-\beta_2)\mathbf g_t^{\odot2}\]
\[\widehat{\mathbf m}_t=\frac{\mathbf m_t}{1-\beta_1^t},\qquad\widehat{\mathbf v}_t=\frac{\mathbf v_t}{1-\beta_2^t}\]
\[\mathbf x_t=\mathbf x_{t-1}-\eta_t\frac{\widehat{\mathbf m}_t}{\sqrt{\widehat{\mathbf v}_t}+\epsilon_A}\]

Apply the adaptive gradient step.

AdamW: decoupled weight decay

\[\mathbf g_t=\widehat{\nabla f}(\mathbf x_{t-1})\]
\[\mathbf m_t=\beta_1\mathbf m_{t-1}+(1-\beta_1)\mathbf g_t\]
\[\mathbf v_t=\beta_2\mathbf v_{t-1}+(1-\beta_2)\mathbf g_t^{\odot2}\]
\[\widehat{\mathbf m}_t=\frac{\mathbf m_t}{1-\beta_1^t},\qquad\widehat{\mathbf v}_t=\frac{\mathbf v_t}{1-\beta_2^t}\]
\[\begin{aligned}\mathbf x_t={}&(1-\eta_t\lambda_{\rm wd})\mathbf x_{t-1}\\&-\eta_t\frac{\widehat{\mathbf m}_t}{\sqrt{\widehat{\mathbf v}_t}+\epsilon_A}.\end{aligned}\]

Apply the same rule, with separate decay.

The moment rules are identical. Setting \(\lambda_{\rm wd}=0\) recovers Adam. All operations are coordinatewise.

Part 6, original PDF page 39AdamW6.21
Part 6, original PDF page 39
Excursion: Doing sparse deep learning with Hadamard products6.22
Kolb, Müller, Bischl and Rügamer, Machine Learning 2026
\[\min_{\mathbf x} f(\mathbf x)+\lambda\|\mathbf x\|_1\quad\longleftrightarrow\quad\min_{\mathbf u,\mathbf v}f(\mathbf u\odot\mathbf v)+\frac{\lambda}{2}(\|\mathbf u\|_2^2+\|\mathbf v\|_2^2).\]
  • Parametrize each coefficient by \(x_j=u_jv_j\), so \(\mathbf x=\mathbf u\odot\mathbf v\).
  • An exact reformulation of the sparse penalty, not a smoothed approximation. Train the smooth surrogate with Adam or SGD.
  • The framework extends to structured sparsity and non-convex sparse penalties.

Exactness concerns the reformulation and its minima; finite training still has numerical tolerances.

Comparing optimizers

Is AdamW the best we have?

6.23
Part 6, original PDF page 25Comparison of optimizers6.24
Part 6, original PDF page 25Descending through a Crowded Valley —Benchmarking Deep Learning OptimizersRobin M. Schmidt Frank Schneider Philipp Hennig https://arxiv.org/pdf/2007.01547
Part 6, original PDF page 26Comparison of optimizers6.24
Part 6, original PDF page 26https://arxiv.org/pdf/2007.01547
Part 6, original PDF page 27Comparison of optimizers6.24
Part 6, original PDF page 27Descending through a Crowded ValleyFigure 4: Mean test set performance over random seeds of all tested optimizers on all eight optimization problems usingthe large budget for tuning and no learning rate schedule. One standard deviation for the tuned DAM optimizer is shownwith a red error bar (; error bars for other methods omitted for legibility). The performance of untuned DAM ) andOUND ) are marked for reference. The upper bound of each axis represents the best performance achieved in thebenchmark, while the lower bound is chosen in relation to the performance of DAM with default parameters. Tabularversion available in the Appendix as Table
Muon on the rise
Screenshot of Keller Jordan’s original Muon blog post, December 8, 2024
6.25
Part 6, original PDF page 38LLMs: structured parameters6.26
Part 6, original PDF page 38

A GPT-style LLM predicts the next token from the preceding text.

Thecatsatpreceding tokensEmbeddingTransformer blocksAttention matricesFeed-forward matricesNext tokenonneardownillustrative probabilities
Adam / AdamW: coordinates

Apply a scalar adaptive rule to each weight entry.

Equivalent view: vec(W). Tensors need not be flattened in code.

Muon: matrix geometry
rows and columnsprocessed together

Transform a hidden-layer update using its matrix structure.

W∈Rdout×din: keep the two-dimensional geometry.

Part 6, original PDF page 38LLMs: structured parameters6.26
Part 6, original PDF page 38

A GPT-style LLM predicts the next token from the preceding text.

Thecatsatpreceding tokensEmbeddingTransformer blocksAttention matricesFeed-forward matricesNext tokenonneardownillustrative probabilities
Adam / AdamW: coordinates

Apply a scalar adaptive rule to each weight entry.

Equivalent view: vec(W). Tensors need not be flattened in code.

Muon: matrix geometry
rows and columnsprocessed together

Transform a hidden-layer update using its matrix structure.

W∈Rdout×din: keep the two-dimensional geometry.

Part 6, original PDF page 38LLMs: structured parameters6.26
Part 6, original PDF page 38

A GPT-style LLM predicts the next token from the preceding text.

Thecatsatpreceding tokensEmbeddingTransformer blocksAttention matricesFeed-forward matricesNext tokenonneardownillustrative probabilities
Adam / AdamW: coordinates

Apply a scalar adaptive rule to each weight entry.

Equivalent view: vec(W). Tensors need not be flattened in code.

Muon: matrix geometry
rows and columnsprocessed together

Transform a hidden-layer update using its matrix structure.

W∈Rdout×din: keep the two-dimensional geometry.

Part 6, original PDF page 38Muon for LLM weight matrices6.27
Part 6, original PDF page 38

LLMs contain large matrices that map one representation to another.

Embeddingtoken → vectorAttentionQ, K, V, O weightsFeed-forwardlinear weightsOutput headvector → logitsMuon: hidden weight matrices
hout=Whin,W∈Rdout×din.
  • Use matrix structure when choosing the update direction.
  • In the reference setup, embeddings, the output head, gains and biases use AdamW.
Part 6, original PDF page 38Muon for LLM weight matrices6.27
Part 6, original PDF page 38

LLMs contain large matrices that map one representation to another.

Embeddingtoken → vectorAttentionQ, K, V, O weightsFeed-forwardlinear weightsOutput headvector → logitsMuon: hidden weight matrices
hout=Whin,W∈Rdout×din.
  • Use matrix structure when choosing the update direction.
  • In the reference setup, embeddings, the output head, gains and biases use AdamW.
Part 6, original PDF page 38Muon: the polar update direction6.28
Part 6, original PDF page 38

One matrix block; Gt=∇Wft(Wt−1), M0=0.

Mt=βMt−1+(1−β)Gt,Mt=UtΣtVt⊤.
Pt=UtVt⊤,Wt=Wt−1−ηtPt.

Teaching variant: plain momentum and exact polar factor; omit decay and shape scaling.

What changes when all nonzero singular values become 1?

Part 6, original PDF page 38Muon: the polar update direction6.28
Part 6, original PDF page 38

One matrix block; Gt=∇Wft(Wt−1), M0=0.

Mt=βMt−1+(1−β)Gt,Mt=UtΣtVt⊤.
Pt=UtVt⊤,Wt=Wt−1−ηtPt.

Teaching variant: plain momentum and exact polar factor; omit decay and shape scaling.

Part 6, original PDF page 38Polar Express: computing the direction6.29
Part 6, original PDF page 38

Approximate the polar factor using matrix products, without an SVD at each update.

Xj+1=ajXj+bj(XjXj⊤)Xj+cj(XjXj⊤)2Xj.
sj+1=ajsj+bjsj3+cjsj5,target s=1(s0>0).

Polar Express chooses a new polynomial for each inner iteration, using a spectral interval.

Start with X0=Mt/(1.01‖Mt‖F+ϵP).

How can a scalar polynomial transform an entire matrix spectrum?

The classical cubic uses fixed coefficients; Polar Express adapts its quintic coefficients.

Part 6, original PDF page 38Polar Express: computing the direction6.29
Part 6, original PDF page 38

Approximate the polar factor using matrix products, without an SVD at each update.

Xj+1=ajXj+bj(XjXj⊤)Xj+cj(XjXj⊤)2Xj.
sj+1=ajsj+bjsj3+cjsj5,target s=1(s0>0).

Polar Express chooses a new polynomial for each inner iteration, using a spectral interval.

Start with X0=Mt/(1.01‖Mt‖F+ϵP).

Part 6, original PDF page 38Polar Express in LLM training6.30
Part 6, original PDF page 38

GPT-2-Large · 774M parameters · FineWeb, 1 billion training tokens

Author figure: GPT-2 validation loss versus learning rate for Muon polar-factor methodsAuthor figure: GPT-2 validation-loss trajectories for the compared Muon implementations
  • These curves compare ways of computing the polar direction inside Muon.
  • They are a result for this training setup; this is not an AdamW comparison.

Practical Muon also specifies Nesterov momentum, weight decay, shape scaling and parameter groups.

Part 6, original PDF page 38Outlook: modern optimization of LLMs6.31
Part 6, original PDF page 38

Marin “Mochi” 535B-A23B

Open pre-training checkpoints · Open Athena · 17 November 2026

Open Athena original plot: Mochi training loss over 18.2 trillion tokens and the released checkpoints
  • A mixture-of-experts LLM.
  • 57 released checkpoints.
  • 18.2 trillion training tokens.

Different parameter groups use Muon- and Adam-family updates.

What makes optimization work at this scale?

Part 6, original PDF page 38Outlook: modern optimization of LLMs6.31
Part 6, original PDF page 38

Marin “Mochi” 535B-A23B

Open pre-training checkpoints · Open Athena · 17 November 2026

Open Athena original plot: Mochi training loss over 18.2 trillion tokens and the released checkpoints
  • A mixture-of-experts LLM.
  • 57 released checkpoints.
  • 18.2 trillion training tokens.

Different parameter groups use Muon- and Adam-family updates.

What makes optimization work at this scale?

Part 6, original PDF page 55Landscapes6.32
Part 6, original PDF page 55

Geometry of trained neural networks

How are solutions connected in parameter space?

Architecture · basins · permutation symmetry

Part 6, original PDF page 28Deep neural network landscapes6.33
Part 6, original PDF page 28Towards Understanding Generalization of DeepLearning: Perspective of Loss LandscapesLei WuSchool of Mathematics, Peking UniversityBeijing, Chinaleiwu@pku.edu.cnZhanxing ZhuBeijing Institute of Big Data Research (BIBDR)Center for Data Science, Peking UniversityBeijing, Chinazhanxing.zhu@pku.edu.cnWeinan EBeijing Institute of Big Data Research (BIBDR)Center for Data Science and BICMR, Peking University, Beijing, ChinaDepartment of Mathematics and PACM, Princeton University, Princeton, NJ, USAweinan@math.princeton.edu
Towards Understanding Generalization of Deep Learning: Perspective of Loss Landscapes

Wu, Zhu & E · 2017

Part 6, original PDF page 29Deep neural network landscapes6.33
Part 6, original PDF page 29Towards Understanding Generalization of DeepLearning: Perspective of Loss LandscapesLei WuSchool of Mathematics, Peking UniversityBeijing, Chinaleiwu@pku.edu.cnZhanxing ZhuBeijing Institute of Big Data Research (BIBDR)Center for Data Science, Peking UniversityBeijing, Chinazhanxing.zhu@pku.edu.cnWeinan EBeijing Institute of Big Data Research (BIBDR)Center for Data Science and BICMR, Peking University, Beijing, ChinaDepartment of Mathematics and PACM, Princeton University, Princeton, NJ, USAweinan@math.princeton.eduLarge Scale Structure of Neural Network LossLandscapesStanislav FortGoogle ResearchZurich, Switzerlandstanislavfort@google.comStanislaw JastrzebskiNew York UniversityNew York, United StatesAbstractThere are many surprising and perhaps counter-intuitive properties of optimizationof deep neural networks. We propose and experimentally verify a unified phenomenological model of the loss landscape that incorporates many of them. Highdimensionality plays a key role in our model. Our core idea is to model the losslandscape as a set of high dimensional wedges that together form a large-scale,inter-connected structure and towards which optimization is drawn. We first showthat hyperparameter choices such as learning rate, network width and regularization, affect the path optimizer takes through the landscape in a similar ways,influencing the large scale curvature of the regions the optimizer explores. Finally,we predict and demonstrate new counter-intuitive properties of the loss-landscape.We show an existence of low loss subspaces connecting a set (not only a pair)of solutions, and verify it experimentally. Finally, we analyze recently popularensembling techniques for deep networks in the light of our model.
Towards Understanding Generalization of Deep Learning: Perspective of Loss Landscapes

Wu, Zhu & E · 2017

Large Scale Structure of Neural Network Loss Landscapes

Fort & Jastrzębski · 2019

Part 6, original PDF page 30Deep neural network landscapes6.33
Part 6, original PDF page 30Towards Understanding Generalization of DeepLearning: Perspective of Loss LandscapesLei WuSchool of Mathematics, Peking UniversityBeijing, Chinaleiwu@pku.edu.cnZhanxing ZhuBeijing Institute of Big Data Research (BIBDR)Center for Data Science, Peking UniversityBeijing, Chinazhanxing.zhu@pku.edu.cnWeinan EBeijing Institute of Big Data Research (BIBDR)Center for Data Science and BICMR, Peking University, Beijing, ChinaDepartment of Mathematics and PACM, Princeton University, Princeton, NJ, USAweinan@math.princeton.eduVisualizing the Loss Landscape of Neural NetsHao Li, Zheng Xu, Gavin Taylor, Christoph Studer, Tom GoldsteinUniversity of Maryland, College Park United States Naval Academy Cornell University{haoli,xuzh,tomg}@cs.umd.edutaylor@usna.edustuder@cornell.eduAbstractNeural network training relies on our ability to find “good” minimizers of highlynon-convex loss functions. It is well-known that certain network architecturedesigns (e.g., skip connections) produce loss functions that train easier, and wellchosen training parameters (batch size, learning rate, optimizer) produce minimizers that generalize better. However, the reasons for these differences, and theireffect on the underlying loss landscape, are not well understood. In this paper, weexplore the structure of neural loss functions, and the effect of loss landscapes ongeneralization, using a range of visualization methods. First, we introduce a simple“filter normalization” method that helps us visualize loss function curvature andmake meaningful side-by-side comparisons between loss functions. Then, usinga variety of visualizations, we explore how network architecture affects the losslandscape, and how training parameters affect the shape of minimizers.Large Scale Structure of Neural Network LossLandscapesStanislav FortGoogle ResearchZurich, Switzerlandstanislavfort@google.comStanislaw JastrzebskiNew York UniversityNew York, United StatesAbstractThere are many surprising and perhaps counter-intuitive properties of optimizationof deep neural networks. We propose and experimentally verify a unified phenomenological model of the loss landscape that incorporates many of them. Highdimensionality plays a key role in our model. Our core idea is to model the losslandscape as a set of high dimensional wedges that together form a large-scale,inter-connected structure and towards which optimization is drawn. We first showthat hyperparameter choices such as learning rate, network width and regularization, affect the path optimizer takes through the landscape in a similar ways,influencing the large scale curvature of the regions the optimizer explores. Finally,we predict and demonstrate new counter-intuitive properties of the loss-landscape.We show an existence of low loss subspaces connecting a set (not only a pair)of solutions, and verify it experimentally. Finally, we analyze recently popularensembling techniques for deep networks in the light of our model.
Towards Understanding Generalization of Deep Learning: Perspective of Loss Landscapes

Wu, Zhu & E · 2017

Large Scale Structure of Neural Network Loss Landscapes

Fort & Jastrzębski · 2019

Visualizing the Loss Landscape of Neural Nets

Li, Xu, Taylor, Studer & Goldstein · 2018

Part 6, original PDF page 31Deep neural network landscapes6.33
Part 6, original PDF page 31Towards Understanding Generalization of DeepLearning: Perspective of Loss LandscapesLei WuSchool of Mathematics, Peking UniversityBeijing, Chinaleiwu@pku.edu.cnZhanxing ZhuBeijing Institute of Big Data Research (BIBDR)Center for Data Science, Peking UniversityBeijing, Chinazhanxing.zhu@pku.edu.cnWeinan EBeijing Institute of Big Data Research (BIBDR)Center for Data Science and BICMR, Peking University, Beijing, ChinaDepartment of Mathematics and PACM, Princeton University, Princeton, NJ, USAweinan@math.princeton.eduVisualizing the Loss Landscape of Neural NetsHao Li, Zheng Xu, Gavin Taylor, Christoph Studer, Tom GoldsteinUniversity of Maryland, College Park United States Naval Academy Cornell University{haoli,xuzh,tomg}@cs.umd.edutaylor@usna.edustuder@cornell.eduAbstractNeural network training relies on our ability to find “good” minimizers of highlynon-convex loss functions. It is well-known that certain network architecturedesigns (e.g., skip connections) produce loss functions that train easier, and wellchosen training parameters (batch size, learning rate, optimizer) produce minimizers that generalize better. However, the reasons for these differences, and theireffect on the underlying loss landscape, are not well understood. In this paper, weexplore the structure of neural loss functions, and the effect of loss landscapes ongeneralization, using a range of visualization methods. First, we introduce a simple“filter normalization” method that helps us visualize loss function curvature andmake meaningful side-by-side comparisons between loss functions. Then, usinga variety of visualizations, we explore how network architecture affects the losslandscape, and how training parameters affect the shape of minimizers.Large Scale Structure of Neural Network LossLandscapesStanislav FortGoogle ResearchZurich, Switzerlandstanislavfort@google.comStanislaw JastrzebskiNew York UniversityNew York, United StatesAbstractThere are many surprising and perhaps counter-intuitive properties of optimizationof deep neural networks. We propose and experimentally verify a unified phenomenological model of the loss landscape that incorporates many of them. Highdimensionality plays a key role in our model. Our core idea is to model the losslandscape as a set of high dimensional wedges that together form a large-scale,inter-connected structure and towards which optimization is drawn. We first showthat hyperparameter choices such as learning rate, network width and regularization, affect the path optimizer takes through the landscape in a similar ways,influencing the large scale curvature of the regions the optimizer explores. Finally,we predict and demonstrate new counter-intuitive properties of the loss-landscape.We show an existence of low loss subspaces connecting a set (not only a pair)of solutions, and verify it experimentally. Finally, we analyze recently popularensembling techniques for deep networks in the light of our model.Journal of Machine Learning Research 20 (2019) 1-34 Submitted 9/18; Revised 7/19; Published 8/19Spurious Valleys in One-hidden-layer Neural NetworkOptimization LandscapesLuca Venturi venturi@cims.nyu.eduCourant Institute of Mathematical Sciences, 251 Mercer Street, New York, NY 10012Afonso S. Bandeira bandeira@cims.nyu.eduJoan Bruna bruna@cims.nyu.eduCourant Institute of Mathematical Sciences, 251 Mercer Street, New York, NY 10012Center for Data Science, 60 5th Avenue, New York, NY 10011Editor: Animashree Anandkumar
Towards Understanding Generalization of Deep Learning: Perspective of Loss Landscapes

Wu, Zhu & E · 2017

Large Scale Structure of Neural Network Loss Landscapes

Fort & Jastrzębski · 2019

Visualizing the Loss Landscape of Neural Nets

Li, Xu, Taylor, Studer & Goldstein · 2018

Spurious Valleys in One-hidden-layer Neural Network Optimization Landscapes

Venturi, Bandeira & Bruna · 2019

Part 6, original PDF page 32Landscapes and DNN type6.34
Part 6, original PDF page 32(a) without skip connections (b) with skip connectionsFigure 1: The loss surfaces of ResNet-56 with/without skip connections. The proposed filternormalization scheme is used to enable comparisons of sharpness/flatness between the two figures.Visualizing the Loss Landscape of Neural NetsHao Li, Zheng Xu, Gavin Taylor, Christoph Studer, Tom GoldsteinUniversity of Maryland, College Park United States Naval Academy Cornell University{haoli,xuzh,tomg}@cs.umd.edutaylor@usna.edustuder@cornell.edu

Visualizing the Loss Landscape of Neural Nets

Without skip connectionsWith skip connections

ResNet-56 loss surfaces with and without skip connections. The source uses filter normalization to compare sharpness/flatness in the two figures.

Part 6, original PDF page 33Landscapes and SGD/Adam6.35
Part 6, original PDF page 33Why is SGD/ADAM/… so effective even though the landscape is highly non-convex with many local minima?
  • Landscapes are not so bad near the minima
  • After accounting for permutation symmetry, landscapes are super nice
Part 6, original PDF page 34Landscapes and SGD/Adam6.35
Part 6, original PDF page 34Essentially No Barriers in Neural Network Energy LandscapeFelix Draxler Kambis Veschgini Manfred Salmhofer Fred A. Hamprecht Figure 1. Left: A slice through the one million-dimensional training loss function of DenseNet-40-12 on CIFAR10 and the minimum energy path found by our method. The plane is spannedby the two minima and the mean of the nodes of the path. Right:Loss along the linear line segment between minima, and along ourhigh-dimensional path. Surprisingly, the energy along this path isessentially flat.Figure 2. Two dimensional loss surface, with two minima connected by a minimum energy path (MEP) and a nudged elasticband (NEB) at iteration 0, 10 and converged. Construction of NEBupdate for one pivot. The tangent points to the neighbouringpivot with higher energy. Re-distribution acts parallelly andthe loss force perpendicularly to the tangent.
Git Re-Basin6.35
Original Git Re-Basin paper title, authors and abstract
Git Re-Basin6.35

Learn permutations of hidden units while preserving the network’s function.

Original Git Re-Basin permutation illustration

Remember LJ clusters?

Lennard–Jones 13-atom cluster

LJ\(_{13}\)

Permuting hidden units can align two solutions before interpolation.

Part 6, original PDF page 37Landscapes and SGD/Adam6.35
Part 6, original PDF page 37Figure 2: Linear mode connectivity is possible after permuting. Loss when interpolating betweenmodels trained on MNIST, CIFAR-10, and ImageNet. In all cases we can significantly improve overıve interpolation. Straight-through estimator matching performs best but is very computationallyexpensive. Weight and activation matching perform similarly, although weight matching is orders ofmagnitude faster and does not rely on the input data distribution. We hypothesize that the ImageNetbarrier could be reduced by increasing the model width as in Section 5.3.After applying learned permutations , solutions are connected again (, i.e., in the same basin).
Replication and landscape claims6.35
Original Stanislav Fort post about his Git Re-Basin replication attempt
Part 6, original PDF page 38Landscape of Thoughts6.36
Part 6, original PDF page 38
Software
6.37
Part 6, original PDF page 21Optimizers in PyTorch6.38

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()
Part 6, original PDF page 22Choosing an optimizer in PyTorch6.38
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.

Part 6, original PDF page 23PyTorch: closure-based optimization6.38

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.

Part 6, original PDF page 406.39
Part 6, original PDF page 40
Part 6, original PDF page 41Optimization software: JAX6.40

JAX provides automatic differentiation and array operations.

  • Differentiate a numerical objective.
  • Compile numerical functions.
  • Use optimization libraries built on the JAX ecosystem.

JAX documentation

Part 6, original PDF page 42Optimization software: CVX6.40

Describe a convex optimization problem in a modeling language.

minx‖Ax−b‖2subject toCx=d,‖x‖∞≤α.
cvx_begin
    variable x(p)
    minimize(norm(A*x - b, 2))
    subject to
        C*x == d
        norm(x, Inf) <= alpha
cvx_end

CVX documentation

Part 6, original PDF page 43Optimization software6.40
Part 6, original PDF page 43https://github.com/cvxpy/cvxpylayers
Optimization software6.40
  • MOSEK: numerical optimization, including conic problems.
  • Gurobi: mathematical programming.
  • NLopt: local and global nonlinear optimization.

Choose a solver that supports the structure and constraints of the problem.

Part 6, original PDF page 47Optimization in a nutshell6.41
Part 6, original PDF page 47

Classical tools

  • Convexity and problem structure.
  • Full gradients and curvature.
  • Theoretical convergence guarantees.

Large-scale learning

  • Sample and mini-batch gradients.
  • Automatic differentiation.
  • Data, memory and compute budgets.

Match the method to the available information and the cost of using it.

Damek Davis — teaching and resources

Part 6, original PDF page 59Take-home messages6.42
  • Mini-batches trade gradient cost against sampling noise.
  • Adam uses adaptive coordinate scaling; AdamW applies decoupled weight decay.
  • Muon transforms matrix update directions; Polar Express approximates the polar factor efficiently.
  • Interpret LLM and landscape results in their tested setting, including symmetry, tuning and compute budgets.
Part 6, original PDF page 59Take-home messages6.42
  • Mini-batches trade gradient cost against sampling noise.
  • Adam uses adaptive coordinate scaling; AdamW applies decoupled weight decay.
  • Muon transforms matrix update directions; Polar Express approximates the polar factor efficiently.
  • Interpret LLM and landscape results in their tested setting, including symmetry, tuning and compute budgets.
Part 6, original PDF page 59Take-home messages6.42
  • Mini-batches trade gradient cost against sampling noise.
  • Adam uses adaptive coordinate scaling; AdamW applies decoupled weight decay.
  • Muon transforms matrix update directions; Polar Express approximates the polar factor efficiently.
  • Interpret LLM and landscape results in their tested setting, including symmetry, tuning and compute budgets.
Part 6, original PDF page 59Take-home messages6.42
  • Mini-batches trade gradient cost against sampling noise.
  • Adam uses adaptive coordinate scaling; AdamW applies decoupled weight decay.
  • Muon transforms matrix update directions; Polar Express approximates the polar factor efficiently.
  • Interpret LLM and landscape results in their tested setting, including symmetry, tuning and compute budgets.
What we have not covered…6.43

There is much more to optimization than we can cover in one day.

The hierarchy of convex programs6.44
GFPCPSDPSOCPQPLP
  • Each problem class has a standard form and associated solvers.
  • Many engineering models can be formulated as convex programs.
  • Convergence guarantees depend on the assumptions and algorithm.
  • Interior-point methods are an important family of solvers.

LP: linear · QP: quadratic · SOCP: second-order cone · SDP: semidefinite · CP: cone · GFP: graph-form program

Part 6, original PDF page 52The hierarchy of convex programs6.44
Part 6, original PDF page 52LP: linear program QP: quadratic program SOCP second-order cone program SDP: semidefinite program CP: cone program GFP: graph form program•Each category has a standard form and associated Generic solvers•Many engineering problems can be formulated as one of these problems and efficiently solved with theoretical guarantees •Convergence guarantees and rates can be proven under certain conditions •Interior-point methods as fundamental breakthrough
A New Polynomial-Time Algorithm for Linear Programming

Narendra Karmarkar · 1984

Linear programs6.45
\[\begin{aligned}\text{maximize}\quad&\mathbf c^\top\mathbf x\\\text{subject to}\quad&\mathbf A\mathbf x\le\mathbf b,\\&\mathbf x\ge0.\end{aligned}\]
Original polygonal feasible region and objective direction
  • The simplex algorithm is widely used, although its worst-case running time can be exponential.
  • Ellipsoid and interior-point methods provide polynomial-time guarantees under the appropriate computational model.
Part 6, original PDF page 55Duality theory6.46
Part 6, original PDF page 55
What we have not covered: Decentralized optimization
Kairouz et al., including Sebastian U. Stich: Advances and Open Problems in Federated Learning
  • Train across clients while the data remain local.
  • Local updates must cope with heterogeneous data and limited communication.
  • Federated learning often uses a central server; fully decentralized methods exchange updates peer to peer.
6.47
Further reading

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

6.48
Part 6, original PDF page 60Thank you - questions?6.49
Part 6, original PDF page 60X: @microbionautch.mueller@lmu.dechristian.mueller@helmholtz-munich.dehttps://bio-datascience.github.io/
References (1/2)6.50
1.Agnihotri, A. & Batra, N. (2020). Exploring Bayesian Optimization. Distill, 5(5), e26.
2.Ainsworth, S. K., Hayase, J. & Srinivasa, S. (2023). Git Re-Basin: Merging Models modulo Permutation Symmetries. International Conference on Learning Representations (ICLR).
3.Ainsworth, S. K., Hayase, J. & Srinivasa, S. (n.d.). Git Re-Basin: Official implementation. GitHub [software repository]. Accessed 20 November 2026.
4.Amsel, N., Persson, D., Musco, C. & Gower, R. M. (2026). The Polar Express: Optimal Matrix Sign Methods and Their Application to the Muon Algorithm. International Conference on Learning Representations (ICLR).
5.Bergstra, J. & Bengio, Y. (2012). Random Search for Hyper-Parameter Optimization. Journal of Machine Learning Research, 13, 281–305.
6.Bottou, L. (2010). Large-Scale Machine Learning with Stochastic Gradient Descent. Proceedings of COMPSTAT'2010, 177–186.
7.c-lasso contributors (n.d.). c-lasso: Constrained sparse regression. bio-datascience [software repository]. Accessed 20 November 2026.
8.Cevher, V., Becker, S. & Schmidt, M. (2014). Convex Optimization for Big Data: Scalable, randomized, and parallel algorithms for big data analytics. IEEE Signal Processing Magazine, 31(5), 32–43.
9.Combettes, P. L. & Pesquet, J. C. (2011). Proximal Splitting Methods in Signal Processing. In Fixed-Point Algorithms for Inverse Problems in Science and Engineering. Springer, 185–212.
10.Combettes, P. L. & Müller, C. L. (2020). Perspective maximum likelihood-type estimation via proximal decomposition. Electronic Journal of Statistics, 14(1), 207–238.
11.CVXPYlayers contributors (n.d.). CVXPYlayers: Differentiable convex optimization layers. CVXPY [software repository]. Accessed 20 November 2026.
12.Davidon, W. C. (1959). Variable Metric Method for Minimization. Argonne National Laboratory Report ANL-5990.
13.Davis, D. (n.d.). Teaching and research resources. Damek Davis, personal academic website. Accessed 20 November 2026.
14.Dawkins, R. (1996). Climbing Mount Improbable. W. W. Norton & Company.
15.Dial, L. (2026). Architecture Decisions for Marin 535B-A23B. Open Athena Blog, 9 November 2026.
16.Draxler, F., Veschgini, K., Salmhofer, M. & Hamprecht, F. A. (2018). Essentially No Barriers in Neural Network Energy Landscape. Proceedings of Machine Learning Research, 80, 1309–1318.
17.Duchi, J., Shalev-Shwartz, S., Singer, Y. & Chandra, T. (2008). Efficient projections onto the ℓ₁-ball for learning in high dimensions. Proceedings of the 25th international conference on Machine learning - ICML '08, 272–279.
18.Duchi, J., Hazan, E. & Singer, Y. (2011). Adaptive Subgradient Methods for Online Learning and Stochastic Optimization. Journal of Machine Learning Research, 12, 2121–2159.
19.Edureka (n.d.). What is Deep Learning?. Edureka blog. Accessed 20 November 2026.
20.Eyring, H. & Polanyi, M. (1931). Über einfache Gasreaktionen. Zeitschrift für Physikalische Chemie, Abteilung B, 12, 279–311.
21.Fort, S. & Jastrzębski, S. (2019). Large Scale Structure of Neural Network Loss Landscapes. Advances in Neural Information Processing Systems, 32.
22.Fort, S. (2022). Post on Git Re-Basin, replication, and loss-landscape claims. X, 15 September 2022 [social media post].
23.Frank, M. & Wolfe, P. (1956). An algorithm for quadratic programming. Naval Research Logistics Quarterly, 3(1-2), 95–110.
24.Frauenfelder, H., Sligar, S. G. & Wolynes, P. G. (1991). The Energy Landscapes and Motions of Proteins. Science, 254(5038), 1598–1603.
25.Grant, M. & Boyd, S. (n.d.). CVX: Matlab Software for Disciplined Convex Programming. CVX Research [software and user guide]. Accessed 20 November 2026.
26.Gurobi Optimization, LLC (n.d.). Gurobi Optimizer. Gurobi [optimization software]. Accessed 20 November 2026.
27.Hall, D. (2026). Initial Pre-Training Checkpoints for Marin “Mochi” 535B-A23B. Open Athena Blog, 17 November 2026.
28.Hansen, N. (2016). The CMA Evolution Strategy: A Tutorial. arXiv:1604.00772.
29.Hazan, E. & Kakade, S. (2019). Revisiting the Polyak step size. arXiv:1905.00313.
30.He, K., Zhang, X., Ren, S. & Sun, J. (2016). Deep Residual Learning for Image Recognition. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 770–778.
31.Hutson, M. (2019). AI protein-folding algorithms solve structures faster than ever. Nature.
32.INFORMS Computing Society (n.d.). The Nature of Mathematical Programming. INFORMS Computing Society glossary [archived 5 March 2014]. Accessed 20 November 2026.
33.Jaggi, M. (2013). Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization. Proceedings of Machine Learning Research, 28(1), 427–435.
34.Jaggi, M. (n.d.). Optimization for Machine Learning, Lecture 2. EPFL Machine Learning and Optimization Laboratory [lecture slides]. Accessed 20 November 2026.
35.JAX authors (n.d.). JAX documentation. JAX [software documentation]. Accessed 20 November 2026.
36.Johnson, S. G. (n.d.). The NLopt nonlinear-optimization package. NLopt [software documentation]. Accessed 20 November 2026.
37.Jones, D. R., Perttunen, C. D. & Stuckman, B. E. (1993). Lipschitzian optimization without the Lipschitz constant. Journal of Optimization Theory and Applications, 79(1), 157–181.
38.Jones, D. R., Schonlau, M. & Welch, W. J. (1998). Efficient Global Optimization of Expensive Black-Box Functions. Journal of Global Optimization, 13(4), 455–492.
39.Jordan, K., Jin, Y., Boza, V., You, J., Cesista, F., Newhouse, L. & Bernstein, J. (2024). Muon: An optimizer for hidden layers in neural networks. Keller Jordan blog.
40.Jordan, K., and Muon contributors (n.d.). Muon: PyTorch implementation. GitHub [software; commit f98f1cacc0263b04290753e32be8d498c1efc806]. Accessed 20 November 2026.
41.Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A. N., et al. (2021). Advances and Open Problems in Federated Learning. Foundations and Trends in Machine Learning, 14(1-2), 1–210.
42.Karmarkar, N. (1984). A new polynomial-time algorithm for linear programming. Combinatorica, 4(4), 373–395.
43.Kingma, D. P. & Ba, J. (2015). Adam: A Method for Stochastic Optimization. International Conference on Learning Representations (ICLR).
44.Kirkpatrick, S., Gelatt, C. D. & Vecchi, M. P. (1983). Optimization by Simulated Annealing. Science, 220(4598), 671–680.
45.Kjellström, G. (1969). Network Optimization by Random Variation of Component Values. Ericsson Technics, 25(3), 133–151.
46.Kjellström, G. & Taxén, L. (1981). Stochastic optimization in system design. IEEE Transactions on Circuits and Systems, 28(7), 702–715.
47.Kjellström, G. (1991). On the efficiency of Gaussian adaptation. Journal of Optimization Theory and Applications, 71(3), 589–597.
48.Kjellström, G. & Taxén, L. (1992). Gaussian Adaptation, an evolution-based efficient global optimizer. Computational and Applied Mathematics. Elsevier Science, 267–276.
49.Kolb, C., Müller, C. L., Bischl, B. & Rügamer, D. (2026). Smoothing the Edges: Smooth Optimization for Sparse Regularization Using Hadamard Overparametrization. Machine Learning, 115(4), Article 87.
References in larger text ↗
References (2/2)6.51
50.LearnThermo (n.d.). Thermodynamics tutorial, Chapter 3, Lesson A, page 1. LearnThermo [archived 2 March 2024]. Accessed 20 November 2026.
51.Li, H., Xu, Z., Taylor, G., Studer, C. & Goldstein, T. (2018). Visualizing the Loss Landscape of Neural Nets. Advances in Neural Information Processing Systems, 31.
52.Liu, D. C. & Nocedal, J. (1989). On the limited memory BFGS method for large scale optimization. Mathematical Programming, 45(1-3), 503–528.
53.Loshchilov, I. & Hutter, F. (2016). CMA-ES for Hyperparameter Optimization of Deep Neural Networks. ICLR Workshop.
54.Loshchilov, I. & Hutter, F. (2019). Decoupled Weight Decay Regularization. International Conference on Learning Representations (ICLR).
55.Maheswaranathan, N., Metz, L., Tucker, G., Choi, D. & Sohl-Dickstein, J. (2019). Guided evolutionary strategies: augmenting random search with surrogate gradients. Proceedings of Machine Learning Research, 97, 4264–4273.
56.Mersmann, O., Bischl, B., Trautmann, H., Preuss, M., Weihs, C. & Rudolph, G. (2011). Exploratory landscape analysis. Proceedings of the 13th annual conference on Genetic and evolutionary computation, 829–836.
57.Mockus, J. (1989). Bayesian Approach to Global Optimization: Theory and Applications. Kluwer Academic Publishers.
58.MOSEK ApS (n.d.). MOSEK Optimization Suite. MOSEK [optimization software]. Accessed 20 November 2026.
59.Müller, C. L. (2010). Black-box Landscapes: Characterization, Optimization, Sampling, and Application to Geometric Configuration Problems. PhD thesis, ETH Zürich, Dissertation No. 19438.
60.Müller, C. L. & Sbalzarini, I. F. (2010). Gaussian Adaptation Revisited—An Entropic View on Covariance Matrix Adaptation. Applications of Evolutionary Computation, LNCS, 6024, 432–441.
61.Müller, C. L. (2014). Stochastic Methods for Single Objective Global Optimization. Computational Intelligence in Aerospace Sciences, 63–112.
62.Neri, F. & Cotta, C. (2012). Memetic algorithms and memetic computing optimization: A literature review. Swarm and Evolutionary Computation, 2, 1–14.
63.Parikh, N. & Boyd, S. (2014). Proximal Algorithms. Foundations and Trends in Optimization, 1(3), 127–239.
64.PETSc development team (n.d.). SNES: Nonlinear Solvers. PETSc Manual [software documentation]. Accessed 20 November 2026.
65.PyTorch contributors (n.d.). torch.optim. PyTorch documentation. Accessed 20 November 2026.
66.Qiu, X., Gan, Y., Hayes, C. F., Liang, Q., Xu, Y., Dailey, R., Meyerson, E., Hodjat, B. & Miikkulainen, R. (2026). Evolution Strategies at Scale: LLM Fine-Tuning Beyond Reinforcement Learning. International Conference on Machine Learning (ICML).
67.Rastrigin, L. A. (1963). The convergence of the random search method in the extremal control of a many-parameter system. Automation and Remote Control, 24, 1337–1342.
68.Robbins, H. & Monro, S. (1951). A Stochastic Approximation Method. The Annals of Mathematical Statistics, 22(3), 400–407.
69.Rockafellar, R. T. (1993). Lagrange Multipliers and Optimality. SIAM Review, 35(2), 183–238.
70.Romero, P. A. & Arnold, F. H. (2009). Exploring protein fitness landscapes by directed evolution. Nature Reviews Molecular Cell Biology, 10(12), 866–876.
71.Romero, P. A., Krause, A. & Arnold, F. H. (2013). Navigating the protein fitness landscape with Gaussian processes. Proceedings of the National Academy of Sciences, 110(3), E193–E201.
72.Schaipp, F. (2023). Decay No More. ICLR Blogposts 2023.
73.Schaipp, F., Hägele, A., Taylor, A., Simsekli, U. & Bach, F. (2025). The Surprising Agreement Between Convex Optimization Theory and Learning-Rate Scheduling for Large Model Training. arXiv:2501.18965.
74.Schmidt, R. M., Schneider, F. & Hennig, P. (2021). Descending through a Crowded Valley - Benchmarking Deep Learning Optimizers. International Conference on Learning Representations (ICLR).
75.Singhee, A. & Rutenbar, R. A. (2009). Novel Algorithms for Fast Statistical Analysis of Scaled Circuits. Lecture Notes in Electrical Engineering, vol. 46. Springer.
76.Snoek, J., Larochelle, H. & Adams, R. P. (2012). Practical Bayesian Optimization of Machine Learning Algorithms. Advances in Neural Information Processing Systems, 25, 2951–2959.
77.Sobol', I. M. (1967). On the distribution of points in a cube and the approximate evaluation of integrals. USSR Computational Mathematics and Mathematical Physics, 7(4), 86–112.
78.Stillinger, F. H. & Weber, T. A. (1984). Packing Structures and Transitions in Liquids and Solids. Science, 225(4666), 983–989.
79.The SciPy community (n.d.). Optimization (scipy.optimize). SciPy User Guide [software documentation]. Accessed 20 November 2026.
80.Vandenberghe, L. (n.d.). Gradient methods. UCLA EE236C [lecture notes]. Accessed 20 November 2026.
81.Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L. & Polosukhin, I. (2017). Attention Is All You Need. Advances in Neural Information Processing Systems, 30, 5998–6008.
82.Venturi, L., Bandeira, A. S. & Bruna, J. (2019). Spurious Valleys in One-hidden-layer Neural Network Optimization Landscapes. Journal of Machine Learning Research, 20(133), 1–34.
83.Verpoort, P. C., Lee, A. A. & Wales, D. J. (2020). Archetypal landscapes for deep neural networks. Proceedings of the National Academy of Sciences, 117(36), 21857–21864.
84.Wales, D. J. & Doye, J. P. K. (1997). Global Optimization by Basin-Hopping and the Lowest Energy Structures of Lennard-Jones Clusters Containing up to 110 Atoms. The Journal of Physical Chemistry A, 101(28), 5111–5116.
85.Wales, D. J. (2003). Energy Landscapes: Applications to Clusters, Biomolecules and Glasses. Cambridge University Press.
86.Watson, L. T. & He, J. (2008). The Deterministic Global Optimization Algorithm DIRECT. HPCS/BIS Tutorial, 16 April 2008, Ottawa, Canada.
87.Wikipedia contributors (n.d.). Ellipsoid method. Wikipedia. Accessed 20 November 2026.
88.Wikipedia contributors (n.d.). Karmarkar’s algorithm. Wikipedia. Accessed 20 November 2026.
89.Wikipedia contributors (n.d.). Leonid Khachiyan. Wikipedia. Accessed 20 November 2026.
90.Wikipedia contributors (n.d.). Mathematical optimization. Wikipedia. Accessed 20 November 2026.
91.Wikipedia contributors (n.d.). Narendra Karmarkar. Wikipedia. Accessed 20 November 2026.
92.Wikipedia contributors (n.d.). Quasi-Newton method. Wikipedia. Accessed 20 November 2026.
93.Wright, S. (1932). The roles of mutation, inbreeding, crossbreeding and selection in evolution. Proceedings of the 6th International Congress of Genetics, 1, 356–366.
94.Wu, L., Zhu, Z. & E, W. (2017). Towards Understanding Generalization of Deep Learning: Perspective of Loss Landscapes. arXiv:1706.10239.
95.Zhou, Z., Zhu, Z., Li, X., Galkin, M., Feng, X., Koyejo, S., Tang, J. & Han, B. (2026). Landscape of Thoughts: Visualizing the Reasoning Process of Large Language Models. International Conference on Learning Representations (ICLR).
References in larger text ↗
Common course notation
p — optimized variables
n — available training examples
qₜ — candidates proposed in search round t
bₜ — training examples drawn for one stochastic gradient
kₜ — cumulative black-box evaluations
m_sel — selected parents

Press N to close
Mathematics pass

Arrows / Space: original reveal sequence
Esc: overview · F: fullscreen · H: close help

Notation corrections span all six decks.
Published source excerpts retain their original notation.
N: common notation key