Source-linked AI summary
Hybrid Deterministic-Stochastic Methods for Data Fitting
Michael P. Friedlander, Mark Schmidt
TL;DR
Large-scale data fitting makes full-gradient evaluations expensive, while incremental methods can slow near a solution. The paper controls gradient error through growing samples and implements the approach with quasi-Newton directions; numerical experiments report benefits, including outperforming the deterministic method after 20 data passes in a small seismic inversion example.
Problem
Full-gradient evaluations are expensive for large datasets or costly individual functions, while incremental-gradient methods may need many more iterations to reach comparable accuracy.
Method
The method gradually increases the sample size controlling the approximate-gradient error and uses scaled limited-memory quasi-Newton directions with a heuristic line search.
Results
After 20 passes through a small seismic-inversion dataset, the hybrid method clearly outperforms the deterministic method.
Takeaways & Limitations
Growing the sample size can preserve full-gradient convergence rates while retaining rapid initial progress from incremental-gradient iterations.
Takeaways & Limitations
The convergence analysis requires a fixed steplength, although the Lipschitz constant is usually unknown and dynamic steplengths are often more effective in practice.
Abstract
from arXiv · showhide
Many structured data-fitting applications require the solution of an optimization problem involving a sum over a potentially large number of measurements. Incremental gradient algorithms offer inexpensive iterations by sampling a subset of the terms in the sum. These methods can make great progress initially, but often slow as they approach a solution. In contrast, full-gradient methods achieve steady convergence at the expense of evaluating the full objective and gradient on each iteration. We explore hybrid methods that exhibit the benefits of both approaches. Rate-of-convergence analysis shows that by controlling the sample size in an incremental gradient algorithm, it is possible to maintain the steady convergence rates of full-gradient methods. We detail a practical quasi-Newton implementation based on this approach. Numerical experiments illustrate its potential benefits.
1. Introduction.
The paper studies data-fitting problems where full-gradient evaluations are expensive and incremental methods trade cheaper iterations for slower eventual convergence. It develops growing-sample strategies that control gradient error, preserve favorable convergence rates, and support a practical quasi-Newton implementation.
- Motivation: Large measurement sets or costly individual evaluations make full objective and gradient calculations expensive, motivating incremental-gradient methods.Incremental iterations can evaluate gradients for only part of the data.
- Motivation: Incremental-gradient iterations cost M times less than full-gradient iterations, producing rapid initial progress but potentially requiring many more iterations for comparable accuracy.Full-gradient methods eventually dominate because they have a faster convergence rate.
- Hybrid approach: The proposed hybrid method begins with small samples and increases the sample size over iterations to retain rapid initial progress while preserving full-gradient convergence rates.The sample size controls the gradient approximation error.
- Convergence analysis: A constructed sequence of gradient-error bounds yields a strong linear rate arbitrarily close to the error-free gradient method without requiring an exact gradient on any iteration.The analysis also allows noisy iterations that may increase the objective and provides a non-asymptotic rate.
- Convergence analysis: Without strong convexity, a summable error-bound sequence is sufficient to maintain the deterministic gradient method’s sublinear convergence rate.The convergence statement also applies to the iterate attaining the lowest function value, which need not be the final iterate.
- Implementation and evaluation: The paper presents a limited-memory quasi-Newton implementation with a heuristic line search and reports numerical comparisons against incremental-gradient and deterministic quasi-Newton methods.The work positions its growing-sample strategy as a theoretically analyzed and practically implemented approach.
2. Convergence analysis.
The analysis bounds convergence when gradients contain deterministic or stochastic errors, showing that decreasing error can preserve sublinear or linear rates. Strong linear guarantees permit nonzero error but require bounds involving problem conditioning and distance to optimality.
- The objective convergence rate is limited by both the decay rate of gradient error and the corresponding noiseless algorithm rate.
- If the error bound B_k decreases linearly, the approximate-gradient method achieves a linear convergence rate.
- Strong linear convergence can be obtained by controlling error bounds using the conditioning parameters µ and L and a lower bound on suboptimality.
- The fastest rate requires exact gradients, while any slower target rate below µ/L permits nonzero gradient error when the lower bound on suboptimality is positive.
- Summable gradient residuals preserve the O(1/k) rate for the average iterate without requiring strong convexity.
- The lowest-function-value iterate also achieves the convergence rate, but it need not be the final iterate.
3. Application to sample-average gradients.
Sample-average gradients control approximation error through batch size. Increasing the sample size can yield weak or strong linear convergence, with stochastic sampling providing a tighter expected error bound than deterministic sampling.
- Increasing the sample size reduces sampled-gradient error, allowing batch size to control the per-iteration gradient residual.
- A geometrically increasing sample size is sufficient for weak linear convergence under deterministic sampling.
- The objective error decreases at twice the rate at which the sample size increases.
- A more controlled sample-size schedule yields strong linear convergence under deterministic sampling.
- Smaller samples suffice when the individual functions f_i are similar, whereas dissimilar functions require larger samples.
- Uniform sampling without replacement gives a strictly tighter expected gradient-error bound than the deterministic bound.
- Figure 3.1 compares deterministic and stochastic error bounds and their sample-size schedules for M = 10^4.
4. Practical implementation.
The practical method combines curvature-aware quasi-Newton directions with a sampled-objective linesearch and progressively larger samples. Although true-objective decrease may fail initially, increasing the sample size eventually restores conventional linesearch behavior and convergence guarantees.
- Practical modifications: The implementation uses curvature-scaled search directions and allows the stepsize to vary.These modifications extend approximate gradient descent with curvature information and adaptive step selection.
- Quasi-Newton direction: A quasi-Newton approximation Hk to the Hessian supplies the search direction dk by solving the scaled-direction system.The approximation is updated recursively through an update formula U.
- Quasi-Newton direction: Limited-memory BFGS maintains the previous ℓ= 10 pairs (sk, yk), recursively updating Hi+1 = U(Hi, si, yi).Updates are skipped when necessary to preserve positive definiteness and a bounded approximation.
- Varying stepsize: The implementation enforces an Armijo-type descent condition on the sampled objective rather than requiring a full true-objective evaluation at every trial.Its initial trial step is α = |Bk−1|/|Bk|, rather than the usual α = 1 test in deterministic quasi-Newton methods.
- Varying stepsize: Because Bk may contain only a fraction of observations, sampled descent can initially be nonmonotonic in the true objective.As the sample size grows, the procedure eventually becomes a conventional true-objective linesearch and inherits global and local convergence guarantees.
- Numerical experiments: Numerical experiments apply the incremental-gradient method with a growing sample size to multiple data-fitting applications.The test problems are summarized in Table 5.
5. Numerical experiments.
The experiments compare deterministic, stochastic, and hybrid optimization across logistic-regression, conditional-random-field, and nonlinear least-squares data-fitting problems. The hybrid method shows rapid initial progress while retaining steady progress in binary logistic regression, and it outperforms the deterministic method after 20 passes in the seismic example.
- Test problems: The first four experiments cover binary and multinomial logistic regression plus chain-structured and general conditional random fields.Applications include spam classification, digit classification, noun-phrase chunking, and image denoising.
- Scope and limitations: The seismic inversion experiment does not satisfy the central convexity assumption, and the general CRF computation can have runtime exponential in graph tree-width.The seismic objective is nonconvex, while general CRF partition-function computation is in ♯P and is feasible for two-dimensional lattices only when one dimension is very small.
- Optimization strategies: The experiments compare deterministic full-gradient, stochastic single-sample, and hybrid growing-sample optimization methods.The deterministic method uses true function and gradient evaluations, the stochastic method uses a randomly selected single sample, and the hybrid sample size grows from one toward all observations.
- Binary logistic regression: In binary logistic regression, the hybrid method makes rapid initial progress and then continues with steady progress similar to the deterministic method.The stochastic method is evaluated with three fixed steplengths, while the deterministic and hybrid methods are less sensitive to the initial step size.
- Multinomial logistic regression: The multinomial logistic-regression results on MNIST show trends similar to the binary logistic-regression experiments.The MNIST data set contains 70,000 28-by-28 digit images, and the experiment uses λ = 1.
- Seismic inversion: After 20 passes through the data, the hybrid method clearly outperforms the deterministic method on the seismic inversion experiment.The example uses M=101 sources and 8 frequencies; after 60 passes, the best methods reach similar residuals, but that requires a prohibitive number of Helmholtz solves.
6. Discussion.
The discussion identifies extensions of the controlled-error analysis beyond the settings studied, while clarifying its current noise assumptions and broader applicability.
- Analogous controlled-error convergence analyses may apply to proximal-gradient methods for convex constraints, non-differentiable composite optimization, and mirror descent.Examples include 1-norm regularization and optimization with simplex constraints.
- The current results cover bounded noise or noise bounded in expectation, yielding convergence rates and expected convergence rates, respectively.
- The approach may also apply when objective evaluations have prescribed accuracy, using a sequence of progressively tighter function accuracies.