PaperlayerView exact revision on arXiv

Source-linked AI summary

A Progressive Batching L-BFGS Method for Machine Learning

Raghu Bollapragada, Dheevatsa Mudigere, Jorge Nocedal, Hao-Jun Michael Shi, Ping Tak Peter Tang

arXiv:1802.05374v2math.OCcs.LGstat.ML

TL;DR

Large-scale machine learning has favored stochastic gradient methods because standard L-BFGS appears to require costly, low-noise full-batch gradients for reliable search and curvature modeling. The paper develops a progressive-batching L-BFGS variant with stochastic line search and stable quasi-Newton updating, and reports good generalization on logistic regression and neural-network training, though deep-learning performance remains limited by extra gradient evaluations and omitted regularization techniques.

  • Problem

    Standard L-BFGS appears to require costly full-batch gradients for reliable descent directions, line searches, and quadratic models, limiting its use in large-scale machine learning.

  • Method

    The method combines progressive batching, a statistically initialized Armijo-style stochastic line search, and stable quasi-Newton updating.

  • Results

    The method achieves good generalization and similar test accuracy to SG and Adam on neural-network training, while requiring more gradient evaluations.

  • Takeaways & Limitations

    Progressive batching provides a context for applying L-BFGS to machine learning while retaining small iteration counts and larger batches during much of training.

  • Takeaways & Limitations

    The deep-learning study omits batch normalization and dropout, and the paper identifies parallel implementation and further component improvements as necessary for competitiveness.

Abstract

from arXiv · show

The standard L-BFGS method relies on gradient approximations that are not dominated by noise, so that search directions are descent directions, the line search is reliable, and quasi-Newton updating yields useful quadratic models of the objective function. All of this appears to call for a full batch approach, but since small batch sizes give rise to faster algorithms with better generalization properties, L-BFGS is currently not considered an algorithm of choice for large-scale machine learning applications. One need not, however, choose between the two extremes represented by the full batch or highly stochastic regimes, and may instead follow a progressive batching approach in which the sample size increases during the course of the optimization. In this paper, we present a new version of the L-BFGS algorithm that combines three basic components - progressive batching, a stochastic line search, and stable quasi-Newton updating - and that performs well on training logistic regression and deep neural networks. We provide supporting convergence theory for the method.

1. Introduction

The paper argues that L-BFGS for machine learning need not remain confined to full-batch or highly stochastic regimes. It combines progressive batching, stochastic line searches, and stable quasi-Newton updating into a method intended to retain efficient early behavior, curvature information, and useful generalization.

  • 1. Introduction: Large batches make L-BFGS costly because reliable gradients, line searches, and quadratic models traditionally require high-quality gradient estimates.This cost has made stochastic gradient methods more effective for large-scale logistic regression and increasingly dominant for deep neural networks.
  • 1. Introduction: Progressive batching increases the sample size during optimization instead of committing to either full-batch or highly stochastic computation.Prior results indicate that increasing sample sizes can preserve test loss and accuracy while improving computational opportunities.
  • 1. Introduction: The paper addresses stochastic line searches by selecting an initial steplength from statistical information for Armijo-style backtracking.The line search targets a sufficiently large predicted decrease despite observing only stochastic objective approximations.
  • 1. Introduction: The proposed algorithm combines progressive batching, stable quasi-Newton updating, and adaptive steplength selection into one method with theoretical and computational support.Its batching strategy extends an inner-product control test to second-order algorithms, while overlapping gradients provide an efficient stability mechanism for updating.
  • 1. Introduction: Numerical tests on large-scale logistic regression and deep neural networks indicate robust, efficient behavior, good generalization, and almost no parameter tuning.The study reports that the approach achieves similar test accuracy to SG and Adam, but requires more gradient evaluations and still needs parallel optimization.

2. A Progressive Batching Quasi-Newton Method

The method combines progressive batching with an inner-product quasi-Newton sample-size test, a stochastic Armijo line search, and stable L-BFGS curvature updates. These components adapt sampling and step selection to noisy gradients while preserving useful second-order information.

  • Progressive batching: The algorithm starts with a small batch and increases it based on observed-gradient conditions rather than a prescribed iteration schedule.The batch-size mechanism is intended to support fast initial progress while enabling a faster local convergence rate and second-order information later.
  • Progressive batching: The inner-product quasi-Newton test seeks a stochastic direction that forms an acute angle with the true quasi-Newton direction with high probability.A descent-direction test alone could underuse the curvature information in the quasi-Newton direction.
  • Progressive batching: When the variance-control condition fails, the method estimates a larger sample size and augments the current batch, using a moving-window estimate when small samples are unreliable.The variance can be computed with one additional Hessian-vector product, and the implementation sets the next batch size to the ceiling of the estimated bound.
  • Stochastic line search: The stochastic line search chooses an initial steplength from statistical information so the predicted decrease in expected objective value is sufficiently large, then backtracks to satisfy an Armijo condition.This addresses the difficulty that stochastic function values are noisy approximations to the true objective.
  • Stable quasi-Newton updates: Stable quasi-Newton updating uses gradient differences from the same sample or from the overlap between consecutive samples to reduce differencing noise.The overlap construction requires no extra computation, but the overlap should not be too small.
  • Stable quasi-Newton updates: The L-BFGS implementation initializes the Hessian approximation with a scaled identity and skips updates when the curvature condition is not satisfied.The limited-memory matrix is defined by stored curvature pairs and is independent of the current sample choice.

3. Convergence Analysis

The analysis establishes convergence guarantees under assumptions on the objective, sample-size tests, step lengths, and quasi-Newton matrices. It proves linear convergence in the strongly convex case and expected convergence to stationary points with a global sublinear rate in the nonconvex case.

  • Assumptions: The convergence analysis assumes bounded eigenvalues for the inverse L-BFGS matrices and studies fixed steplengths to isolate the effect of progressive sampling.The results cover both strongly convex and nonconvex objectives.
  • Algorithm: The algorithm samples a batch, enlarges it when the control condition fails, computes an L-BFGS direction, selects a steplength, and updates curvature pairs subject to a curvature test.The pseudocode also limits stored curvature pairs through the L-BFGS memory parameter.
  • Assumptions: The analysis adds an orthogonality-based sample-size control because the exact inner-product test could otherwise permit arbitrarily long search directions in rare cases.This control extends the first-order sampling strategy to the quasi-Newton setting.
  • Nonconvex objectives: For twice continuously differentiable nonconvex objectives bounded below, the gradient norms converge to zero in expectation and the smallest gradients over every T steps have a global sublinear convergence rate.The result requires the stated sample-size conditions, matrix assumptions, and a suitable steplength.

4. Numerical Results

The numerical experiments evaluate PBQN on logistic regression and neural-network training, comparing multi-batch and full-overlap variants with SG, SVRG, or Adam. PBQN competes well on generalization and training behavior, while showing promising iteration efficiency but requiring further work for fast performance and broader deep-learning applicability.

  • Logistic Regression: PBQN is evaluated on binary logistic-regression classification using multi-batch and full-overlap curvature-vector variants against SG and SVRG.The experiments use eight datasets, with training error, test loss, and test accuracy as evaluation measures.
  • Logistic Regression: PBQN competes well with SG and SVRG on training error, test loss, and test accuracy, while decreasing these measures more evenly.Its estimated steplength is accepted by backtracking for most iterations, so the line search requires very few additional function evaluations.
  • Logistic Regression: SVRG is less efficient than PBQN or SG during initial epochs on test loss and test accuracy, although neither PBQN nor SVRG consistently dominates training error across datasets.The comparison distinguishes early test performance from later training-error reduction.
  • Logistic Regression: The multi-batch curvature-vector approach is preferred to full overlap, and PBQN requires significantly fewer iterations than SG.The smaller iteration count suggests potential efficiency gains from parallel implementation.
  • Neural Networks: On neural-network tasks, PBQN achieves generalization comparable to SG and similar test accuracy to SG and Adam, but requires more gradient evaluations.The study covers convolutional, AlexNet-like, and ResNet18 architectures, with CIFAR-10 results shown for AlexNet and ResNet18.
  • Neural Networks: The neural-network investigation remains preliminary: fast-performance improvements and extensions involving batch normalization and dropout are left for future work.The tested methods omit batch normalization and dropout because their current forms are not conducive to PBQN's gradient-consistency requirement.
  • Neural Networks: PBQN uses few iterations and larger batches than SG during much of training, suggesting that a distributed implementation could be competitive.The line-search steplength is almost always accepted and typically lies within (0.1, 1), but full-batch training can later worsen test loss and accuracy through overfitting.

5. Final Remarks

The paper positions progressive batching as the setting for an L-BFGS method intended to combine favorable stochastic behavior with second-order information. The authors report promising logistic-regression results but identify substantial work needed before deep-learning competitiveness.

  • 5. Final Remarks: Progressive batching is presented as the context for an L-BFGS method with good generalization, no free parameters, and fast convergence.The approach is motivated as an alternative to purely stochastic or purely batch methods.
  • 5. Final Remarks: The method’s advantages are clearly demonstrated in logistic regression experiments.
  • 5. Final Remarks: Deep-learning competitiveness requires improvements to progressive batching, normalization and dropout heuristics, and parallel implementation.The authors especially emphasize exploiting the higher granularity of each iteration through parallelization.
  • 5. Final Remarks: The proposed approach is described as a potential alternative to stochastic-gradient methods for deep learning, warranting further investigation.

A. Initial Step Length Derivation

The initial-step-length analysis defines the stochastic quasi-Newton iteration and its sampled gradient structure, then establishes an inequality used to choose the initial steplength for stochastic line search.

  • A. Initial Step Length Derivation: The stochastic quasi-Newton method uses a batch or subsampled gradient within its iteration.
  • A. Initial Step Length Derivation: The sample set S_k indexes data points, while H_k is selected before a new sample defines the search direction p_k.
  • A. Initial Step Length Derivation: The exact variance inner-product quasi-Newton test is the primary mechanism for determining batch sizes.
  • A. Initial Step Length Derivation: The derivation establishes the inequality used to determine the initial steplength α_k for the stochastic line search.The supporting lemma assumes a continuously differentiable objective with Lipschitz-continuous gradient.

B. Convergence Analysis

The convergence analysis studies stochastic quasi-Newton iterations under orthogonality, Hessian-spectrum, smoothness, and lower-bound assumptions. It establishes linear convergence for strongly convex objectives and a bounded-below nonconvex convergence result under the batch-size test and steplength conditions.

  • Assumptions: The analysis assumes an orthogonality condition and positive bounded eigenvalues for the quasi-Newton matrices H_k.The orthogonality condition controls alignment and variance, while the eigenvalue condition bounds the matrices uniformly.
  • Proof Strategy: The proofs obtain the results through a technical descent lemma, expectation bounds, summation over iterations, and lower-boundedness of F.
  • Strongly Convex Case: For strongly convex F, the stochastic quasi-Newton iteration is shown to converge linearly with contraction factor ρ = 1 − µΛ1α.The result is stated for F with curvature constants 0 < µ ≤ L.
  • Strongly Convex Case: The exact-variance inner-product quasi-Newton test chooses |S_k| while the steplength satisfies the stated line-search condition.
  • Nonconvex Case: For twice continuously differentiable F that is bounded below, the analysis derives a convergence result for the nonconvex case.The result uses a Lipschitz-type constant, the same batch-size test, and the stated steplength condition.

C.1. Datasets

The experiments use datasets summarized in Table 2, with existing train/test divisions retained where available and random 90% training splits used otherwise.

  • C.1. Datasets: Datasets without predefined splits are randomly divided so that training data comprise 90% of the total.
  • C.1. Datasets: Table 2 summarizes the characteristics of all datasets used in the experiments.
  • C.1. Datasets: The alpha dataset is synthetic and available from the listed large-scale machine-learning repository.

C.2. Logistic Regression Experiments

The logistic-regression experiments evaluate progressive-batching L-BFGS variants across eight datasets using training error, test loss, and test accuracy. The figures compare multi-batch and full-overlap approaches with SG and SVRG.

  • Experimental setup: Performance is measured by training error, test loss, and test accuracy against gradient evaluations.The experiments also report batch-size and steplength behavior for both PBQN variants.
  • Methods compared: Across the logistic-regression figures, multi-batch (MB) with 25% overlap and full-overlap (FO) are compared with SG and SVRG.This comparison is shown for gisette, mushrooms, sido, ijcnn, spam, alpha, covertype, and url.
  • Dataset-specific condition: On url, SG and SVRG were run for only 3 gradient evaluations because the equivalent iteration count had already reached order 10^7.The shortened SG and SVRG runs affect the direct extent of that figure comparison.

C.3. Neural Network Experiments

The neural-network experiments evaluate PBQN variants using training loss, test loss, and test accuracy against iterations and gradient evaluations. They cover a small ConvNet and a larger AlexNet adaptation for CIFAR-10 and MNIST.

  • Experimental setup: Neural-network performance is plotted using training loss, test loss, and test accuracy against total iterations and gradient evaluations.Batch-size and steplength behavior are also reported for both PBQN variants.
  • ConvNet architecture: The ConvNet is a 2-layer convolutional network with 5 × 5 kernels, 2 × 2 max pooling, and a 1000-unit ReLU fully connected layer.Its convolutional layers produce 6 and 16 output channels, respectively.
  • AlexNet architecture: The AlexNet adaptation uses convolutional layers with max pooling followed by two fully connected layers for CIFAR-10 and MNIST.The CIFAR-10 version has three convolutional layers, with a 5×5 first kernel and 3 × 3 later kernels.

C.3.3. CIFAR-10 RESIDUAL NETWORK (R) ARCHITECTURE

The CIFAR-10 residual-network experiments use a modified ResNet18 and compare PBQN performance with SG and Adam. The accompanying model analyzes effective batch size, iteration cost, and parallel efficiency.

  • CIFAR-10 ResNet18 architecture: The CIFAR-10 ResNet18 is modified by removing the ImageNet architecture’s global average pooling layer before the 1000-neuron fully connected layer.ReLU activations and max poolings are included appropriately.
  • CIFAR-10 ResNet18 architecture: Figure 16 compares multi-batch and full-overlap PBQN with SG and Adam, with the best L-BFGS results achieved at θ = 2.The figure concerns CIFAR-10 ResNet18 performance.
  • Parallel performance model: Increasing PBQN batch sizes produce a larger effective batch size than SG, which may support scaling to more nodes and reduce training time.The paper presents this as the motivation for extending an idealized parallel-performance model.
  • Parallel performance model: PBQN iterations add L-BFGS recursion, stochastic line-search, and curvature-update computation beyond SG gradient computation.The stochastic line search may require extra forward propagations, but rejected steplengths are described as infrequent in practice.
  • Parallel performance model: With effective batch size approximately 4× larger and SG parallel efficiency assumed to be 0.2, PBQN must converge in about the same iterations as SG to achieve lower training time.The example uses SG large batch ≈8K and PBQN ≈32K.
Loading 1802.05374v2…