acceptodds
Under review as a conference paper at ICLR 2027

Provable Benefits of Block Preconditioning over Gradient Descent under Block-Heterogeneous Smoothness

Abstract

Motivated by the empirical advantage of adaptive optimizers on Transformers, we study the comparison between block-preconditioned gradient descent (Block-PGD) and constant-step gradient descent (GD). We introduce block-heterogeneous smoothness, in which parameter blocks have distinct smoothness constants Lₖ, and measure stationarity by G² = Σₖ ‖∇ₖf‖²/Lₖ, the ordinary gradient norm in curvature-normalized coordinates. Block-PGD attains min(t < T) G² ≤ 2Δ/T, whereas GD attains 2RₕΔ/T, where Rₕ is the ratio of the largest to the smallest block smoothness constant. A quadratic instance proves that linear dependence on Rₕ is necessary for GD, including under loss and ordinary-gradient criteria, although it does not match the general nonconvex dependence on accuracy. We extend the upper bounds to stochastic gradients, establish a local Zipfian softmax majorizer with ratio V raised to the power α, and give a conditional RMSProp-style result with √Rₕ dependence. Direct Hessian–vector-product diagnostics on a small GPT-2 model trained on WikiText-2 find persistent architecture-block curvature heterogeneity and strong second-moment/curvature alignment for output-class blocks. These results explain the benefit of block preconditioning; they do not constitute a convergence theory for full Adam with momentum.

Primary area:
optimization
Keywords:
block preconditioning, smoothness, gradient descent, optimization, adaptive methods

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_woZDOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces a Block-Heterogeneous Smoothness framework, which includes definitions of smoothness and a weighted stationarity measure. Under this framework, it studies block-preconditioned GD compared to GD. The theoretical analysis gives upper bounds for both Block-PGD and GD, together with a quadratic lower-bound example establishing necessary linear dependence on block heterogeneity for GD under the weighted stationarity measure. The paper additionally extends the analysis to softmax regression, providing a local result, and to square-root diagonal preconditioning. The experimental part compares SGD with Adam on synthetic softmax regression, compares Block-PGD with GD on a separable quadratic function, and includes an empirical curvature analysis for a small language model.

Critical strengths

The theoretical analysis is well motivated, and its proofs are short and easy to check. The developed framework provides a useful perspective on optimization under block heterogeneity. The extension to softmax regression gives the theoretical results a concrete application beyond quadratic problems.

Critical weaknesses
  1. The softmax experiments could connect more directly to the theory. The theory analyses Block-PGD and GD, while Section 7.2 compares Adam with SGD and the comparison of GD with Block-PGD is only shown on a quadratic task. Extending the softmax regression comparison would help reinforce theoretical insights. A comparison of SGD with block-preconditioned SGD would also be appropriate.

  2. The general separation in Corollary 5 has a limited scope. Theorem 4 and Proposition 11 establish a separation on quadratic problems. For general nonconvex objectives, the paper compares upper bounds without a matching lower bound. Although the paper acknowledges this limitation, it restricts the scope of the theoretical separation. Extending the experiments in Section 7.1 and Figure 2 to include a comparison of GD and Block-PGD on nonquadratic, nonconvex objectives with known block-smoothness constants would strengthen the empirical evidence.

Presentation issues

  • The repeated caveats, for example in lines 70–71, 138, 253–254, and 323, interrupt the exposition. Consolidating them into the discussion or limitations section would improve the presentation.
  • In Theorem 4, the general indexing with K≥2K\geq2 is unnecessary for the two-block construction. Using L1L_1 and L2L_2 would simplify the statement.
  • The title of Section 5 "Application to Transformers" overstates its scope. The paper should either discuss how the analysis applies beyond the softmax output head or use a narrower section title.
Questions for authors
  1. Could you include a comparison of SGD with block-preconditioned SGD on the softmax regression task?

  2. Could you extend the experiments in Section 7.1 to nonquadratic, nonconvex objectives with known block-smoothness constants?

Reviewer_J36wOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies how differences in curvature across parameter blocks can make a single global learning rate inefficient. Under a blockwise quadratic upper model, it proves that ideal block-preconditioned GD achieves a 2Δ/T2\Delta/T convergence bound, versus 2RHΔ/T2R_H\Delta/T for constant-step GD, where RH=Lmax⁡/Lmin⁡R_H=L_{\max}/L_{\min}. This comparison uses a curvature-weighted gradient norm. Its contributions include a quadratic example proving necessary linear dependence on RHR_H for GD, including under loss and ordinary gradient criteria, a stochastic extension, a local softmax analysis connecting Zipfian class frequencies to curvature heterogeneity, and conditional guarantees for diagonal preconditioning and a momentum-free RMSProp style like update.

Critical strengths
  1. The paper explicitly connects block-curvature heterogeneity to an RHR_H-factor difference between convergence upper bounds. Its quadratic construction additionally builds a necessary linear dependence on RHR_H for GD under loss and ordinary gradient criteria.

  2. The experiments measure curvature, optimizer second moments, and effective steps, finding strong alignment for output-class blocks while reporting failures for architecture blocks. The evidence tests the theory’s underlying assumptions and identifies the decompositions where its connection to practical optimization is credible.

Critical weaknesses
  1. The non-convex separation problem is still open and dependent upon the metric. The RHR_H-factor improvement is established between upper bounds in curvature weighted stationarity; converting to ordinary-gradient stationarity can eliminate that advantage. The quadratic lower bound establishes necessary linear RHR_H dependence, but does not match the general nonconvex accuracy dependence. This materially limits the theoretical contribution: whether the displayed RH/ε2R_H/\varepsilon^2 dependence is inherently necessary remains unresolved.

  2. The connection to practical adaptive optimization is based on assumptions that the experiments did not show. For example, Block-PGD requires appropriate curvature scales; the RMSProp-style guarantee requires uniform second moment/curvature comparability. Architecture-block effective steps do not meet the stronger sufficient alignment condition, and output-class correlations do not provide the necessary uniform bounds or a causal explanation for Adam's advantage. This has consequences for the Transformer motivation since it is only partially supported: the paper shows relevant geometric associations but does not verify the mechanism that connects learned preconditioning to improved optimization.

Questions for authors
  1. Does the advantage persist under standard metrics? Beyond the quadratic construction, under what additional conditions does block preconditioning retain an RHR_H-dependent advantage when both methods are evaluated using ordinary-gradient stationarity or objective suboptimality? Can the authors provide a nonconvex example demonstrating this?

  2. How much of the nonconvex gap reflects the analysis? Since the joint RH/ε2R_H/\varepsilon^2 lower bound remains open, can the authors provide evidence about the tightness of the GD upper bound? For example, a controlled nonconvex family where RHR_H and the target accuracy are varied independently?

  3. Can an intervention test the proposed mechanism? Can the authors compare curvature-aligned preconditioners with shuffled assignments of the same scaling values, while controlling momentum and tuning learning rates comparably?

Reviewer_VKfvOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies when block-specific learning rates can improve on a single global learning rate. It assumes a quadratic upper bound with a separate smoothness constant for each block. Under this assumption, it compares block-preconditioned gradient descent with gradient descent in a weighted gradient norm. It also gives quadratic examples, stochastic extensions, and a conditional analysis of square-root preconditioning. Experiments examine synthetic problems and a small language model.

Critical strengths

The paper gives a clear account of how block-specific learning rates can help when curvature varies across blocks. A global learning rate is limited by the block with the largest curvature. This can make progress unnecessarily slow in blocks with smaller curvature. The quadratic examples make this mechanism explicit and show that the resulting slowdown can grow with the ratio between the largest and smallest block smoothness constants. The paper also goes beyond the simplest example, where each block has constant curvature and exact preconditioning solves the problem in one step. It considers variation in curvature within each block and errors in the estimated smoothness constants. These extensions show that the advantage can persist when block preconditioning does not perfectly match the Hessian. This makes the examples more informative and helps clarify which aspects of the benefit depend on accurate curvature information.

Critical weaknesses
  1. Several uncited papers already study how heterogeneous smoothness can favor adaptive or layer-wise updates. You et al. (ICLR 2020) compare layer-wise methods with SGD through average and maximum layer smoothness constants. Liu, Pan, and Zhang (ICLR 2025) analyze AdaGrad under anisotropic smoothness and noise. Xie, Mohamadi, and Li (ICLR 2025) study Adam in ℓ∞ geometry and extend their analysis to blockwise updates. Gluon (Riabinin et al., 2025) is especially relevant. With Euclidean block norms and its gradient-dependent smoothness term set to zero, its update reduces to the same inverse-smoothness block step. Its descent analysis also yields the same weighted-gradient bound. Its assumptions are stronger, so this does not establish that the present theorem is already covered in full. However, the paper should identify the precise advance over this result. This matters because the main upper bound follows directly from the change of variables z=H1/2wz=H^{1/2}w, where (H) contains the block smoothness constants. In these coordinates, the method is ordinary gradient descent. The quadratic lower bound gives a useful example, but it does not establish a matching separation for general nonconvex problems. The paper needs to explain which new result remains after these connections are made.

  2. The experiments contain many inconsistencies. In Figure 3(c), the text and caption describe per-class gradient measurements and state that these are not smoothness estimates. The panel title, axis, and legend nevertheless label them as smoothness constants. The synthetic softmax experiment also needs clarification. Gaussian class-conditional features with unequal class priors generally require class-specific intercepts to obtain the true posterior. The displayed model has no intercept. Unless the implementation includes a bias or a constant feature, the experiment does not satisfy the well-specification assumption used in the theory. Increasing vocabulary size while keeping the sample count fixed also changes the number of parameters and the number of observations per class. This makes it difficult to attribute the observed effect to curvature heterogeneity alone. Finally, the square-root preconditioning result assumes that the second-moment estimates remain within fixed multiples of the block smoothness constants. The language-model measurements do not establish this condition. They provide evidence of an association in selected blocks, but do not yet explain the optimizer’s behavior across the full model.

Yang You, Jing Li, Sashank Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song, James Demmel, Kurt Keutzer, and Cho-Jui Hsieh. “Large Batch Optimization for Deep Learning: Training BERT in 76 Minutes.” ICLR, 2020.

Yuxing Liu, Rui Pan, and Tong Zhang. “AdaGrad under Anisotropic Smoothness.” ICLR, 2025.

Shuo Xie, Mohamad Amin Mohamadi, and Zhiyuan Li. “Adam Exploits ℓ∞\ell_\infty-geometry of Loss Landscape via Coordinate-wise Adaptivity.” ICLR, 2025.

Artem Riabinin, Egor Shulgin, Kaja Gruntkowska, and Peter Richtárik. “Gluon: Making Muon & Scion Great Again! (Bridging Theory and Practice of LMO-based Optimizers for LLMs).” arXiv preprint arXiv:2505.13416, 2025, version 1.

Tim Large, Yang Liu, Minyoung Huh, Hyojin Bahng, Phillip Isola, and Jeremy Bernstein. “Scalable Optimization in the Modular Norm.” Advances in Neural Information Processing Systems, 37, 2024.

Yushun Zhang, Congliang Chen, Ziniu Li, Tian Ding, Chenwei Wu, Diederik P. Kingma, Yinyu Ye, Zhi-Quan Luo, and Ruoyu Sun. “Adam-mini: Use Fewer Learning Rates To Gain More.” ICLR, 2025.

Shuo Xie, Tianhao Wang, Sashank J. Reddi, Sanjiv Kumar, and Zhiyuan Li. “Structured Preconditioners in Adaptive Optimization: A Unified Analysis.” Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:68746–68776, 2025.

Questions for authors
  1. What is new relative to the closest theoretical results? Could the authors compare the assumptions, updates, and stationarity measures with Gluon, the blockwise analysis of Xie et al., and the anisotropic analysis of Liu et al.? Does the weaker smoothness assumption provide the main advance?

  2. What exactly is plotted in Figure 3(c)? Please give the measured quantity and its normalization. If it is a gradient statistic, what evidence supports the claimed scaling of the smoothness constants?

  3. How are the hitting-time ratios in Figure 2 computed? What is the target threshold, and does every method reach it within the iteration budget? How are unfinished runs and the initial iterate counted?

  4. Does the synthetic softmax implementation include class-specific biases? If not, how should the experiment be interpreted relative to the well-specification assumption?

  5. How well does the second-moment assumption hold in practice? Can the authors report the spread of vt,i/Lkv_{t,i}/L_k across coordinates and training steps? The size of this spread affects whether the square-root preconditioning bound improves on the GD bound.

3 comments

We would like to add a few clarifications in response to the questions above.

  1. Relation to the closest theory. Gluon's deterministic Euclidean specialization with its gradient-dependent term set to zero recovers the inverse-smoothness update and weighted-gradient descent bound. We now credit that result explicitly and do not claim the shared descent argument or coordinate change as new. Liu et al. study AdaGrad with an adaptive, data-dependent geometry under anisotropic smoothness, while Xie et al. study Adam and blockwise updates in ℓ∞\ell_\infty geometry. Our comparison instead fixes declared block scales, uses one common block quadratic majorizer, and evaluates ∑k∥∇kf∥2/Lk\sum_k\|\nabla_k f\|^2/L_k. The paper's additional results are the matched scalar-GD comparison, the quadratic examples showing necessary linear heterogeneity dependence under loss and ordinary-gradient criteria, the stochastic comparison, and the explicit scale-misspecification analysis. The joint upper model allows cross-block interactions, but we do not present that fact alone as the novelty.

  2. Figure 3(c) and the softmax intercept. The original panel did not plot smoothness. For each class, it sums the squared norm of the class-conditioned minibatch gradient and then normalizes all class totals by their maximum. It is therefore a normalized class-conditioned gradient-energy statistic, not a smoothness estimate. The revision separates this descriptive statistic from the Hessian-based curvature diagnostic. The training model is affine and includes class-specific intercepts. Under the shared-covariance Gaussian construction, these intercepts absorb the unequal class priors, so the population posterior remains representable. The separate legacy diagnostic omitted the intercept and is not used to establish well-specification or curvature scaling.

  3. Hitting times. The revised audit counts actual updates from t=0t=0 and keeps non-hits censored. At heterogeneity 1,000 and absolute weighted-squared-gradient target 10−310^{-3}, reconstructed GD does not hit within 3,000 recorded iterates, while Block-PGD hits after one update. We therefore assign no finite ratio to this cell; the previous substitution of the iteration budget is removed.

  4. Time-resolved second-moment audit. The earlier GPT-2 reruns measured only the final checkpoint. We added one declared trajectory at steps 25, 50, 100, 150, 200, 250, and 300. At each checkpoint we evaluated 11,008,896 architecture coordinates and 11,136 selected output-row coordinates. Among the architecture coordinates, 6,336 have zero bias-corrected second moment at every checkpoint. Across the seven checkpoints, the 1st percentile of the moment-to-curvature ratio ranges from 2.54×10−132.54\times10^{-13} to 3.96×10−123.96\times10^{-12}, while the 99th percentile ranges from 3.51×10−73.51\times10^{-7} to 1.79×10−61.79\times10^{-6}. For the selected output rows, the positive max/min spread ranges from 7.66×1047.66\times10^4 to 4.76×1064.76\times10^6. The zero moments rule out a positive uniform lower constant on the measured architecture coordinates, and the remaining ratios span many orders of magnitude. Thus the measurements do not verify useful constants a,b>0a,b>0 satisfying aLk≤vt,i≤bLkaL_k\leq v_{t,i}\leq bL_k across coordinates and steps. The conditional square-root corollary therefore should not be used to explain full-model Adam in this experiment. We will include the single-run protocol and raw record in the supplement and keep the Transformer claim at this diagnostic level.

  5. Scope of the conclusion. When valid block scales are known, block preconditioning can improve on scalar-step GD. The GPT-2 measurements do not show that Adam learns the uniform scales required by the conditional corollary.

Thank you again for your review. We would appreciate any feedback on whether our response addresses your main concerns, and would be happy to clarify any remaining questions.

I thank the authors for their detailed response and corrections. The clarification about the intercepts and the revised treatment of hitting times address those concerns. However, my main concerns about novelty and significance remain. The overlap with prior work limits the theoretical contribution, and the new second-moment audit does not support applying the conditional result to explain Adam’s behavior in the reported experiment. While I appreciate the more careful presentation and narrower claims, these changes do not sufficiently alter my overall assessment, so I maintain my score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.