acceptodds
Under review as a conference paper at ICLR 2027

A Second-Order Complexity Theory for Spectral Optimization

Abstract

Neural-network training combines approximate gradients with approximate update computations. Recent advances in spectral optimization, including Muon for large-scale training, make the balance between computational cost and update accuracy especially important. How much gradient information and arithmetic accuracy suffice to preserve optimization progress? We address this question using second-order complexity theory, which accounts for the requested accuracy and the cost of reading and processing gradient approximations. We measure spectral update quality by the shortfall in linearized descent relative to the best direction under the same spectral-norm constraint. This criterion weights weak gradient components by their small contribution to descent, even when their normalized directions are sensitive to error. We establish the exact minimax tradeoff between update sensitivity, uncertainty, and descent, attained by spectral clipping calibrated to a gradient-error bound and a supplied rank bound. On a normalized gradient class, we determine the input precision required for a target descent tolerance to within one bit. A certified matrix-multiplication algorithm achieves the guarantee in second-order polynomial bit time, uniformly across rank changes. For smooth nonconvex objectives, these local guarantees yield stationarity bounds that separate gradient uncertainty from implementation error and have optimal uncertainty dependence. These results quantify, in precise mathematical terms, how accurately gradients and updates need to be computed to preserve optimization progress, providing a complexity-theoretic framework for understanding when spectral optimization methods remain computationally feasible at high precision.

Primary area:
optimization
Keywords:
spectral optimization, second-order complexity, gradient uncertainty, spectral clipping, minimax optimality, finite-precision computation, nonconvex optimization

Reviews

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

The paper provides a theoretical study of spectral optimization techniques via algorithms such as Muon and related methods. The paper aims to establish descent guarantees for different variants of spectrally regularized gradient updates. In particular, the authors show that a properly calibrated "spectral clipping" procedure attains the optimal descent in their problem formulation. They also provide an efficient approximate implementation of spectral clipping, and study the effect of finite precision and gradient approximation on the descent guarantees.

Critical strengths

The early observations of the paper (Theorem 1 and Corollary 2), comparing calibrated clipping and the polar factor, are interesting.

Also, the authors give an algorithm for implementing spectral clipping in the matrix-vector query model (Lemma 5 and Appendix D), which seems interesting.

Critical weaknesses

The paper becomes progressively more and more difficult to follow as it goes on, with more and more results and notations being introduced.

I found the finite-precision model somewhat confusing and not particularly helpful. I think I would have preferred if the paper spent more time on discussing the implementation of calibrated clipping, instead of relegating it to the appendix (I'm not sure whether this is a significant novelty of the paper, or if similar constructions appeared in prior works).

Not sure what was the point of some of the later results, such as for example why do you introduce the "fractional family" in section 5, if you already have an "optimal" clipping procedure.

It was not immediately clear to me how Section 4 fits with the remainder of the paper. I see the point of obtaining broader optimization guarantees from the rest of the theory, but I just didn't get how it fits together.

Questions for authors

See the weaknesses section.

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

This paper studies how gradient uncertainty and computational precision affect spectral update directions. It establishes an exact minimax tradeoff between update sensitivity, uncertainty, and linearized descent loss, attained by calibrated spectral clipping. It also derives nearly matching input precision bounds and provides a certified implementation based on matrix multiplication.

Critical strengths

The paper addresses an interesting question about how gradient uncertainty and computational precision affect the quality of spectral update directions. The manuscript is clearly structured, with a coherent progression from local descent guarantees to precision requirements and optimization results.

Critical weaknesses

The connection between the theoretical results and practical optimization could be strengthened. Some numerical illustrations or further discussion of their practical implications would help clarify the relevance of the guarantees.

Questions for authors
  1. The calibration relies on a supplied gradient error bound and rank information. Although the paper discusses uncertainty budgets and approximate low rank, could the authors clarify how these quantities can be estimated in practice and how inaccurate estimates affect the guarantees?

  2. Please clarify how representative this procedure is of practical spectral optimizers and distinguish this separation from a broader advantage over alternative update computations.

  3. Could the authors clarify the practical implications of the bit complexity guarantees, particularly the required working precision, memory overhead from symmetric dilation, and computational cost relative to standard SVD or Newton–Schulz implementations?

  4. While extensive experiments may be beyond the scope of this theoretical work, a small numerical illustration of the tradeoff between precision and descent quality, particularly near rank changes, would help clarify the practical relevance of the guarantees.

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

The paper theoretically studies gradient spectral optimization with the aim of understanding how gradient uncertainty and update accuracy influence the optimization performance and convergence. The main quantity considered, dubbed descent shortfall, is the difference between the linearized descent of the selected update and optimal update under operator norm constraint. The authors proceed to prove that an optimally tuned spectral clipping of the approximate gradient achieves the minimax bound of this shortfall quantity, and they give approximation error bounds on the gradients needed to achieve certain shortfall. They also provide bounds on the average nuclear gradient norm, as an indicator of convergence, that depend on gradient quality, update accuracy and the number of iterations, and provide finite approximation complexity guarantees.

Critical strengths
  1. The theory works seems solid and well founded. In particular, the proofs seem to be correct and statements support main theoretical contributions of the paper.

  2. I find the topic of analyzing gradient uncertainty and update accuracy timely. Moreover, I find especially interesting the matching of the lower bounds coming from the optimal spectral clipping. The results seem promising and I find evidence motivating further exploration.

Critical weaknesses
  1. Even though I mentioned the main theoretical results relating to spectral clipping as promising, I believe that the main question of how gradient uncertainty and update accuracy influence the optimization to be also a practical one. Thus, I believe it is important to check how the proposed theory optimal spectral clipping, under the estimated rank and gradient approximation bounds, would perform empirically. More broadly, I find important understanding how the insights about theory derived gradient uncertainty and update accuracy influence translate to a practical setting, and whether it can inform practical method design. Without any supporting evidence, it is hard to asses practical relevance of these results.

  2. The presentation is a bit dense and there is use of jargon, as well as abrupt mentioning of not defined quantities (e.g. what the decision loss considered is and smoothness parameter β\beta which is only formally introduced later). This makes following arguments and main results more challenging.

Questions for authors
  1. My main question is related to the potential practical consequences of this work. Namely, how would you expect the derived theoretical insights, relating to resource allocation between improving gradient certainty and update accuracy, to translate to a more practical setting in neural network training?

  2. How do you expect that, under the estimated rank and gradient approximation bounds, theory informed optimal spectral clipping method would perform compared to other spectral optimizers, e.g. Muon? Even though the spectral clipping is not the explicitly proposed contribution of the paper, it is used as an algorithm that matches all the theory lower bounds. Thus, I think understanding its practical relevance can give better indication of the practical implications of the theory itself.

Comments on the paper

1 comment

Dear Reviewers,

As the rebuttal deadline is approaching, please review the authors' responses and participate in the discussion. Kindly indicate whether your concerns have been addressed and update your scores if appropriate.

Thank you for your time and effort!

Best regards,
--AC

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.