We thank the reviewer for acknowledging the theoretical insight of our work. We will address your concerns below.

A larger set of preconditioner is not necessarily better: We appreciate the reviewer’s concern regarding our claim. Due to computational limitations, it is indeed difficult to compare full-matrix AdaGrad with those structured preconditioners on real-world tasks. However, our intention is not to assert that simpler preconditioners always perform better, but rather to challenge the assumption that a larger set is always superior. We successfully show it is wrong via the theoretical analysis and synthetic task.

Practical advantage of one-sided Shampoo: Thanks for the clarification. We realize that our paper might have unintentionally suggested that one-sided Shampoo has practical benefits on real-world tasks, which we do not claim. Our work is mainly theoretical, and our experiments are limited to a simplified setting that aligns with our analysis. We agree that demonstrating practical benefits would require larger-scale experiments, which is beyond the scope of this submission. We leave this for future work and welcome pointers to such work if it already exists. However, we want to clarify that the theoretical analysis (Theorem 3.3 and 3.7) holds for any convex functions so the analysis of one-sided Shampoo is not restricted to a specific type of function (equation 7).

Motivation for specific quadratic problem: We propose a simple quadratic function so that we can easily compute those convergence rates in table 2 and verify the effectiveness of our theory. We agree it seems unclear why to choose such specific quadratic problem so we decide to add a new quadratic loss function on which the empirical results are consistent. We only introduce the loss function below and more details can be found in our response to reviewer N1Ca.

We consider a synthetic linear regression problem $||\mathbf{A} \mathbf{X} - \mathbf{y}||\_2^2$ where $\mathbf{A}$ is the data matrix and $\mathbf{y} =\mathbf{A} \mathbf{X}^*$ is the label vector generated by ground-truth $\mathbf{X}^*$. Thus, the loss function can be equivalently written as $f(\mathbf{X}) = \langle \mathbf{H}, (\mathbf{X}-\mathbf{X}^*)(\mathbf{X}-\mathbf{X}^*)^\top \rangle$ for $\mathbf{H} = \mathbf{A}^\top \mathbf{A}$, which is the same function that we studied in section 4.3 and show that 1-sided shampoo outperforms other adaptive algorithms.

Detailed comparison between optimizers: We would like to elaborate on the comparative insights our theory can offer. As mentioned in line 74-80, line 222-231 and line 430-434, we should really consider the tradeoff between different terms in the regret bound or convergence rate. A less structured preconditioner such as full-matrix AdaGrad may have strength in having smaller $|||\mathbf{g}\_{1:t}|||\_\mathcal{H}$ and its weakness lies in inducing larger $||\mathcal{X}||_\mathcal{H}$.

Property of subalgebra: The conditions for the well-structured $\mathcal{H}$ are required to ensure that $\mathbf{H}\_t\succeq \mathbf{H}\_{t-1}$. In particular, the condition for being closed under scalar multiplication and matrix addition (i.e., $\mathcal{K}$ is a linear subspace) and the condition for being closed under matrix multiplication are important in the proof of the desired property. Indeed, without the linear subspace condition, we have the failure example of two-sided Shampoo as discussed in Example 2.2 and Appendix A.3.1; moreover, without the matrix multiplication condition, we have the failure example of tridiagonal matrices as discussed in Example 2.3 and Appendix A.3.2. Also, as can be seen from the proofs in Appendix A.2, for any $\mathbf{H}\in\mathcal{H}$, we require $p(\mathbf{H}) \in \mathcal{H}$ for any polynomial $p$, which guarantees especially that $\mathbf{H}^{-1}\in\mathcal{H}$. All these requirements naturally inspire us to formulate the well-structured preconditioner sets using the notion of matrix subalgebra.

We sincerely thank the reviewer for recognizing the value of our unified framework. We will address your concern below.

Clarification of our results: We never claim that the regret bound for the full-matrix AdaGrad is worse than AdaGrad-norm or AdaGrad with diagonal preconditioner and we apologize if any words cause such misunderstanding. We only argue that it is a misleading belief that adding more structures to the preconditioner will always lead to worse performance. We use the specific comparison between one-sided Shampoo and full-matrix AdaGrad to illustrate this clearly. And we only focus on optimization speed, specifically characterized by regret bound or convergence rate. Other properties such rotation-equivariance are beyond the scope of this paper.

Common belief that full-matrix preconditioner is “ideal”: First we would like to clarify we agree with the reviewer on the statement that full-matrix preconditioner is not necessarily ideal as there is no theoretical justification on that. However, this is a common belief held by many researchers in the community. For example, Agarwal et al., 2019 explicitly argues that full-matrix preconditioning allows for better exploitation of anisotropic curvature in loss landscapes and their experiments show that full-matrix version can work better than Adam in some cases. The belief that full-matrix preconditioners are “ideal” is also implicit in the design of many optimizers, such as Shampoo, and Shampoo^2, which all attempt to approximate the full-matrix version more efficiently.

Vector vs Matrix Problems: The reviewer argues our comparison is unfair when using a matrix-structured problem to highlight the benefits of one-sided Shampoo. We disagree with this interpretation. First, vector and matrix problems are mathematically equivalent up to reshaping and vectorization. Second, the models in practice are often built by complicated matrix-based modules and thus our formulation is relevant to practice.

Most importantly, we do not claim that one-sided Shampoo is better than the AdaGrad family in general. We only demonstrate that it can be better on certain losses since it already sufficiently supports our claim. We agree that AdaGrad family may perform better on simple vector problems, which doesn’t contradict our argument.

Comparison within AdaGrad family: Our goal is not to provide a comprehensive comparison among all AdaGrad variants. As mentioned above, we never make any claims within the AdaGrad family. That said, we found that AdaGrad-Norm and diagonal AdaGrad can outperform full-matrix AdaGrad empirically from figure 1. We are also happy to clarify that AdaGrad-Norm can outperform full-matrix AdaGrad in some setting in response to the next question.

Can AdaGrad-Norm be the best: Yes. We can show that the regret bound of AdaGrad-Norm is the best for a specific setting when $\mathcal{X}$ is the $\ell_2$-norm constrained ball. Due to space constraints, we are happy to share the complete proof in follow-up discussion.

Even in practice, Xie et al., 2025 shows that AdaSGD (EMA version of AdaGrad-Norm) can outperform rotated Adam on a GPT-2 model. While rotated Adam differs from the original, it shows an important insight that supports our claim: coordinate-wise adaptivity is not always better the global adaptivity. We think this is even a better example than a regression problem with real data for which AdaGrad-Norm can beat diagonal AdaGrad.

Definition of Structure: We agree that the notion of “structure” can be more clearly explained even though we have discussed this in line 29-40. In our usage, a structured preconditioner imposes constraints on the preconditioning, formalized via a subalgebra $\mathcal{K}$. As mentioned in the abstract and introduction, some examples of structured preconditioner includes layerwise, diagonal and kronecker-factored. In contrary, full-matrix preconditoner is the least structured preconditioner because there is no constraint.

Experiments on Shampoo: Please see the response to reviewer N1Ca.

Insights for Developing new algorithms: Please see the response to reviewer N1Ca.

References

1. Efficient full-matrix adaptive regularization. (Agarwal et al., ICML 2019)
2. Adam Exploits $\ell_\infty$-geometry of Loss Landscape via Coordinate-wise Adaptivity. (Xie et al., ICLR 2025)

We thank the reviewer for acknowledging the value of our unified analysis. Below we will address your concerns.

Comparison with Shampoo and Shampoo^2: We appreciate the suggestion to include two-sided Shampoo and Shampoo^2 in the experiments. As reviewer tCyu pointed out there is lack of motivation for our current experiment, we conduct experiments on a better setting which is more practical and better motivated by our theory analysis. We will add this experiment and focus more on it in the future revision.

We consider a synthetic linear regression problem $||\mathbf{A} \mathbf{X} - \mathbf{y}||\_2^2$ where $\mathbf{A}$ is the data matrix and $\mathbf{y} =\mathbf{A} \mathbf{X}^*$ is the label vector generated by ground-truth $\mathbf{X}^*$. Thus, the loss function can be equivalently written as $f(\mathbf{X}) = \langle \mathbf{H}, (\mathbf{X}-\mathbf{X}^*)(\mathbf{X}-\mathbf{X}^*)^\top \rangle$ for $\mathbf{H} = \mathbf{A}^\top \mathbf{A}$, which is the same function that we studied in section 4.3 and show that 1-sided shampoo outperforms other adaptive algorithms. We consider $\mathbf{X} \in \mathbb{R}^{d \times d}$ with $d=10^3$. We set the eigenvalues of $\mathbf{H}$ by $\sigma_1 = \cdots = \sigma_{10}=1$ and $\sigma_i = \frac{1}{(i-10)^2}$ for $11 \leq i \leq 10^3$. Each element of the solution $\mathbf{X}^*$ is independently sampled from $\mathcal{N}(0, \frac{1}{d})$.

We compared all the optimization algorithms by sweeping learning rate from 1e-4 to 1e2. The plots are here. The results are consistent with the original experiment: (1). one-sided Shampoo outperforms other variants of AdaReg; (2). Shampoo is slightly worse than one-sided Shampoo; (3). Shampoo^2 fails to make progress in optimizing this loss function. We are unsure why Shampoo^2 underperforms on this loss function but note that Morwani et al. (2024) also does not provide empirical evidence of the effectiveness of Shampoo^2. Investigating this behavior is beyond the scope of our current work, but may be a worthwhile direction for future study. The implementation of Shampoo and Shampoo^2 is here.

One-sided Shampoo as a new, improved algorithm: We disagree with the reviewer’s opinion that this work doesn’t lead to an improved algorithm. To the best of our knowledge, we are the first to explicitly define and analyze the one-sided Shampoo algorithm even though it is informally mentioned on social media. And our section 4.2 shows that it improves original Shampoo theoretically and section 4.3 shows it can achieve the best rate on some specific loss functions, which is empirically verified by our added experiment above.

Plausible directions for designing better optimizer: Thanks for this insightful question. We believe the definition of well-structured preconditioners can help designing novel optimization algorithms as discussed in line 261-308 though they may not necessarily be better.

Notably, our framework already encompasses recent algorithms such as Adam-mini (Zhang et al., 2024) and Adalayer (Zhao et al., 2024) via specific choices of the subalgebra $\mathcal{K}$. Inspired by these two examples, we identify three basic operations that can construct new matrix subalgebras that can be used for defining well-structured preconditioner.

1. Direct sum of matrix subalgebras. This is defined in line 261-308.
2. Kronecker product between a matrix subalgebra and identity matrix. For a matrix subalgebra $\mathcal{K}$, we can define $\mathcal{K}’$ by $\mathcal{K} \otimes \mathbf{I}_d = \\{ \mathbf{A} \otimes \mathbf{I}_d | \mathbf{A} \in \mathcal{K}\\}$.
3. Rotations via orthogonal matrices. For a matrix subalgebra $\mathcal{K}$ and an orthogonal matrix $\mathbf{U}$, we can define $\mathcal{K’}$ by $\mathbf{U}^\top \mathcal{K} \mathbf{U} = \\{ \mathbf{U}^\top \mathbf{A} \mathbf{U} | \mathbf{A} \in \mathcal{K} \\}$. Such $\mathcal{K’}$ is still a matrix subalgebra.

These operations offer a principled way to design new preconditioners and optimizers. As noted in our conclusion (lines 430–435), a theory-driven strategy would be to evaluate terms in the regret bound or convergence rate under different $\mathcal{K}$ and choose $\mathcal{K}$ to optimize the trade-off. While this remains challenging to evaluate empirically on large models, we view this as an interesting direction for future work.