{"id":"f31404d9-ce30-4382-83a2-9650067a8dbc","arxiv_id":"2508.21106","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"AdaGram applies a dynamical low-rank integrator to the preconditioner of adaptive gradient methods, achieving full-matrix-like updates with rank 1-5 approximations at low cost on small GLM benchmarks.","lead":"AdaGram is a new optimizer that speeds up full-matrix adaptive gradient methods by maintaining a low-rank approximation of the preconditioner with a matrix integration technique. On small logistic regression benchmarks it matches or beats diagonal AdaGrad, but its claimed scalability is not yet demonstrated beyond 60 features.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Rank-r projector-splitting truncation of the preconditioner is uncontrolled: no error bound, and the error feeds into the step-size normalization; experiments up to 60 features do not establish scalability.","rationale":"The reader's weakest assumption is precisely the accuracy of the rank-r truncation. My analysis confirms this is the load-bearing point: the exact part of the theory (Theorem 1, Lemma 1) is correct, but the algorithm replaces the exact A_t with a rank-r approximation via a projector-splitting integrator, and no error control is provided. This is not merely a missing formal proof; the integrator is intended for ODEs and is used here on a discrete recurrence, so there is no automatic guarantee of accuracy. The empirical evidence is too small to rule out error growth. The recommended verdict is unchanged because the reader already judged it CONDITIONAL; my concrete test would either support the conditional acceptance (if errors stay flat) or escalate the concern.","tokens_in":10214,"tokens_out":11050,"duration_ms":97101,"concrete_test":"Set up a synthetic logistic regression with n=100, 1000, and 5000 and a fixed correlation structure. Run AdaGram-PS with r=1,2,5 and the full-matrix AdaGrad baseline. After each epoch, compute the exact A_t using the untruncated Lemma 1 recursion with the same gradient sequence, and compute (a) relative Frobenius error \\|A_t^{exact}-A_t^{rank}\\|/\\|A_t^{exact}\\| and (b) relative error in the preconditioned gradient L^{-1}g. If the error grows with t or with n, or the test-loss gap to full AdaGrad widens with n, the low-rank update is not a controlled approximation and the scalability claim is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim relies on the rank-r projector-splitting update (Algorithm 1) faithfully approximating the exact recurrence A_{t+1}=A_t+\\Delta A_{t+1} from Lemma 1. No error bound is given. Algorithm 1 is taken from [18], where it is a numerical integrator for an ODE; here it is applied with a fixed step h=1 to a discrete update, and the increment \\Delta A_{t+1} may be large. The approximation error in A_t is therefore uncontrolled and may accumulate over iterations. Since the same approximate \\bar g_t is used in the normalization 1/sqrt(1+\\|\\bar g_t\\|^2) on line 7 of Algorithm 2, the error also perturbs the effective learning rate. Empirical validation is restricted to logistic regression with at most 60 features (Splice), so the conclusion that rank 5 (or smaller) is sufficient for scalable full-matrix preconditioning is not supported. This is the weakest link: if the truncation error grows with dimension or iteration count, AdaGram degrades to an uncontrolled heuristic and the central claim fails.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes AdaGram, an optimizer that maintains a low-rank approximation of the inverse Cholesky factor of the accumulated outer-product gradient matrix G_t, with the goal of realizing full-matrix adaptive preconditioning at reduced memory and computational cost. The theoretical core is Theorem 1, which gives an exact recurrence for the action of the inverse Cholesky factor on the current gradient: L_{t+1}^{-1} g_{t+1} = (1 + ||L_t^{-1} g_{t+1}||^2)^{-1/2} L_t^{-1} g_{t+1}. Because the exact representation grows unbounded in rank, the authors use a projector-splitting integrator (Algorithm 1, from Lubich--Oseledets) to keep a rank-r factorization, controlled by a memory parameter µ. The method is evaluated on synthetic correlation-structured data and three UCI logistic-regression benchmarks (Heart, Australian, Splice), comparing against SGD, diagonal AdaGrad, Shampoo, KATE, and full AdaGrad.","tokens_in":10512,"tokens_out":16020,"duration_ms":149006,"significance":"The exact recurrence in Theorem 1 is clean, self-contained, and could be of independent use, and the connection to dynamical low-rank integrators is original. The development from Eq. (3) to Eq. (7) is a useful observation that avoids forming G_t explicitly. The paper also makes code available, which aids reproducibility. However, the central empirical claim---that rank 1--5 AdaGram variants match or beat diagonal adaptive optimizers---rests on a small and narrowly tuned experimental base, and the algorithm's interpretation as a full-matrix AdaGrad method is not fully supported. If the low-rank truncation were supplied with an error bound or a descent/convergence guarantee, this would be a solid contribution; as it stands, it is mainly an interesting heuristic with a clean exact recurrence behind it.","major_comments":[{"comment":"The recursive update computes L^{-1} g, not G^{-1/2} g. The isometry argument in §3.2 preserves only the norm (g^T G^{-1} g = ||L^{-1} g||^2), not the direction of the preconditioned gradient. For positive definite G = L L^T, L^{-1} and G^{-1/2} differ by an orthogonal factor, so the update is a rotated version of AdaGrad. This rotation can turn the step into an ascent direction. Example: take L = [[1, 0], [0.9, 0.1]], G = L L^T (positive definite), and g = (1, 0.2); then g^T L^{-1} g = -0.4 < 0. Thus AdaGram is not equivalent to full-matrix AdaGrad, and the comparisons to FullAdaGrad in §4 compare two different optimizers. The authors should either prove a descent/convergence property for the L^{-1} update or revise the claim that AdaGram enables full-matrix adaptive gradient updates.","section":"§3.3, Eq. (7) and §3.2"},{"comment":"The rank-r truncation is uncontrolled. Algorithm 1 is a projector-splitting integrator designed for an ODE; here it is applied with a fixed step h=1 to a discrete rank-(r+1) update, with no error analysis. The increment ΔA_{t+1} in Eq. (12) is rank-one but not small in norm, and the approximation error in A_t feeds directly into the normalization 1/sqrt(1+||\\bar g_t||^2) on line 7 of Algorithm 2. Without an error bound or a stability analysis, there is no guarantee that the low-rank method tracks the exact recurrence of Lemma 1 or preserves even the (problematic) direction of the exact update.","section":"§3.4, Eq. (13), Algorithm 1"},{"comment":"The experimental evidence is too narrow for the abstract's claim. Hyperparameters are selected per method by minimizing the final training loss, which is a training-time selection criterion and can bias comparisons, especially for AdaGram with the extra rank r and memory µ hyperparameters. No run-to-run variance or error bars are reported. The largest real dataset (Splice) has only 60 features. Demonstrating that rank 1--2 works on these three problems does not establish that rank-five (or smaller) approximations are sufficient for scalable full-matrix preconditioning in large models.","section":"§4.2, §4.4"},{"comment":"The algorithm as written is underspecified and contains a dimension inconsistency. Line 1 sets L_0 = sqrt(ε) I_m, while gradients are in R^{mn}; if the weight matrix is m×n, the preconditioner should act on R^{mn}. The initial P, Q, U, S, V are not defined, and it is not stated how the memory parameter µ enters Algorithm 1's steps (Eq. (14) gives A_{t+1} = µ A_t + (1-µ) ΔA_{t+1}, but Algorithm 1 expects a rank-r factorization and an increment). These details are necessary for a reproducible optimizer.","section":"Algorithm 2"}],"minor_comments":[{"comment":"The parameter α is defined through 1 + α||\\bar g||^2 = sqrt(1+||\\bar g||^2); when ||\\bar g||=0 the formula for α involves division by zero. The zero case should be handled separately.","section":"Eq. (5)"},{"comment":"The proof of Lemma 1 contains a wrong algebra line: 'P_t Q_t^T \\bar g_{t+1} = Q_t(P_t^T \\bar g_{t+1})' should be P_t(Q_t^T \\bar g_{t+1}). The lemma statement can be verified independently, but the proof as printed is not reliable.","section":"Appendix A.3"},{"comment":"The text states that the optimal rank for AdaGramPS is consistently rank 1 or 2, but Figure 2 plots AdaGramPS rank 3, 4, and 5. Clarify which ranks were actually selected by grid search and which are shown for comparison.","section":"§4.3, Figure 2"},{"comment":"The time indexing is off by one relative to Eq. (3). At iteration t, the preconditioner G_t includes g_t, but the algorithm computes \\bar g_t = L_{t-1}^{-1} g_t and then normalizes; it would help to state explicitly that the update uses L_t^{-1} g_t following Theorem 1.","section":"Algorithm 2"}],"recommendation":"major_revision","confidential_remarks":"The paper has a clean exact recurrence and a plausible empirical direction, but the conceptual link to full-matrix AdaGrad is broken by the use of a non-symmetric Cholesky factor, and the low-rank truncation is not justified. The experiments, as designed, are too small and too favorably tuned to support the scalability claims. I would encourage the authors to reposition the contribution as a new preconditioned optimizer with explicit descent/convergence analysis, and to add larger-scale, multi-seed experiments with a proper validation split. If the direction issue cannot be resolved theoretically, the paper's main claim should be revised substantially."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"What you should know: this paper combines a known rank-1 update identity for the inverse Cholesky factor with a projector-splitting integrator to keep a rank-r factorization of the preconditioner. That combination is new, and the derivation of the recursive update (Theorem 1) is correct. But the evidence for the central claim—that rank 5 or lower is enough—is thin, and the truncation error from the projector-splitting step is never bounded. The experiments stop at 60 features, so the abstract's 'scalable solution for large models' language is not supported.\n\nWhat it does well: the proof is self-contained, including the appendix, and the isometry argument that lets them switch from the symmetric square root to the Cholesky factor is clean. The algorithm is simple to implement, and the code is available. The connection to dynamical low-rank approximation is a legitimate new idea, even if the pieces are not new on their own.\n\nSoft spots: the projector-splitting algorithm is taken from an ODE integrator but applied with a fixed step h=1 to a discrete update. There is no error analysis for this step, and since the same approximate preconditioned gradient is used in the normalization on line 7 of Algorithm 2, the error also perturbs the effective learning rate. That's a real gap. The experiments are on three small UCI datasets with hyperparameters selected per method to minimize final training loss; there are no repeated runs or variance estimates. The synthetic experiments are fine but do not rescue the scale claim. Also, minor citation issues: ref [12] for SOAP appears to point to a different paper, and ref [10] does not match the text describing online matrix estimation.\n\nBottom line: this is a reasonable idea that deserves a serious look, but the paper currently overclaims. The right referee would ask for larger experiments with statistical replicates and at least an informal argument about the truncation error. I'd take it to peer review, with the expectation of major revision.","headline":"Neat combination of a known recursive identity with a projector-splitting integrator, but the empirical evidence is thin and the low-rank truncation error is never analyzed.","tokens_in":10945,"tokens_out":2111,"would_cite":false,"duration_ms":21482,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"AdaGram computes full-matrix AdaGrad-style updates by tracking a rank-r inverse-Cholesky factor, and its experiments show that rank 1–5 factors match or beat diagonal optimizers on correlated logistic regression tasks.","keywords":["AdaGram","full-matrix preconditioning","adaptive gradient methods","low-rank approximation","projector-splitting integrator","Cholesky factorization","logistic regression","second-order optimization"],"falsifier":"Run AdaGram at rank 1, 5, and 10 against exact full-matrix AdaGrad on a logistic regression with roughly 10^5 features and designed pairwise correlations; if the loss-versus-time curves diverge with dimension, or if the spectral norm of L^{-1}_t − (I − P_tQ_t^T)L_0^{-1} grows without bound along a fixed trajectory, the rank-truncation assumption fails.","tokens_in":10139,"feed_emoji":"⚡","tokens_out":8352,"duration_ms":81305,"temperature":0.7,"pith_summary":"The paper proposes AdaGram, an optimizer that aims to make full-matrix adaptive gradient updates practical by maintaining only a low-rank factor of the inverse Cholesky factor of the accumulated gradient matrix. The key mathematical claim is a recursive identity: the preconditioned gradient at step t+1 is a scalar multiple of the preconditioned gradient at step t, with the scalar determined entirely by the norm of the current transformed gradient. Because the inverse-Cholesky factor itself is updated by a projector-splitting low-rank integrator, the method avoids O(n^3) inversions and O(n^2) storage. If correct, the correlation information that full-matrix preconditioning uses can be obtained at a fraction of the cost, and the experiments on logistic regression with up to 60 features support that claim.","feed_headline":"AdaGram matches or beats diagonal AdaGrad at rank 1–2","feed_subtitle":"Full-matrix correlation benefits at near-diagonal cost: no O(n^2) storage, no O(n^3) inversion.","key_machinery":"The load-bearing object is the inverse Cholesky factor L^{-1}_t of the accumulated gradient matrix G_t = εI + Σ g_τ g_τ^T, represented as (I − P_t Q_t^T)L_0^{-1}. Theorem 1's recursion turns preconditioning into a scalar-normalized update of the previous preconditioned gradient; Lemma 1 converts that recursion into growing P and Q factors; and Algorithm 1, the projector-splitting integrator for dynamical low-rank approximation, truncates A_t = P_t Q_t^T to rank r at each step. Together these replace exact matrix inversion with low-rank SVD/QR updates, reducing memory and per-step cost from quadratic in n to roughly linear in n times r.","core_discovery":"AdaGram computes AdaGrad's full-matrix direction θ ← θ − ηG^{-1/2}g without forming n×n G. It uses the inverse Cholesky factor L^{-1} and the identity L^{-1}_{t+1} g_{t+1} = (1+||L^{-1}_t g_{t+1}||^2)^{-1/2} L^{-1}_t g_{t+1} (Theorem 1), so each preconditioned gradient follows from the previous one and its norm. Lemma 1 stores L^{-1}_t as (I − P_tQ_t^T)L_0^{-1}; the projector-splitting integrator keeps P_tQ_t^T at fixed rank r. Experiments on synthetic and UCI logistic regression show rank-1–5 AdaGram matching or beating diagonal AdaGrad, Shampoo, KATE, and SGD on correlated losses.","pith_inferences":["The paper does not test whether the rank-r truncation error stays bounded as the feature dimension grows beyond 60; a direct high-dimensional experiment with strong correlations would reveal whether the low-rank preconditioner keeps tracking exact full-matrix AdaGrad.","If truncation error does accumulate, a remedy not explored in the paper is a periodic full-rank refresh (recomputing L^{-1} exactly every K steps) to keep the low-rank factors from drifting away from the true preconditioner.","The scalar-normalized recursion in Theorem 1 could be useful for distributed or Hessian-free solvers, since exchanging only rank-r factors or preconditioned gradient vectors avoids communicating full matrices.","Existing techniques for error control in dynamical low-rank approximation could supply the missing bound and turn the rank-truncation heuristic into a certified algorithm with per-step error guarantees."],"forward_implications":["Full-matrix AdaGrad-style updates become feasible for models where O(n^2) storage is unacceptable, because memory and per-iteration cost scale with n times r rather than n^2.","The recursion identity means the preconditioned gradient can be computed from the previous step's transformed gradient and its norm, so no matrix square root needs to be recomputed at each step.","Rank r acts as a dial between diagonal preconditioning and full-matrix behavior, with the paper's experiments finding best performance at very low ranks (1–2 on real datasets).","The low-rank integrator viewpoint gives a principled way to 'forget' old gradient directions as training progresses, since the magnitude of each gradient update controls how strongly the stored factor changes.","The same machinery can be attached to other adaptive methods that use gradient second-moment matrices, such as Adam- and RMSProp-style updates, replacing diagonal estimates with low-rank full-matrix estimates."],"supporting_citations":[{"why":"Defines the AdaGrad full-matrix update θ ← θ − η G^{-1/2} g and the diagonal variant that AdaGram generalizes; supplies the accumulated-gradient preconditioner form.","marker":"[5]"},{"why":"Provides the fast symmetric factorization P = I + α ḡḡ^T used in the proofs of Theorem 1 and Lemma 1 to derive the recursive Cholesky update.","marker":"[8]"},{"why":"Supplies the projector-splitting integrator (Algorithm 1) that AdaGram uses to keep P_t Q_t^T at fixed low rank.","marker":"[18]"},{"why":"Shampoo is a baseline Kronecker-factored preconditioner that AdaGram is compared against in the experiments.","marker":"[11]"},{"why":"KATE is a square-root-free scale-invariant AdaGrad variant; its datasets and preprocessing framework are reused for the empirical evaluation.","marker":"[14]"},{"why":"Supplies the UCI benchmark datasets (Australian, Heart, Splice) used for the real-data experiments.","marker":"[20]"},{"why":"Defines the isotropic/simple/complex correlation structures used to generate synthetic data on which the full-matrix benefit is demonstrated.","marker":"[21]"}],"fun_headline_variants":["AdaGram: full-matrix updates without O(n^2) memory","Rank-5 preconditioner matches diagonal AdaGrad","Full-matrix adaptive optimization at near-diagonal cost","AdaGram: full-matrix correlations for cheap"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The rank-r truncation done by the projector-splitting integrator is accurate enough to preserve the convergence benefit of full-matrix preconditioning; the paper gives no error bound and only tests up to 60 features.","fun_headline_variants_meta":{"raw":{"variants":["AdaGram: full-matrix updates without O(n^2) memory","Rank-5 preconditioner matches diagonal AdaGrad","Full-matrix adaptive optimization at near-diagonal cost","AdaGram: full-matrix correlations for cheap"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000486,"raw_usage":{"total_tokens":2236,"prompt_tokens":753,"completion_tokens":1483,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":497,"completion_tokens_details":{"reasoning_tokens":1426}},"tokens_in":497,"tokens_out":1483,"duration_ms":13086,"temperature":1.0,"reasoning_tokens":1426,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T14:49:55.757836+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run AdaGram at rank 1, 5, and 10 against exact full-matrix AdaGrad on a logistic regression with roughly 10^5 features and designed pairwise correlations; if the loss-versus-time curves diverge with dimension, or if the spectral norm of L^{-1}_t − (I − P_tQ_t^T)L_0^{-1} grows without bound along a fixed trajectory, the rank-truncation assumption fails.","supporting_citations":[{"cited_title":"A projector-splitting integrator for dynamical low-rank approximation, 2013","cited_arxiv_id":null,"evidence_quote":"Supplies the projector-splitting integrator (Algorithm 1) that AdaGram uses to keep P_t Q_t^T at fixed low rank."},{"cited_title":"Remove that square root: A new efficient scale-invariant version of adagrad","cited_arxiv_id":null,"evidence_quote":"KATE is a square-root-free scale-invariant AdaGrad variant; its datasets and preprocessing framework are reused for the empirical evaluation."},{"cited_title":"Stress test procedure for feature selection algorithms","cited_arxiv_id":null,"evidence_quote":"Defines the isotropic/simple/complex correlation structures used to generate synthetic data on which the full-matrix benefit is demonstrated."}],"review_version":1}