- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The authors prove the exact worst case asymptotic rate of accelerated gradient method (AGD) for smooth strongly convex optimization problem with the condition number . The argument can be summarized as follows:
-
The authors consider interpolation conditions for smooth and strongly convex functions based on the Legendre transform. The main difference from Taylor et al. (2017) is that they eliminate function values using Rockafellar's cyclic monotonicity interpolation conditions for proper closed convex functions.
-
The authors consider -dimensional trajectories of the AGD, where each 2-dimensional block corresponds to a complex geometric sequence of the form , where . For these trajectories they provide simplified (equivalent to Rockafellar's) interpolation conditions (10) in terms of finitely supported probability measures over phases of (Lemma 3.1).
-
Finding the worst convergence rate (maximal element in ) over such trajectories can be formulated as finding the largest amplitude such that interpolation conditions (10) hold for some measure . The authors also provide a lifted version of this problem over probability distributions on a complex disc in (12). Propositon 3.2 shows that the optimal measure is supported on a circle, which allows to recover the angular measure and proves equivalence between (12) and maximal value in .
-
Theorem 4.1 shows that the worst-case rate over considered geometric trajectories matches the true worst-case rates in (2) and (3). The main result for the exact worst-case asymptotic rate is proved in Corollary 4.3: the upper bound uses the interpolation conditions (10), and the lower bound is proved by providing a certain feasible measure in (12).
Critical strengths
The main strengths are interesting theoretical insights:
-
Interesting utilization of the interpolation conditions for closed and convex functions that do not use objective function values. Most existing papers (e.g. Taylor et al. (2017)) use simpler conditions with function values.
-
Interesting connection of the worst-case asymptotic convergence rates with the linear optimization problems over probability measures.
Critical weaknesses
The main weakness is significance: the main result for the worst-case asymptotic rate only shows an optimality of the universal constant factor . Moreover, slight modifications of AGD already achieve exact optimal rates [a]. It would be interesting to see if the theoretical developments from this paper could be used to establish genuinly new results beyond improvement of constants.
[a] Taylor, Adrien, and Yoel Drori. "An optimal gradient method for smooth strongly convex minimization." Mathematical Programming 199.1 (2023): 557-594.
Questions for authors
n/a
Exact characterization beyond the large-condition-number constant
Thank you for the review and the connection to Taylor and Drori. We agree that the paper should explain its significance more clearly.
The sharp constant 4/3 is just one consequence of our results. Theorem 4.1 gives (a) an exact characterization of the asymptotic factor for every fixed κ>1, (b) equality of the fixed-objective and horizon-dependent factors, and (c) attainment by one finite-dimensional objective with standard initialization. Corollary 4.3 then extracts the large-κ expansion.
The fixed-objective statement also distinguishes the result from an improvement of an upper-bound constant. It shows that the slower behavior can persist on one objective throughout an infinite run. At κ=10, the quadratic factor is approximately 0.4675445, Gannot's upper bound is approximately 0.5652352, and our exact factor is approximately 0.5644233. The upper-bound improvement is small, but the matching construction proves that nearly all the gap above the quadratic benchmark is unavoidable for standard NAG.
Quantitative comparison with ITEM. We agree that modifying the algorithm improves its guarantee. Taylor and Drori's Information-Theoretic Exact Method attains the oracle-complexity lower bound for distance to the optimizer. Their Sections 2.2–2.3 give the exact asymptotic squared-distance factor (1−1/κ)2 for the output sequence zN. Comparing this with standard NAG's iterates xt, our theorem quantifies the gap:
\qquad q_{\rm NAG}=1-\frac{4}{3\sqrt{\kappa}}+o(\kappa^{-1/2}).$$ Both methods use one gradient evaluation per iteration. At fixed $\kappa$, the leading worst-case iteration counts for relative squared-distance tolerance $\varepsilon\downarrow0$ are $\log(1/\varepsilon)/[-\log q]$. Their ratio, NAG divided by ITEM, is therefore $\log q_{\rm ITEM}/\log q_{\rm NAG}$. This ratio is approximately $1.33$ at $\kappa=10$ and tends to $3/2$ as $\kappa\to\infty$. Thus, in this high-accuracy asymptotic comparison, standard NAG requires about 33% more gradient evaluations at $\kappa=10$, rising to 50% more as $\kappa$ grows. These are asymptotic comparisons, not finite-iteration or runtime claims. ITEM establishes what an optimally designed method can guarantee. Our result identifies the exact penalty for using standard NAG and constructs one fixed objective exhibiting its slower behavior. **Consequences beyond the leading constant.** Corollary 4.4 gives the same exact factor for function gap and squared gradient norm. At $\kappa=100$, the optimal measure in our characterization requires two rotation angles, and the construction combines two planar spirals. Remark 4.2 gives a condition number at which the exact factor is not expressible by radicals over the rationals. The two-angle example rules out a single rotating mode within our characterization. The radical obstruction explains why a general formula by radicals is unavailable. The proof constructs one finite-dimensional objective attaining the factor and bounds every trajectory. Finite support and standard initialization are essential to this argument. To extend it to other stationary methods, one must establish the analytic bounds and nonzero limiting function needed for finite support, stability of the rescaled recurrence, and compatibility with standard initialization. In the uploaded revision, we have emphasized exactness for every fixed condition number, added the Taylor–Drori reference and the distinction between algorithm design and analysis, and expanded the proof sketch. The exact-rate theorem, metric corollary, two-angle example, and radical obstruction were already established in the submission.