A Multi-Batch L-BFGS Method for Machine Learning

1 Introduction

• Asynchronous SGD cannot use large batches without compromising stability and scalability, while synchronous mini-batch SGD gains iteration speed only up to a point.Beyond that point, added computation is not offset by faster convergence.Source: §1 · p. 2
• Batch L-BFGS can reach high training accuracy and use more computation per node to balance communication costs, but is less efficient than SGD sequentially.Some systems therefore begin with SGD and later switch to a batch method.Source: §1 · p. 2
• Changing batches can destabilize L-BFGS because gradient differences used for Hessian updates may be computed from different data points.The proposed update uses the overlap between consecutive batches and is intended to avoid extra computation or special synchronization.Source: §1 · p. 2
• The multi-batch L-BFGS method is reported to balance computation and communication costs, with convergence analyzed for convex and nonconvex problems.The convergence analysis uses a fixed step length strategy.Source: §1 · p. 2

2 The Multi-Batch Quasi-Newton Method

• In distributed L-BFGS, ignoring slow or unresponsive nodes changes the samples used for objective and gradient evaluations, creating an inconsistency that can harm quasi-Newton methods.The method targets fault tolerance without requiring sample consistency, which the authors regard as impossible or undesirable in these settings.Source: §2 · pp. 2–3
• Large batches yield relatively low-variance gradients and make distributed evaluation useful, distinguishing this second-order approach from small-mini-batch SGD.The multi-batch method changes its training subset at each iteration; the inverse-Hessian approximation is denoted H_k.Source: §2 · pp. 2–3
• Using the overlap O_k between consecutive samples to compute gradient differences provides a curvature estimate for the BFGS update when that overlap is not too small.The overlap can be smaller than the batch used to compute the gradient.Source: §2 · p. 3

2.1 Specification of the Method

• The algorithm forms correction vectors from samples shared by S_k and S_{k+1}, uses a constant step length, and stores recent correction pairs for limited-memory updates.The limited-memory implementation applies two-loop recursion rather than forming H_k explicitly.Source: §2.1 · pp. 3–4

2.2 Sample Generation

• In fault-tolerant execution, each sample is the union of data assigned to responding nodes, and the overlap comes from nodes responding in both consecutive iterations.Random failures can produce independent samples, whereas repeated failures can bias sample creation; shuffling and redistributing data is one proposed way to ensure independent sampling.Source: §2.2 · pp. 4–5
• The ordered sampling strategy builds each batch from overlaps with neighboring batches and unique samples, reshuffling after each pass and using every sample once per epoch.Its batches are not independent.Source: §2.2 · p. 5
• A second strategy independently selects each batch, then subsamples its overlap; evaluating the overlap gradient costs extra computation, though the cost is small when overlap is small.Source: §2.2 · p. 5

3.1 Strongly Convex case

• Under the strongly convex assumptions, constant-step multi-batch L-BFGS converges to a neighborhood of the minimizer, with a bound combining linear decay and a neighborhood term.The assumptions include smoothness, curvature bounds for subsampled objectives, and unbiased sampled gradients.Source: §3.1 · pp. 5–6
• A larger step length improves the linearly decaying term's constant but enlarges the convergence neighborhood; larger batches improve parallelism and limiting accuracy but slow learning.Source: §3.1 · p. 6
• A Robbins–Monro step-length schedule can yield convergence to the optimum, but only at a sublinear rate that the paper considers less relevant for large-batch settings.Source: §3.1 · p. 6

3.2 Nonconvex case

• For nonconvex problems, the method skips a Hessian update when the curvature condition fails, and the resulting Hessian approximations are bounded above and away from zero.The cautious strategy is used under the stated nonconvex assumptions.Source: §3.2 · p. 6
• With cautious updating, the analysis bounds the average gradient norm after the first L−1 iterations and shows iterates increasingly spend time where the objective gradient is small.Source: §3.2 · pp. 6–7

4 Numerical Results

• Robust L-BFGS is more stable than inconsistent L-BFGS, especially at small batch sizes, and is not too sensitive to overlap size.At r = 1%, serial SGD achieves similar accuracy at a similar rate, but uses n communications per epoch versus 1/[r(1−o)] for robust L-BFGS.Source: Figure 2 · p. 7, §4 · p. 7
• Across node failure probabilities p ∈ {0.1, 0.3, 0.5}, the experiments suggest robust L-BFGS is more stable than L-BFGS without sample consistency.The comparison uses 10 runs per algorithm on webspam with K = 16 MPI processes.Source: Figure 3 · p. 8, §4 · p. 8
• In strong scaling, gradient computation time decreases with K, but at small r communication exceeds compute time; in weak scaling, gradient time stays almost constant while communication-inclusive L-BFGS direction time rises slightly.Figure 4 uses artificial data; the strong-scaling problem has d = 10^4 and n = 10^7, while weak scaling varies sparsity and local problem size.Source: Figure 4 · p. 8, §4 · p. 8

5 Conclusion

• The proposed L-BFGS variant addresses changing batches and node failures by basing quasi-Newton updates on overlap between consecutive samples.The paper reports practical efficiency and analyzes convergence properties.Source: §5 · p. 8

A.1 Assumptions

• Assumption A includes twice continuous differentiability and independently sampled batches whose gradients are unbiased estimators of the true gradient.The paper identifies Assumptions A with the strongly convex case.Source: §A.1 · p. 10

Assumptions B

• Assumption B includes twice continuous differentiability, Lipschitz-continuous gradients, a lower bound on F, and independently sampled batches with unbiased gradient estimates.The paper identifies Assumptions B with the nonconvex case.Source: §A.1 · p. 10, Assumptions B · p. 10

A.2 Proof of Lemma 3.1 (Strongly Convex Case)

• Under Assumptions A.1–A.2, the eigenvalues of the generated Hessian approximations are bounded above and away from zero.The proof studies B_k = H_k^-1, the direct Hessian approximation, rather than the inverse approximation H_k.Source: §A.2 · p. 10
• The trace and determinant bounds imply that all B_k have largest eigenvalues uniformly bounded above and smallest eigenvalues uniformly bounded away from zero.The proof derives these bounds using the L-BFGS update and the assumptions on sub-sampled Hessians.Source: §A.2 · pp. 11–12

A.3 Proof of Theorem 3.2 (Strongly Convex Case)

• With Assumptions A, the multi-batch L-BFGS iterates converge linearly to a neighborhood of the optimal solution.The theorem is stated for Assumptions A.1–A.4 and the minimizer w⋆ of F.Source: §A.3 · p. 12
• Reducing the expected function value relative to the previous iterate requires the step length to lie in a specified range.The proof takes expectations over sampled batches and the history from the initial iterate.Source: §A.3 · p. 13

A.4 Proof of Lemma 3.3 (Nonconvex Case)

• Under the stated assumptions and cautious update strategy, the Hessian approximations have eigenvalues bounded above and away from zero.The skipping mechanism bounds the curvature-pair quantity used to keep the initial Hessian approximation bounded.Source: §A.4 · p. 13

A.5 Proof of Theorem 3.4 (Nonconvex Case)

• Theorem 3.4 establishes a result on gradient-norm behavior under its assumptions and the condition that the inverse Hessian update is skipped when specified.Source: §A.5 · p. 14

B Extended Numerical Experiments - Real Datasets

• Further numerical experiments cover listed datasets, with notation for sample count, parameter dimension, process count, batch fraction, and overlap fraction.Table 1 gives basic dataset statistics.Source: B Extended Numerical Experiments -… · p. 16, Table 1 · p. 16

• The experiments compare robust L-BFGS, L-BFGS without sample consistency, multi-batch gradient descent, and serial SGD.The inconsistent L-BFGS variant computes gradient differences using different samples; gradient descent sets Hk = I, while serial SGD uses one sample per iteration.Source: §B.1 · p. 16
• The plots track gradient-norm evolution across step lengths, batch fractions, and overlap fractions, with average and best/worst performance shown over 10 runs.The figures vary α, r, and o across the specified settings on datasets including ijcnn1, cov, news20, and rcvtest.Source: §B.1 · p. 16, Figure 5 · p. 17, Figure 6 · p. 18
• Robust L-BFGS performs best for the most part with step size α = 1.Source: §B.1 · p. 16

B.2 Fault-tolerant L-BFGS Implementation

• On the shared cluster, computation and communication times are more stochastic and unbalanced, with some minimum-to-maximum differences of an order of magnitude or more.The paper identifies using only updates returned within a preallocated time budget as a natural fault-tolerant choice for this setting.Source: §B.2 · p. 26, Figure 14 · p. 26
• Across five datasets, robust multi-batch L-BFGS is not affected much by node failure probabilities p from 0.1 to 0.5.Source: Figure 15 · p. 27, Figure 16 · p. 27, §B.2 · p. 27

C.1 Strong Scaling

• As process count increases, gradient and L-BFGS-direction compute times decrease, but combined cost rises slightly; at large K, r = 10% provides too little local work to overcome communication cost.Source: Figure 20 · p. 30, §C.1 · p. 30

• At K = 128 and r = 10%, with 192GB of data, nearly 20GB are processed per iteration in less than 0.1 seconds, implying an epoch takes around 1 second.The problem dimension is fixed while data sparsity decreases as MPI processes increase; input size is 1.5GB per process. Communication overhead grows with K, while gradient compute time stays almost constant.Source: §C.2 · p. 30

C.3 Increasing Problem Dimension, Fixed Data Size and K

• Including communication time, both gradient and L-BFGS direction computation times increase as dimension d increases.Figure 22 includes communication time in the +C measurements.Source: §C.3 · p. 31, Figure 22 · p. 31
• Without communication time, increasing dimension d has a mild effect on gradient computation time and a more apparent effect on L-BFGS direction computation time.Source: §C.3 · p. 31, Figure 22 · p. 31
• The experiment fixes data size at 29GB and uses K = 8 MPI processes with n = 107 samples, each containing 200 non-zero elements.Source: §C.3 · p. 31, Figure 22 · p. 31