{"id":"2d90ec61-90c5-43b4-93ec-224746969d0c","arxiv_id":"2412.10663","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A 4-bit Shampoo optimizer that quantizes Cholesky factors and adds error feedback matches 32-bit Shampoo's accuracy at a fraction of the memory.","lead":"This paper shows how to store Shampoo's preconditioning matrices in 4-bit precision using Cholesky factorization and error feedback, cutting GPU memory use while keeping training quality close to the 32-bit version. The method could make memory-hungry second-order optimizers practical for large language model training.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The convergence proofs rest on an unproven positive-definiteness guarantee: Proposition B.1's error bound is for uniform quantization and is violated by the linear-2 mapping in Eq. (4), and Proposition B.2's diagonal-dominance proof contains an algebra error.","rationale":"I read the paper as making two central claims: a practical claim that CQ+EF 4-bit Shampoo is memory-efficient and nearly matches 32-bit Shampoo, and a theoretical claim that the method converges at O(1/√T) in smooth nonconvex settings and globally for stratifiable nonsmooth losses. The practical claim is well supported by the experiments: Tables 3-6 show consistent gains over vanilla 4-bit quantization, real memory savings, and modest time overhead. The weakness is entirely in the theoretical claim. The load-bearing step is the boundedness and positive definiteness of H_k (Assumption 5.1c). The paper argues this follows from Proposition 5.1, but Proposition 5.1 relies on a quantization error bound (Prop. B.1) that is false for the linear-2 quantizer actually used, and on a diagonal-dominance argument whose algebra is incorrect. Without a corrected error constant and a verified diagonal-dominance condition, Assumption 5.1c is an unproven premise, so the theorems as printed do not go through. The issue is likely repairable: one could prove a correct bound for the nonlinear quantizer, fix the algebra, and either verify the stronger dominance condition numerically or add it as an explicit assumption. The empirical contribution stands, and the reader's CONDITIONAL verdict is the right response. I would keep it unchanged, with a request to correct the quantizer analysis and the Proposition B.2 derivation.","tokens_in":22632,"tokens_out":13615,"duration_ms":117113,"concrete_test":"Re-derive the scalar quantization error for the linear-2 mapping in Eq. (4), computing max_{a∈[-1,1]} min_j |a - M(j)| for b=4; if it exceeds 2^{-4}, Proposition B.1 is false. Then rewrite Proposition B.2's positive-definiteness argument with the correct error constant, fix the row-sum algebra, and evaluate the resulting diagonal-dominance condition on the logged M_k matrices from a ResNet-34/CIFAR-100 run (or on synthetic matrices with the same spectrum). If any row violates the corrected condition while D(hat L_k) still has positive eigenvalues, the paper's stated proof does not establish Assumption 5.1c.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 5's convergence theorems hinge on Assumption 5.1c, which is asserted to follow from Proposition 5.1/PROP B.2. That proposition is not supported as written. First, Proposition B.1 claims ||D(Q(x))-x||∞ ≤ ||x||∞/2^b for any b-bit quantization, using a uniform grid of spacing 2/2^b. The actual quantizer in Eq. (4) is nonlinear: for b=4 the positive representable values are (i/15)^2 for odd i=1,3,...,15. The largest gap is 1-(13/15)^2 = 56/225, so the worst scalar error is 28/225 ≈ 0.124, larger than 1/16. Thus the stated bound fails, and the proof's use of the 2^{-b} factor in Proposition B.2 is invalid for the implemented quantizer. Second, the proof of Proposition B.2 derives a lower bound on the Gershgorin row sum as (1-2^{-b})|M_ii| + (1+2^{-b})Σ|M_ij| and declares it positive; that expression is trivially positive and does not follow from the preceding inequality. A correct derivation would give |M_ii| - (1+C)Σ|M_ij| for some quantizer-dependent constant C, so positivity requires a strict diagonal-dominance condition that the paper neither proves nor verifies on the actual M_k matrices. With Proposition 5.1 unsupported, Assumption 5.1c is an extra unverified premise, and Theorems 5.1 and 5.2 (via Assumption 5.2c) are conditional rather than established. This critique does not affect the empirical results, which appear credible.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a memory-efficient 4-bit quantization scheme for Shampoo preconditioners. Instead of quantizing the preconditioning matrices L_k and R_k directly, the authors compute their Cholesky factors, quantize only the off-diagonal entries of those factors at 4-bit precision while keeping diagonals at 32-bit, and store an error-feedback state in the upper triangular part of the same storage. They report extensive image-classification experiments (VGG, ResNet, Swin, ViT on CIFAR-100, Tiny-ImageNet, ImageNet) and LLaMA pretraining experiments showing that the method nearly matches 32-bit Shampoo while reducing peak memory. The theoretical section claims an O(1/sqrt(T)) convergence rate for smooth nonconvex objectives and convergence to stationary points for nonsmooth stratifiable objectives, both under an assumption that the quantized preconditioner has uniformly bounded positive-definite spectrum.","tokens_in":23013,"tokens_out":5694,"duration_ms":51385,"significance":"If the convergence claims were fully supported, this would be a meaningful contribution: memory-efficient preconditioned optimization with a practical 4-bit implementation, a new Cholesky-quantization idea, and the first global-convergence result for quantized preconditioned gradient descent. The empirical evaluation is broad and internally consistent: Tables 3–6 cover several architectures and LLM scales, report peak memory and wall-clock time, and include ablations over the momentum parameters. The paper does not appear to fit constants to data or bake results into the derivation; the empirical claims are credible. The main weakness is the theoretical support: the positive-definiteness and bounded-spectrum assumption that underpins both convergence theorems rests on two unproven or incorrectly proven propositions. The contribution would still be of practical value if the theorems were restated as conditional on an explicit assumption, but the current text overclaims.","major_comments":[{"comment":"Proposition B.1 claims the bound ||D(Q(x)) - x||_∞ <= ||x||_∞ / 2^b for any b-bit quantization, with the proof using a uniform grid of spacing Δ = 2/2^b. The algorithm actually uses the linear-2 mapping in Eq. (4), which is not uniform. For b = 4, the positive representable values are (i/15)^2 for odd i = 1,3,...,15, so the largest gap is 1 - (13/15)^2 = 56/225 and the worst scalar quantization error is 28/225 ≈ 0.124, which is larger than 1/16. Therefore the stated error bound fails for the implemented quantizer, and the subsequent use of the factor 2^{-b} in Proposition B.2 is not justified. The authors must either prove an analogous error bound for the linear-2 mapping (with the correct quantizer-dependent constant) or change the quantizer to one for which the bound holds.","section":"Appendix B, Proposition B.1"},{"comment":"The diagonal-dominance proof contains a sign error. From the Gershgorin lower bound |[M_k]_ii| - |[E_k]_ii| - Σ_{j≠i}(|[M_k]_ij| + |[E_k]_ij|), applying |[E_k]_ij| ≤ 2^{-b}|[M_k]_ij| gives (1 - 2^{-b})|[M_k]_ii| - (1 + 2^{-b})Σ_{j≠i}|[M_k]_ij|, not the stated (1 - 2^{-b})|[M_k]_ii| + (1 + 2^{-b})Σ_{j≠i}|[M_k]_ij|. The displayed expression is trivially positive and does not follow from the preceding line. A correct argument would require strict row-wise diagonal dominance of M_k with a margin depending on the quantizer, and this condition is neither derived from Algorithm 1 nor verified on the actual M_k matrices. Since Assumption 5.1c is justified by Proposition 5.1, and Assumption 5.2c is used by Theorem 5.2, both convergence theorems are currently conditional on an unproven premise.","section":"Proposition 5.1 / Proposition B.2"},{"comment":"The text states that Assumption 5.1c is 'guaranteed by the implementation of the Schur–Newton method, the regularization step in Eq. (7), and Proposition 5.1.' Given the problems with Proposition B.1 and Proposition B.2, this guarantee is not established. Figure 3 only shows that eigenvalues of dequantized preconditioners are positive for VGG-19 on CIFAR-100 at a few epochs; it does not establish a uniform lower bound over all iterations, layers, and datasets. The upper bound is less problematic, but the lower-bound/positive-definiteness part must be either proved, verified exhaustively for the reported configurations, or explicitly assumed. As written, the statement that Assumption 5.1c is guaranteed is too strong.","section":"Section 5.1, Assumption 5.1c and Figure 3"}],"minor_comments":[{"comment":"The notation ∇L_k(W_k) appears to be a typo: the loss is defined as F(W) in Eq. (1), and there is no loss L_k defined. It should presumably be ∇F(W_k) or the corresponding mini-batch loss.","section":"Algorithm 1, line 2"},{"comment":"The joint-storage scheme places the Cholesky factor and the error state in the lower and upper triangular parts of one matrix, but the exact memory layout, the bit-width of the error state, and how the 32-bit diagonal interacts with the 4-bit off-diagonal storage are not fully specified. Since the reported memory savings in Tables 3–6 depend on this layout, a precise description would help reproducibility.","section":"Section 4.3 and Figure 2"},{"comment":"The additive error term C_B n_k 2^{-b} I uses n_k as the number of rows of W_k, but the actual preconditioner in Eq. (14) is H_k = D(ˆR_k) ⊗ D(ˆL_k), which has dimension mn; the dependence of the bound on the matrix dimensions should be clarified or corrected.","section":"Proposition 5.1"},{"comment":"The linear-2 mapping in Eq. (4) is attributed to [15,32], but [15] is an 8-bit optimizer paper and the mapping may originate elsewhere; please ensure the credit is accurate and define b explicitly in Algorithm 1, since the algorithm is called '4-bit' but the quantizer mapping is stated for general b.","section":"Section 3.2"}],"recommendation":"major_revision","confidential_remarks":"The paper has a strong empirical component and the proposed technique is plausible, but the theoretical section currently overclaims: the two load-bearing propositions used to justify Assumption 5.1c are either mismatched to the quantizer or algebraically incorrect. This is repairable, either by proving correct quantizer-specific error bounds and diagonal-dominance conditions, or by demoting the spectral assumption to an explicit, clearly stated assumption and adjusting the theorems' claims accordingly. If the authors can do that, the paper would be a solid contribution; if not, the convergence results should be removed or substantially weakened."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the empirical recipe is real and useful; the theory as written is not. I'd send it to review because the method deserves scrutiny and the proofs need fixing, not because the proofs are convincing.\n\nWhat's new: quantizing the Cholesky factors of Shampoo's preconditioners rather than the preconditioners themselves, plus error feedback applied to the stored factors. That combination is genuinely new relative to the 4-bit Shampoo work they cite, and it buys real memory savings: storing lower-triangular 4-bit factors plus a packed error state is about 75% of the cost of vanilla 4-bit, and the experiments show CQ+EF consistently beats vanilla 4-bit and lands close to 32-bit Shampoo on CIFAR, Tiny-ImageNet, ImageNet, and LLaMA up to 1B on a single A100. The evaluation is broad, the ablations on beta/beta_e are there, the hyperparameters are detailed enough to reproduce, and the citation pattern is serious. That's solid work.\n\nThe soft spot is Section 5. The convergence theorems are standard structural arguments, but they rest on Assumption 5.1c (bounded eigenvalues of the quantized preconditioner). The paper tries to justify that with Proposition 5.1 / B.2, and the proof doesn't hold up. First, Proposition B.1 bounds quantization error for a uniform grid with spacing 2/2^b. The actual quantizer in Eq. (4) is the nonlinear linear-2 map; for b=4 the largest gap between representable values is 56/225, so worst-case error is about 0.124, larger than 1/16. The stated 2^{-b} bound is false for the implemented quantizer. Second, the diagonal-dominance argument in Proposition B.2 contains an algebraic error: the inequality (1-2^{-b})|M_ii| + (1+2^{-b})sum|M_ij| > 0 is trivially true and doesn't establish the Gershgorin condition. A correct derivation would need |M_ii| > (1+C)sum|M_ij| for a quantizer-dependent constant C, and that condition is neither proved nor verified on the actual M_k. So Assumption 5.1c is effectively an additional unproven premise, and Theorems 5.1 and 5.2 are conditional as written. The claim about 'first proof of global convergence for preconditioned gradient descent' is also broader than what's demonstrated.\n\nNone of this damages the empirical core, which I find credible. The method is simple, memory-efficient, and consistently beats its direct baseline.\n\nWho is this for? Researchers working on memory-efficient optimizers and large-scale training. It deserves a serious referee: the theory needs a corrected quantizer bound or a change of quantizer, and the PD condition needs a proper derivation or an explicit assumption. Worth engaging, not desk-rejecting.","headline":"Solid empirical recipe for 4-bit Shampoo via Cholesky quantization and error feedback, but the convergence proofs rest on a quantizer error bound that doesn't match the implemented quantizer and a positivity argument that doesn't go through.","tokens_in":23539,"tokens_out":3633,"would_cite":true,"duration_ms":29574,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T07","90C26","62L20"],"pacs":[],"model":"deepseek-v4-flash","headline":"4-bit Shampoo with compensated Cholesky quantization matches 32-bit Shampoo's accuracy at a fraction of the memory, with an $O(1/\\sqrt{T})$ convergence rate for smooth nonconvex losses and stationary-point convergence for nonsmooth…","keywords":["4-bit Shampoo","Cholesky quantization","error feedback","preconditioned stochastic optimization","memory-efficient training","nonconvex convergence","low-precision optimizer"],"falsifier":"Watch the condition in Proposition 5.1 during a run of Algorithm 1: for each refreshed block, check whether every row satisfies $|[M_k]_{ii}| > (1 + 2/(2^4-1)) \\sum_{j\\neq i} |[M_k]_{ij}|$, and measure the actual per-entry error of the linear-2 quantizer against the claimed $2^{-b}$ bound; a violation of either at any step would break the positive-definiteness assumption that the convergence theorems depend on.","tokens_in":22355,"feed_emoji":"💾","tokens_out":8471,"duration_ms":68481,"temperature":0.7,"pith_summary":"Shampoo-style preconditioned optimizers can outperform diagonal preconditioners like Adam, but they carry memory-heavy full preconditioners that block large-scale training. This paper tries to establish that the preconditioners can be stored in 4-bit without losing the method's benefit: instead of quantizing the matrices themselves, it quantizes their Cholesky factors, whose triangular form halves storage and whose reconstruction is automatically symmetric positive definite, and it feeds the quantization error back through a cheap 4-bit error state stored in the unused upper triangle. If the claim holds, memory-hungry preconditioned optimizers become practical for billion-parameter models, including LLaMA-scale pretraining where 32-bit Shampoo runs out of GPU memory, while retaining accuracy close to the 32-bit baseline.","feed_headline":"4-bit Shampoo matches 32-bit accuracy via Cholesky quantization","feed_subtitle":"Store preconditioners as quantized Cholesky factors plus error states: half the memory, near-full accuracy.","key_machinery":"The load-bearing object is the compensated Cholesky quantizer. Each Shampoo preconditioner $L_k$ is factored as $C_k C_k^T$; the lower-triangular Cholesky factor $C_k$ is quantized blockwise to 4-bit for off-diagonal entries while diagonals stay at 32-bit, and the quantization error is accumulated into a 4-bit error state $E_k$ that is exponentially averaged and added back to the next Cholesky factor before quantization. Because the error state is triangular with zero diagonal, it is stored in the upper-triangular half of the same matrix that holds the factor, so the scheme costs no more memory than vanilla 4-bit Shampoo. Reconstruction $D(C_k)D(C_k)^T$ is symmetric positive definite by construction, which is what keeps the inverse-fourth-root preconditioners spectrally close to the 32-bit versions; the convergence theorems then only need the reconstructed preconditioners to have bounded eigenvalues, which the paper attempts to guarantee through a diagonal-dominance argument on the unquantized inverse-root matrix.","core_discovery":"The paper's central claim is that compensated Cholesky quantization makes 4-bit Shampoo behave like 32-bit Shampoo. Experimentally, on CIFAR-100, Tiny-ImageNet, and ImageNet, the proposed 4-bit Shampoo outperforms vanilla 4-bit Shampoo and lands within a fraction of a percentage point of 32-bit Shampoo on ResNet, Swin, and ViT models, and on LLaMA pretraining it trains a 1B model that 32-bit Shampoo cannot fit, reaching perplexity 46.31 versus 48.39 for AdamW. Theoretically, the paper proves an $O(1/\\sqrt{T})$ convergence rate for smooth nonconvex objectives, matching the optimal rate for first-order methods, and, for nonsmooth Whitney-stratifiable objectives such as ReLU networks, convergence of the iterates to the stationary-point set, which it describes as the first global convergence proof for preconditioned gradient descent.","pith_inferences":["The same Cholesky-quantization-plus-error-feedback construction should transfer to other preconditioned optimizers whose preconditioners are symmetric positive definite, such as K-FAC-style block methods; the paper notes this generality only as future work.","Because the proof's spectrum bound hinges on diagonal dominance of the unquantized inverse-root matrix, a practical safeguard would be to monitor this condition during training and fall back to higher precision for stray blocks; the paper does not propose such a monitor.","The diagonal-in-32-bit, off-diagonal-in-4-bit split suggests a natural mixed-precision schedule: reserve more bits for diagonal entries when preconditioners become ill-conditioned late in training; this is a testable extension not explored in the paper.","Theorem 5.2's proof actually uses only bounded SPD preconditioners and Cesàro summability, so the same nonsmooth convergence argument would cover quantized variants of any preconditioned method satisfying those conditions."],"forward_implications":["On ImageNet, 4-bit compensated Cholesky Shampoo reaches 78.00% accuracy on ResNet-50 and 75.01% on ViT-Base, within 0.06 and 0.46 percentage points of 32-bit Shampoo while cutting peak memory.","With LLaMA-1B on C4, 32-bit Shampoo exceeds the 80GB GPU memory while 4-bit Shampoo trains at perplexity 46.31, beating AdamW's 48.39.","The error state adds no memory beyond vanilla 4-bit Shampoo, since it is stored in the upper-triangular half of the Cholesky factor matrix.","For smooth nonconvex objectives, quantized Shampoo converges at the optimal $O(1/\\sqrt{T})$ rate.","For nonsmooth stratifiable objectives such as ReLU networks, the paper claims global convergence to stationary points, a first for preconditioned gradient descent."],"supporting_citations":[{"why":"introduces Shampoo, the preconditioned optimizer whose memory cost this paper compresses.","marker":"[22]"},{"why":"provides the practical Shampoo update rules and inverse-root computation that Algorithm 1 builds on.","marker":"[3]"},{"why":"supplies block-wise linear-2 quantization, the compression scheme used on Cholesky factors.","marker":"[15]"},{"why":"establishes the 4-bit optimizer-state quantization setting that the memory comparisons target.","marker":"[32]"},{"why":"defines an earlier 4-bit Shampoo baseline whose vanilla quantization is the main comparison point.","marker":"[51]"},{"why":"originates the error-feedback idea that the compensated error states adapt from gradient compression to preconditioners.","marker":"[42]"},{"why":"provides the stratifiable-function convergence machinery on which Theorem 5.2 rests.","marker":"[13]"},{"why":"supplies the Schur-Newton algorithm used to compute inverse fourth roots of the reconstructed matrices.","marker":"[21]"},{"why":"supplies the lower bound that makes the $O(1/\\sqrt{T})$ rate optimal.","marker":"[8]"}],"fun_headline_variants":["4-bit Shampoo with Cholesky factors cuts memory, keeps accuracy","Cholesky quantization shrinks Shampoo memory to 4 bits","Error feedback boosts 4-bit Shampoo to match full precision","4-bit Shampoo halves memory via Cholesky quantization and error feedback"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Everything rests on the assumption that the reconstructed 4-bit preconditioners stay well-behaved—symmetric, positive, and not exploding—for every training step, and the paper's guarantee of that fact assumes a row-dominance condition on the unquantized inverse-root matrix that the algorithm itself is not shown to satisfy.","fun_headline_variants_meta":{"raw":{"variants":["4-bit Shampoo with Cholesky factors cuts memory, keeps accuracy","Cholesky quantization shrinks Shampoo memory to 4 bits","Error feedback boosts 4-bit Shampoo to match full precision","4-bit Shampoo halves memory via Cholesky quantization and error feedback"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001565,"raw_usage":{"total_tokens":6249,"prompt_tokens":940,"completion_tokens":5309,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":556,"completion_tokens_details":{"reasoning_tokens":5229}},"tokens_in":556,"tokens_out":5309,"duration_ms":31549,"temperature":1.0,"reasoning_tokens":5229,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T15:44:41.333328+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Watch the condition in Proposition 5.1 during a run of Algorithm 1: for each refreshed block, check whether every row satisfies $|[M_k]_{ii}| > (1 + 2/(2^4-1)) \\sum_{j\\neq i} |[M_k]_{ij}|$, and measure the actual per-entry error of the linear-2 quantizer against the claimed $2^{-b}$ bound; a violation of either at any step would break the positive-definiteness assumption that the convergence theorems depend on.","supporting_citations":[{"cited_title":"Shampoo: Preconditioned stochastic tensor optimization","cited_arxiv_id":null,"evidence_quote":"introduces Shampoo, the preconditioned optimizer whose memory cost this paper compresses."},{"cited_title":"Memory efficient optimizers with 4-bit states","cited_arxiv_id":null,"evidence_quote":"establishes the 4-bit optimizer-state quantization setting that the memory comparisons target."},{"cited_title":"1-bit stochastic gradient descent and its application to data- parallel distributed training of speech dnns","cited_arxiv_id":null,"evidence_quote":"originates the error-feedback idea that the compensated error states adapt from gradient compression to preconditioners."},{"cited_title":"Stochastic subgradient method converges on tame functions","cited_arxiv_id":null,"evidence_quote":"provides the stratifiable-function convergence machinery on which Theorem 5.2 rests."},{"cited_title":"A schur–newton method for the matrixp th root and its inverse.SIAM Journal on Matrix Analysis and Applications , 28(3):788–804, 2006","cited_arxiv_id":null,"evidence_quote":"supplies the Schur-Newton algorithm used to compute inverse fourth roots of the reconstructed matrices."},{"cited_title":"Lower bounds for finding stationary points ii: first- order methods","cited_arxiv_id":null,"evidence_quote":"supplies the lower bound that makes the $O(1/\\sqrt{T})$ rate optimal."}],"review_version":1}