Thank you for continued interest & questions
We greatly appreciate the reviewer's interest in understanding the work! Thank you for your continued investment.
Even in the vector-parameter case (S-Adagrad), low-rank second-moment algorithms have previously required either:
1. curvature (FD-SON and its derivatives do this) to yield an ONS-type algorithms
2. weak bounds (Radagrad is heuristic in low memory form, and see Observation 1 for Ada-FD).
So even for analyzing the vector case, our Theorem 3 provides a novel worst-case sqrt-T guarantee when dealing with general convex functions with vector parameters. This is a gap in the literature and may be of interest due to recent work on lower bounds (Efficient Convex Optimization Requires Superlinear Memory by Marsden et al 2022).
What we do differently from, say, Ada-FD, is set up a strictly more convex preconditioner, which allows us to establish the approximate isometry in Remark 9 in the Supplement (L569).
This two-sided bound around the "ideal" full matrix preconditioner makes the FD preconditioner essentially a modular component in OCO proofs, so long as the algorithm applies the dominating approximation to an exact preconditioner: we rely on the same isometry for Shampoo's Kronecker factors $L_t,R_t$ (implied by Lemma 12). We hope the community can use the same technique in other OCO settings too; surely the community stands to gain from the demonstration of this technique in our work, as the OCO sqrt-T result was missing.
Finally, we invite the reviewer to take a look at our empirical results, summarized in Figure 2. We believe that this another "challenge" which has been neglected in this line of work and not yet considered by the reviewer: empirical application of low memory algorithms to real optimization problems of interest to practictioners. As mentioned in Fig.1 and our top-level comment, existing low-memory approaches result in **superlinear** accumulator memory size. Perhaps on the theoretical side, low memory approaches are well known, but in practice algorithms such as RFD, SCFD, Ada-FD, Radagrad, GGT could not be applied to large networks such as the ResNet-50, Conformer, and GNN we have in our work. Storing multiple copies' worth of the parameters for these networks on GPUs is prohibitive.
Adafactor may be the only real example of sublinear memory optimizers in practice, but it does not have a robust theory and performs much worse than Adam in terms of quality on all three of our datasets (notice we improve on Adam in all three).