Ben Grimmer

The latest "News and Views" issue from SIAM's Group on Optimization just came out. The issue highlights Alex Wang, Kevin Shu, and my work on "subgame perfect" algorithm design. These algorithms use game theory ideas to describe the best way for algorithms to adapt at runtime 1/4

Our conclusion gives several open frontiers we see ahead. This was motivated by Jelena Diakonikolas's previous News and Views piece calling for more open problems As AI becomes increasingly capable, there is growing value in articulating well what problems are open/important 3/4

siagoptimization.github.iosiagoptimization.github.io

Links for those interested Our new issue on subgame perfection: siagoptimization.github.io/assets/views... Jelena's past issue calling for open problems: siagoptimization.github.io/assets/views...

It was a joy to write some short, friendly exposition on subgame perfection (7pages). I hope many of you find it useful-or at least entertaining The resulting methods hit a sweet spot for me as a researcher, being theoretically satisfying and surprisingly, practically strong 2/4

I'm excited to share some joint work done with TaeHo Yoon. We considered algorithm design for fixed-point problems. This area models gradient descent, minimax optimization, and more. Below, I give the wild ride of this paper. Mathematically, it is gorgeous.

Taking this duality, one may ask for methods that are self-dual. Recursively building a maximally self-dual method gives a simple fractal arc diagram and a new Fractal Self-Dual Method. This FSDM nicely balances anytimeness and robustness; see the paper for details.

arxiv.orgA Theory of Composition and Duality of Extremal Optimal Fixed-Point AlgorithmsIn this work, we reveal a rich combinatorial structure underlying exact minimax optimal algorithms for classical nonexpansive fixed-point problems. This viewpoint unifies all extremal optimal methods ...

Discovering these results with TaeHo has been a delightful experience. I learned a lot. We drew on tools from combinatorics, spectral graph theory, performance estimation, and more. For those interested, the paper is here: arxiv.org/abs/2605.02231

These enable combinatorial design approaches. You can take two arc diagrams and glue them together, just adding an edge connecting their final root nodes. Spectacularly, doing so gives a new optimal method whose H matrix just glues together the component H matrices.

Connecting back to H matrices, the theory of H-duality gives relations between optimal methods. This duality has a lovely combinatorial interpretation in our arc diagrams. Dualizing an arc diagram exactly gives its so-called H-dual algorithm.

The table below shows this new perspective. OHM, in addition to its nice recursive definition and H matrix form, corresponds to a simple path graph. New diagrams generate new optimal methods. No need to think algebraically or optimize coefficients. Its all combinatorial.

Arc diagrams arise from optimal proofs of convergence. Each edge/arc corresponds to an inequality invoked in the algorithm's proof. From this equivalence, you can, without loss, totally forget about algorithm descriptions like H matrices and just think about proof graphs.

We care about optimal algorithm design (methods with the best-possible worst-case guarantee). For fixed step methods, defined by an H matrix of coefficients (below), this is tractable. The Optimal Halpern Method (OHM) converges at rate 4/N^2 and no method can do better.

It turns out there are infinitely many optimal methods. Previously, with Ernest Ryu, we characterized every optimal H matrix. Its really a zoo. TaeHo and I set out to catalogue this zoo of optimal methods. Wonderfully, extremal methods can be understood by simple "arc diagrams".

Last year, Mateo Diaz and Ian McPherson began searching for provably good nonsmooth optimization methods on manifolds. Oh boy, did I quickly learn the hard subtleties of numerical work on manifolds, especially combined with finicky subgradients.

If you retract/transport vectors by projections or via Taylor approx, you can not trust the resulting subgradients give valid lower bounds. After a year of pushing, we found a bundle method form that (provably) works despite this. I'll comment a link if you want to read more.

arxiv.orgNonsmooth Riemannian optimization with inexact manifold primitives via bundle methodsOptimization on Hadamard manifolds -- the natural Riemannian setting for globally geodesically convex problems -- relies on exponential maps to retract tangent vectors and parallel transport to connec...

Fresh arxiv paper on our method and analysis: arxiv.org/abs/2604.27078

Ben Grimmer reposted

ArXiv math.OC Optimization and Control

@optb0t.bsky.social

📚 New Arxiv Paper Title: Nonsmooth Riemannian optimization with inexact manifold primitives via bundle methods Authors: Mateo D\'iaz, Benjamin Grimmer, Ian McPherson Read more: https://arxiv.org/abs/2604.27078

Ben Grimmer reposted

Sebastian Pokutta

@spokutta.bsky.social

13 Apr

For a decade it was open whether Frank-Wolfe's O(1/√ε) rate on strongly convex sets is tight. We show it is: Ω(1/√ε), even for a simple quadratic on a unit ball.

11 Mar

For the second morning this week, one of my phd students defended (successfully!) 🎉🎓🎉 Today, Alan Luner defended his excellent work, "On Large-Scale Optimization: Optimal Methods and Computer-Assisted Algorithm Design". I promise this is the last such announcement for the year

9 Mar

This morning my PhD student Thabo Samakhoana defended his thesis (successfully!) 🎉🎓🎉 Was a great five years working with him towards his thesis "On Optimal Smoothings and their Applications to Optimization and Deep Learning"

arxiv.orgLower Bounds for Linear Minimization Oracle Methods Optimizing over Strongly Convex SetsWe consider the oracle complexity of constrained convex optimization given access to a Linear Minimization Oracle (LMO) for the constraint set and a gradient oracle for the $L$-smooth, strongly convex...

This paper generated me new office decorations as well. Below is the strongly convex set we designed that is provably hard for all Frank-Wolfe methods (at least for two steps). The paper builds this "evil" shape in d dimensions able to counteract any d/2 step method

Ben Grimmer@profgrimmer.bsky.social

For anyone interested in our lower bound result for Frank-Wolfe methods in Nemirovski and Yudin "zero-chain" lower bounding style, a link: arxiv.org/abs/2602.22608

A small digression on something I find strange in accelerated convex optimization theory: Since the 80s, in unconstrained minimization by gradient methods, smoothness is known to allow a fast O(1/T^2) convergence rate by Nesterov. Nemirovski and Yudin give matching lower bounds.

Smoothness and strong convexity are dual to each other, but here we have smoothness of the objective and strong convexity of the constraint set. Linear minimization examines the support function of the set, a dual object I don't see the connection, but there ought to be symmetry!

For anyone interested in our lower bound result for Frank-Wolfe methods in Nemirovski and Yudin "zero-chain" lower bounding style, a link: arxiv.org/abs/2602.22608

In constrained optimization by linear minimization oracle methods (Frank-Wolfe), strong convexity of the set was shown to accelerate convergence to also be O(1/T^2) by Garber and Hazan in 2015. Yesterday, I posted a paper giving the matching lower bounds So why are these two settings mirrored?

Lately, non-crossing partitions have shown up out of nowhere in my research, which have a lovely duality structure. This inspired some good art and fractals :) Wanted to share the fun here (just sharing the pretty art for now, the research story will come in due time) 1/4

The partition {1,2}{3} above is "self-dual". To get this note, I numbered the 1', 2', 3' nodes counterclockwise. We can use this self-dual partition of size N=3 to build a self-dual partition of N=7 recursively. Physically self-dual == "dream-catcher" mirrors blue and green 3/4

The pattern continues. We can fractally build an N=31 self-dual pattern constructed of two N=15 patterns or 4 N=7 patterns, carefully sewn together (pun intended). I'll stop sewing after I finish N=63 :) Stay tuned for an upcoming paper where this has unexpected algorithmic/engineering value

A noncrossing partition of {1 ... N} requires if you connect grouped numbers in a circle by string, no strings cross. Blue is {1,2}{3}. The "Kreweras" dual of this adds numbers 1', ... N', between each, taking the maximal noncrossing partition of them. Green is dual to blue. 2/4

link.springer.comOptimization LettersOptimization Letters covers all aspects of optimization, including theory, algorithms, computational studies, and applications. This journal provides an ...

2 Feb

Happy to announce that my work "On optimal universal first-order methods for minimizing heterogeneous sums" just received the Optimization Letters Best Paper Prize. link.springer.com/journal/1159... This work is part of a larger trend, fighting the brittleness of classic smooth/nonsmooth models.

Johns Hopkins Data Science and AI Institute

11 Jan

Sunday morning spent setting up my office in the new @hopkinsdsai.bsky.social building. I gained a good amount more wall space, so I have the freedom to grow my collections again

Ben Grimmer reposted

@hopkinsdsai.bsky.social

19 Dec 2025

Join us in advancing data science and AI research! The Johns Hopkins Data Science and AI Institute Postdoctoral Fellowship Program is now accepting applications for the 2026–2027 academic year. Apply now! Deadline: Jan 23, 2026. Details and apply: apply.interfolio.com/179059

My student Thabo Samakhoana and I have been obsessed with smoothings lately. The softmax/logSumExp smoothing seems to be the standard everywhere in ML and optimization. So, in what sense is this choice "optimal"? We found some "elementary" answers, both good and bad news (1/4)

The "bad" news: Despite being *nearly* optimal, we show for fixed small dimensions that strictly better smoothings exist, approximating the max function more closely and attaining our lower bound. So LogSumExp is only nearly, not exactly, minimax optimal. (3/4)

arxiv.orgAn Elementary Proof of the Near Optimality of LogSumExp SmoothingWe consider the design of smoothings of the (coordinate-wise) max function in $\mathbb{R}^d$ in the infinity norm. The LogSumExp function $f(x)=\ln(\sum^d_i\exp(x_i))$ provides a classical smoothing, ...

A link for those interested in reading 🤓 arxiv.org/abs/2512.10825 (4/4)

LogSumExp is within 20% of a lower bound we derive on how good *any* similar smoothing can be. The proof just combines inequalities for smooth convex functions, no heavy machinery needed. The good news: We aren't leaving much on the table by choosing logSumExp. (2/4)

A new paper out with TaeHo Yoon and Ernest Ryu: We looked at the design of optimal fixed-point algorithms. That is, seeking to approximately solve T(y)=y using as few evaluations of the operator T() as possible. Maximally efficient methods are "minimax optimal" 1/

This polynomial characterization opens a lot of new directions in algorithm design. As a 3D printing enthusiast I was quick to want to visualize the set of optimal methods Below is the region (living in 6 dimensions) of optimal 3-step methods that happens to sit nicely in 3D 4/

For those interested in reading 🤓 arxiv.org/pdf/2511.14915

arxiv.orgarxiv.org

This is a classic type of problem; fixed points are a broad modelling tool, capturing, for example, gradient descent In terms of algorithm design (my interest): In recent years the community pinned down an optimal method (Halpern) but showed that infinitely many others exist 2/

Our new work provides a complete description of all minimax-optimal methods. We give a set of polynomial equalities that every optimal method must satisfy ("H invariants") and similarly a needed set of polynomial ineq ("H certificates") Together these are "if and only if"!! 3/

Lately, I have been obsessed with developing theoretically based optimization algorithms that actually attain the best practical performance. Alas, the classic model of minimax optimal methods is overly conservative; it overfits to tune its worst-case. We found a path forward 1/

We have done a wide range of numerics for smooth, convex settings where our resulting subgame perfect gradient methods SPGM compete with state-of-the-art L-BFGS methods and beat existing adaptive gradient methods in iter and realtime. I am excited about the future here :) 4/

Some links for those interested 🤓 Smooth convex: arxiv.org/abs/2412.06731 Adaptive smooth convex: arxiv.org/abs/2510.21617 Nonsmooth convex: arxiv.org/abs/2511.13639

Rather than asking to do the best on the worst-case problem, we should be asking that, as it seems first-order information, our alg updates to do the best against the worst problem **with those gradients** This demands a dynamic form of optimality, called subgame perfection. 2/

In a series of works with the newest showing up on arxiv TODAY, we show that this strengthened standard is surprisingly attainable! Today we proved a method of Drori and Teboulle 2014 is a subgame perfect subgradient method and designed a new, subgame perfect proximal method 3/