acceptodds
Under review as a conference paper at ICLR 2027

Spectral Analysis of the Dynamics of Gradients and Updates

Abstract

Let and denote the sequences of gradient and update vectors. Each pair is recorded at the -th iteration of an optimization algorithm. For a deep neural network (DNN), these vectors may instead represent the full optimizer-visible state at the -th training step on input-label pair , including the gradients produced by backpropagating the prediction error. We study the spectral properties of and across a collection of convex optimization problems and DNNs, including convolutional neural networks (CNNs) and residual networks (ResNets). Our experiments show that the spectral energy of these histories is sharply concentrated in a small number of directions. Now, focusing only on optimization algorithms, for a given choice of descent such as Nesterov accelerated gradient descent (NAG), we define a corresponding Nesterov-Ramanujan descent in which vectors from the gradient and update histories are transformed according to Here, is a sparse mixing operator supported on a randomly directed, two-colored Ramanujan graph designed to be ergodic, rapidly mixing, and large-girth. Ordinary NAG corresponds to . At iteration , our update rule uses the histories and to determine a step size and then computes The intervention broadens the spectrum of at least one of the two histories. We use this spectral change to increase the step size through a safeguarded adaptive rule, which typically enables faster convergence in our experiments. Surprisingly, the update history is often more informative than the gradient history , even though classical momentum methods are usually formulated primarily in terms of gradients.

Primary area:
optimization
Keywords:
spectral collapse, gradient descent, nesterov, adam, ramanujan graphs

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_hiZHOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper analyzes how the spectral concentration happen along training in gradient optimizers. It shows update concentrates more often than gradient or momentum. It then proposes a more general algorithm class using LPS, and tested similar statistics.

Critical strengths

In my batch of reviews, this work stands out for being human. This is the only work I read where every notation follows a standard choice (e.g., g for gradient, u for update).

The different concentration behaviors between updates and gradients is unexpected to me. More studies can be interesting.

Critical weaknesses

I think this work is incomplete. It should be the start of interesting discoveries. Main questions remain not answered.

  1. Why do gradients and updates behave differently?
  2. When and why concetration is good for training or not desirable?
  3. Why use LPS but not other matrix to mix information?
  4. What about ADAM + ResNet ? How does diagonal / full preconditioning change results?

I would incline to accept because, though this work might not be accepted from past ICLR standards, it stands out this year when submissions seem to suffer from a great decline in quality.

Questions for authors

See weaknesses.

1 comment

Thank you for you helpful comments, we have fleshed out the manuscript. Addressing your questions:

Do gradients and updates behave differently? Not really. As noted in our Introduction, we can describe a broad class of descent algorithms in a Nesterov-inspired framework: at step m+1m+1, they compute a weighted version of gradients from the history GmG_m and use it to compute an update vector um+1u_{m+1}. The gradient history GmG_m can be empty or unavailable, yet one must compute um+1u_{m+1}. Both GTG_T and UTU_T typically have full algebraic rank. In terms of spectral representation, they again behave similarly: typically both have smaller effective rank and thus exhibit spectral collapse. Our starting point was the broad observation that signals in audio, video, and physical systems are often spectrally compact, and that algorithmic histories can exhibit analogous spectral compaction, as in the Tao–Candès versions of the restricted isometry property (RIP).

When concentration helps or hurts. During the iterations after spectral collapse occurs, the update vectors become smaller in magnitude and diffuse, which affects their learning rates. Intuitively, one can think of this in terms of an uncertainty theorem: localization of UTU_T in the frequency domain prevents localization in the space domain, making update vectors small in magnitude and directionally unlocalized or diffuse. So can we gain LR by fixing this spectral collapse? Experiments indicate Adam and its variants do catch this collapse and fix it, but with some delay. In addition, a smaller LR leads to a proportional reduction in convergence rate. We do not present experimental data or analysis directly on this Adam-related mechanism, but we show that RDLPS graphs whose spectral properties yield mixing (i.e., norm-reducing) properties fix this collapse and also lead to effective speedup. See the table attached in this response that was missing in the submitted version.

We experimentally verify the concentration properties of Mgood(κ)M_{\mathrm{good}}(\kappa). Mgood(κ)M_{\mathrm{good}}(\kappa) is defined in this response to replace C1 and C2 in the submission and address the caveat that they admittedly had only “limited experimental evidence”. Mgood(κ)M_{\mathrm{good}}(\kappa) is the number of good updates in the first κ\kappa steps that improve the reciprocal gap Γi=1/Δi\Gamma_i=1/\Delta_i by at least some fixed b>0b > 0, where Δi=f(xi)−fmin⁡\Delta_i=f(x_i)-f_{\min}. Concentration can be benign when the dominant directions contain the displacement needed to reach the target and have favorable curvature. It is obstructive only relative to the target and the actual trajectory's useful motion. But this is hard to characterize, measure, or detect for a general loss function, especially when provided as a black box or a deep circuit. It is desirable to have a provable algorithm under some robust hypothesis. Concentration is a ubiquitous phenomenon.

Why LPS rather than another matrix. LPS is a sparse Ramanujan graph (i.e., it has an optimal spectral gap for a given degree dd), and the ERH graphs in the submission are almost Ramanujan. So are random dd-regular graphs, but they have small girth, whereas LPS graphs have precise bounds on girth and clique sizes. We construct randomly directed multigraphs colored with two colors that have no sources or sinks and can be used to construct circuits in lieu of DNNs. The cut-set balance properties and small diameter emerging from the spectral-gap property help balance the flow of gradient information across the network, whereas in a DNN it is constrained to adjacent layers. The lower bound on the girth ensures this flow does not bounce back in a few steps. We tested all kinds of variants of the reference RDLPS construction from LPS in the early part of the paper; this led to inconsistent and confusing descriptions of our graphs in the submission, as Reviewer 1 observed. In our experiments, we could not get sparse random regular graphs to work so well. In our limited experiments, large cliques lead to instability under mild perturbations of input training data. Recent literature aims at keeping graphs of connections sparse.

Adam, ResNet, and preconditioning. The submission documents spectral-collapse studies across DNNs and CNNs, including ResNet models, and across optimizer families, including Adam and its variants. These spectral studies do not constitute a matched Adam-plus-ResNet speedup study. Adam's adaptive diagonal scaling changes the relationship between gradient and update histories and can change their spectral energy distributions. A fixed invertible preconditioner preserves algebraic rank but need not preserve effective rank; for adaptive diagonal or full preconditioning, we make no universal monotonic claim about spectral concentration. A matched Adam-plus-ResNet speedup study, analogous to the convex ladder, remains necessary; the existing spectral-collapse measurements do not establish that result.

Reviewer_oJvFOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates the spectral properties of gradient and update histories during optimization. The authors report that these histories often exhibit strong spectral energy concentration, even when their numerical rank remains high. To quantify this phenomenon, they employ effective spectral rank and energy-coverage rank as diagnostic measures.

Motivated by these observations, the authors propose Nesterov–Ramanujan Descent (NRD), which modifies Nesterov accelerated gradient descent by applying sparse graph-based transformations to the momentum updates. The graph operators are constructed from directed variants of Ramanujan graphs and are intended to redistribute information across parameter coordinates. The paper also develops theoretical results concerning graph mixing, trajectory subspaces, and conditional convergence advantages.

Experiments on several convex optimization problems show increases in the effective spectral rank of gradient and update histories after applying the proposed method. Additional experiments on neural networks, including ResNet-18, provide evidence of spectral concentration in conventional optimizer trajectories.

Critical strengths

The distinction between gradient histories and realized update histories is potentially useful. The empirical observations suggest that the spectral concentration of these two histories can differ substantially, particularly for momentum-based optimizers. This provides motivation for investigating update histories as additional information about optimization dynamics.

The proposed NRD method introduces an interesting connection between accelerated optimization and sparse graph mixing. The accompanying analysis of directed mixing operators and trajectory subspaces provides a theoretical framework for understanding possible effects of the intervention.

Critical weaknesses

The paper motivates the proposed method through spectral concentration and reports improvements in effective spectral rank across several convex optimization problems. However, an increase in effective spectral rank does not necessarily imply faster convergence or better optimization performance.

Questions for authors

Under what conditions does the proposed graph transformation guarantee improvements in the relevant trajectory-subspace geometry? Can the authors clarify how the conditional assumptions in Appendix E relate to the actual NRD trajectories used in the experiments?

1 comment
AuthorsOpenReview ↗

Response to Reviewer

Thank you for you helpful response. We have made significant changes to the manuscript, and may also see our comments to the other reviewers for additional context. Addressing your questions:

Under what conditions does the proposed graph transformation guarantee improvements in the relevant trajectory-subspace geometry?

As for fixing the spectral collapse, the theorem on Mixing on Directed Multigraphs guarantees this will always happen. We have confirmed this in our experiments for convex examples and the CNN/DNN/ResNet/Adam study. This spectral fixing alone may not be sufficient to get speedups, as the table in this response for Reviewer 1 shows. The Mixing theorem there shows the norm reduction we need.

There are two central issues here: how should spectral collapse be measured, and what formal properties are needed? For a formal measure of spectral collapse, we propose an entropy-based measure. For example, GTG_T and UTU_T may have 30 dominant spectral components (e.g., singular values from the SVD of the matrices GTG_T and UTU_T) having a prescribed amount of energy, say 95%. But it may be that the first 5 components have 94% of the energy and the remaining 25 may have equally distributed energies, in which case the effective spectral rank is 5. Secondly, the definition must be such that if we improve the spectral collapse, it will imply that convergence will improve. The best we have for that is that our tables show improvements in spectral collapse, and our RDLPS-based algorithm has speedups, as we show in the table in Reviewer 1's response.

How do the assumptions in Appendix E relate to the actual NRD trajectories used in the experiments? We recall the mathematical quantities behind these assumptions. For a specified trajectory subspace SS and initial point x0x_0, the minimum objective gap attainable in the trajectory subspace is defined by restricting xx to the affine space x0+Sx_0+S:

ΔS=min⁡x∈x0+Sf(x)−fmin⁡.\Delta_S=\min_{x\in x_0+S}f(x)-f_{\min}.

Here fmin⁡f_{\min} is the global minimum objective value. This quantity measures what objective values the subspace permits; it does not specify how quickly an algorithm reaches them. The idea is that if SS is restricted for the baseline algorithm and better after a spectral collapse fix, we can see improvements in convergence rates.

As we detailed in our response to Reviewer 1, we define Mgood(κ)M_{\mathrm{good}}(\kappa) as a quantity that can serve experimentally and analytically as a better replacement for C1 and C2 while keeping the algorithm and tables on spectral collapse/improvements in the submission unchanged. And we have now detailed how the experimental and analytical claims work.

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

The paper observes that the gradient history GTG_T and the update history UTU_T of optimization algorithms are concentrated in a few spectral directions ("spectral collapse"). Measuring this with the effective rank D1D_1, the authors report it on convex problems optimized with Nesterov accelerated gradient (NAG) and on small DNN training runs (MLPs and ResNet-18), with the update history of momentum methods being especially concentrated.

To counter this concentration, the authors propose Nesterov–Ramanujan Descent (NRD), which multiplies the momentum in NAG by a sparse doubly stochastic operator. The operator is built from a randomly oriented, two-colored LPS Ramanujan graph (RDLPS) whose vertices correspond to parameter coordinates, and the two colors alternate across iterations. Combined with an adaptive step-size controller, NRD increases D1D_1 of both histories relative to NAG on the convex problems. Theoretically, the paper bounds the mixing of products of directed doubly stochastic operators, shows that routing preserves the stationary points, and gives conditional results under which the routed trajectory leads to faster convergence.

Critical strengths
  1. A different perspective on optimization dynamics. The paper studies optimization through the spectral structure of the realized gradient and update histories, treating them as quantities that can be diagnosed and potentially intervened on, rather than only as by-products of training. In particular, it separates the gradient history from the update history, observes that the latter is much more concentrated for momentum methods, and explores routing the momentum through expander-graph operators as a way to influence this structure. This perspective connects the analysis of optimization dynamics with tools from spectral graph theory in an interesting way.

  2. Careful spectral diagnostics and explicit acknowledgement of limitations. The paper distinguishes numerical rank, the effective rank D1D_1 and the energy rank r90r_{90}, and Appendix A explains with examples why D1D_1 is more sensitive to gradual redistribution of energy. The authors also state openly that spectral concentration is not necessarily harmful, that the acceleration results in Appendix E are conditional, and that the experiments should be read as heuristic. I appreciate this candor, as it helps readers judge what the paper does and does not establish.

Critical weaknesses
  1. The evidence for faster convergence seems limited. The abstract and contributions state that NRD allows larger step sizes and typically converges in fewer iterations. However, I was not able to find objective gaps, iteration counts or gradient-evaluation counts in the paper; Table 1 and Fig. 2 report the effective rank D1D_1 of the histories. The changes in D1D_1 appear modest (the mean over all problems goes from 1.399 to 1.496 for GTG_T and from 1.427 to 1.600 for UTU_T, in dimension 2,184), and, as the paper itself notes, a higher D1D_1 does not by itself imply better optimization. The acceleration results in Appendix E rely on Assumptions C1 and C2, which, as I understand them, assume that the routed subspace is better and that the actual iterates follow the projected ones; these do not appear to be verified, and the paper notes that a convergence certificate for the controller has not yet been established. It is also not fully clear to me whether the "Original NAG" baseline uses the same adaptive controller, which makes it difficult to separate the effect of routing from that of the controller.

  2. The description of the graph construction appears to be inconsistent. Section 3 builds each color as an acyclic orientation and then applies Sinkhorn balancing to obtain a doubly stochastic matrix with the same support. If I read this correctly, such a matrix cannot exist: by the Birkhoff–von Neumann theorem, the support of a doubly stochastic matrix must contain a permutation, while the adjacency matrix of an acyclic orientation can be permuted into strictly upper-triangular form and contains none. Fig. 1 describes each color as strongly connected with directed girth five, and Appendix B uses a different construction based on Euler circuits, so I suspect that the Appendix B construction is the one used in the experiments. Relatedly, contribution 3 states that rapid mixing is shown for RDLPS, whereas the uniform-gap condition of Theorem C.2 seems to be verified only for the unaugmented LPS graph with uniform weights, with the operators actually used supported by a numerical check on a single instance (Appendix C.1).

  3. The rationale and scope of the method could be explained further. The routing operator mixes momentum coordinates according to a random graph whose vertices are the parameter coordinates, so the number of vertices needs to match the problem dimension (n=d=2,184n=d=2{,}184 in the experiments; Appendix B notes that GRH-based expanders allow more flexible sizes), and the mixing does not appear to be related to the structure of the objective. For the diagonal quadratics in the convex ladder, it couples coordinates that are independent in the problem. I could not find an explanation of why this should help, and NRD does not seem to be applied to a DNN. The DNN observations may also be partly expected, since the update history of a momentum method is an exponentially smoothed gradient history, and low-dimensional gradient and trajectory subspaces have been reported before (e.g., Gur-Ari et al., 2018; Li et al., 2018; 2023).

  4. The writing is hard to follow. Even after several readings, I found it difficult to fully reconstruct what the method does and what is being compared. The opening description of the histories in the abstract is hard to parse, and the key fact that the routing operator acts on parameter coordinates appears only in Appendix C.1. Several terms are not defined, such as "shadow safeguard", "authenticated NAG bank", "registered magnitude and bank-membership checks", "transaction", "sealed operators" and "provenance-hash and replay gates". The adaptive controller is described in a single dense paragraph without pseudocode, the descriptions of the graph construction in Section 3 and Appendix B differ, and Appendix D.5 refers to a held-out experiment "reported below" that I could not find. I believe addressing these points would make the contribution considerably easier to assess and reproduce.

References

[1] Guy Gur-Ari, Daniel A. Roberts, and Ethan Dyer. Gradient descent happens in a tiny subspace. 2018.

[2] Chunyuan Li, Heerad Farkhoor, Rosanne Liu, and Jason Yosinski. Measuring the intrinsic dimension of objective landscapes. 2018.

[3] Tao Li, Lei Tan, Zhehao Huang, Qinghua Tao, Yipeng Liu, and Xiaolin Huang. Low dimensional trajectory hypothesis is true: DNNs can be trained in tiny subspaces.2023.

Questions for authors

I would appreciate it if the authors could clarify the points raised in the weaknesses, in particular which graph construction is used in the experiments, how the "Original NAG" and "Adaptive + shadow RDLPS" runs in Table 1 are defined, and whether NRD converges faster in terms of objective value.

If these points can be clarified and supported with evidence, I would be glad to reconsider my assessment.

6 comments

Dear authors,

I would appreciate a response to my review. If my main concerns are addressed, I will consider raising my score; if they remain unaddressed at the end of the discussion period, I will have to maintain my current score.

We thank the reviewer for the detailed response and constructive comments. We have modified the manuscript such as revamping the appendix, adding results to the main paper etc. We also list the main changes here with respect to your concerns.

We apologize for the oversight in not including an explicit iteration-speedup table alongside the spectral results. Our emphasis was on documenting spectral concentration in the gradient and update histories, GTG_T and UTU_T, across a broad range of optimizers and CNN/DNN architectures, and formalizing a new entropy-based measure for the spectral collapse. We proposed a randomized directed version of LPS Ramanujan graphs whose adjacency matrix acts on the optimizer vectors that generate the histories GTG_T and UTU_T, and compared it with the unaltered original baseline algorithm (i.e., one that uses an identity matrix). We also intended to keep optimization guarantees conditional on explicit mathematical assumptions that can be experimentally verified and under which we can prove convergence and speedups.

Recall that we measure convergence speed here by the number of complete iterations needed to reach the same target. The cost of per-step operations can vary widely across different and rapidly changing machine architectures, so we believe this is a reasonable first measure. The table makes the observed convex optimization improvements explicit without changing the algorithms. It does not extend those improvements to the neural-network experiments.

We replace C1 and C2 in the revised convergence argument with a criterion based on actual reciprocal-gap progress. At complete-iteration index ii, let Δi=f(xi)−f⋆\Delta_i=f(x_i)-f^\star and, for Δi>0\Delta_i > 0, let Γi=1/Δi\Gamma_i=1/\Delta_i. Fix b>0b > 0 and count iteration ii as good when Δi+1>0\Delta_{i+1} > 0 and Γi+1−Γi≥b\Gamma_{i+1}-\Gamma_i\ge b. Then Mgood(κ)M_{\mathrm{good}}(\kappa) is the number of good iterations among the first κ\kappa. Under nonincreasing objective gaps, concentration of Mgood(κ)M_{\mathrm{good}}(\kappa) near κ\kappa yields the stated reciprocal-gap convergence bound; a speedup comparison additionally requires that the baseline has not reached the target (see “Proof of speedup” below). We do not change the algorithms or spectral-concentration tables in the submission; we sharpen the criterion to make progress experimentally measurable and to support a conditional proof.

Relation to earlier work. Reciprocal-gap analysis has precedent; we do not claim that the reciprocal gap itself is new. Cartis and Scheinberg [1] explicitly use 1/(f(xk)−f⋆)1/(f(x_k)-f^\star) in their convex analysis and prove a lower bound on its increase at true, successful iterations. Concentration of integer-valued iteration counts also has precedents. Jin, Scheinberg, and Xie [2] use indicator sums for true and good iterations and exponential lower-tail bounds, based on the Azuma–Hoeffding inequality [3], to obtain high-probability iteration-complexity bounds. Here we define good iterations directly by a fixed reciprocal-gap increment and formulate the convergence condition through concentration of Mgood(κ)M_{\mathrm{good}}(\kappa) near κ\kappa, with an explicit deficit δ\delta. This provides a single count for the stated conditional convergence argument and its experimental measurements.

Scope of concentration claims. All concentration claims in this submission are experimental, covering the convex ladder and the CNN, DNN, and ResNet experiments. We have a proof for a more general class of objectives ff, but that proof is not part of this submission.

Observed iteration speedups. We consider a relative objective-error target 0.01 i.e. (f(x)−f⋆)/(f(x0)−f⋆)≤0.01(f(x)-f^\star)/(f(x_0)-f^\star)\le 0.01: the remaining objective gap is at most 1% of its initial value, a reduction of at least 99%. Speedup is original NAG's iteration (to reach the target) divided by the adaptive method's iteration.

Table 2 (abridged). Median iterations to the target, for the 8 of 14 settings where both methods hit in all ten runs. The full table is in the revised manuscript.

ProblemCond.NAGAdaptiveSpeedup
Clustered spectrum10210^238.5123.17x
10410^4522.50x
10610^6522.50x
Geometric spectrum10210^246143.29x
10410^481243.33x
10610^677233.39x
Ill-conditioned least squares5002893.24x
Random QQ10210^2146433.40x

Note on the methods. Original NAG is standard Nesterov momentum: it uses no graph and keeps one fixed step size, ρ/L\rho/L with ρ=0.125\rho=0.125. The fixed graph shadow is a separate run that passes momentum through the graph, also at fixed ρ=0.125\rho=0.125. The adaptive method (“Adaptive + shadow RDLPS” in the submission) starts at ρ=0.125\rho=0.125. At each iteration it tries candidate steps with different step sizes and amounts of graph mixing, and keeps the one with the lowest objective value. The revised manuscript has more details.

Reciprocal-gap interpretation and convergence proof. Fix b>0b > 0 across the run and assume every iteration is nonincreasing in objective value, including iterations not counted as good. If zero gap is reached, stop the count and keep the iterate at the optimum; no reciprocal at zero is needed.

Theorem 5.1 (Convergence from concentration of good updates). Let Δ0>0\Delta_0 > 0. Assume that Mgood(K)M_{\mathrm{good}}(K) is concentrated in [K−s,K][K-s,K]: for a deficit 0≤s<K0\le s < K and failure probability 0<δ<10 < \delta < 1,

P{K−s≤Mgood(K)≤K}≥1−δ.\mathbb P\{K-s\le M_{\mathrm{good}}(K)\le K\}\ge1-\delta.

Then, with probability at least 1−δ1-\delta,

ΔK≤Δ01+bΔ0(K−s).\Delta_K\le \frac{\Delta_0} {1+b\Delta_0(K-s)}.

If, for every δ\delta, this concentration holds for all sufficiently large KK with a fixed deficit ss (which may depend on δ\delta), then ΔK→0\Delta_K\to0 in probability, with a fixed-confidence O(1/K)O(1/K) bound.

Proof. If the optimum has been reached, the bound is immediate. Otherwise all gaps through KK are positive. Every reciprocal increment is nonnegative, and each good iteration contributes at least bb. On the concentration event,

1ΔK=1Δ0+∑i=0K−1(Γi+1−Γi)≥1Δ0+bMgood(K)≥1Δ0+b(K−s).\frac{1}{\Delta_K} =\frac{1}{\Delta_0}+\sum_{i=0}^{K-1}(\Gamma_{i+1}-\Gamma_i) \ge\frac{1}{\Delta_0}+bM_{\mathrm{good}}(K) \ge\frac{1}{\Delta_0}+b(K-s).

Taking reciprocals proves the bound. For fixed ss, its right-hand side tends to zero at rate O(1/K)O(1/K); since δ\delta can be arbitrarily small, this gives convergence in probability. No independence of successive iterations is needed. □\square

Proof of speedup

Since the optimum is not achieved at step 0, we have Δ0>0\Delta_0 > 0, and we fix some 0<ε<Δ00 < \varepsilon < \Delta_0. Compare the analyzed method with the unaltered baseline on the same objective and starting point, counting complete two-step iterations for both. Write ΔiB=f(xiB)−f⋆\Delta_i^B=f(x_i^B)-f^\star for the baseline gap and define the first hitting times

TR(ε)=inf⁡{i≥0:Δi≤ε},TB(ε)=inf⁡{i≥0:ΔiB≤ε},T_R(\varepsilon)=\inf\{i\ge0:\Delta_i\le\varepsilon\}, \qquad T_B(\varepsilon)=\inf\{i\ge0:\Delta_i^B\le\varepsilon\},

with inf⁡∅=∞\inf\varnothing=\infty.

Additional assumption (baseline nonhit). For a fixed integer L≥K≥1L\ge K\ge1, assume that the baseline's objective gap remains strictly greater than ε\varepsilon at every iteration up to and including LL:

ΔiB>εfor all i=0,…,L.\Delta_i^B > \varepsilon\qquad\text{for all }i=0,\ldots,L.

Since L≥KL\ge K, reaching the target by KK therefore gives our method a strict iteration advantage.

This is a lower bound on the baseline's first hitting time, not an upper convergence bound. It must be established separately; concentration of MgoodM_{\mathrm{good}} does not imply it.

We need not require ΔiB>ε\Delta_i^B > \varepsilon for every i≤Li\le L on every run. An average-case version, in which the baseline remains above the target through LL with high probability, also suffices with a corresponding adjustment to the speedup probability, but we omit it here.

Evidence from Table 2. The full Table 2 in the revised manuscript provides direct empirical evidence for this additional assumption on the reported runs, at the target ε=0.01Δ0\varepsilon=0.01\Delta_0. In the 95 cases where both methods finish, our method reaches the target before the baseline, so taking K=TR(ε)K=T_R(\varepsilon) and L=TB(ε)−1L=T_B(\varepsilon)-1 verifies L≥KL\ge K and the baseline nonhit condition. For example, on the random quadratic with one seed, our method first hits at iteration 45 and original NAG at iteration 153; hence the baseline remains strictly above the target through L=152L=152, while our method hits by K=45K=45. In 30 further cases, our method finishes by iteration 256 while the baseline does not, verifying the same condition with L=256L=256. The 15 cases where neither method finishes do not establish a speedup. Table 2 verifies the baseline nonhit condition for the measured runs. Evidence concerning concentration of MgoodM_{\mathrm{good}} for neural networks is presented separately in Figure 1 of the revised manuscript. The lemma combines these conditions with the sufficient-count inequality below.

Lemma 5.2 (Conditional iteration speedup). Under the preceding convergence theorem's assumptions and the baseline nonhit assumption, suppose

K−s≥⌈ε−1−Δ0−1b⌉.K-s\ge \left\lceil\frac{\varepsilon^{-1}-\Delta_0^{-1}}{b}\right\rceil.

Then

P{TR(ε)≤K≤L<TB(ε)}≥1−δ.\mathbb P\{T_R(\varepsilon)\le K\le L < T_B(\varepsilon)\} \ge1-\delta.

On this event the analyzed method reaches the target strictly earlier. If the baseline eventually reaches the target, its iteration speedup factor satisfies

TB(ε)TR(ε)≥L+1K>1.\frac{T_B(\varepsilon)}{T_R(\varepsilon)} \ge\frac{L+1}{K} > 1.

The proof is in Appendix F of the revised manuscript.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.