acceptodds
Under review as a conference paper at ICLR 2027

Gradient Methods with Chaotic-Inspired Step Sizes

Abstract

This paper investigates gradient methods with dynamically varying step sizes for convex quadratic optimization problems. We propose a family of step-size rules, named FC and FCA, motivated by the chaotic behavior of gradient iterations. The main theoretical contribution is a rigorous analysis of the two-dimensional convex quadratic setting. For this low-dimensional case, we derive closed-form characterizations of the iteration map and establish the stability properties of its fixed points under different parameter regimes. The emergence of chaotic dynamics is demonstrated numerically via positive Lyapunov exponents, initial sensitivity, and ergodicity, though a rigorous mathematical proof of chaos is not established in this work. The theoretical findings in two dimensions inspire the construction of the FC/FCA step-size schemes for high-dimensional problems. We conduct extensive numerical experiments on large-scale convex quadratic test problems with a wide range of condition numbers, including ill-conditioned cases. Our numerical results demonstrate the empirical performance of FC/FCA compared with classical gradient methods such as the BB and CBB step-size rules. We further state several conjectures regarding the high-dimensional dynamical behavior and iteration complexity of the proposed methods. Rigorous proofs for these high-dimensional claims remain open.

Primary area:
optimization
Keywords:
Cauchy steplength, Barzilai-Borwein method, chaotic dynamics, convex quadratic optimization, gradient methods

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_aEaGOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates gradient methods with dynamically varying step sizes for convex quadratic optimization. The authors introduce a family of chaotic-inspired step-size strategies, termed FC and FCA, motivated by the dynamical behavior of the reciprocal Cauchy step size. By introducing a relaxation parameter t>0t>0, the paper analyzes the resulting iteration dynamics and identifies different stability regimes for two-dimensional convex quadratic problems. The paper presents an interesting investigation of chaotic-inspired gradient methods for convex quadratic optimization. The two-dimensional dynamical analysis offers useful insights into the behavior of relaxed gradient iterations, and the numerical experiments demonstrate promising performance of the proposed FCA method on certain ill-conditioned problems.

Critical strengths

The main theoretical contribution is a characterization of the scalar rational iteration map in two dimensions, including its critical points, fixed points, and local stability properties. The authors further provide numerical evidence of chaotic behavior through positive Lyapunov exponents, sensitivity to initial conditions, and empirical ergodicity. Motivated by these observations, the paper develops FC and FCA algorithms for high-dimensional quadratic optimization using an approximate scalar mapping and periodic exact step-size evaluations.

The authors presented Interesting connection between dynamical systems and optimization. The paper explores how nontrivial dynamical behavior of adaptive step sizes may contribute to improved optimization performance. This perspective is potentially useful for understanding non-monotone gradient methods. The derivation of the rational iteration map and the investigation of its fixed points provide a useful framework for studying the dynamics of relaxed gradient methods on quadratic objectives. The authors additionally conjecture an iteration complexity of O(κlog⁡(1/ϵ))O(\sqrt{\kappa}\log(1/\epsilon)), although no rigorous high-dimensional complexity guarantee is established.

The author also conduct numerical experiments by comparing the proposed methods with classical gradient algorithms, including steepest descent, relaxed steepest descent, Barzilai–Borwein, and cyclic Barzilai–Borwein methods. The experiments indicate that FCA can outperform several classical gradient methods in iteration counts, particularly for ill-conditioned quadratic problems. For example, Table 1 reports 2,320 iterations for FCA compared with 10,267 for CBB when κ=105\kappa=10^5. The results suggest that FCA can achieve substantially fewer iterations on certain ill-conditioned quadratic problems.

Critical weaknesses

The major weakness of this submission is the limited theoretical guarantees for the proposed algorithms. The most significant limitation is the absence of rigorous convergence and complexity guarantees for the proposed high-dimensional FC and FCA algorithms. Although Section 3 establishes properties of a two-dimensional scalar iteration map, the actual algorithms in Section 4 operate in high-dimensional spaces and employ approximate step-size predictions. The two-dimensional analysis does not directly establish convergence of these algorithms. In particular, the paper conjectures the iteration complexity O(κlog⁡1ϵ)O(\sqrt{\kappa}\log\frac{1}{\epsilon}), but provides no rigorous justification for this accelerated rate. Moreover, the convergence argument in Appendix C applies to the exact relaxed steepest-descent iteration with step size 1/(trk)1/(tr_k), rather than the proposed algorithms incorporating approximate step sizes and safeguarding mechanisms.

Moreover, there is insufficient justification of the high-dimensional approximate mapping The proposed algorithms rely heavily on the approximation rk+1≈Gn(rk)r_{k+1}\approx G_n(r_k), where GnG_n is constructed using only the smallest and largest eigenvalues of the Hessian matrix. However, in high dimensions, the evolution of rkr_k depends on the entire spectral distribution and the corresponding gradient components. Therefore, the two-dimensional mapping does not generally characterize the high-dimensional dynamics. The paper conjectures that intermediate eigenmodes decay rapidly, effectively reducing the dynamics to a two-dimensional subspace. However, this claim is supported primarily by numerical observations rather than rigorous analysis. More importantly, the paper does not provide quantitative bounds on the approximation error ∣rk+1−Gn(rk)∣|r_{k+1}-G_n(r_k)|. Without such estimates, it is difficult to determine when the approximate mapping is reliable or how prediction errors affect convergence. The authors should provide either a theoretical error bound under suitable spectral assumptions or a systematic numerical investigation of prediction errors across different eigenvalue distributions.

Also the chaotic interpretation requires further theoretical justification. The paper identifies the regime t>1t>1 as a repelling or chaotic regime based on the instability of a fixed point and numerical observations. However, the instability of a fixed point does not, by itself, establish chaotic dynamics. Similarly, a numerically estimated positive Lyapunov exponent and apparent sensitivity to initial conditions are suggestive but do not constitute a rigorous characterization of chaos. The manuscript acknowledges this limitation, but several discussions still appear to treat chaotic behavior as a general property of the entire parameter regime t>1t>1. The authors should distinguish more carefully between local fixed-point instability, numerical evidence of chaos for specific parameter choices, and rigorously established chaotic behavior. Additionally, the manuscript should clarify whether the claimed ergodicity is supported by quantitative statistical tests or merely by the similarity of empirical histograms.

The numerical experimental evaluation is also insufficient. The experiments are conducted exclusively on synthetic convex quadratic optimization problems. Although such problems are appropriate for studying spectral properties, they provide limited evidence of practical effectiveness.

Finally, the practical implementation of the algorithm requires spectral information. The approximate mapping GnG_n requires knowledge of both λmax⁡\lambda_{\max} and λmin⁡\lambda_{\min}. For large-scale optimization problems, accurately computing these eigenvalues can be computationally expensive, especially when the Hessian is available only implicitly. The paper does not sufficiently discuss how these spectral quantities are obtained or whether their computational costs are included in the experiments. This requirement potentially limits the practical applicability of the proposed algorithms. The authors should investigate whether approximate eigenvalue estimates are sufficient and how estimation errors influence algorithmic stability and convergence.

Questions for authors

Since FCA effectively applies a squared gradient iteration matrix, how does its performance compare with two consecutive standard gradient steps when the total number of matrix-vector products is matched?

3 comments

I thank the reviewer for this balanced assessment. I respond to each comment below.

R3-Q1: FCA versus two consecutive standard gradient steps. While the FCA update structurally resembles two successive standard gradient steps, its core advantage stems from the step-size evaluation mechanism. Explicitly computing two steps (as in CBB) requires a step-size evaluation at every iteration. In contrast, FCA computes the exact r_k only l times per block of m iterations with l << m; for the remaining m-l iterates, r_k is predicted via the G-function at O(1) cost. This asynchronous scheme avoids expensive exact evaluations across most iterations. Combined with its inherent dynamical benefit, FCA achieves substantially lower wall-clock time (see R2-Q5) despite comparable iteration counts.

R3-Q2: Lack of rigorous guarantees for high-dimensional FC/FCA. Rigorous theoretical guarantees are established for the 2D setting. The O(sqrt(κ) log(1/ε)) complexity for high dimensions remains a conjecture, supported by the numerical evidence presented below.

R3-Q3: Inadequate justification of the high-dimensional approximate map. To address this concern, I run FC for 10,000 iterations with n = 10000 and t = 1.2, and record the error between the raw G-function prediction G(r_k) and the realized r_{k+1}. Since r spans four orders of magnitude, I adopt relative error for evaluation. The median absolute error is extremely small (approximately 0.00895). Over 93% of iterations yield relative error below 20%, and nearly 88% fall below 10%. These results demonstrate that within the chaotic regime t > 1, the one-dimensional map G(r) delivers high accuracy for the vast majority of iterates.

The sparse long tail (roughly 6.69% of iterations with relative error exceeding 20%) arises almost exclusively near the smallest eigenvalue a^(n) = λ_min, where the local derivative of G(r) becomes large. In contrast, the map is smooth near the largest eigenvalue and such anomalies do not emerge. Critically, these errors are isolated and self-correcting.

Clarification on the truncation rule: Although G-predictions are accurate in most cases, truncation is not designed to compensate for prediction errors. Instead, it handles the special dynamics near λ_min. Applying t > 1 at these points would excessively dilute the effective step size and slow convergence of the slowest eigenmode. Truncation reverts to the unscaled step, preserving progress for the slow mode and accelerating overall convergence.

R3-Q4: Chaotic interpretation and ergodicity. I will revise the manuscript to distinguish three levels of claims: (i) local instability (proven in Theorem 1); (ii) numerical evidence of chaos (Lyapunov exponent 0.4424, Proposition 3); and (iii) rigorous topological chaos (not established). The evidence for ergodicity is empirical, based on histogram similarity. Quantitative statistical testing of ergodicity is left for future work.

R3-Q5: Experiments limited to synthetic quadratics; spectral information. Extensions to non-quadratic problems are reserved for future research. Regarding spectral estimation:

  • λ_max is estimated using approximately 100 Hessian-free iterations with negligible overhead. Even under a budget of 1000 iterations, FCA remains faster than CBB.
  • λ_min is approximated via a lightweight Lanczos run. For the test case a_n = 1, a_1 = 10000, n = 10000, the minimum Ritz values are 1.67, 1.41 and 1.14 for m = 40, 80, 100, converging monotonically to the true value 1. This upper-bound estimate takes 0.5–0.75 seconds. A fraction of this estimate is used as the surrogate threshold for safeguarding, which reflects a deliberate trade-off between accuracy and computational cost.

The truncation rule in Section 4.1 adopts θ_low = 10, θ_high = 8333. It is triggered rarely and serves as a low-frequency safeguard. Threshold sensitivity analysis and ablation studies are deferred to future work.

The rebuttal solved some of the issues. I have raised the score to weak acceptance.

I thank the reviewer for the careful re-evaluation and for recognizing the clarifications provided in the rebuttal. I am also grateful for the time and effort spent on this review. I am glad that the additional content helped address several of the concerns.

Reviewer_KjQDOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes FC and FCA, two gradient methods with dynamic stepsizes inspired by chaotic iteration behavior, for positive definite quadratic optimization. It analyzes the associated scalar dynamics in two dimensions and uses these insights to construct stepsize predictors for higher dimensional problems. Experiments compare the proposed methods with classical gradient baselines, while the main claims about higher dimensional dynamics and iteration complexity remain conjectural.

Critical strengths

The paper has a clear overall structure and is easy to navigate.

Critical weaknesses

The paper would benefit from clearer writing and a stronger justification of its research focus. Although the proposed methods are motivated by the chaotic behavior of gradient iterations, the discussion does not sufficiently explain how this behavior informs the algorithm design or improves optimization. As a result, the terminology sometimes obscures rather than clarifies the underlying mechanism. Unresolved references also detract from the presentation. Finally, the theoretical proofs require more complete derivations and rigorous arguments to substantiate the stated results.

Questions for authors
  1. The novelty relative to existing adaptive and nonmonotone stepsize methods needs clearer justification. The setting is restricted to positive definite quadratic optimization, a well studied problem, and most references and experimental baselines are classical. Although a 2024 stepsize scheduling paper is cited, comparisons with recent methods are missing. Please clarify the methodological advance and include stronger contemporary baselines.

2.Page 4 contains an unresolved citation after “in the gradient-descent literature” and an unresolved equation reference in “Under equation ??.” The bibliography also contains malformed author names, including “Pablo Parrilo. Jason Altschuler” and “Uri Ascher Kees van den Doel.” These issues should be corrected throughout.

  1. Appendix A largely consists of brief statements such as “direct computation,” without providing the derivative calculations or detailed arguments. In particular, local fixed point stability does not by itself establish the global convergence of rkr_k asserted in Theorem 1. Please provide complete proofs and state any exceptional initial conditions. The high dimensional results are explicitly conjectural, leaving the guarantees for the proposed practical algorithms limited.

  2. The experimental protocol and computational comparisons need greater precision. Algorithm 1 permits additional exact evaluations through safeguard fallbacks, contradicting the claim that only ll exact evaluations occur per block. Runtime and matrix–vector product counts, including fallbacks and extremal eigenvalue estimation, should be reported. The random distributions, seeds, repeated trials, numerical precision, and iteration limits are also insufficiently specified. Finally, Table 1 marks BB as unsuccessful for n=10000n=10000 and κ=100000\kappa=100000, whereas Table 2 reports 28551 iterations for the same configuration. Please reconcile these results and justify the unusually strict stopping tolerance of 10−4010^{-40}.

Additional corrections:

Page 4, Eq. (14): Remove the stray kk in the denominator.

Page 6, Theorem 1: Remove the duplicated item “(i)” containing the placeholder “...”.

1 comment

I thank the reviewer for this exceptionally thorough reading, which has helped me pinpoint concrete issues to address in the revision.

R2-Q1: Novelty relative to adaptive/nonmonotone methods; missing contemporary baselines. Our methodological contribution shifts from chaos diagnosis (the 2012 work) toward predictive step-size design built upon the r_k map, equipped with built-in safeguards including two-sided truncation and periodic exact evaluation. Comparisons against recent step-size scheduling algorithms (including the cited 2024 reference) are reserved for future investigation, and we will clarify this conceptual distinction in Section 1.

R2-Q2: Editorial issues. All items have been corrected in the revised PDF: the broken citation on Page 4, unresolved equation references marked "Equation ??", bibliography author entries ("Pablo Parrilo, Jason Altschuler"; "Kees van den Doel, Uri Ascher"), the spurious denominator symbol in Eq. (14), and the duplicated "(i)" label in Theorem 1.

R2-Q3: Insufficient proofs in Appendix A; local stability versus global convergence. We agree that the proofs in Appendix A require more elaboration. To address this, we will supplement the appendix with the full step-by-step derivative calculations for the fixed-point stability analysis. Regarding global convergence: for any step size α_k satisfying the absolute stability bound 0 < α_k < 2/λ_max, the quadratic objective decreases strictly. Within our algorithm's normal operating regime, the effective step size is 1/(t r_k), which is bounded above by 1/(t λ_min) since r_k >= λ_min. When r_k approaches either boundary, the truncation rule reverts to the exact Cauchy step (or CBB step), which respects the stability bound 2/λ_max. Consequently, the objective sequence is globally monotonically decreasing and bounded below, ensuring convergence. Theorem 1 only establishes the local stability of the fixed-point map; global convergence arises separately from our step-size safeguards. We will clearly distinguish these two layers of guarantees in the revised manuscript.

R2-Q4: Algorithm 1 fallbacks; table inconsistencies; stopping tolerance.

  • Fallback mechanism: The original statement "only exact evaluations per block" was inaccurate. Algorithm 1 carries out l exact evaluations within each block and activates fallback steps whenever r_k falls outside [θ_low, θ_high]. Quantification of exact evaluation counts accounting for fallbacks is left for future work.
  • Table 1 vs. Table 2: The iteration counts of FC and CBB were swapped during transcription. Corrected values are consistent with Table 2. The iteration count of BB at κ = 10^5 is 28551; the "-" entry in Table 1 was a transcription omission. All table entries have been cross-checked against raw logs. After correction, FC requires roughly twice as many iterations as CBB, yet its lower overhead for step-size evaluation still yields competitive wall-clock time (see R2-Q5).
  • Stopping tolerance 10^{-40}: This stringent tolerance was selected to probe asymptotic behavior beyond the machine-precision plateau. We also have results obtained with tolerance 10^{-15}, which preserve the same performance ranking. A comprehensive sensitivity analysis is deferred to future work.

R2-Q5: Runtime and gradient evaluation counts. CPU timing results (omitted earlier due to page limits) are reported for n = 100000, κ = 100000, with random initial vectors and random spectra. Results are averaged over 10 independent runs under an iteration cap of 20000:

MethodIterationsTime (s)
SD2000016.98
RSD2000014.20
BB18573.412.30
CBB9345.48.85
FC17951.26.78
FCA9218.45.07

Gradient evaluation overhead: FC requires one gradient evaluation per iteration to compute g_k; FCA requires two gradient evaluations per iteration, for g_k and A g_k. Even though FCA doubles the per-iteration gradient cost, it achieves the shortest wall-clock time (5.07 s). This gain stems from substantially fewer total iterations (9218.4 versus 17951.2 for FC) and the avoidance of costly exact step-size evaluations for most iterations via G-function prediction.

Spectral estimation: The largest eigenvalue is estimated by a Hessian-free power iteration (around 100 iterations suffice in practice). Even under a conservative budget of 1000 iterations, the total runtime of FCA remains lower than that of CBB. We validate this estimator across three test configurations (a_1 = 10000, a_n = 1, n = 10000): uniformly spaced and random spectra paired with all-ones and random [0,1] initializations. The resulting estimates are approximately 4.5% below λ_max and stable across different spectral distributions. The threshold θ_high = 8333 does not rely on this eigenvalue estimate. Threshold sensitivity tests and ablation studies (FCA with and without truncation) are directions for future research.

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

This paper studies chaotic step-size dynamics in under-relaxed steepest descent methods for convex quadratic optimization. The authors analyze the iteration map of the reciprocal Cauchy steplength and its fixed-point stability in two dimensions. Motivated by this analysis, they propose FC and FCA methods for high-dimensional problems and evaluate them on synthetic quadratic problems.

Critical strengths
  • Investigating the relationship between chaotic dynamics and optimization performance is potentially interesting.
  • The experiments show promising performance on some ill-conditioned quadratic problems.
Critical weaknesses
  • Insufficient motivation and presentation: The paper does not clearly explain what is meant by chaotic step-size dynamics, why they are beneficial for optimization, or why the relaxation parameter tt is introduced. The motivation and main contributions could be explained more clearly, particularly at a conceptual level.

  • Limited novelty: Chaotic dynamics and acceleration in under-relaxed steepest descent have already been studied by van den Doel and Ascher (2012). The paper does not sufficiently distinguish its contributions from this prior work.

  • Limited theoretical contributions: The rigorous analysis is restricted to the two-dimensional setting, while the existence of chaos is supported only numerically and the high-dimensional acceleration and iteration complexity results remain conjectures.

  • Insufficient experiments: The experiments are restricted to synthetic convex quadratic problems with a limited set of baselines. More importantly, they do not clearly demonstrate the role of chaotic dynamics in the observed acceleration.

Questions for authors
  • What are the main contributions beyond van den Doel and Ascher (2012)?
3 comments

I thank the reviewer for the careful reading and for raising the important question of novelty relative to prior work.

R1-Q1: Main contributions beyond van den Doel and Ascher (2012)?

The 2012 paper leverages the Akaike-probability map (their Eq. 26) to diagnose chaotic dynamics in faster gradient descent, yet it does not develop any high-dimensional algorithm built upon this map. Our work investigates a distinct dynamical quantity: the reciprocal Cauchy steplength ratio r_k. Its associated scalar map G(r) (Eq. 16) directly yields a step-size predictor, which enables the proposed FC/FCA algorithms (Algorithm 1) — these algorithms are absent from the 2012 work. The comparison is summarized below:

Aspectvan den Doel & Ascher (2012)This work
Dynamical objectAkaike probability p_iReciprocal Cauchy steplength ratio r_k
Relaxation parameterSD(ω), ω in Akaike mapMultiplicative t on 1/r_k; bifurcation structure characterized in 2D
AlgorithmNot proposedFC/FCA: approximate map G_n + periodic exact evaluation + two-sided truncation
High-dimensional treatmentNot addressedConjectures + systematic numerical evidence (see R3-Q3)

Regarding the restriction of rigorous theory to 2D and the conjectural nature for high dimensions: The scope of our rigorous theory is explicitly stated in Lines 82–86: all theorems are established for the two-dimensional setting, while high-dimensional extensions are presented as conjectures. The 2D analysis is fully rigorous, and the high-dimensional conjectures are backed by systematic numerical evidence (R3-Q3). Extending this mechanism beyond quadratic objectives is left as ongoing future work.

Regarding experiments restricted to synthetic quadratic functions: Our current experiments focus on synthetic quadratic problems, which serve as a natural testbed for spectral-effect analysis. Extensions to non-quadratic problems, such as regularized logistic regression, are reserved for future investigation.

Thank you for the clarification and the additional numerical evidence. I better understand the differences from prior work, but my concern about the significance of the novelty remains, so I will keep my original assessment.

I thank the reviewer for acknowledging the clarified distinctions from prior work, and for the time and effort spent on this review.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.