acceptodds
Under review as a conference paper at ICLR 2027

Optimal Recursive Composition and Dyadic Phase Laws for Gradient Descent with Predetermined Stepsizes

Abstract

Predetermined stepsize schedules featuring carefully chosen long steps have recently been shown to accelerate gradient descent (GD) on smooth convex functions. A prominent class of such schedules is built through recursive composition. In this paper, we characterize the convergence of these optimized recursive schedules, revealing a nonconstant log-periodic modulation across prescribed horizons. Specifically, we prove that for every , the optimized ConPP/OBS-S schedules satisfy where is a positive, Lipschitz, nonconstant -periodic function. We derive this by proving that balanced splitting is optimal at every horizon for these constructions, resolving a conjecture of Zhang and Jiang. Furthermore, for their asymmetric counterparts (ConPD/OBS-F schedules), we show that although optimal splits are not necessarily balanced, the same Silver exponent asymptotically persists alongside a distinct log-periodic modulation.

Primary area:
optimization
Keywords:
gradient descent, convex optimization, stepsize schedules, convergence analysis, recursive composition

Reviews

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

The paper studies accelerated convergence of gradient descent via predetermined step sizes. The paper analyzes two existing families: symmetric ConPP/OBS-S schedules and asymmetric ConPD/OBS-F schedules. For ConPP/OBS-S schedules, the paper shows that balanced splitting is the optimal schedule, and provide a tight guarantee that depends on a periodic function Φ({log⁡2N})\Phi(\{\log_2 N\}). The key ingredient of the proof is a local four-point rearrangement inequality and an induction to bound every possible split. For ConPD/OBS-F, the paper proves the same convergence exponent and a different, nonconstant periodic coefficient appearing asymptotically. although balanced splits might not be optimal. To prove this, the strategy is to compare the schedule with the symmetric recursion, then show that the coefficient sequence decreases and is bounded below whenever the time horizon doubles thus converges, and control neighboring coefficients to combine these limits into one continuous periodic profile.

Critical strengths
  • The paper resolves an explicit conjecture regarding a family of step size schedules: it characterizes all symmetric schedules for ConPP/OBS-S and prove the optimality of the balanced splitting.
  • Despite the fact that the asymmetric case appears more challenging, the paper still establishes uniform convergence and provides some characterization of the coefficient Ψ\Psi.
  • The paper guarantees a sharp convergence for ConPP/OBS-S with balanced split and also identifies the guarantees for the coefficient function in the convergence of the asymmetric case.
Critical weaknesses
  • The main limitation of the paper is the optimality is only restricted within the ConPP/OBS-S recursive family. In terms of improvement in the convergence, the exponent is already known from prior work, the paper only improves in the leading constant (or rather the coefficient Φ\Phi), which is very close to 1.
  • The characterization of the asymmetric schedules is incomplete (not necessarily a weakness though), while the exponent in the convergence has already been shown in prior works.
Questions for authors

N/A

3 comments

We thank the reviewer for the assessment of our work and for highlighting the contributions and limitations of both the symmetric and asymmetric analyses. We clarify the scope and significance of our results below.

1. Significance of the recursive families.

We would first like to emphasize the importance of the recursive families studied in this paper. Recursive composition has been a central approach to constructing accelerated GD schedules with predetermined stepsizes. The ConPP/OBS-S family includes the celebrated Silver schedule and extends its construction to arbitrary horizons, while ConPD/OBS-F further optimizes the worst-case objective-gap guarantee. Moreover, Grimmer et al. (2025b, Conjecture 1) conjectured that OBS-F achieves the minimax guarantee among all predetermined GD schedules. Thus, understanding these families is an important step toward understanding the limits of acceleration through stepsize design.

2. Optimality and phase law for the symmetric family.

While the Silver exponent was already known, the optimal way to construct these recursive schedules at arbitrary horizons, and the precise behavior of their convergence guarantees, remained unresolved. Our paper addresses both questions.

For the symmetric family, we resolve an explicit conjecture of Zhang & Jiang (2026) by proving that balanced splitting is always optimal. We further characterize all optimal recursive constructions and obtain an efficient algorithm for evaluating their optimal guarantees. These results provide a complete structural characterization of the symmetric recursive optimization problem.

We acknowledge that the numerical variation of the symmetric coefficient is small. However, our phase law reveals a persistent dependence on the time horizon that is invisible in the previously known convergence rate. Even after accounting for the Silver exponent, the sharp convergence coefficient continues to vary with the horizon rather than approaching a single constant. Moreover, these guarantees are tight and attained by explicit worst-case examples. Thus, our results provide a precise characterization of the actual worst-case behavior of these accelerated schedules.

3. Phase law and characterization for the asymmetric family.

The asymmetric ConPD/OBS-F family presents a more challenging problem, as its optimal recursive splits can be unbalanced and vary with the horizon. Despite this complexity, we establish that its asymptotic worst-case performance follows a well-defined, nonconstant phase law, uniformly across large horizons. This demonstrates that the horizon-dependent behavior discovered in the symmetric family persists even under more complicated recursive constructions.

Importantly, our results characterize the leading-order convergence behavior of the optimized asymmetric schedules. We have further strengthened this characterization in the revised manuscript by providing a direct mathematical description of the limiting phase function.

We have revised the manuscript to better explain the significance of our results, clarify the scope of our contributions, and strengthen their presentation and supporting analysis. We thank the reviewer again for the constructive feedback.

Thank you for your response. I agree with the authors that understanding acceleration via predetermined stepsizes is an important problem and I think the paper has made nice contributions. However, my concerns remain as I still think ConPP/OBS-S is rather restricted and in terms of convergence behavior, most was known before. Also the characterization of the asymmetric schedules has room for improvement. Therefore I maintain my current assessment.

Thank you for your thoughtful follow-up and careful consideration of our work. We sincerely appreciate your constructive feedback and your recognition of our contributions.

Reviewer_WiQsOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper studies the predetermined stepsize schedules for gradient descent (GD) on smooth convex objective function, where the schedules are built by the recursive composition rule defined in equation (3). Every recursive composition is reduced to a split-selection problem: given a total recursive number N=n+1N = n + 1, a split (m,N−m)(m, N-m) is selected to minimize the optimality gap GD can achieve at step nn. The main theoretical contribution Theorem 3.1 shows that the optimal worst-case convergence rate is achieved if and only if the split is even (i.e., m=⌊N/2⌋m = \lfloor{N/2}\rfloor). The key principle used to prove Theorem 3.1 is briefly mentioned in Section 3.1. The explicit optimal convergence rate (over this family of recursive predetermined schedule) described in the abstract is established in Section 4. Further discussion regarding non-even split (or asymmetric recursion) is provided in Section 5 but with limited motivation.

Critical strengths
  1. Theorem 3.1 resolves open conjecture regarding recursive stepsize schedule and presents clean results. The paper's main Theorem 3.1 provides a clean conclusion on the optimal split to yield best worst-case convergence rate, under no technical assumptions. The result resolves the conjecture in the field.

  2. The proofs passed GPT 5.6 Sol audit and reviewer's selective reading. The reviewer uses AI tool to conduct a preliminary scan of the paper’s proofs, which identified no obvious errors and provides some evidence that the results are plausible. However, the reviewer examined the proofs only selectively rather than verifying every step in detail; therefore, subtle technical errors may still remain.

Critical weaknesses
  1. Theoretical narrative is not sufficiently clear or self-contained. (1) The authors repeatedly mention the terms like ConPP/OBS-S and ConPD/OBS-F and are central to their main central theoretical results. But these algorithms/procedure/schedules are never descried and/or explained formally, so that the reviewer cannot really understand their difference and position this work in the related literature. (2) The motivation of Section 5 is particularly difficult to follow: Section 3 analysis identifies a symmetric optimal split, but Section 5 studies an asymmetric construction without clearly explaining why the symmetry result no longer applies or how this new setting relates to the preceding sections. The reviewer can guess that it might be due to a different family ConPD/OBS-F, not previous family ConPP/OBS-S, but since the terms are never explained and linked to current work, so the reviewer cannot assess the contribution of Section 5.

  2. The presentation is extremely hard to follow. The current manuscript is organized as a dense sequence of technical statements and proofs, providing insufficient intuition or intermediate explanations connecting the results. The reviewer assess that the manuscript might be very hard to follow even if the reader has strong theoretical background in different fields, as long as they are not directly working in this specific problem. From the reviewer's understanding, the central takeaway contributions are essentially optimal split of Theorem 3.1 and the follow-up rate in analytic form as stated in the abstract. Lacking of additional insights or clearer explanation to connect each of the theoretical piece is one of the major concern for the paper to be accepted.

Questions for authors
  1. Can you define the terms ConPD/OBS-F and ConPP/OBS-S properly? Please also explain the connection of these work with current work.

  2. Why we need to consider asymmetric split in Section 5? What is the central question Section 5 wants to answer?

  3. Could you provide a visualization of the final identified optimal stepsize schedule? A figure similar to Figure 1 in "Altschuler, J. M., & Parrilo, P. A. (2025). Acceleration by stepsize hedging: Silver Stepsize Schedule for smooth convex optimization: JM Altschuler, PA Parrilo. Mathematical Programming, 213(1), 1105-1118." (https://arxiv.org/pdf/2309.16530) should be sufficient.

  4. Line 56 claims that the results help understand the behavior of "the horizons in between". Is this claim reflected by the fact that the results in this paper apply to every NN instead of specific N=2kN = 2^k?

  5. Do these theoretical results provide any practical guidance for designing step-size schedules? Although the analysis focuses on vanilla GD, while most commonly used optimization algorithms differ substantially from this setting, could the authors clarify whether any of the resulting insights are expected to transfer to more practical algorithms?

4 comments

We appreciate the reviewer’s constructive feedback on the clarity of the exposition, particularly the definitions of the recursive schedule families and the motivation for Section 5. We have revised the presentation accordingly and address the questions below.

Q1. Definitions and relationships of ConPP/OBS-S and ConPD/OBS-F

We thank the reviewer for this suggestion. We have refined the exposition in the Introduction (including Table 1) and Section 2 and reorganized Appendix A to clarify these constructions and their relationships.

Definitions and correspondence. In Zhang and Jiang (2026), ConPP joins two primitive schedules to produce a primitive schedule, whereas ConPD joins a primitive prefix with a dominant continuation to produce a dominant schedule. In Grimmer et al. (2025b), OBS-S and OBS-F are the Optimized Basic s-composable and f-composable Schedules, respectively. Their underlying joining rules combine two s-composable schedules (s-join), or an s-composable prefix with an f-composable continuation (f-join). These constructions form two corresponding pairs: ConPP/OBS-S (symmetric) and ConPD/OBS-F (asymmetric). Within each pair, the two frameworks generate identical numerical stepsize schedules and tight worst-case objective-gap coefficients when the same ordered composition tree is used, despite their different certificate formulations.

Connections to our work. Section 3 characterizes all optimal splits in the symmetric ConPP/OBS-S family, and Section 4 establishes its exact dyadic phase law. Section 5 extends the phase analysis to the asymmetric ConPD/OBS-F family, establishing a distinct limiting dyadic phase law.

Q2. Motivation for the asymmetric recursion in Section 5

We thank the reviewer for raising this question. We would first like to clarify an important distinction in our terminology: "symmetric/asymmetric" refers to the joining rules, whereas "balanced/unbalanced" refers to the sizes of the two child blocks.

ConPP/OBS-S forms the symmetric family, whose joining rule treats both children symmetrically, while ConPD/OBS-F forms the asymmetric family, whose ordered joining rule combines a symmetric prefix with an objective-specific continuation. Importantly, neither joining rule inherently restricts the child blocks to balanced splits; both allow arbitrary admissible splits. Theorem 3.1 optimizes over all possible splits within the symmetric family and proves that balanced splitting always attains the optimum, though it need not be unique; the theorem also characterizes all unbalanced optimal ties. Since ConPD/OBS-F uses a different joining rule, this balanced-optimality result does not directly apply to Section 5.

Motivation. ConPD/OBS-F achieves a worst-case final objective-gap coefficient no larger than that of ConPP/OBS-S at every horizon (Eq. (20)). More importantly, Grimmer et al. (2025b, Conjecture 1) conjecture that OBS-F attains the minimax final objective gap among all predetermined GD stepsize schedules. This makes understanding its convergence behavior particularly meaningful, as our results would characterize the asymptotic minimax objective-gap guarantee if the conjecture holds.

Central question and results. Section 5 asks whether the nonconstant dyadic-phase phenomenon established for the symmetric family persists under the asymmetric recursion. Theorem 5.1 answers this affirmatively: despite the absence of balanced optimality and exact dyadic scaling, the optimized asymmetric coefficients retain the Silver exponent and converge uniformly over dyadic blocks to a distinct, nonconstant periodic phase profile.

We have revised the Introduction and Section 5 to clarify this motivation and the relationship between the two recursive families.

Q3. Visualization of the optimal stepsize schedules

We thank the reviewer for this helpful suggestion. We have added two figures to visualize the actual optimized stepsize schedules, in the style of Figure 1 of Altschuler and Parrilo (2025).

Specifically, Figure 4 illustrates the symmetric ConPP/OBS-S schedules at N=64N=64 and N=100N=100. The former recovers the classical Silver schedule, while the latter demonstrates the optimal recursive construction at a non-dyadic horizon. Figure 5 displays the corresponding asymmetric ConPD/OBS-F schedules. In particular, their optimal root splits are 42+2242+22 and 64+3664+36, respectively, compared with the balanced splits 32+3232+32 and 50+5050+50 in the symmetric family.

These visualizations highlight the hierarchical structure of the optimized stepsizes and make the distinction between the symmetric and asymmetric recursive constructions more intuitive. We have also added explicit references to these figures in Section 3 and Section 5 of the revised manuscript.

Q4. Interpretation of the horizons in between

Thank you for this question. Yes, "the horizons in between" refers to prescribed horizons NN between consecutive powers of two, rather than only N=2kN=2^k.

Our results address this question at two levels. First, at the structural level, Theorem 3.1 establishes that balanced splitting is optimal for the ConPP/OBS-S family at every horizon NN, extending the perfectly balanced Silver construction at N=2kN=2^k to arbitrary horizons. We also characterize all unbalanced splits that attain the same optimal value. Second, at the convergence-rate level, Theorem 4.1 and Corollary 4.2 provide a more precise characterization of the behavior between dyadic horizons. Specifically, the exact tight worst-case objective coefficient is

BN=12NpΦ(log⁡2N)−1,B_N=\frac{1}{2N^p\Phi(\log_2 N)-1},

where Φ\Phi is a nonconstant periodic function. Thus, the position of NN within a dyadic block affects the leading convergence coefficient, even asymptotically. For example, the normalized coefficients NpBNN^pB_N converge to 1/21/2 along N=2kN=2^k, but to approximately 0.50340.5034 along the intermediate horizons N=3⋅2k−1N=3\cdot2^{k-1}.

Furthermore, Theorem 5.1 establishes an analogous asymptotic phase dependence for the asymmetric ConPD/OBS-F family, whose optimal splits may be unbalanced.

We have revised the Introduction to clarify the meaning of "the horizons in between".

Q5. Practical guidance and transferability

We thank the reviewer for raising this important question. Our goal is to understand the fundamental role of predetermined stepsize design in smooth convex optimization. Studying vanilla GD provides a clean theoretical framework for understanding how predetermined stepsize design affects convergence and deriving tight worst-case bounds on the final objective gap.

Within this setting, our results provide concrete guidance for schedule design. First, Theorem 3.1 shows that recursively splitting the iteration horizon as evenly as possible yields an optimal ConPP/OBS-S schedule for any prescribed number of iterations. Algorithm 1 further allows the corresponding optimal scalar value to be evaluated in O(log⁡N)O(\log N) operations. Second, for the same iteration budget, the optimized ConPD/OBS-F schedule achieves a worst-case final objective-gap guarantee at least as strong as that of the optimized ConPP/OBS-S schedule. Finally, our dyadic-phase characterizations quantify how the leading convergence coefficient varies with the prescribed horizon, providing a more precise assessment of worst-case performance across different iteration budgets.

Regarding extensions to more advanced optimization methods, we believe that the recursive composition perspective has potential beyond vanilla GD, particularly for methods that admit analogous stepsize-composition mechanisms. Encouragingly, Bok and Altschuler (2025) have shown that the Silver stepsize schedule can also accelerate projected and proximal gradient methods, suggesting that the underlying recursive stepsize design principles can extend to broader optimization settings. Since our balanced construction recovers the classical Silver schedule at dyadic horizons, extending our arbitrary-horizon optimality results and dyadic-phase characterizations to these methods would be a natural next step. More broadly, investigating whether similar recursive composition principles can guide stepsize design for momentum-based and adaptive optimization methods is another promising direction for future research.

We have revised the Discussion in Section 6 to highlight these connections and outline potential extensions to broader optimization methods.

The reviewer thanks the authors for detailed response. My concerns have been addressed and I'm willing to raise my score to 3.

Thank you very much for your thoughtful follow-up and careful consideration of our responses. We are glad that our clarifications have addressed your concerns. We sincerely appreciate your constructive feedback, which has helped us improve the clarity and presentation of our paper.

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

This paper studies long-step stepsize schedules for gradient descent on smooth convex functions that are built by recursive composition. In this kind of construction, two shorter schedules are glued together with one extra "joining" step to make a longer schedule. The paper looks at two existing families of this type: the symmetric ConPP/OBS-S family and the asymmetric ConPD/OBS-F family, which is designed for the final objective gap.

For the symmetric family, building the best schedule of a given length comes down to choosing how to split the horizon into two smaller pieces at every level of the recursion. The main result is that splitting as evenly as possible is always optimal. The paper also identifies exactly when an uneven split does equally well. This settles Conjecture 4.17 of Zhang and Jiang (2026). The key tool is a four-point rearrangement inequality. It compares the different ways of pairing four sub-schedules, which is needed because the joining rule is not associative. A practical by-product is that the optimal value at a single horizon can be computed with about log N operations instead of an exhaustive search.

Because balanced splitting is optimal, doubling the horizon multiplies the optimal value by exactly 1 + √2. The authors use this to show that the tight worst-case bound for the symmetric family has the form

\qquad p = \log_2(1+\sqrt{2}),$$ where the function Φ repeats with period one and is not constant. In other words, the leading constant in the usual rate depends on where N sits between two consecutive powers of two. For the asymmetric family, exact doubling is no longer available and the optimal splits can be uneven. Even so, the paper proves that the normalized constants converge to a periodic profile that is also not constant. This profile stays strictly above the lower barrier known from Grimmer et al. (2025b). All results are proved in the appendices. The authors back them up with interval-arithmetic certificates for some numerical constants and report Lean formalizations of the scalar and combinatorial parts. I read the main arguments and checked several numerical claims independently: balanced optimality against brute-force search for horizons up to several thousand, and the reported range of the phase minimum. Everything I checked agreed with the paper. I did not inspect or run the Lean files or the interval-arithmetic code.
Critical strengths

1. The paper fully solves the split problem for the symmetric family. It was not obvious that balanced splitting should always be optimal. The joining rule is symmetric but not associative, so symmetry alone says nothing about how different tree shapes compare. The four-point rearrangement inequality (Theorem 3.2) fills exactly this gap. It also keeps track of when equality holds, and that information carries through the induction to give every optimal split, not just one. The ties turn out to be exactly the pairs of the form

{m,n}={2kr,  2k(r+1)},\{m, n\} = \{2^k r,\; 2^k (r+1)\},

that is, two consecutive integers scaled by a common power of two. This resolves an open conjecture from prior work with a clean and complete answer. I consider it the main reason to accept the paper.

2. The two halves of the paper are connected, and the asymmetric argument has real content. The asymmetric result is not just a parallel story told in the same language. Its key step depends on the symmetric phase. The proof that the asymmetric profile stays strictly above the known barrier works by contradiction. Getting close to the barrier would force a large prefix to be exactly tight for the symmetric bound. By the symmetric phase analysis, that only happens at phase zero, meaning horizons near a power of two. Applying the same reasoning to the remaining part of the schedule then gives a second phase condition that contradicts the first. I found this argument elegant. It explains why a bound that is sharp locally cannot be reached by a schedule that has to be consistent across the whole recursion. So the paper does deliver the unified picture it promises: rearrangement gives balanced optimality, balanced optimality gives the symmetric phase, and the symmetric phase drives the asymmetric separation result.

Critical weaknesses

1. The paper does not explain well why the phase effect matters, even though it is the headline result. The abstract leads with the periodic modulation, but the effect is very small. Using the paper's own bound on the minimum of Φ, the leading constant for the symmetric family only moves within

[12, 12ϕ∗]≈[0.5000, 0.5036],\left[\tfrac{1}{2},\ \tfrac{1}{2\phi_*}\right] \approx [0.5000,\ 0.5036],

which is a change of about 0.7%. The asymmetric bounds also leave room for less than 1% variation. I agree that showing there is no single asymptotic constant is a meaningful mathematical statement. However, the paper does not say what this changes for our understanding of acceleration. The exponent stays the same, the best guarantees within these families stay the same, and nothing is said about schedules outside these families.

The strongest reason to care is not mentioned at all. Grimmer, Shu, and Wang conjecture that OBS-F schedules are minimax optimal among all predetermined schedules (Section 3.2.2, Conjecture 1). If that conjecture is true, Theorem 5.1 would imply that the minimax rate of gradient descent itself has no single leading constant. That would be a much more striking statement than anything the paper currently claims. Stating it clearly, as a conditional result, would give the phase analysis the motivation it currently lacks.

I would also like a short discussion of related work on periodic fluctuations in divide-and-conquer recurrences (for example, Flajolet and Golin's analysis of mergesort, or Drmota and Szpankowski). This kind of oscillation is well known there. The paper should explain what is new in its setting, for example the nonlinear joining rule and the link to exact worst-case guarantees.

2. The asymmetric results are mostly qualitative. The asymmetric family has the better objective guarantee, and it is the one conjectured to be minimax optimal. Yet it gets a less complete treatment. Its optimal splits are not characterized the way the symmetric ones are. The convergence to the limiting profile comes from a compactness argument, so there is no rate. There is also no certified value for the limiting profile's extremes or for the size of the gap above the barrier. As a result, the finite-scale numbers in Figure 3 are illustrations, not certified estimates of the limit. None of this is an error in the proofs. These are open problems beyond what is claimed. But they limit how much the new asymptotic description tells us about constructing schedules or estimating their constants. This is the main reason my score is a weak accept rather than a clear accept.

Questions for authors

Questions that could change my assessment:

  1. Minimax interpretation. Could you state explicitly what your results would imply if OBS-F schedules are minimax optimal, as conjectured by Grimmer et al.? Please check that the schedule class and the normalization match the setting of that conjecture. More generally, what do you see as the main takeaway of the phase phenomenon for readers interested in stepsize acceleration?

  2. Quantitative asymmetric results. Can you give a convergence rate for the asymmetric interpolants, or a certified range for the limiting profile and the gap above the barrier? If not, which step of the compactness argument makes this hard?

  3. Characterizing the asymmetric profile. Is there a way to characterize the limiting asymmetric profile more directly, for example through some principle inherited from the finite recursion? Note that a plain limiting Bellman equation is not enough here. Letting the split fraction go to zero makes the equation hold trivially for any profile that satisfies the corresponding inequality, and scaling a solution up gives another solution. So such an equation cannot pick out the true profile on its own.

Clarification request:

  1. Scope of the Lean formalization. You report Lean proofs of some scalar and combinatorial results. Could you say exactly which parts of Theorems 4.1 and 5.1 are covered, and which parts rely only on the written proofs or on the imported certificate results from prior work?
2 comments

We thank the reviewer for the careful assessment and constructive questions, particularly those concerning the significance of the phase phenomenon and the characterization of the asymmetric profile. We address these points below and describe the corresponding additions to the manuscript.

Q1. Minimax interpretation and significance of the phase phenomenon

Conditional minimax implication. We thank the reviewer for pointing out this connection. We verified that Grimmer et al. (2025b, Conjecture 1) consider the same final-iterate objective-gap criterion and normalization, with minimax optimality taken over all predetermined stepsize schedules. Under their conjecture, our optimized OBS-F schedules would be globally minimax optimal. Theorem 5.1 would then imply that the minimax worst-case objective gap has a nonconstant log-periodic leading coefficient, even after optimizing the stepsizes separately at each horizon. In particular, the normalized minimax coefficients have multiple subsequential limits rather than a single asymptotic constant. We have added a statement of this conditional implication in the Introduction and a detailed formulation and derivation in Appendix E.10.

Main takeaway for stepsize acceleration. The key insight is that the Silver exponent characterizes the polynomial scale of acceleration, while the sharp leading coefficient retains a systematic dependence on the horizon's dyadic phase. This refines the usual convergence-rate description by showing that the exponent alone does not determine a universal leading constant. Moreover, this phase dependence persists in the asymmetric OBS-F family, where optimal splits can be unbalanced and exact dyadic scaling is absent. Since the objective guarantees are tight, the phase profiles capture genuine variations in worst-case performance. Although the numerical modulation is small, it reveals a persistent structural feature of optimized long-step acceleration that the convergence exponent alone cannot capture.

Q2. Quantitative asymmetric results

We agree that a convergence rate and certified extrema for the limiting asymmetric profile would strengthen its quantitative characterization.

Current theoretical and numerical results. Theorem 5.1 rigorously establishes

\le \frac{c_\star}{\phi_\star}.$$ The certified enclosure in Appendix also yields a numerical upper bound for $\max\Psi_F$. Figure 3 further provides a numerical illustration of the asymmetric phase through the finite-scale interpolant $\Psi_{18}$. An explicit quantitative lower bound for the strict gap $\min\Psi_F-c_\star$ and tighter certified bounds for the limiting extrema remain open. **Obstacle to a convergence rate.** Our proof combines monotone convergence along fixed dyadic rays with uniform Lipschitz control across phases. These yield uniform convergence through compactness, but provide no quantitative bound on the remaining error along each ray. Controlling this scale-wise error is the missing ingredient for an explicit convergence rate.

Q3. A more direct characterization of the limiting asymmetric profile

Thank you for this insightful question. We have derived a more direct characterization of the limiting asymmetric profile. Specifically, Theorem E.14 in our revised manuscript provides the representation

ΨF(t)=2ptW(2t),\Psi_F(t)=\frac{2^{pt}}{\mathcal W(2^t)},

where W(⋅)\mathcal W(\cdot) is explicitly defined by optimizing over finite ordered partitions of a continuous horizon using only the known symmetric phase Φ\Phi and the joining kernel AA. Importantly, this characterization determines ΨF\Psi_F without requiring the unknown profile as an input.

Furthermore, Theorem E.15 provides a complementary vanishing-discount characterization: each discounted Bellman problem has a unique fixed point, and these fixed points converge uniformly to ΨF−1/2\Psi_F^{-1/2} as the discount approaches one.

We have added a brief explanation in Section 5.2, with the complete statements and proofs in Appendix E.9.

Q4. Scope of the Lean formalization

We thank the reviewer for requesting this clarification. For Theorem 4.1, Lean verifies the exact identity UN=NpΦ(θN)U_N=N^p\Phi(\theta_N), the existence and uniqueness of the positive Lipschitz periodic profile, its nonconstancy, and 0<ϕ∗<1=max⁡Φ=Φ(0)0<\phi_*<1=\max\Phi=\Phi(0). For Theorem 5.1, it verifies uniform convergence of the dyadic interpolants to the unique positive Lipschitz periodic profile, the asymptotic expansion and cluster interval, and

c∗<min⁡ΨF<max⁡ΨF≤c∗/ϕ∗.c_*<\min\Psi_F<\max\Psi_F\le c_*/\phi_*.

The connection to gradient descent relies on the composition and tightness results from prior work recalled in Appendix A; these external certificate results are not included in our Lean formalization. For Theorem 4.1, these results translate the scalar phase law for UNU_N into the tight objective-gap guarantee in Corollary 4.2. For Theorem 5.1, these results justify interpreting 1/WN1/W_N as the optimized ConPD/OBS-F objective-gap coefficient ηNF\eta_N^F. The Lean formalization covers the scalar results, while their interpretation as tight GD guarantees is established through these certificate results.

Additional clarification: Related work on periodic fluctuations

We appreciate the suggestion to discuss periodic fluctuations in divide-and-conquer recurrences. Log-periodic behavior has been studied extensively: Flajolet and Golin (1994) analyzed log-periodic oscillations in mergesort; Drmota and Szpankowski (2013) developed a general asymptotic theory for discrete linear recurrences; and Hwang et al. (2024) established exact periodic identities for balanced linear recurrences and studied certain weighted-linear extremal recursions.

Our setting involves optimizing recursive GD schedules under nonlinear joining rules, where different groupings and split choices affect the outcome. We establish an exact phase law for the symmetric family and a limiting phase law for the asymmetric family, even when optimal splits are unbalanced. Importantly, these phase laws characterize tight worst-case objective-gap coefficients for gradient descent, giving the periodic phenomenon a direct optimization-theoretic interpretation. We have added a discussion of these connections and distinctions to the Introduction.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.