The Broximal Point Method and Its Impact on Optimization Theory and Machine Learning
This talk introduces the Broximal Point Method (BPM), a condition-number-free alternative to classical proximal methods, that replaces proximal penalties with ball constraints, surveys its theoretical extensions and distributed variants, and explains how approximate non-Euclidean Brox updates underpin practical machine learning optimizers.
Overview
The Broximal Point Method (BPM) of Gruntkowska, Li, Rane, and Richtárik, related to the ball-oracle work of Carmon, Sidford, et al., replaces the quadratic penalty of the classical proximal point method with a ball constraint. In the nonsmooth convex regime it converges linearly and in finitely many steps, without dependence on any condition number. I will focus on the basic results described in Gruntkowska et al., then briefly cover four extensions: a non-Euclidean theory that makes BPM a blueprint for geometry-aware methods; Broximal Alignment, a condition under which BPM finds a global minimizer with no smoothness or Lipschitz assumption; Local LMO, which applies a linear minimization oracle on the constraint set intersected with a local ball and recovers gradient-descent rates without projections; and distributed Brox (new results; not yet online). BPM itself is a conceptual method. What makes it useful in machine learning is approximation: apply Brox to a stochastic linear model of the objective, approximately, under a specific non-Euclidean norm. That construction is Muon (and its relatives). I will sketch this link and our follow-up work on theory of this family.
Presenters
Brief Biography
Before joining KAUST in 2017, he was an Associate Professor of Mathematics at the University of Edinburgh, and held postdoctoral and visiting positions at Université Catholique de Louvain, Belgium, and University of California, Berkeley, USA, respectively. Richtárik obtained a Mgr. in Mathematics ('01) at Comenius University in his native Slovakia. In 2007, he received his Ph.D. in Operations Research from Cornell University, U.S. Dr. Richtarik is a founding member and a Fellow of the Alan Turing Institute (UK National Institute for Data Science and Artificial Intelligence), and an EPSRC Fellow in Mathematical Sciences.
A number of honors and awards have been conferred on Dr. Richtárik, including:
- the Best Paper Award at the NeurIPS 2020 Workshop on Scalability, Privacy, and Security in Federated Learning (joint with S. Horvath);
- the Charles Broyden Prize, a Distinguished Speaker Award at the 2019 International Conference on Continuous Optimization, the SIAM SIGEST Best Paper Award (joint with O. Fercoq);
- the IMA Leslie Fox Prize (second prize, three times, awarded to two of his students and a postdoc);
- the SIAM SIGEST Best Paper Award (joint award with Professor Olivier Fercoq);
- the IMA Leslie Fox Prize (Second prize: M. Takáč 2013, O. Fercoq 2015 and R. M. Gower 2017);
- the INFORMS Computing Society Best Student Paper Award (sole runner-up: M. Takáč);
- the EUSA Award for Best Research or Dissertation Supervisor (Second Prize), 2016;
- and the Turing Fellow Award from the Alan Turing Institute, 2016.
Before joining KAUST, he was nominated for the Chancellor’s Rising Star Award from the University of Edinburgh in 2014, the Microsoft Research Faculty Fellowship in 2013, and the Innovative Teaching Award from the University of Edinburgh in 2011 and 2012.
Dr. Richtárik has given more than 150 research talks at conferences, workshops and seminars worldwide. And several of his works are among the most read papers published by the SIAM Journal on Optimization and the SIAM Journal on Matrix Analysis and Applications.
Dr. Richtárik regularly serves as an Area Chair for leading machine learning conferences, including NeurIPS, ICML and ICLR, and is an Action Editor of the Journal of Machine Learning Research (JMLR), Associate Editor of Optimization Methods and Software and Numerische Mathematik, and a Handling Editor of the Journal of Nonsmooth Analysis and Optimization. In the past, he served as an Action Editor of Transactions of Machine Learning Research and an Area Editor of Journal of Optimization Theory and Applications. He was an Area Chair for ICML 2019 and a Senior Program Committee Member for IJCAI 2019. And he is an Associate Editor of Optimization Methods and Software and a Handling Editor of the Journal of Nonsmooth Analysis and Optimization.
