- 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 , 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 , 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 . 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 , 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 , 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 , where is constructed using only the smallest and largest eigenvalues of the Hessian matrix. However, in high dimensions, the evolution of 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 . 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 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 . 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 requires knowledge of both and . 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
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.
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:
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.