- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper propose adaptive dual preconditioned gradient descent (DPGD), which combines nonlinear preconditioning with a stepsize rule based on local Bregman curvature estimates. For convex objectives, the authors prove convergence and, under additional local strong convexity assumptions on the preconditioner, R-linear convergence of both objective gaps and gradient norms. They also develop a separate stepsize rule for weakly convex objectives with a known weak convexity parameter, proving asymptotic stationarity without global Lipschitz smoothness. A second contribution is a semiautomatic procedure for constructing radial preconditioners from the normal or tangential inverse curvatures of target growth models. Experiments on eight real datasets compare preconditioner choices and stepsize strategies in terms of gradient evaluations and runtime, supplemented by exponent ablations. The implementation uses a linesearch to initialize the stepsize. Subsequent updates are linesearch-free.
Critical strengths
-
The convergence result makes adaptive nonlinear preconditioning applicable under local regularity conditions. The convex analysis establishes R-linear convergence without requiring a global dual relative smoothness constant. The weakly convex extension retains the explicit DPGD update and proves asymptotic stationarity through a different stepsize rule and Lyapunov analysis.
-
The paper gives a concrete procedure for designing preconditioners and evaluates their contribution separately from stepsize adaptation. The normal and tangential constructions connect the geometry of the update to the curvature growth of a target model. They recover several existing methods and produce additional variants, with Proposition 12 establishing the regularity needed for the convergence results. Comparing the same preconditioners under adaptive and line-search strategies helps identify where the gains come from. Reporting runtime as well as gradient evaluations also accounts for the auxiliary function evaluation required by the adaptive rule.
Critical weaknesses
-
The contribution of the convex algorithm should be distinguished more explicitly from the existing Bregman adaptive framework. The paper acknowledges that its convex stepsize rule is a gradient-space specialization of B-adaPG. I therefore see the linear convergence analysis, the weakly convex extension, and the preconditioner construction as the main contributions. A direct correspondence between the algorithms, assumptions, and convergence statements would make this distinction easier to assess. See Ou et al., Sections 2.1-2.2 (https://arxiv.org/html/2508.01353v2).
-
The experiments leave uncertainty about how sensitive the gains are to initialization and scaling. Several convex experiments deliberately start in regions with pronounced nonquadratic curvature, and the powered hinge experiments choose an initial point with a maximum residual of 10. The interpolation scale is fixed at 1. In addition, the Malitsky–Mishchenko baseline starts with a stepsize of , while Adaptive DPGD uses linesearch initialization. The results support the method’s effectiveness in the tested settings; additional sensitivity checks would strengthen the evidence that the design procedure works reliably across different initial points and objective scales.
Questions for authors
-
Could you provide an explicit correspondence between the convex algorithm and B-adaPG in gradient space, including the curvature estimates and assumptions? Which parts of Theorems 7 and 9 require new arguments beyond this specialization?
-
Do the main convex comparisons retain their conclusions with zero initialization or different magnitudes of the nonzero initial points? How do the results change when the Malitsky–Mishchenko baseline is given an initial stepsize selected using information comparable to that used by Adaptive DPGD?
-
How sensitive is performance to the interpolation scale, which is fixed at 1?
2 comments
Dear Reviewer qpVJ,
Thank you again for your time and valuable comments. Your feedback has been very helpful in improving our manuscript.
We have carefully considered your feedback and revised the manuscript to address your concerns, as detailed in our responses. In particular, we have clarified the relation to B-adaPG and added experiments on initialization, objective scaling, and the interpolation radius.
Would you mind reviewing our responses and revised manuscript and letting us know if you have any remaining questions or concerns? We would be happy to provide further clarification.
Best regards,
The Authors
We thank the reviewer for the constructive comments and suggestions.
(W1, Q1) Relation to B-adaPG and theoretical contributions.
We have clarified the dual relationship between DPGD and Bregman gradient methods in the "Relation to prior work" paragraph of the Introduction and Appendix F.1. Our convex algorithm can be interpreted as B-adaPG in gradient space, with smooth objective ϕ and reference function f∗.
The condition ϕ∈P in Assumption 4(ii) requires ∇f(Rd)⊆intdomϕ. If we restrict attention to domϕ=Rd, the following correspondence holds.
Appendix B.5 gives a proof of Theorem 8 directly in terms of xk, without using convex conjugacy.
In contrast, Theorem 10 (previously Theorem 9) provides a new R-linear convergence result for f under the additional assumption that ϕ is locally strongly convex (Assumption 9). The bounds on f(xk)−f⋆ and ∥∇f(xk)∥ in Eq. (13), proved in Appendix B.6, are not provided by Ou et al. (2026).
Although the dual interpretation above relates DPGD to Bregman gradient methods, DPGD uses ϕ as a potential for minimizing f, rather than simply minimizing ϕ. This role of ϕ and the freedom to design ϕ as a convex potential also support the contributions highlighted in your review: Section 5 constructs ϕ satisfying Assumption 4(ii) and Assumption 9 (Proposition 14 (previously Proposition 12)). The convexity of ϕ, retained even when f is not convex, is key to the weakly convex extension in Section 4.2.
We have also added a new variant for the convex case in Eq. (8), changing only the second argument of the corresponding minimum in Eq. (7). In particular, f∈C2(Rd) and ∇2f≻0 are relaxed to f∈C1(Rd) and convexity. It exploits the known minimum ϕ(0): unlike the objective gap in a general Bregman minimization problem, ϕ(∇f(xk))−ϕ(0) is directly computable. Using this gap directly in the Lyapunov argument yields the new candidate. The weaker assumptions and the counterparts of Theorems 8 and 10 are stated in Assumption 5 and Theorems 25 and 26, with proofs in Appendix B.7. We also added experiments using this rule, showing favorable convergence behavior of the proposed method relative to the baselines (Appendix E.7, Figure 23).
(W2, Q2, Q3) Sensitivity to initialization, objective scaling, and interpolation radius.
We have added Appendix E.6 (Figures 17–22), covering Malitsky–Mishchenko (MM) initialization, initial points, objective scaling, and the interpolation radius.
MM initialization. The initial value λ0=10−10 follows the setup in Malitsky and Mishchenko (2020, Algorithm 1 and Section 2.1). Their adaptive rule is
\sqrt{1+\theta_{k-1}}\lambda_{k-1}, \frac{\lVert x_k-x_{k-1}\rVert}{2\lVert\nabla f(x_k)-\nabla f(x_{k-1})\rVert} \right), \qquad \theta_k=\frac{\lambda_k}{\lambda_{k-1}}, \qquad \theta_0=+\infty.$$ At the first adaptive update ($k=1$), the first candidate is $+\infty$. Thus, the small initial value does not force the subsequent stepsizes to remain comparably small. We interpreted the question about MM's initial stepsize in Q2 as referring to linesearch initialization, in light of the comparison in W2. We therefore tested MM with Armijo initialization: the proposed method still reaches the stopping criterion with fewer gradient evaluations and less runtime than this MM baseline on all four datasets (Appendix E.6.1, Figure 17). **Initial points.** We compared zero initialization and different magnitudes of the initial point. The proposed method remains competitive across these starts, and larger initial norms highlight the benefits of nonlinear preconditioning over Euclidean Adaptive DPGD and MM (Appendix E.6.2, Figures 18–19). **Objective scaling.** We scaled $f$ by $c\in\lbrace0.1,1,10\rbrace$. The proposed method retains its advantage over Euclidean Adaptive DPGD and GD Armijo, and its objective-gap curves remain similar across the tested scales (Appendix E.6.3, Figures 20–21). **Interpolation radius.** Changing the radius has little effect in some experiments and a larger effect in others. The observed differences are consistent with insufficient nonlinear correction when the radius is too large and excessive correction when it is too small. The original radius of 1, used without tuning, performs well (Appendix E.6.4, Figure 22).