Source-linked AI summary
Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
Aaron J. Defazio, Tibério S. Caetano, Justin Domke
TL;DR
The paper studies how to exploit finite-sum structure to optimize smooth strongly convex problems more efficiently than black-box methods. It introduces Finito, analyzes its convergence under a sufficiently large-data condition, and examines randomized and permuted access schemes. Finito has tight theoretical and practical behavior, while sampling without replacement yields speedups of up to two in practice but lacks supporting theory.
Problem
Finite-sum optimization can exploit structure beyond treating the objective as a single black-box function, but randomized access is central to the analyzed methods.
Method
The paper introduces Finito for smooth strongly convex finite sums and studies its convergence, oracle lower bounds, randomized access, and sampling without replacement.
Results
Finito's practical convergence rate is at most twice as good as its theoretical prediction, while sampling without replacement gives speedups of up to a factor of two in practice.
Takeaways & Limitations
Under the big data condition, Finito achieves a rate of 0.6065 per epoch in expectation and can be 124x faster than a black-box rate of 0.996 in the stated example.
Takeaways & Limitations
The method's step-size behavior when the big data condition fails is conjectured rather than theoretically established, and the permuted case has no supporting theory.
Abstract
from arXiv · showhide
Recent advances in optimization theory have shown that smooth strongly convex finite sums can be minimized faster than by treating them as a black box "batch" problem. In this work we introduce a new method in this class with a theoretical convergence rate four times faster than existing methods, for sums with sufficiently many terms. This method is also amendable to a sampling without replacement scheme that in practice gives further speed-ups. We give empirical results showing state of the art performance.
1. Introduction
Finite-sum structure enables optimization methods that improve on black-box approaches for smooth strongly convex problems with sufficiently many data points. Finito stores information about individual data points, has theoretically tight practical performance, and avoids the extensive tuning associated with SGD.
- Finite sums arise naturally in empirical risk minimization, with one term corresponding to each data point.
- SAG improves over black-box optimization for smooth strongly convex problems when sufficiently many data points are available, often by a factor of 10 or more.
- The big data condition requires the dataset size to be on the same order as the problem's condition number.
- Finito and SAG store additional information for each data point instead of treating every revisit as entirely new information.
- Finito's practical convergence rate is at most twice as good as its theoretical prediction, unlike methods whose empirical performance substantially exceeds weak theoretical bounds.
- Finito requires less tuning than SGD, but the paper does not propose it as a replacement for SGD outside convex problems.
2. Algorithm
Finito is an incremental method for differentiable finite-sum problems that stores per-data-point information and uses a fixed step size under a big data condition. Its theory gives a convergence-rate proof, while its practical use is limited when the condition fails or stored points are dense.
- Problem class: Finito targets differentiable convex finite sums whose component functions have Lipschitz gradients and strong convexity, subject to the big data condition.The condition requires the dataset size to be on the same order as the condition number L/s.
- Algorithm: The algorithm stores tables of per-data-point values and updates one randomly selected index at each iteration.The update procedure first changes w, samples an index j, and replaces only φ_j with the current iterate.
- Theory: Finito has a convergence-rate proof, with the main theorem allowing α = 2 when the big data condition holds with β = 2.The paper presents this as its main theoretical result.
- Theory: 1 − 1/(2n)^n ≈ exp(−1/2) = 0.606 per epoch, reducing the error bound by more than 148x after 10 epochs.The cited rate is reported in the paper’s comparison of Finito’s per-epoch convergence behavior.
- Practical use: A fixed step size α = 2 can be used without tuning when the quadratic regularizer supplies a known strong convexity constant and the big data condition holds.When the condition does not hold, the authors conjecture that the step size must be reduced proportionally and may need empirical testing.
- Limitations: Finito can require substantial memory because it stores φ_i, and the authors do not recommend it when gradients are sparse but φ_i are not.The stored points can create significant additional memory usage despite sparse gradients.
3. Randomness is key
Random index selection is essential for the practical convergence behavior of SAG and Finito. Sampling without replacement can make Finito substantially faster in practice, although the paper reports no theory supporting that case.
- Randomness: Neither SAG nor Finito works in practice with the same ordering each pass or with the non-random access schemes tested.The paper emphasizes that random index selection is crucial even though the optimization problem itself is offline.
- Randomness: Reducing the step size by a factor of n permits non-randomized orderings but produces an extremely slow method in the MISO case.A similar step-size reduction also gives convergence under non-randomized orderings for SAG.
- Permuted sampling: Sampling without replacement gives Finito speedups of up to a factor of two in practice, unlike its reported effect on SAG.The authors call this the permuted case because the data are re-permuted after each pass.
- Permuted sampling: The faster convergence of Finito under sampling without replacement lacks theoretical support in the paper.The authors state that they are unaware of an analysis proving faster rates for this sampling scheme.
- Related methods: Permuted SDCA can sometimes produce a large speedup over uniform random sampling, but it appears less reliable than with Finito.This comparison is based on the experiments reported in Section 7.
4. Proximal variant
The proximal variant extends Finito to composite objectives with a convex, potentially nonsmooth regularizer by replacing the standard minimization step with a proximal update. The paper reports empirical support for the non-proximal convergence rate but no supporting theory.
- Problem setting: The proximal variant targets composite problems with a convex regularizer r that need not be smooth or strongly convex.Such problems are commonly handled with proximal algorithms when the proximal operator for r has a closed-form solution, including L1 regularization.
- Standard update: Finito’s update can be interpreted as minimizing a surrogate quantity with respect to x while holding the stored points φ_i fixed.This surrogate is related to the upper bound minimized by MISO, but uses αs instead of L.
- Proximal update: The composite extension expresses the modified minimizer using the proximal operator.This preserves the gradient-descent-like structure of the standard update while incorporating r.
- Status: No theory has yet been developed for proximal Finito, although empirical evidence suggests the same convergence rate as in the non-proximal case.The claim is empirical rather than a proved convergence guarantee.
5. Convergence proof
The convergence proof builds an expected-decrease argument around a Lyapunov function that combines several error and gradient-related terms. Under the theorem’s assumptions and initialization, this yields the stated convergence result by unrolling the one-step bound.
- Proof ingredients: The proof takes expectations over the uniformly random index selected at each iteration and establishes lemmas for the expected step and variance decomposition.The expected w-step is a gradient-descent step, unlike the corresponding SAG equality.
- Lyapunov argument: The Lyapunov function T = T1 + T2 + T3 + T4 combines four terms and is constructed to decrease in expectation at every iteration.The remaining gradient-norm term is non-positive under the stated assumptions.
- One-step bound: The proof groups the lemmas’ terms, cancels matching components, and applies standard inequalities to obtain the one-step convergence relation.The cancellations include terms from the variance decomposition and the auxiliary inequalities used in the appendix.
- Lower bound: The auxiliary function R(x) is evaluated at selected points to obtain a lower bound on f(w*) using strong convexity.Convexity of R supports the lower-bounding step in the Lyapunov analysis.
- Initialization and corollary: Theorem 4 applies the result when all initial stored points φ_i^(0) are equal and the assumptions of Theorem 2 hold.The theorem is obtained by unrolling the one-step result and controlling the initial Lyapunov value.
6. Lower complexity bounds and exploiting problem structure
The paper separates black-box lower bounds from finite-sum gains: strong convexity plus a sufficiently large dataset permits faster expected rates, whereas smooth convex nonstrongly convex problems retain the black-box lower bound. The analysis also distinguishes randomized oracle access from controlled sampling.
- Strongly convex finite sums: For smooth strongly convex problems, black-box first-order rates are essentially optimal without additional structure, while finite-sum structure enables faster rates.The finite-sum setting is modeled through the stochastic oracle class FS1,1.
- Strongly convex finite sums: 0.6065 per epoch is Finito’s expected rate under the big data condition; with L/s = 1,000,000 and n ≥ 4,000,000, this is reported as 124x faster than the 0.996 black-box rate.The comparison is stated for the specific condition number and dataset size in the passage.
- Oracle classes: The FS1,1 oracle samples an index uniformly at random and returns the selected function value and gradient at the queried point.The alternative DS1,1 class supplies the index to the oracle and assumes access to true random indices.
- Nonstrongly convex case: The theory’s lower bound for smooth convex but nonstrongly convex finite sums matches the black-box lower bound in sufficiently high-dimensional spaces.The construction uses noninteracting component functions, preventing an optimization scheme from improving on separate in-order handling.
- Nonstrongly convex case: Strong convexity prevents the component functions from being noninteracting in the construction used for the nonstrongly convex lower bound.Each strongly convex component has a quadratic term acting on all dimensions.
7. Experiments
Experiments compare Finito with SAG, SDCA, and LBFGS on problems satisfying the big data condition. With permutation each pass, Finito shows a clear empirical advantage and stable convergence.
- Experimental setup: The experiments compare Finito, SAG, SDCA, and LBFGS on problems where the big data condition holds.The authors note that smaller step sizes may extend practical use beyond this theoretical setting.
- Step-size choices: SAG was evaluated across step sizes, while Finito used α = 2 as the fastest tested rate under the big data condition.Reducing α to 1 did not further improve Finito's convergence rate.
- Datasets: The datasets include three classification tasks and two regression tasks, with training sizes ranging from 5.0×10^4 to 5.3×10^5.The tasks use ijcnn1, covtype, MNIST, Million Song, and slice-localization data.
- Results: Finito, SAG, and SDCA often converge at similar rates without permutation, while LBFGS is not competitive with the incremental methods.Differences without permutation often arise from first-pass speed, after which convergence slopes are usually comparable.
- Results: With permutation each pass, Finito has a clear advantage and produces very flat convergence lines, indicating stable convergence.The reported advantage is empirical and concerns the permuted variants across the tested problems.
8. Related work
Related methods include classical incremental gradient algorithms, SAG, MISO, and SDCA. Their relationships to Finito involve convergence behavior, step-size choices, applicability, implementation complexity, and memory requirements.
- Incremental gradient methods: Classical incremental gradient methods resemble SGD on finite sums, but SGD does not yield linear convergence on strongly convex problems.The paper describes these methods as the non-online analogue of SGD.
- MISO: MISO is essentially Finito with step sizes n times smaller, while Finito's larger step sizes fall outside MISO's upper-bound-minimization framework.The cited comparison also reports a related but weaker rate for MISO.
- SDCA: SDCA has fast convergence where applicable but requires convex conjugates and additional loss structure, increasing implementation complexity.SDCA applies only to linear predictors in the paper's comparison.
- SDCA: For sparse datasets, SDCA may be preferable to Finito because of Finito's memory requirements.The paper specifically identifies sparse data as a setting where SDCA is a better choice.
- Empirical comparisons: The paper includes convergence-rate plots for MNIST, Covtype, ijcnn1, Million Song, slice, and aggregate test problems.The supplied figure labels identify the datasets and the convergence-rate plot.
9. Conclusion
The paper presents Finito for minimizing smooth strongly convex finite sums with sufficiently many terms, develops lower-complexity-bound theory, and evaluates its empirical performance.
- Contribution: Finito targets finite sums of smooth strongly convex functions when the summation contains sufficiently many terms.This conclusion states the method's supported problem class.
- Contribution: The paper develops theory for lower complexity bounds on this problem class and reports empirical performance of the method.The conclusion presents both theoretical and empirical components.