When gradient descent stalls because the gradient is nearly zero, the optimizer faces a binary question. It may be sitting on a saddle point, where some direction still leads downhill. Or it may have reached a true local minimum, where it should stop. Current escape methods answer this with one fixed test. They inject a single random kick, or run one fixed-length routine that hunts for a downhill direction, and then wait a preset number of steps to see whether the loss drops. We propose to replace that single test with a small race. Several cheap, different "probes" start from the stalled point, and a budget-allocation rule from the multi-armed bandit literature decides which probes keep receiving gradient steps. That rule treats each probe as a slot machine and repeatedly gives more pulls to the ones that look most promising. The race ends in one of two ways. Either one probe has clearly found an escape direction and becomes the new iterate, or every probe has been ruled out with stated confidence and the point is certified as a local minimum.
This matters because the two failure modes of today's methods pull in opposite directions. Random isotropic kicks, meaning noise spread equally in every direction, carry only $O(1/d)$ of their variance along the escape direction in $d$ dimensions, and they degrade empirically as $d$ grows. Structured first-order routines escape better, but they spend a statically tuned number of steps no matter what the local geometry looks like. Treating the stall as a short, self-contained pure-exploration problem gives a principled way to spend gradient evaluations where they are informative, and to stop spending them when nothing is there.
Core Claim
The obvious way to combine bandits with saddle escape is to put a bandit over escape operators across the whole training run. That design runs into the problem the file flags as open. The landscape keeps changing as the iterate moves through descent corridors, saddle neighborhoods, and convex basins (Symmetry, Saddle Points, and Global Geometry of Nonconvex Matrix Factorization), so the rewards are non-stationary and regret theory does not apply cleanly. Our key observation is that during a stall the base point $x$ is frozen. Every probe launched from $x$ is therefore an arm whose reward distribution is stationary for the length of the race. The stall becomes a thresholding bandit problem: decide whether any arm's mean exceeds a threshold, and if so, find one such arm.
The second ingredient is the choice of reward. Escape along negative curvature grows exponentially, so the loss decrease of a probe is nearly zero for most of its early steps. Ranking probes by early loss decrease would prune the correct one. We instead score each probe $k$ after $t$ gradient steps by its displacement growth rate,
$$\hat g_k(t) = \frac{1}{t}\log\frac{\|x_k^{(t)} - x\|}{\|x_k^{(0)} - x\|},$$
where $x_k^{(t)}$ is the probe's position after $t$ steps. This quantity is informative from the first few steps. The reason is the mechanism behind NEON in First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time. Near $x$, repeated gradient steps act like power iteration on $I - \eta \nabla^2 f(x)$. So $\hat g_k$ approaches $\log(1 + \eta|\lambda|)$ for the most negative eigenvalue $\lambda$ that the probe's seed overlaps with, and to a non-positive value if the seed has no negative-curvature component. The race declares escape when some arm's lower confidence bound on $\hat g_k$ exceeds a threshold tied to $\epsilon_H$. It certifies a second-order stationary point when all upper bounds fall below that threshold.
The probes differ in their seeds, not just in their random draws. One family uses isotropic kicks at a few discrete radii, as in How to Escape Saddle Points Efficiently. A second uses differences of two mini-batch gradients. These are aligned with negative curvature under the correlated-negative-curvature condition of Escaping Saddles with Stochastic Gradients, which reports that, unlike isotropic noise, stochastic-gradient variance along the most negative eigenvector stays high and increases with eigenvalue magnitude. A third reuses the previous successful escape direction. Arms that are rolled out with Nesterov momentum, in the style of NEON+ and of Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent, form a fourth family.
Research Program
The method side borrows directly from bandit strategy selection. Monte Carlo Search Algorithm Discovery for Single-Player Games casts the choice among grammar-generated search algorithms as a pure-exploration bandit that discards weak candidates under a fixed compute budget. We reuse that elimination structure, but apply it to probes at one point rather than to algorithms across many problems. KernelBand supplies two lessons. Its finding that measured execution statistics beat a language model's reasoning about which strategy to pick motivates driving selection only by observed rollout behavior. Its own admission that Lipschitz sharing across arms breaks at algorithmic cliffs is a constraint on us: we treat perturbation radii and seed families as independent discrete arms and do not assume smoothness between them.
We will build the race as a successive-elimination routine over $K$ arms, with a total stall budget $B$ measured in gradient evaluations. Confidence intervals on $\hat g_k$ will account for mini-batch noise.
The analysis aims at one bound. The expected number of gradient evaluations to escape should scale as follows: $\log(1/\delta)$ times a sum over arms of inverse squared gaps between each arm's growth rate and the threshold, with the dominant term coming from the best-aligned arm. Here $\delta$ is the allowed probability of a wrong escape-or-certify decision. This is the standard thresholding-bandit form. Its practical meaning is that probes in the stuck slab are dropped after a handful of steps instead of consuming a full PGD waiting period.
A secondary, more speculative component carries arm priors from one stall to the next. Whether that helps, or whether non-stationarity across stalls makes it harmful, is an empirical question we will test rather than assume.
Baselines
The naive reference is fixed-parameter perturbed gradient descent from How to Escape Saddle Points Efficiently. It applies one isotropic kick whenever the gradient falls below $\epsilon$, then waits a fixed number of steps for a loss drop. We will run it with its radius and waiting time tuned by grid search under the same tuning budget given to our method. Beating it means fewer gradient evaluations to a verified second-order stationary point at matched false-certification rate.
The strongest existing competitor is NEON+, the momentum-accelerated first-order negative-curvature finder from First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time. It is the right foil because it already exploits the power-iteration effect our reward relies on, and that paper reports it performs similarly to, and sometimes better than, Lanczos. No reported numeric result was found on Lacuna for NEON+ or NEON-SGD escape counts on the quartic benchmark or on Gisette; the paper states only that Noisy SGD degraded significantly as $d$ rose from $10^3$ to $10^5$ while NEON-SGD remained efficient. We will therefore re-run NEON+ ourselves, with its step budget tuned on the same grid and the same total gradient-evaluation accounting.
Vanilla mini-batch SGD and CNC-SGD with periodic step-size increases (Escaping Saddles with Stochastic Gradients) are the "rely on intrinsic noise" reference. Their theoretical rate to a second-order point is $\tilde O(\epsilon^{-5})$, against $\epsilon^{-4}$ for perturbed methods.
Two ablations isolate the key ingredients. The first is block NEON: $K$ seeds iterated jointly with orthogonalization and an equal budget per seed. It tests whether adaptive allocation adds anything beyond multiple seeds. The second is equal-budget best-of-$K$ with heterogeneous seeds and no elimination. It separates the value of seed diversity from the value of the bandit rule.
A Lanczos solver using Hessian-vector products serves as an oracle upper reference and as the ground-truth certifier of $\lambda_{\min}$ at evaluation time.
Why not just…?
Why not just use PGD with a well-tuned radius? On low-dimensional, well-conditioned saddles it may be as good as our method, and we expect to tie there. The evidence against it as a general answer is the $O(1/d)$ variance dilution measured on MNIST in Escaping Saddles with Stochastic Gradients and the degradation with dimension reported for noise-based escape in the NEON paper. PGD also gives no confidence statement when it certifies a minimum. Our dimension sweep on the quartic function will show where, if anywhere, the gap opens.
Why not just always run NEON+? This is the real threat. If a single well-tuned NEON+ rollout matches our race on every benchmark, the bandit layer is unjustified and we will report that. Our hypothesis is that NEON+ loses in two regimes. The first is saddles where the negative-curvature subspace is tiny and isotropically seeded power iteration starts with little overlap; mini-batch-difference seeds should help there. The second is near true minima, where NEON+ must burn its full step budget before certifying, while elimination can stop early. Both regimes are built into the experiments below.
Why not just run block power iteration with several seeds? Subspace iteration already shares information across seeds through orthogonalization and is a cleaner linear-algebra answer. The block-NEON ablation tests this directly. Our method should win only if heterogeneous seed families plus early pruning save evaluations. If block NEON with mixed seeds closes the gap, the contribution shrinks to "use CNC-aligned seeds," and we will say so.
Why not just compute $\lambda_{\min}$ with Lanczos? For models small enough that Hessian-vector products are cheap and stable, Lanczos is the honest answer, and we use it as an oracle. The case for a gradient-only race rests on settings where Hessian-vector products are awkward or memory-heavy, as the NEON paper argues. We will report wall-clock as well as evaluation counts so this trade-off is visible.
Proposed Experiments
The first benchmark is the synthetic quartic $f(x)=\sum_i \xi_i(x_i^4-4x_i^2)$ from the NEON paper. Here $\xi_i$ sets the curvature of coordinate $i$, and the Hessian at the origin is known exactly. We will sweep $d$ from $10^3$ to $10^5$ and vary how many $\xi_i$ are non-negligible, which controls the dimension of the escape subspace.
We will add a mirrored variant: a function with a planted true minimum surrounded by near-zero curvature. On it we measure false-escape and false-certification rates against the analytic spectrum. The decisive check on this pair of benchmarks is that our method uses fewer gradient evaluations than tuned NEON+ in the thin-escape-subspace regime and in the certification regime, at equal error rates. Tying elsewhere is acceptable. Losing to block NEON with mixed seeds would falsify the claim that adaptive allocation is the key ingredient.
The second benchmark is symmetric low-rank factorization $f(X)=\tfrac14\|XX^\top-M^*\|_F^2$. Here $X$ is an $n \times r$ factor and $M^*$ is a rank-$r$ positive semi-definite target matrix. All saddles are strict and all local minima are global (Symmetry, Saddle Points, and Global Geometry of Nonconvex Matrix Factorization), so every certification can be checked exactly. We also include the constructed slow-escape landscapes motivated by Gradient Descent Can Take Exponential Time to Escape Saddle Points and SGD May Never Escape Saddle Points. There we expect SGD alone to stall and the race to escape.
The third benchmark is non-convex regularized least squares on Gisette ($n=6000$, $d=5000$). The fourth is MNIST multilayer perceptrons of increasing width, following the CNC paper's setup. On these two we record gradient evaluations and wall-clock to a Lanczos-verified $(\epsilon,\epsilon_H)$ second-order point, plus the fraction of stalls in which the mini-batch-difference arm wins. That fraction directly tests whether CNC-aligned seeds carry the gains the CNC measurements predict.
Across all benchmarks every method gets the same gradient-evaluation accounting, the same tuning grid size, and at least ten seeds. Results are reported with confidence intervals rather than single runs.
References
- Symmetry, Saddle Points, and Global Geometry of Nonconvex Matrix Factorization
- First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time
- How to Escape Saddle Points Efficiently
- Escaping Saddles with Stochastic Gradients
- Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
- Monte Carlo Search Algorithm Discovery for Single-Player Games
- KernelBand: Steering LLM-based Kernel Optimization via Hardware-Aware Multi-Armed Bandits
- Gradient Descent Can Take Exponential Time to Escape Saddle Points
- SGD Can Converge to Local Maxima