- Rating
- 1
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
This paper is a theoretical analysis paper and focuses on the Adam optimizer. The standard smoothness controls the normalized descent and the adaptive smoothness controls adaptive methods. This paper shows that these two constants, and a pointwise constant between them, are one quantity: the largest expected curvature that a random probe can detect.
However, the writing is very unclear. The motivation is unclear, and the objective is confusing. Authors should consider readers without related background.
Critical strengths
-
The decomposition in Theorem 2.1 provides a useful explanation of the dimension gap.
-
The accelerated algorithm has a theoretical guarantees in the Theorem 5.1.
Critical weaknesses
-
The paper structure is very unclear. It should highlight the motivation, challenge, and contribution. It is very unfriendly for readers without a related background.
-
The paper mentions convex optimization. However, the motivation for the convex optimization is unclear. Given neural network is a non-convex optimization, the convex optimization is not related to the deep learning.
-
The relationship between section 6 (experiments) and theoretical analysis is unclear. It provides much theoretical analysis. But the experiment is very short. We are not sure whether these analysis could be verified in the practical training
Questions for authors
- For the section 6, what is the datasets you use.
3 comments
Response to Reviewer BMEG (2/2)
Response to Reviewer BMEG (2/2)
Q1 (datasets). Binary logistic regression uses the breast-cancer data of scikit-learn ( principal components, ). Softmax regression uses the digit images of scikit-learn, restricted to the first classes ( principal components, ). The network is a one-hidden-layer network on the digit classes (). This is Appendix I.1 (lines 2440-2447). The revised PDF now names the two datasets in the first sentence of Section 6 (lines 471-474).
W1 (structure: motivation, challenge, contribution). The revised PDF now has an explicit contributions paragraph with a notation key in the introduction (lines 115-125). The three elements are at the following places.
Motivation (lines 056-066). Sign descent and Adam are analysed with two different smoothness constants, and . They can differ by the dimension , and the factor decides whether accelerated rates are available. The paragraph ends with the question the paper answers: "What is the factor made of?"
Challenge (Section 2). The two constants are defined by different optimization problems, a norm that is NP-hard to compute and a semi-infinite semidefinite program over the whole landscape, so neither is expressed in terms of the other.
Contribution (lines 067-114, five titled paragraphs, and the contributions paragraph), in summary:
- Both constants, and a new one between them, are the largest curvature a probe can read under three budgets (Theorem 2.1).
- The first gap is a Grothendieck constant that depends only on the family of preconditioners; for Adam it is below (Theorem 3.1).
- The second gap is the rotation of the curvature across the landscape. It is at most the rank of the family, and convex functions approach this bound (Theorem 4.1).
- In box-constrained convex optimization, rotation is the number of gradient queries before which no deterministic first-order method can accelerate (Theorem 5.2).
- Gradient noise has the same three levels (Theorem G.1).
Figure 1 states the result in one inequality, and Table 1 lists the constants for six preconditioner families. Items 1 to 5 are the content of the contributions paragraph.
Every result has a complete proof in Appendices B to H (roadmap at line 648), and we will answer any question on a specific step.
We ask you to reconsider the rating in the light of the scope of Theorems 2.1, 3.1, 4.1 and G.1, which assume no convexity, and of the role of Section 6.
Thanks a lot for the response. However, I still have concerns about its contribution, presentation and application in the Neural networks. I will keep my scores.
Response to Reviewer BMEG (1/2)
Response to Reviewer BMEG (1/2)
Thank you for the review. Its question has a direct answer: the data are the breast-cancer and digits sets of scikit-learn, specified in Appendix I.1 (lines 2440-2447). The three weaknesses are answered below, each with its place in the paper. Line numbers refer to the revised PDF, in which every change is in blue.
W2 (convexity and deep learning).
Most of the paper does not assume convexity. Four of the five results listed under W1 assume none: Theorem 2.1 (the three smoothness constants are one probing problem) and Theorem 4.1 (rotation is at most the rank) hold for every C2 objective with finite LH; Theorem 3.1 (the Grothendieck constant of every preconditioner family) is stated for all symmetric matrices, hence for indefinite Hessians; Theorem G.1 (Appendix G) concerns gradient noise and places no condition on the objective. Section 6 includes a non-convex model, a tanh network with d=63, and reports both quantities along its Adam training run.
Among the theorems, convexity is a hypothesis only in Section 5 (Theorems 5.1 and 5.2), which studies the minimax risk f(xT)−minf and acceleration, as do the results it sharpens (Xie et al., ICLR 2026; Guzmán and Nemirovski, 2015). Elsewhere convexity appears as a special case with a better constant (π/2 in place of KG, one direction u in place of a pair, as in display (1) of the introduction; lines 077-078 state the general case) or in examples (Proposition 4.2(ii)). It also makes one statement stronger: the extremal functions of Theorem 4.1 are convex, so the worst case of the comparison between Adam's constant and sign descent's is approached by convex functions. For non-convex rates the decomposition applies to the known guarantees as they stand: in diagonal geometry, the ratio of the AdaGrad and sign-descent coefficients in the deterministic non-convex rates is at most KGϱ(f) (paragraph after Theorem A.13).
The paper was submitted to the Optimization primary area. Its objects are Adam and sign descent, and its constants are those of the ICLR 2025, ICML 2025 and ICLR 2026 papers of Xie et al. that it builds on.
W3 (how Section 6 relates to the theory).
Section 6 measures the two quantities that Theorems 3.1 and 4.1 bound, on Hessians recorded along Adam training runs. Its first paragraph defines them (lines 474-476): the pointwise gap ν(A)/∥A∥∞→1, which Theorem 3.1 bounds by KG (by π/2 for positive semidefinite A), and the rotation of the recorded Hessians, which Theorem 4.1 bounds by d. Figure 4(a) draws the bounds π/2 and KG as dashed lines above the measured gaps, and the caption names both theorems. The text then sets each number against the result that governs it (lines 477-484): every pointwise gap is below 1.13, against π/2 and KG; rotation is exactly 1 for logistic regression, as Proposition 4.2(ii) predicts; it is 1.082 for the network, against the bound d=63.
The claims of the paper are theorems, each with a complete proof (Appendices B to H). The experiment is not their evidence. It answers a separate question: do the worst cases of the theorems occur on training trajectories? On these runs they do not, which is the stated conclusion: "On these runs the optimizer never meets the dimension factor of ΛH≤dLH" (lines 483-484). The runs are small (d≤63) because both quantities require exact Hessians and semidefinite programs, and the norm ∥A∥∞→1 is NP-hard to compute. Appendix I gives the protocol with every model, seed and solver, and the supplementary material regenerates the figure.