PaperlayerView exact revision on arXiv

Source-linked AI summary

Training Neural Networks for and by Interpolation

Leonard Berrada, Andrew Zisserman, M. Pawan Kumar

arXiv:1906.05661v2cs.LGstat.ML

TL;DR

Deep networks often interpolate training data, but SGD's strong generalization comes with laborious learning-rate scheduling and full objective evaluation is costly. ALI-G exploits interpolation to compute stochastic adaptive learning-rates, clips them with a non-decaying maximum, and provides convergence guarantees with strong empirical performance. It is intended as an easy-to-tune, practical replacement that retains SGD's descent direction and comparable generalization performance.

  • Problem

    SGD often generalizes well but requires manual learning-rate schedules, while full-objective Polyak updates are expensive and can fail on non-convex deep networks.

  • Method

    ALI-G uses interpolation to compute a stochastic adaptive learning-rate from sample losses and gradients, clips it at a fixed maximum, and updates in SGD's descent direction.

  • Results

    ALI-G provides convergence guarantees in stochastic settings and achieves state-of-the-art empirical results among neural-network methods, including comparable performance with SGD.

  • Takeaways & Limitations

    ALI-G offers a simple, drop-in optimization method with substantially less tuning because its maximal learning-rate does not require a decay schedule.

  • Takeaways & Limitations

    The analysis does not establish a corresponding positive-tolerance result for all individual losses in the non-convex setting, which remains an open question.

Abstract

from arXiv · show

In modern supervised learning, many deep neural networks are able to interpolate the data: the empirical loss can be driven to near zero on all samples simultaneously. In this work, we explicitly exploit this interpolation property for the design of a new optimization algorithm for deep learning, which we term Adaptive Learning-rates for Interpolation with Gradients (ALI-G). ALI-G retains the two main advantages of Stochastic Gradient Descent (SGD), which are (i) a low computational cost per iteration and (ii) good generalization performance in practice. At each iteration, ALI-G exploits the interpolation property to compute an adaptive learning-rate in closed form. In addition, ALI-G clips the learning-rate to a maximal value, which we prove to be helpful for non-convex problems. Crucially, in contrast to the learning-rate of SGD, the maximal learning-rate of ALI-G does not require a decay schedule, which makes it considerably easier to tune. We provide convergence guarantees of ALI-G in various stochastic settings. Notably, we tackle the realistic case where the interpolation property is satisfied up to some tolerance. We provide experiments on a variety of architectures and tasks: (i) learning a differentiable neural computer; (ii) training a wide residual network on the SVHN data set; (iii) training a Bi-LSTM on the SNLI data set; and (iv) training wide residual networks and densely connected networks on the CIFAR data sets. ALI-G produces state-of-the-art results among adaptive methods, and even yields comparable performance with SGD, which requires manually tuned learning-rate schedules. Furthermore, ALI-G is simple to implement in any standard deep learning framework and can be used as a drop-in replacement in existing code.

1 Introduction

Deep-network training combines high-dimensional non-convex optimization with a practical tension: SGD generalizes well but requires laborious learning-rate schedules. ALI-G addresses this by automatically adapting the learning-rate while retaining SGD's descent direction.

  • SGD often generalizes better than adaptive gradient methods, but manually designing its learning-rate schedule is onerous and time consuming.
  • ALI-G uses an adaptive learning-rate with the same descent direction as SGD to reduce tuning while targeting comparable generalization performance.
  • The method builds on Polyak's adaptive step-size when the objective minimum is known and on approximately known minima in interpolating models.

2 THE ALGORITHM

ALI-G is designed as a practical interpolation-based optimizer with fast convergence guarantees and strong neural-network results. Its central design uses one non-decaying maximal learning-rate, alongside stochastic and projection-based updates.

  • ALI-G converges fast in convex or Restricted Secant Inequality settings and obtains state-of-the-art empirical results with neural networks.
  • ALI-G uses a single learning-rate hyper-parameter without a decaying schedule, unlike aProx with two and L4 with four learning-rate hyper-parameters.
  • The analysis provides stochastic convex convergence rates that account for error in estimating the minimum objective value.
  • A maximal learning-rate is proved helpful for convergence on a class of non-convex problems.
  • Experiments cover a differentiable neural computer, residual networks on SVHN and CIFAR, and a Bi-LSTM on SNLI.
  • The framework models sample losses as non-negative functions and can incorporate regularization through a computationally efficient projection constraint.

2 THE ALGORITHM

The Polyak step-size uses the known objective minimum to scale full-gradient updates, but its computational cost and non-convex behavior limit deep-learning applicability. ALI-G is motivated as an inexpensive stochastic extension that addresses these limitations in interpolation settings.

  • 2.1 Problem Setting: The interpolation assumption means one solution simultaneously minimizes every individual loss, equivalently giving f⋆=0; approximate interpolation permits ℓz(w⋆)≤ε.
  • 2.2 The Polyak Step-Size: The Polyak update projects a full-gradient step whose learning-rate is the objective gap divided by the squared gradient norm.
  • 2.2 The Polyak Step-Size: Assuming f⋆=0, the Polyak step-size illustration coincides with Newton-Raphson root finding in one dimension.
  • 2.2 The Polyak Step-Size: Polyak updates require full evaluations of the objective and derivative, and can sometimes fail to converge for non-convex deep-network problems.
  • 2.2 The Polyak Step-Size: ALI-G therefore targets stochastic computation with cost independent of total sample count and convergence in deep neural networks under interpolation.

3 JUSTIFICATION AND ANALYSIS

ALI-G operationalizes interpolation by replacing full-objective information with stochastic sample losses and gradients, then projecting a clipped update. Its unbounded variant removes the step-size hyper-parameter entirely.

  • ALI-G assumes the model can drive the loss near zero on all samples simultaneously, enabling interpolation-based stochastic updates.
  • Each iteration obtains a stochastic sample loss and gradient, computes a step-size, then moves in the negative derivative direction and projects onto the feasible region.
  • The algorithm requires a maximal learning-rate η, an initial feasible point, and a small constant δ, while iterating until convergence.
  • ALI-G∞ removes the maximal learning-rate and consequently requires no step-size hyper-parameter.
  • Some experiments accelerate ALI-G with Nesterov momentum by updating a velocity before the projected parameter step.

3 Justification and Analysis

ALI-G uses interpolation to replace the unknown objective minimum with zero and compute learning-rates from individual stochastic losses. Its convex analysis allows approximate interpolation and yields convergence guarantees.

  • Interpolation sets f⋆=0, simplifying ALI-G’s learning-rate formula and allowing updates to use one sample’s loss and gradient instead of the full objective.The stochastic quantities suffice because each individual loss has the known minimum in the interpolation setting.
  • Under convex Lipschitz losses, ALI-G∞ has a convergence guarantee even when each sample loss at the solution is bounded by tolerance ε.The theorem explicitly models approximate interpolation through ℓ_z(w⋆) ≤ ε.

3 JUSTIFICATION AND ANALYSIS

The analysis explains why stochastic interpolation-based rates are cheaper than Polyak’s full-objective computation and how clipping stabilizes non-convex optimization. Guarantees depend on interpolation accuracy and include exact or exponential convergence in supported settings.

  • ALI-G computes its learning-rate from one sample’s loss and gradient, whereas Polyak’s step-size requires the full objective and gradient over all training samples.This difference gives ALI-G a computational advantage in stochastic training.
  • Exact interpolation yields exact convergence in the convex guarantee, while the analysis explicitly tracks degradation through tolerance ε.The result depends on ε and becomes exact when ε = 0.
  • For smooth convex objectives ALI-G achieves O(1/T) rates, while α-strongly convex and β-smooth objectives admit O(exp(−αT/8β)) rates.A sufficiently large maximal learning-rate preserves convergence speed; a small one lowers it.
  • Polyak’s step-size can oscillate on non-convex problems, whereas ALI-G converges on the illustrated problem whenever its maximal learning-rate is below 10.The example motivates controlling the step-size in non-convex settings.
  • The RSI assumption does not require convexity, but the supplied analysis introduces it to study non-convex convergence.The example in Figure 2 satisfies RSI, yet Polyak’s method can still fail there.

4 RELATED WORK

Related work positions ALI-G among proximal, adaptive, line-search, and Polyak-style methods. Its distinguishing combination is stochastic interpolation-based updates, a maximal learning-rate without decay, convergence analysis, and strong neural-network results.

  • Non-Convexity: The RSI is weaker than strong convexity because every strongly convex function satisfies it, yet it does not itself require convexity.This assumption broadens the class of problems considered by the non-convex analysis.
  • ALI-G converges exponentially fast on interpolating RSI problems when the maximal learning-rate lies in the theorem’s specified range.The theorem assumes β-smooth losses, perfect interpolation, and 1/(2β) ≤ η ≤ 2µ/β^2.
  • Non-Convexity: Theorem 2 assumes perfect interpolation, and whether the corresponding non-convex result extends to tolerance ε > 0 remains open.This is an explicit scope limitation of the theorem.
  • Proximal Interpretation: Unlike proximal SGD, ALI-G exploits non-negative sample losses to use a constant maximal learning-rate instead of SGD’s manually decayed rate.Both methods locally linearize the sample loss, but ALI-G solves the resulting proximal problem in closed form.
  • Adaptive Gradient Methods: ALI-G’s experiments outperform popular adaptive gradient methods, while related warmup-based Adam still requires a learning-rate schedule.The comparison is reported in the related-work discussion.
  • Frank-Wolfe Methods: Deep Frank-Wolfe is procedurally identical to unregularized ALI-G, but ALI-G is presented as applicable to arbitrary lower-bounded losses.The supplied passage identifies this as one of ALI-G’s stated advantages over DFW.
  • aProx Algorithm: Compared with aProx and L4, ALI-G uses fewer learning-rate hyperparameters, avoids decay, accounts for interpolation tolerance, and provides neural-network experiments and convergence guarantees.The comparison describes aProx as using two hyperparameters and L4 as using four, while ALI-G uses one non-decayed hyperparameter.

5 EXPERIMENTS

Across tasks including differentiable neural computers, SVHN, SNLI, CIFAR, and ImageNet, ALI-G provides robust or competitive optimization with less learning-rate tuning than SGD. It matches or approaches SGD while outperforming several adaptive baselines in reported experiments.

  • Experimental Scope: The experiments span differentiable neural computers, SVHN, SNLI, CIFAR networks, and large-scale ImageNet training using publicly available implementations and reproduced baselines.The evaluated architectures include wide residual networks, densely connected networks, a Bi-LSTM, and a ResNet-18.
  • Differentiable Neural Computers: ALI-G reaches an objective of 4.10^-8 on the differentiable neural computer and remains accurate across η from 10^-1 to 10^6.SGD, momentum SGD, and Adam are sensitive to their main learning-rate hyper-parameter on this task.
  • SVHN: ALI-G and other adaptive methods achieve close performance to SGD on SVHN, where most methods reach about 98% test accuracy.L4Mom fails to converge despite cross-validation, whereas SGD uses a hand-designed schedule.
  • SNLI: ALI-G outperforms all other methods on both SVM and cross-entropy losses for the SNLI Bi-LSTM, while ALI-G∞ remains competitive with scheduled SGD without a learning-rate hyper-parameter.The comparison includes a hand-designed SGD schedule and adaptive methods with tuned learning rates.
  • CIFAR: ALI-G obtains competitive performance with manually decayed SGD on CIFAR, while largely outperforming AMSGrad, AdamW, and Yogi.The CIFAR results average three independent runs, with standard deviations at most 0.3 for ALI-G and SGD.
  • Training at Large Scale: On ImageNet, ALI-G matches SGD's final performance despite SGD's custom schedule and reaches 99% top-5 accuracy in 12 epochs faster than SGD.The experiment uses a top-5 classification loss tailored to satisfy the interpolation assumption.

6 Discussion

ALI-G automatically adapts the learning-rate in the interpolation setting and retains SGD’s descent direction, yielding comparable generalization performance with less tuning. Its proximal interpretation characterizes the update as the closest point satisfying a linearized objective constraint.

  • 6 Discussion: ALI-G provides convergence guarantees while using the same descent direction as SGD, offering comparable generalization performance with significantly less tuning.The method automatically adapts the learning-rate in the interpolation setting.
  • 6 Discussion: The standard Polyak step-size moves to the closest point on the linearization of f at w_t whose value equals the known minimum f⋆.This interpretation follows from the unconstrained update and its linearized equality constraint.
  • 6 Discussion: ALI-G’s update can be derived as a proximal problem whose solution depends on the stochastic gradient and a learning-rate selected through a one-dimensional closed-form optimization.The derivation introduces KKT conditions and solves a projected quadratic problem in the dual variable.
  • 6 Discussion: The proximal derivation distinguishes the zero-gradient case, where the iterate remains unchanged, from the nonzero-gradient case that produces the adaptive update.For d_t = 0, the selected step is zero; otherwise the KKT solution gives the next iterate.

B SUMMARY OF CONVERGENCE RESULTS

ALI-G has convergence guarantees across stochastic convex settings, including approximate interpolation, with rates depending on the maximal learning-rate. For non-convex problems, maximal learning-rate clipping is necessary and sufficient for convergence under the analyzed conditions.

  • B SUMMARY OF CONVERGENCE RESULTS: Maximal learning-rate clipping is necessary and sufficient for convergence in the analyzed non-convex setting, while the unclipped Polyak step-size can oscillate indefinitely.The convergence overview states that clipping yields exponentially fast convergence, whereas η = ∞ may fail.
  • B SUMMARY OF CONVERGENCE RESULTS: In convex Lipschitz, convex smooth, and smooth strongly convex settings, ALI-G achieves rates O(1/√T), O(1/T), and O(exp(−kT)), respectively.These rates match those of the non-stochastic Polyak step-size and optimal non-stochastic gradient descent in the corresponding settings.
  • B SUMMARY OF CONVERGENCE RESULTS: The convex convergence analysis covers approximate interpolation, where each sample loss at w⋆ is at most ε, rather than requiring exact zero loss.Theorems 3–6 analyze this tolerance and distinguish small-η and large-η regimes.
  • B SUMMARY OF CONVERGENCE RESULTS: The convex results separate small and large maximal learning-rates, with different bounds and assumptions for η below or above 1/(2β).The smooth convex analysis explicitly treats η ≥ 1/(2β) and η ≤ 1/(2β) separately.

C.3 Smooth and Strongly Convex Functions

For smooth strongly convex losses, ALI-G obtains separate convergence guarantees for maximal learning-rates above and below 1/(2β), under approximate interpolation and a stability condition on δ.

  • C.3 Smooth and Strongly Convex Functions: The strongly convex analysis assumes β-smooth, α-strongly convex sample losses with interpolation error at most ε and δ > 2βε.These conditions support both the large-η and small-η theorems.
  • C.3 Smooth and Strongly Convex Functions: Theorem 7 gives a convergence result for maximal learning-rates η ≥ 1/(2β) under the stated strongly convex, smooth, and approximate-interpolation assumptions.Its proof combines the smoothness and strong-convexity relationships with the stochastic update analysis.
  • C.3 Smooth and Strongly Convex Functions: The proof relates parameter distance to objective suboptimality using strong convexity and a Polyak–Łojasiewicz-type inequality.The argument minimizes an auxiliary bound over an arbitrary comparison point before invoking the resulting inequality.
  • C.3 Smooth and Strongly Convex Functions: Theorem 8 gives a corresponding convergence result for maximal learning-rates η ≤ 1/(2β) under the same assumptions.The analysis reuses the small-learning-rate inequalities and derives the final bound through expectation and induction.

D Detailed Non-Convex Results

Under the RSI, ALI-G converges for suitable maximal learning-rates, whereas the unclipped Polyak step-size can oscillate even with the exact minimum known. The section also documents the perfect-interpolation assumption and experimental scope.

  • D Detailed Non-Convex Results: The RSI is presented as weaker than convexity and is used to analyze convergence without assuming convex sample losses.The RSI definition supplies the condition used in the non-convex results.
  • D Detailed Non-Convex Results: The unclipped Polyak step-size may fail to converge under RSI even in a deterministic problem with the exact minimum known.For f(w)=w^2−|w|^3 on [−3/5, 3/5], starting at −3/5 produces iterates that oscillate between −3/5 and 3/5.
  • D Detailed Non-Convex Results: A β-smooth RSI problem with exact interpolation converges under ALI-G when 1/(2β) ≤ η ≤ 2α/β^2.This is the large-learning-rate RSI guarantee stated in Theorem 9.
  • D Detailed Non-Convex Results: A β-smooth RSI problem also has an ALI-G convergence guarantee when 0 < η ≤ 1/(2β).In this regime, the clipped learning-rate equals η under the stated assumptions.
  • D Detailed Non-Convex Results: The empirical materials include CIFAR test-accuracy results with standard deviations, while the described ImageNet setup uses 1.23M training images and top-5 truncated cross-entropy.Each CIFAR experiment was run three times.
Loading 1906.05661v2…