Ben Grimmer @profgrimmer.bsky.social · 23/05/2026Taking 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. 110
Ben Grimmer @profgrimmer.bsky.social · 23/05/2026Connecting 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. 100
Ben Grimmer @profgrimmer.bsky.social · 23/05/2026These 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. 100
Ben Grimmer @profgrimmer.bsky.social · 23/05/2026Arc 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. 100
Ben Grimmer @profgrimmer.bsky.social · 23/05/2026The 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. 100
Ben Grimmer @profgrimmer.bsky.social · 23/05/2026It 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". 100
Ben Grimmer @profgrimmer.bsky.social · 23/05/2026We 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. 100
Ben Grimmer @profgrimmer.bsky.social · 23/05/2026I'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. 181
Ben Grimmer @profgrimmer.bsky.social · 27/02/2026This 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 040
Ben Grimmer @profgrimmer.bsky.social · 12/02/2026The 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 120
Ben Grimmer @profgrimmer.bsky.social · 12/02/2026The 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 100
Ben Grimmer @profgrimmer.bsky.social · 12/02/2026A 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 100
Ben Grimmer @profgrimmer.bsky.social · 12/02/2026Lately, 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 131
Ben Grimmer @profgrimmer.bsky.social · 11/01/2026Sunday 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 070
Ben Grimmer @profgrimmer.bsky.social · 20/11/2025This 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/ 130
Ben Grimmer @profgrimmer.bsky.social · 20/11/2025Our 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/ 120
Ben Grimmer @profgrimmer.bsky.social · 20/11/2025This 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/ 110
Ben Grimmer @profgrimmer.bsky.social · 20/11/2025A 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/ 160
Ben Grimmer @profgrimmer.bsky.social · 18/11/2025We 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/ 120
Ben Grimmer @profgrimmer.bsky.social · 18/11/2025In 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/ 140
Ben Grimmer @profgrimmer.bsky.social · 18/11/2025Rather 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/ 150
Ben Grimmer @profgrimmer.bsky.social · 18/11/2025Lately, 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/ 2154
Ben Grimmer @profgrimmer.bsky.social · 14/08/2025Enjoyed being part of the Brin Mathematical Research Center's summer school on Scientific Machine Learning last week. Many very good talks and always nice to visit UMD! 020
Ben Grimmer @profgrimmer.bsky.social · 12/08/2025You'll have to read the paper if you want the maths defining these extremal smoothings for any sublinear function and convex cone. I now have a whole family of optimal smoothing Russian nesting dolls living in my office. Enjoy: arxiv.org/abs/2508.06681 010
Ben Grimmer @profgrimmer.bsky.social · 12/08/2025If instead, you wanted the optimal outer smoothings (ie, sets containing K), there is a similar spectrum of optimal smoothings being everything between the minimal and maximal sets shown below. 100
Ben Grimmer @profgrimmer.bsky.social · 12/08/2025If we restrict to looking at inner smoothings (ie, subsets of K), it turns out there are infinitely many sets attaining the optimal level of smoothness. Our theory identifies that there is a minimal and maximal such smoothing, shown below (nesting dolls from before). 100
Ben Grimmer @profgrimmer.bsky.social · 12/08/2025To do something more nontrivial, consider the exponential cone K={(x,y,z) | z >= y exp(x/y)}, which is foundational to geometric programming. The question: What is the smoothest set differing from this cone by at distance one anywhere? My 3D print of this cone is below :) 110
Ben Grimmer @profgrimmer.bsky.social · 12/08/2025For example, you could invent many smoothings of the two-norm (five given below). In this case, the Moreau envelope gives the optimal outer smoothing. If you wanted the best smoothing of the second-order cone (the epigraph of the two-norm) a different smoothing is optimal. 110
Ben Grimmer @profgrimmer.bsky.social · 12/08/2025📢 Excited to share a new paper with PhD student Thabo Samakhoana. Nonsmooth optimization often uses smoothings, nearby smooth functions or sets. Often chosen in an ad hoc fashion. We do away with ad hoc, characterizing optimal smoothings for convex cones and sublinear functions 130
Ben Grimmer @profgrimmer.bsky.social · 05/08/2025In honor of the fun I've had playing with this puzzle and property, a homemade, ocean-themed, ceramic p=4/3 norm ball. Enjoy! 010
Ben Grimmer @profgrimmer.bsky.social · 05/08/2025As a cruel mathematician, I leave the task of verifying that the p=4/3 rotated appropriately fully and perfectly plugs a hole (equivalently has a perfect circle as a shadow) as an exercise to the reader. The dual of this wonderful property is that the 4-norm hides a circle :) 210
Ben Grimmer @profgrimmer.bsky.social · 05/08/2025For good measure, one extra round of this physical verification process, adding a purple ball fully blocks our view of the green ball, entirely plugging the hole and saving our lives yet again. 100
Ben Grimmer @profgrimmer.bsky.social · 05/08/2025Don't believe me? We can put another green p=4/3-norm ball in the glass. Looking from above, you cannot see any of the blue ball past the green one. It entirely plugs the hole! 100
Ben Grimmer @profgrimmer.bsky.social · 05/08/2025To demonstrate this, suppose my glass is the hole in our boat, we can plug it entirely by placing a blue 4/3-norm ball in the glass. 100
Ben Grimmer @profgrimmer.bsky.social · 05/08/2025The solution to cork the hole is surprisingly, radically simple: Just put the p=4/3 norm ball in the hole. Appropriately rotated, sending the direction (1,1,1)/sqrt{3} to (0,0,1). 100
Ben Grimmer @profgrimmer.bsky.social · 05/08/2025Yesterday I posted a maths puzzle that AIs all failed at (thanks for running the premium versions @xy-han.bsky.social and Ernest Ryu). The puzzle just needs elementary reasoning about p-norm balls (third row on my shelf below). This thread gives the puzzle, solution, and a 3D printed demo :) 151
Ben Grimmer @profgrimmer.bsky.social · 15/03/2025My PhD students are awesome. They gave my fiancee(wife) and I this gorgeous cherry blossom card for our wedding and soon honeymoon in Japan <3 0110
Ben Grimmer @profgrimmer.bsky.social · 12/03/2025From top row to bottom, Figure 0 above has Schatten p-norms, Vector p-norms, Function p-norms, CVAR norms, Their duals, OWL norms, Their duals. Figure 1 on the other side of my office has induced p->q matrix norm balls. p goes 1 to inf left to right. q goes 1 to inf bottom to top. 141
Ben Grimmer @profgrimmer.bsky.social · 12/03/2025As an early wedding present (happening this Saturday!), my dad made me a custom shelf to hold my collection of unit norm balls! Rockafellar+Wets's thick textbook is included for reference. 3516
Ben Grimmer @profgrimmer.bsky.social · 11/03/2025This is all modeled with ideas of Holder smoothness and uniform convexity Much to our surprise, we give "simple" optimal rates that look just like classic accelerated smooth (strongly) convex rates by *very* carefully aggregating all the heterogeneous structures! Link: arxiv.org/abs/2503.07566 040
Ben Grimmer @profgrimmer.bsky.social · 11/03/2025New (first) paper with my student Aaron Zoll :) We consider first-order methods for a ridiculously general model: minimizing a convex composition of functions g_j(x) that vary heterogeneously in whether they are smooth, nonsmooth, convex, strongly convex or anything in between. 1121
Ben Grimmer @profgrimmer.bsky.social · 15/02/2025PhD students set up arts and crafts to make Valentine's mailboxes and collect cards. They (slide) rule :) 130
Ben Grimmer @profgrimmer.bsky.social · 29/01/2025Newest office addition might be the biggest computer in my department! (Assuming compute is measured by length) 040
Ben Grimmer @profgrimmer.bsky.social · 08/01/2025Continuing to use January's freedom, some exposition on OWL Norms: Their unit balls are all Catalan solids (every face is the same). So the dual balls are all Archimedean solids (every corner is the same) www.ams.jhu.edu/~grimmer/OWL... Files to make your own: www.printables.com/model/113805... 050
Ben Grimmer @profgrimmer.bsky.social · 29/12/2024The way computers store real numbers (floating point) is exactly the same as how our grandparents did math mechanically, slide rules and log scales. I'm mass producing binary slide rules to give students on day one of my "Intro to Computational Math" this Spring :) 1120
Ben Grimmer @profgrimmer.bsky.social · 10/12/2024SPGM (and a variant using only a limited memory of old gradients) is surprisingly cheap to implement, only requiring solving a low-dim convex problem to plan each dynamically minimax optimal step. Numerical it keeps up with BFGS(!) while sporting stronger theoretical guarantees 110
Ben Grimmer @profgrimmer.bsky.social · 10/12/2024Our "Subgame Perfect Gradient Method" attains not only the best worst-case over all smooth convex problems but, at every iteration, the best worst-case over all smooth convex problems agreeing with the first-order info seen so far. For x^2, it solves exactly in two steps. 100
Ben Grimmer @profgrimmer.bsky.social · 10/12/2024New work out with Alex L Wang and Kevin Shu going beyond minimax optimal gradient method design! Kim and Fessler designed an optimal method (OGM), with the best worst-case over all smooth convex problems. Alas, on easier problems, it may be slow, its worst case occurs on x^2! 171
Ben Grimmer @profgrimmer.bsky.social · 07/12/2024Leveling up from 3D printing: I present a p=4/3 norm ball ceramic (Moreau, featured in background, likes it) 1112
Ben Grimmer @profgrimmer.bsky.social · 30/11/2024I'd like to add some more spectrahedron's to my office and to serve as examples in some upcoming talks. My current working examples come from approximating the MAX-CUT polyhedron for 3x3 and 4x4 matrices. Anyone have recommendations? Details on MAX-CUT bodies below: www.ams.jhu.edu/~grimmer/Max... 050