---
references:
- id: AgarwalReliable2014
  accessed:
    - year: 2015
      month: 6
      day: 18
  author:
    - family: Agarwal
      given: Alekh
    - family: Chapelle
      given: Olivier
    - family: Dudık
      given: Miroslav
    - family: Langford
      given: John
  citation-key: AgarwalReliable2014
  container-title: Journal of Machine Learning Research
  ISSN: 1532-4435
  issue: '1'
  issued:
    - year: 2014
  page: 1111–1133
  title: A Reliable Effective Terascale Linear Learning System
  type: article-journal
  URL: http://www.jmlr.org/papers/volume15/agarwal14a/agarwal14a.pdf
  volume: '15'

- id: Allen-ZhuLingering2019
  accessed:
    - year: 2019
      month: 1
      day: 14
  author:
    - family: Allen-Zhu
      given: Zeyuan
    - family: Simchi-Levi
      given: David
    - family: Wang
      given: Xinshang
  citation-key: Allen-ZhuLingering2019
  container-title: arXiv:1901.02871 [cs, math, stat]
  issued:
    - year: 2019
      month: 1
      day: 9
  title: 'The Lingering of Gradients: How to Reuse Gradients over Time'
  type: article-journal
  URL: http://arxiv.org/abs/1901.02871

- id: Allen-ZhuOptimal2016
  author:
    - family: Allen-Zhu
      given: Zeyuan
    - family: Hazan
      given: Elad
  citation-key: Allen-ZhuOptimal2016
  container-title: Advances in Neural Information Processing Systems 29
  editor:
    - family: Lee
      given: D. D.
    - family: Sugiyama
      given: M.
    - family: Luxburg
      given: U. V.
    - family: Guyon
      given: I.
    - family: Garnett
      given: R.
  issued:
    - year: 2016
  page: 1606–1614
  publisher: Curran Associates, Inc.
  title: Optimal Black-Box Reductions Between Optimization Objectives
  type: paper-conference
  URL: >-
    http://papers.nips.cc/paper/6364-optimal-black-box-reductions-between-optimization-objectives.pdf

- id: AnderssonCasADi2019
  accessed:
    - year: 2020
      month: 4
      day: 16
  author:
    - family: Andersson
      given: Joel A. E.
    - family: Gillis
      given: Joris
    - family: Horn
      given: Greg
    - family: Rawlings
      given: James B.
    - family: Diehl
      given: Moritz
  citation-key: AnderssonCasADi2019
  container-title: Mathematical Programming Computation
  container-title-short: Math. Prog. Comp.
  DOI: 10.1007/s12532-018-0139-4
  ISSN: 1867-2949, 1867-2957
  issue: '1'
  issued:
    - year: 2019
      month: 3
  language: en
  page: 1-36
  title: 'CasADi: a software framework for nonlinear optimization and optimal control'
  type: article-journal
  URL: http://www.optimization-online.org/DB_FILE/2018/01/6420.pdf
  volume: '11'

- id: BansalPotentialFunction2019
  accessed:
    - year: 2023
      month: 8
      day: 25
  author:
    - family: Bansal
      given: Nikhil
    - family: Gupta
      given: Anupam
  citation-key: BansalPotentialFunction2019
  issued:
    - year: 2019
      month: 6
      day: 2
  language: en
  number: arXiv:1712.04581
  publisher: arXiv
  title: Potential-Function Proofs for First-Order Methods
  type: article
  URL: http://arxiv.org/abs/1712.04581

- id: BeckFast2009
  accessed:
    - year: 2016
      month: 9
      day: 21
  author:
    - family: Beck
      given: Amir
    - family: Teboulle
      given: Marc
  citation-key: BeckFast2009
  container-title: SIAM Journal on Imaging Sciences
  DOI: 10.1137/080716542
  ISSN: 1936-4954
  issue: '1'
  issued:
    - year: 2009
      month: 1
  language: en
  page: 183-202
  title: >-
    A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse
    Problems
  type: article-journal
  URL: http://mechroom.technion.ac.il/~becka/papers/71654.pdf
  volume: '2'

- id: BeckMirror2003
  accessed:
    - year: 2019
      month: 7
      day: 3
  author:
    - family: Beck
      given: Amir
    - family: Teboulle
      given: Marc
  citation-key: BeckMirror2003
  container-title: Operations Research Letters
  container-title-short: Operations Research Letters
  DOI: 10.1016/S0167-6377(02)00231-6
  ISSN: '01676377'
  issue: '3'
  issued:
    - year: 2003
      month: 5
  language: en
  page: 167-175
  title: >-
    Mirror descent and nonlinear projected subgradient methods for convex
    optimization
  type: article-journal
  volume: '31'

- id: BetancourtSymplectic2018
  accessed:
    - year: 2019
      month: 7
      day: 26
  author:
    - family: Betancourt
      given: Michael
    - family: Jordan
      given: Michael I.
    - family: Wilson
      given: Ashia C.
  citation-key: BetancourtSymplectic2018
  container-title: arXiv:1802.03653 [stat]
  issued:
    - year: 2018
      month: 2
      day: 10
  title: On Symplectic Optimization
  type: article-journal
  URL: http://arxiv.org/abs/1802.03653

- id: BotevNesterov2016
  accessed:
    - year: 2017
      month: 7
      day: 28
  author:
    - family: Botev
      given: Aleksandar
    - family: Lever
      given: Guy
    - family: Barber
      given: David
  citation-key: BotevNesterov2016
  container-title: arXiv:1607.01981 [cs, stat]
  issued:
    - year: 2016
      month: 7
      day: 7
  title: >-
    Nesterov's Accelerated Gradient and Momentum as approximations to
    Regularised Update Descent
  type: article-journal
  URL: http://arxiv.org/abs/1607.01981

- id: BubeckConvex2015
  accessed:
    - year: 2015
      month: 12
      day: 2
  author:
    - family: Bubeck
      given: Sébastien
  citation-key: BubeckConvex2015
  collection-title: Foundations and Trends in Machine Learning
  DOI: 10.1561/2200000050
  issued:
    - year: 2015
  language: en
  publisher: Now Publishers
  title: 'Convex Optimization: Algorithms and Complexity'
  type: book
  URL: http://arxiv.org/abs/1405.4980
  volume: '8'

- id: BubeckFive2019
  archive: Calibre
  author:
    - family: Bubeck
      given: Sébastien
  citation-key: BubeckFive2019
  issued:
    - year: 2019
  title: The five miracles of mirror descent
  type: book

- id: ChenSmoothing2012
  accessed:
    - year: 2016
      month: 7
      day: 13
  author:
    - family: Chen
      given: Xiaojun
  citation-key: ChenSmoothing2012
  container-title: Mathematical Programming
  container-title-short: Math. Program.
  DOI: 10.1007/s10107-012-0569-0
  ISSN: 0025-5610, 1436-4646
  issue: '1'
  issued:
    - year: 2012
      month: 6
      day: 22
  language: en
  page: 71-99
  title: Smoothing methods for nonsmooth, nonconvex minimization
  type: article-journal
  URL: https://www.polyu.edu.hk/ama/staff/xjchen/MPB2012_reprint.pdf
  volume: '134'

- id: ChoromanskaLoss2015
  accessed:
    - year: 2015
      month: 6
      day: 17
  author:
    - family: Choromanska
      given: Anna
    - family: Henaff
      given: MIkael
    - family: Mathieu
      given: Michael
    - family: Ben Arous
      given: Gerard
    - family: LeCun
      given: Yann
  citation-key: ChoromanskaLoss2015
  container-title: >-
    Proceedings of the Eighteenth International Conference on Artificial
    Intelligence and Statistics
  event-title: Artificial Intelligence and Statistics
  issued:
    - year: 2015
  page: 192–204
  title: The Loss Surfaces of Multilayer Networks
  type: paper-conference
  URL: http://proceedings.mlr.press/v38/choromanska15.html

- id: dAspremontAcceleration2021
  accessed:
    - year: 2021
      month: 2
      day: 18
  author:
    - family: Aspremont
      given: Alexandre
      non-dropping-particle: d’
    - family: Scieur
      given: Damien
    - family: Taylor
      given: Adrien
  citation-key: dAspremontAcceleration2021
  container-title: arXiv:2101.09545 [cs, math]
  issued:
    - year: 2021
      month: 1
      day: 23
  title: Acceleration Methods
  type: article-journal
  URL: http://arxiv.org/abs/2101.09545

- id: DefazioSAGA2014
  author:
    - family: Defazio
      given: Aaron
    - family: Bach
      given: Francis
    - family: Lacoste-Julien
      given: Simon
  citation-key: DefazioSAGA2014
  container-title: Advances in Neural Information Processing Systems 27
  issued:
    - year: 2014
      month: 7
      day: 1
  title: >-
    SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly
    Convex Composite Objectives
  type: paper-conference
  URL: http://arxiv.org/abs/1407.0202

- id: DeVoreNonlinear1998
  accessed:
    - year: 2015
      month: 6
      day: 26
  author:
    - family: DeVore
      given: Ronald A.
  citation-key: DeVoreNonlinear1998
  container-title: Acta Numerica
  DOI: 10.1017/S0962492900002816
  ISSN: 1474-0508
  issued:
    - year: 1998
      month: 1
  page: 51–150
  title: Nonlinear approximation
  type: article-journal
  URL: http://people.math.sc.edu/devore/publications/NLACTA.pdf
  volume: '7'

- id: DomingosEvery2020
  accessed:
    - year: 2020
      month: 12
      day: 12
  author:
    - family: Domingos
      given: Pedro
  citation-key: DomingosEvery2020
  container-title: arXiv:2012.00152 [cs, stat]
  issued:
    - year: 2020
      month: 11
      day: 30
  title: Every Model Learned by Gradient Descent Is Approximately a Kernel Machine
  type: article-journal
  URL: http://arxiv.org/abs/2012.00152

- id: GohWhy2017
  accessed:
    - year: 2022
      month: 4
      day: 23
  author:
    - family: Goh
      given: Gabriel
  citation-key: GohWhy2017
  container-title: Distill
  container-title-short: Distill
  DOI: 10.23915/distill.00006
  ISSN: 2476-0757
  issue: '4'
  issued:
    - year: 2017
      month: 4
      day: 4
  language: en
  page: e6
  title: Why Momentum Really Works
  type: article-journal
  URL: http://distill.pub/2017/momentum
  volume: '2'

- id: HintonNeural
  author:
    - family: Hinton
      given: Geoffrey
    - family: Srivastava
      given: Nitish
    - family: Kevin Swersky
      given: ''
  citation-key: HintonNeural
  title: Neural Networks for Machine Learning
  type: speech

- id: JacobsenParameterfree2022
  accessed:
    - year: 2023
      month: 8
      day: 24
  author:
    - family: Jacobsen
      given: Andrew
    - family: Cutkosky
      given: Ashok
  citation-key: JacobsenParameterfree2022
  DOI: 10.48550/arXiv.2203.00444
  issued:
    - year: 2022
      month: 9
      day: 17
  number: arXiv:2203.00444
  publisher: arXiv
  title: Parameter-free Mirror Descent
  type: article
  URL: http://arxiv.org/abs/2203.00444

- id: JakoveticConvergence2014
  author:
    - family: Jakovetic
      given: D.
    - family: Freitas Xavier
      given: J.M.
    - family: Moura
      given: J.M.F.
  citation-key: JakoveticConvergence2014
  container-title: IEEE Transactions on Signal Processing
  DOI: 10.1109/TSP.2013.2291221
  ISSN: 1053-587X
  issue: '4'
  issued:
    - year: 2014
      month: 2
  page: 868-882
  title: >-
    Convergence Rates of Distributed Nesterov-Like Gradient Methods on Random
    Networks
  type: article-journal
  URL: http://arxiv.org/abs/1308.0916
  volume: '62'

- id: LangfordSparse2009
  accessed:
    - year: 2015
      month: 6
      day: 18
  author:
    - family: Langford
      given: John
    - family: Li
      given: Lihong
    - family: Zhang
      given: Tong
  citation-key: LangfordSparse2009
  container-title: Advances in Neural Information Processing Systems 21
  editor:
    - family: Koller
      given: D.
    - family: Schuurmans
      given: D.
    - family: Bengio
      given: Y.
    - family: Bottou
      given: L.
  issued:
    - year: 2009
  page: 905–912
  publisher: Curran Associates, Inc.
  title: Sparse Online Learning via Truncated Gradient
  type: paper-conference
  URL: >-
    http://papers.nips.cc/paper/3585-sparse-online-learning-via-truncated-gradient.pdf

- id: LeeFirstorder2017
  accessed:
    - year: 2020
      month: 12
      day: 14
  author:
    - family: Lee
      given: Jason D.
    - family: Panageas
      given: Ioannis
    - family: Piliouras
      given: Georgios
    - family: Simchowitz
      given: Max
    - family: Jordan
      given: Michael I.
    - family: Recht
      given: Benjamin
  citation-key: LeeFirstorder2017
  container-title: arXiv:1710.07406 [cs, math, stat]
  issued:
    - year: 2017
      month: 10
      day: 19
  title: First-order Methods Almost Always Avoid Saddle Points
  type: article-journal
  URL: http://arxiv.org/abs/1710.07406

- id: LeeGradient2016
  accessed:
    - year: 2020
      month: 12
      day: 14
  author:
    - family: Lee
      given: Jason D.
    - family: Simchowitz
      given: Max
    - family: Jordan
      given: Michael I.
    - family: Recht
      given: Benjamin
  citation-key: LeeGradient2016
  container-title: arXiv:1602.04915 [cs, math, stat]
  issued:
    - year: 2016
      month: 3
      day: 4
  title: Gradient Descent Converges to Minimizers
  type: article-journal
  URL: http://arxiv.org/abs/1602.04915

- id: MaDiving2017
  author:
    - family: Ma
      given: Siyuan
    - family: Belkin
      given: Mikhail
  citation-key: MaDiving2017
  container-title: arXiv:1703.10622 [cs, stat]
  issued:
    - year: 2017
      month: 3
      day: 30
  title: >-
    Diving into the shallows: a computational perspective on large-scale shallow
    learning
  type: article-journal
  URL: http://arxiv.org/abs/1703.10622

- id: MandtStochastic2017
  accessed:
    - year: 2018
      month: 4
      day: 3
  author:
    - family: Mandt
      given: Stephan
    - family: Hoffman
      given: Matthew D.
    - family: Blei
      given: David M.
  citation-key: MandtStochastic2017
  container-title: JMLR
  issued:
    - year: 2017
      month: 4
      day: 13
  title: Stochastic Gradient Descent as Approximate Bayesian Inference
  type: article-journal
  URL: http://arxiv.org/abs/1704.04289

- id: NesterovEfficiency2012
  accessed:
    - year: 2016
      month: 9
      day: 21
  author:
    - family: Nesterov
      given: Y.
  citation-key: NesterovEfficiency2012
  container-title: SIAM Journal on Optimization
  container-title-short: SIAM J. Optim.
  DOI: 10.1137/100802001
  ISSN: 1052-6234
  issue: '2'
  issued:
    - year: 2012
      month: 1
      day: 1
  page: 341-362
  title: Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems
  type: article-journal
  URL: http://www.optimization-online.org/DB_FILE/2010/01/2527.pdf
  volume: '22'

- id: NesterovGradient2012
  accessed:
    - year: 2016
      month: 7
      day: 13
  author:
    - family: Nesterov
      given: Yu
  citation-key: NesterovGradient2012
  container-title: Mathematical Programming
  container-title-short: Math. Program.
  DOI: 10.1007/s10107-012-0629-5
  ISSN: 0025-5610, 1436-4646
  issue: '1'
  issued:
    - year: 2012
      month: 12
      day: 21
  language: en
  page: 125-161
  title: Gradient methods for minimizing composite functions
  type: article-journal
  URL: http://premolab.ru/pub_files/pub88/qhkDNEyp8.pdf
  volume: '140'

- id: NocedalNumerical2006
  accessed:
    - year: 2019
      month: 2
      day: 5
  author:
    - family: Nocedal
      given: Jorge
    - family: Wright
      given: S.
  citation-key: NocedalNumerical2006
  collection-title: Springer Series in Operations Research and Financial Engineering
  edition: '2'
  event-place: New York
  ISBN: 978-0-387-30303-1
  issued:
    - year: 2006
  language: en
  publisher: Springer-Verlag
  publisher-place: New York
  title: Numerical Optimization
  type: book
  URL: https://www.springer.com/gp/book/9780387303031

- id: RichardsLearning2021
  accessed:
    - year: 2022
      month: 2
      day: 14
  author:
    - family: Richards
      given: Dominic
    - family: Rabbat
      given: Mike
  citation-key: RichardsLearning2021
  container-title: arXiv:2101.04968 [cs, math, stat]
  issued:
    - year: 2021
      month: 6
      day: 1
  title: Learning with Gradient Descent and Weakly Convex Losses
  type: article-journal
  URL: http://arxiv.org/abs/2101.04968

- id: RuderOverview2016
  accessed:
    - year: 2017
      month: 3
      day: 2
  author:
    - family: Ruder
      given: Sebastian
  citation-key: RuderOverview2016
  container-title: arXiv:1609.04747 [cs]
  issued:
    - year: 2016
      month: 9
      day: 15
  title: An overview of gradient descent optimization algorithms
  type: article-journal
  URL: http://arxiv.org/abs/1609.04747

- id: SagunExplorations2014
  accessed:
    - year: 2015
      month: 6
      day: 17
  author:
    - family: Sagun
      given: Levent
    - family: Guney
      given: V. Ugur
    - family: Arous
      given: Gerard Ben
    - family: LeCun
      given: Yann
  citation-key: SagunExplorations2014
  container-title: arXiv:1412.6615 [cs, stat]
  issued:
    - year: 2014
      month: 12
      day: 20
  title: Explorations on high dimensional landscapes
  type: article-journal
  URL: http://arxiv.org/abs/1412.6615

- id: WainwrightStructured2014
  accessed:
    - year: 2014
      month: 8
      day: 16
  author:
    - family: Wainwright
      given: Martin J.
  citation-key: WainwrightStructured2014
  container-title: Annual Review of Statistics and Its Application
  DOI: 10.1146/annurev-statistics-022513-115643
  ISSN: 2326-8298, 2326-831X
  issue: '1'
  issued:
    - year: 2014
      month: 1
      day: 3
  language: en
  page: 233-253
  title: >-
    Structured Regularizers for High-Dimensional Problems: Statistical and
    Computational Issues
  type: article-journal
  URL: http://www.eecs.berkeley.edu/~wainwrig/Papers/Wai14_AnnRev.pdf
  volume: '1'

- id: WibisonoAccelerated2015
  accessed:
    - year: 2018
      month: 1
      day: 17
  author:
    - family: Wibisono
      given: Andre
    - family: Wilson
      given: Ashia C.
  citation-key: WibisonoAccelerated2015
  container-title: arXiv:1509.03616 [math]
  issued:
    - year: 2015
      month: 9
      day: 11
  title: On Accelerated Methods in Optimization
  type: article-journal
  URL: http://arxiv.org/abs/1509.03616

- id: WibisonoVariational2016
  accessed:
    - year: 2018
      month: 1
      day: 17
  author:
    - family: Wibisono
      given: Andre
    - family: Wilson
      given: Ashia C.
    - family: Jordan
      given: Michael I.
  citation-key: WibisonoVariational2016
  container-title: Proceedings of the National Academy of Sciences
  container-title-short: PNAS
  DOI: 10.1073/pnas.1614734113
  ISSN: 0027-8424, 1091-6490
  issue: '47'
  issued:
    - year: 2016
      month: 11
      day: 22
  language: en
  page: E7351-E7358
  PMID: '27834219'
  title: A variational perspective on accelerated methods in optimization
  type: article-journal
  URL: http://arxiv.org/abs/1603.04245
  volume: '113'

- id: WrightOptimization2021
  author:
    - family: Wright
      given: Stephen J.
    - family: Recht
      given: Benjamin
  call-number: QA76.9.B45 W75 2021
  citation-key: WrightOptimization2021
  DOI: 10.1017/9781009004282
  event-place: New York
  ISBN: 978-1-316-51898-4
  issued:
    - year: 2021
  publisher: Cambridge University Press
  publisher-place: New York
  title: Optimization for data analysis
  type: book
  URL: >-
    https://www.cambridge.org/core/books/optimization-for-data-analysis/C02C3708905D236AA354D1CE1739A6A2

- id: ZinkevichOnline2003
  accessed:
    - year: 2018
      month: 3
      day: 17
  author:
    - family: Zinkevich
      given: Martin
  citation-key: ZinkevichOnline2003
  collection-title: ICML'03
  container-title: >-
    Proceedings of the Twentieth International Conference on International
    Conference on Machine Learning
  event-place: Washington, DC, USA
  ISBN: 978-1-57735-189-4
  issued:
    - year: 2003
  page: 928–935
  publisher: AAAI Press
  publisher-place: Washington, DC, USA
  title: Online Convex Programming and Generalized Infinitesimal Gradient Ascent
  type: paper-conference
  URL: http://dl.acm.org/citation.cfm?id=3041838.3041955
...
