These days, preconditioners seem to be everywhere. In discussions of deep learning optimizers, we collect gradients, build matrices, take matrix roots, and call the result “an adaptation to the geometry of the problem.” The matrices can be diagonal, block diagonal, or Kronecker factored. There is an impressive amount of linear algebra involved. But what, exactly, is being conditioned? And what does it mean to “condition”?
In this blog post, I will present one of the deep learning myths: the full-matrix AdaGrad explanation of preconditioning.
TL;DR Full-matrix AdaGrad bound is never better and often worse than the one with a scalar learning rate.
1. Preconditioning, The One With A Definition
In classical optimization, preconditioning has precise role and definition. Consider a quadratic function
A preconditioned gradient step has the form
Under the change of variables , this is equivalent to gradient descent on a quadratic with Hessian
. So, the purpose of the preconditioner is to improve the condition number
That ratio controls the convergence rate. With an appropriate stepsize, a smaller ratio gives faster convergence; if , the transformed Hessian is the identity and a step with
reaches the minimizer. Here, there is a quantity to improve, and a theorem connecting it to progress (Boyd & Vandenberghe, 2004, Sections 9.4.1 and 9.4.4).
Instead, in the deep learning mythology the explanation often takes a different, unclear route. The theoretical story begins with AdaGrad: choose a matrix that would have been optimal in hindsight, approximate it using past gradients, and prove an adaptive regret bound. Shampoo is a concrete example of carrying this motivation into tensor optimization for deep learning (Gupta et al., 2018). In this story, a Hessian and its condition number does not appear at all.
There is nothing wrong with constructing a different view of “conditioning.” But are we sure this explanation makes sense? Let’s take a closer look at it.
2. A Prequel To The Myth
Let be nonempty, closed, convex, and bounded, with Euclidean diameter
At round , we produce
, receive a subgradient
of a convex function
. For
, convexity gives
The left hand side measure the average suboptimality gap, that is, how much on average we are far from the minimum. It is therefore enough to control the sum on the right hand side to obtain the convergence of the optimization algorithm.
Fix a symmetric positive-definite matrix and define the weighted norm
Since , the Bregman divergence is
Absorb the scalar stepsize into . Online Mirror Descent (OMD) becomes
Completing the square gives
Without constraints, this is simply . Thus, a quadratic regularizer gives a preconditioned gradient step, with
as the preconditioner.
The optimality condition for (1) says
Using the identity for three squared distances, then completing a square, we obtain
Now sum over time. The distance terms telescope. Writing
and using , we get
For a positive-semidefinite matrix, . Consequently,
This gives a convenient upper bound:
The first term increases if becomes “bigger”; the second decreases if the
becomes bigger and if its inverse aligns with
. We can now choose
by balancing them.
2.1. The Best Matrix, If We Knew The Future
Suppose that were available. What matrix would minimize the right-hand side of (3)?
There is a short proof that avoids matrix derivatives. Recall that . For every
,
If , equality holds precisely when
If is singular, this is an infimum, approached by
as
.
The inverse square root has appeared naturally. It is the choice that optimizes this upper bound. Unfortunately, it requires the gradients from all rounds, including the ones we have not seen. A useful calculation, but not yet an algorithm.
Remark 1. Observe that this optimization holds the gradient sequence fixed. For nonlinear losses, changing the matrix can change the iterates and therefore later gradients. However, this is a minor problem in our derivations and we will ignore it.
2.2. Replace The Future By The Gradients We Have
After observing , define
The obvious approximation to is
. More generally, let
and use the changing quadratic regularizer
Choose any . At each round, OMD uses the Bregman divergence of this current regularizer:
The literal substitution corresponds to . We keep
in the proof so that we can optimize the final constant.
Note that if the matrix is singular, a minimizer still exists and the update can be written using the pseudo-inverse.
We can now prove a convergence guarantee for this update.
Theorem 2. For every
, the OMD update (5) satisfies, for all
,
In particular,
gives
This is the classical full-matrix AdaGrad bound (Duchi et al., 2010, Corollary 12). Let us prove it directly.
Proof Of The Full-Matrix-AdaGrad
The one-step OMD argument in (2) applies with . The only extra point is that completing the square must remain valid for singular matrices. For any
,
because . Thus,
Now, the distance terms no longer telescope completely. Define . Rearranging the sum gives the exact identity
After dropping the final nonpositive term, we obtain
Since and the matrix square root is operator monotone,
. Appendix 5 proves this fact without any commutativity assumption. Therefore,
This controls the cost of changing the regularizer.
For the gradient term, we have the following lemma.
Proof: Fix and put
,
. Their ranges are nested, so
. Expanding the right-hand side and using cyclicity of the trace gives
Since , it follows that
Sum over and use
.
Substitute these two estimates into (6):
The learning rate minimizing this bound is , proving the theorem. The literal hindsight substitution
would give the slightly larger constant
instead of
.
So our online method is within a factor of the retrospectively optimized expression in (4), even though it never sees a future gradient. Amazing, isn’t it?
3. The Myth Of The Full-Matrix AdaGrad Explanation For Preconditioning
Now, this is the story we can tell. A matrix chooses the geometry of the update. The hindsight calculation identifies a favorable matrix using the complete gradient sequence. The online algorithm estimates that matrix using the gradients already observed, and the proof shows that this replacement costs only a constant factor.
Moreover, a full matrix uses directional information. If an eigenvector of has eigenvalue
, the inverse-square-root preconditioner scales the gradient component in that direction by
. Directions with larger accumulated squared gradients receive smaller multipliers. Off-diagonal entries allow the method to use correlations between coordinates.
This seems a pretty good story, right?
You can then extend it, by looking for affordable approximations to the full matrix. Shampoo explicitly develops such a structured approximation and analyzes it through online convex optimization (Gupta et al., 2018).
We have an algorithm, a matrix chosen by an optimization problem, and a proof. It is very tempting to stop here, but…
3.1. …Now Try A Scalar
Before celebrating, let us run the same argument with a scalar. Define
and use the OMD regularizer . The update is
If , keep
. This is AdaGrad-norm.
The same one-step calculation and summation give
A term is interpreted as zero. Now use
and telescope. Choosing the same , we obtain
This is the usual scalar adaptive bound that I already described on this blog.
Now compare this guarantee with the one we obtained for full-matrix AdaGrad on one fixed gradient sequence. Let be the nonzero eigenvalues of
. Then,
where the inequality follows immediately by squaring.
The horror! The horror! The scalar bound is always at least as good as the full-matrix bound we just proved, and it can be much better! It is strictly better whenever has at least two positive eigenvalues.
So, all that matrix algebra has bought us an upper bound that a scalar already improves.
It’s even worse: the possible gap is not just a constant. Cauchy–Schwarz gives
Thus, the matrix bound can be worse by a factor of .
After all, maybe our story was not so solid. But how did it happen?
3.2. How Did The “Optimal” Matrix Lose?
Scalar matrices were among the matrices we could choose. So how did optimizing over all matrices give something worse?
Return to the step preceding (3). We replaced by
. But the sharper estimate is
For a scalar matrix , the exact quadratic is
, while the trace estimate gives
. Basically, we introduced a factor of
even before choosing our best preconditioner.
Let’s now retain the sharper estimate and optimize
Put . Since
, inversion gives
. Therefore
For , equality is attained by
A scalar matrix is already optimal for this sharper Euclidean-diameter objective.
There is no contradiction. The matrix was optimal for the particular trace expression in (3). But that expression had already discarded information. Optimizing it perfectly does not restore the information we removed.
The core problem is that we discarded the information about the geometry of the feasible set. If one retains that information, one can discover that the classic result that the shape of the domain tells us which algorithm is better in the worst-case. Coordinatewise AdaGrad bound on boxes is an example of why geometry matters.
3.3. This Issue Has Been Explained In The Other AdaGrad Paper
Given that so many people missed it, one might think that this is a new result, or something hidden in some obscure paper. Quite the opposite: this is as old as AdaGrad itself, and it is in the twin paper on AdaGrad by McMahan & Streeter (2010). In fact, AdaGrad was proposed at the same conference by two different groups independently. But people tend to forget this second paper. It is a pity because the above reasoning is in that second paper.
The story that the shape of the domain together with the characteristics of the functions determines which algorithm to use is also much older. Take a look at the discussion of mirror descent vs subgradient descent on pages 277–278 in lecture notes by Nemirovski from 2005 (https://www.ttic.edu/optimization2012/Lect_ModConvOpt.pdf)
Later, people rediscovered all the above, but I prefer not to advertise papers that rediscover known stuff.
A better potential explanation was given by Cutkosky (2020, Section 5). There, he first explains the same trace-versus-scalar comparison and points out that the classical guarantee does not explain the benefit of the extra matrix computations. Then, he shows that, if one could tune the learning rate with perfect knowledge of the optimum, one could obtain the bound
This is a big “if” because the learning rate itself will change the gradients! That said, under some conditions on gradients and optimal solution, this last bound can be better than the scalar one. However, there still a missing step in the story: we still need to check that these conditions happen in practice, otherwise we are still hallucinating explanations.
4. Alchemy Of Deep Learning
Let me very clear on the fact that any succesful algorithm in an applied field like deep learning does not need a theory that “explains” how it works. But, if you insist on a theory, then it has to make sense. The “alchemistic” view of deep learning is not in using heuristics without theoretical justistications, but in insisting in motivating these heuristics using theoretical explanations that do not make any sense. The chemical reactions the alchemists were inducing were real, their explanations not so much.
A proper theory of preconditioning in deep learning optimization should identify what improves: for example, a condition number, a curvature–noise relationship, a relevant notion of geometry. Moreover, any “explanation” based on assumptions need a precise verification of the assumptions in the real world.
Instead, the classical full-matrix AdaGrad trace bound shows the danger of following alchemical explanations without checking them carefully. In fact, the very same reasoning gives an even better bound by removing the matrices, whose presence we were trying to justify!
5. Appendix: Why The Matrix Square Root Is Monotone
For completeness, here is the matrix fact used in the OMD proof. For , the spectral theorem and the scalar integral for
give
Suppose . For every
, inversion reverses the positive-definite order:
Consequently,
Integration proves . No commutativity between
and
is needed.