Polyak Steps Along Guaranteed-Descent Conjugate Directions, Audited Under Mini-Batch Noise

Most optimizers answer two questions at every step: which way to move, and how far. In classical conjugate gradient methods, which mix the current gradient with the previous step to avoid zig-zagging, the "which way" answer is only guaranteed to point downhill if the "how far" answer comes from a careful line search, a routine that repeatedly evaluates the loss until a decrease condition holds. A line of work in numerical optimization removes this dependency. Its direction formulas, such as three-term conjugate gradient, are built so that the direction is always downhill by a fixed margin, whatever step size is used. These methods have been validated only on small deterministic test problems. Deep-learning practice runs the other way: adaptive step sizes like the stochastic Polyak step are tested on real networks, but always along the plain gradient.

This note proposes joining the two pieces and testing the result honestly. The descent guarantee is the property that makes a Polyak-type step size well-defined along a non-gradient direction. So a guaranteed-descent conjugate direction can be paired with a closed-form step size that needs no line search and no hand-made schedule. The guarantee, however, is stated with respect to the mini-batch gradient. Whether it still holds for the true training objective once gradients are noisy is an empirical question no one has measured. The project builds the method, measures how often the guarantee actually holds on the true objective during training, and benchmarks the method against tuned Adam, momentum SGD and the stochastic Polyak step under the standardized DeepOBS protocol.

Core Claim

Write $g_k$ for the gradient at iterate $x_k$ and $d_k$ for the search direction. The sufficient descent condition is

$$g_k^T d_k \le -c\,\|g_k\|^2, \qquad c>0.$$

The three-term direction of Dong et al. takes the form $d_k = -g_k + \beta_k s_{k-1} - \theta_k y_{k-1}$, where $s_{k-1}$ is the previous step and $y_{k-1}$ is the change in gradient. That paper chooses the scalars so the condition holds for every step size. The stochastic Polyak step of Loizou et al. sets the step along $-\nabla f_i$ so that the predicted first-order decrease equals the gap between the mini-batch loss $f_i(x_k)$ and its lower bound $f_i^*$. The natural generalization along any direction $d_k$ is

$$\gamma_k = \frac{f_i(x_k) - f_i^*}{c'\,(-g_k^T d_k)},$$

where $c'>0$ is the usual Polyak scaling constant. When $d_k = -g_k$ this reduces exactly to SPS. For a general conjugate direction, the denominator can be zero or negative, so the step is undefined or points uphill. Sufficient descent rules this out by construction. It also bounds the step: $\gamma_k \le (f_i - f_i^*)/(c' c \|g_k\|^2)$, which inherits the same scaling as SPS.

Our claim has three parts. First, line-search-independent sufficient descent is the structural ingredient that lets Polyak steps work along conjugate directions. Second, under mini-batch noise the guarantee transfers to the full training objective only partially, and the gap is measurable. Third, a variant that computes the gradient difference $y_{k-1}$ on a single batch closes most of that gap.

No paper in the material makes this combination. CoBA (Kobayashi & Iiduka) inserts conjugate directions into AMSGrad but uses Adam-style learning rates, needs an extra damping term $M/t^a$ to stay stable, and has no descent guarantee. SPS and the Armijo line-search analyses (Armijo Line-search Can Make SGD Provably Faster, Fan et al.) all keep the steepest-descent direction.

Research Program

The first component is the method itself, called PolyakCG here. It computes the three-term direction from the current mini-batch gradient using Dong et al.'s coefficient rules, then takes the generalized Polyak step above. As in SPS, it sets $f_i^*=0$ for interpolating models. As in SPSmax, it keeps an optional step cap so the comparison with SPS is like-for-like.

The method comes in two variants that differ only in how $y_{k-1}$ is formed. The cross-batch variant takes the difference of gradients from two different mini-batches. It costs nothing extra, but it injects noise from both batches into a vector that is meant to measure curvature. The same-batch variant recomputes the gradient at the previous iterate on the current batch, a trick familiar from stochastic quasi-Newton methods. It costs one extra backward pass per step. This is comparable to, and often cheaper than, the extra forward passes of stochastic line search.

The second component is a descent audit. The guarantee holds exactly for the batch gradient $\hat g_k$. The quantity that matters for the true objective is

$$g_k^T d_k = \hat g_k^T d_k + (g_k - \hat g_k)^T d_k .$$

Here $g_k$ is the full-data gradient. The second term has zero mean only if $d_k$ is independent of the batch noise, and it is not: $\beta_k$, $\theta_k$ and $y_{k-1}$ all depend on $\hat g_k$. At regular intervals we will estimate $g_k$ with a large held-out batch. From that estimate we record the fraction of steps where the direction is uphill on the full objective, and the ratio $-g_k^T d_k/\|g_k\|^2$, which is the empirical value of $c$.

We will record the same quantities for momentum SGD and for CoBA. Momentum SGD is itself a conjugate-style direction with a fixed mixing coefficient, so the comparison shows whether the guarantee buys anything measurable over methods that have no such guarantee. This addresses the tension the file flags between Dong et al.'s deterministic proof and CoBA's observed instability under noise.

The third component is a short theoretical note. Under interpolation and bounded noise, we will bound the expected uphill component of the second term for the same-batch variant. The aim is to explain the audit results, not to build a full convergence theory.

Baselines

The naive reference point is plain SGD with a constant step size, tuned by the same random search used for everything else. It shows how much any adaptive scheme helps on each problem.

The strongest practical competitors are tuned Adam and momentum SGD as run in DeepOBS. Schmidt et al. found across 53,760 training curves that Adam-family methods are hard to beat. They also found that moving from default settings to a 50-run tuning budget gives only a median relative improvement of 3.4%, rising to roughly 5.2% with a schedule. A new method that wins by less than these margins has not clearly beaten tuning. On CIFAR-100, DeepOBS reports 60.33% test accuracy for momentum SGD and 56.15% for Adam. Our CIFAR-100 runs must reproduce those numbers within seed variance before any comparison is trusted. Beating these baselines means matching or exceeding their test accuracy at equal tuning budget while reaching the DeepOBS speed threshold in less wall-clock time, or matching them with a much smaller tuning budget.

The strongest method on the step-size question is SPSmax from Loizou et al.. That paper reports that on ResNet-34 with CIFAR-10/100 it matches stochastic line search and is competitive with Adam, Lookahead and RAdam. The file has no reported final accuracy figure for SPS on these tasks, so we will rerun it ourselves on the identical seeds and budget.

Stochastic line search, analyzed in Armijo Line-search Can Make SGD Provably Faster, is the strongest competitor on wall-clock cost. It will be reported both per step and per second. CoBA with its Hager-Zhang variant is the closest existing conjugate method in deep learning. Its damping constants will receive the same tuning budget as our cap and $c'$. No test-accuracy number for CoBA is reported in the file.

Two ablations isolate the key ingredient. In the first, the three-term direction is replaced by a standard two-term PRP direction with a restart to $-g_k$ whenever $g_k^T d_k \ge 0$. In the second, the generalized Polyak step is applied along a heavy-ball momentum direction and the step is clipped whenever the denominator is non-positive.

All methods get the same data, architectures, 10 seeds, and the Schmidt et al. random-search budgets of 1, 25 and 50 runs.

Why not just…?

Why not just use SPS along the plain gradient? This is the most serious threat. SPS already gives a closed-form step with no line search, and nothing in the file shows that conjugate directions improve test accuracy in deep networks. CoBA's gains were in training loss and early epochs. If PolyakCG matches SPSmax on test metrics and only wins on training loss, the honest conclusion is that direction memory does not matter under this protocol. The DeepOBS comparison at equal budget settles this directly.

Why not just use momentum, which is already a conjugate-style direction? Momentum adds the previous step with a fixed weight and never checks for descent. The momentum-plus-Polyak ablation tests whether the guarantee itself matters. If that ablation needs clipping rarely and performs as well as PolyakCG, the three-term construction is unnecessary. The descent audit will show whether momentum directions go uphill on the full objective more often than three-term ones.

Why not just keep a two-term conjugate gradient and restart when it goes uphill? Zhou et al. documents that cheap line searches leave classical conjugate directions without a descent guarantee. Restarts are the usual repair, and they throw away conjugacy. Under noise, restarts may fire constantly. The restart ablation measures how often they fire and what that costs.

Why not just use Armijo backtracking? Backtracking needs extra forward passes per step, and its stochastic sample complexity depends on dataset size. The same-batch variant also adds one pass, so the advantage is not free. That is why the comparison is reported in wall-clock time, not only in steps.

Proposed Experiments

The first experiment is a deterministic sanity check on the 145 CUTEr unconstrained problems used by Dong et al., accessed through the S2MPJ interface, with the true $f^*$ supplied. It checks that the Polyak-stepped three-term method is competitive with the Wolfe-search version on Dolan-Moré performance profiles. Dong et al. report NPRP on the top curve but give no per-problem numbers.

The second is a separable logistic regression study using the setup of Fan et al. (synthetic $n=d=500$) and the ijcnn dataset. It asks whether conjugate directions preserve the $\tilde O(1/T)$ margin convergence proved for steepest descent, which tests the generalization concern on a problem where margins are computable.

The main experiment covers the DeepOBS problems, including Fashion-MNIST and CIFAR-10 classifiers, the CIFAR-100 network, the MNIST VAE and the Tolstoy character-level RNN. Each runs with 10 seeds and the three tuning budgets. We report test accuracy or loss, time to threshold, and the descent-audit statistics.

Three outcomes are decisive. The first is the audit itself: if the cross-batch three-term direction goes uphill on the full objective about as often as momentum, the deterministic guarantee does not survive noise. If the same-batch variant sharply reduces that rate, the proposed fix is supported. The second is whether PolyakCG beats SPSmax on test metrics on at least the CIFAR-100 and CharRNN problems by more than the 3.4% median gain that tuning alone provides. The third is the momentum-Polyak ablation: if it performs as well, the contribution narrows to the generalized step rule, and the paper will say so.