Source-linked AI summary
A Lower Bound for the Optimization of Finite Sums
Alekh Agarwal, Leon Bottou
TL;DR
The paper asks how much finite-sum structure can improve optimization and what limits apply to algorithms with incremental access. It defines an IFO model and derives a lower bound by reducing finite-sum optimization to smooth, strongly convex first-order problems; the bound is near existing IFO upper bounds, but no method has a precisely matching complexity bound.
Problem
The paper asks how much better algorithms can do when optimizing finite sums than general stochastic or batch optimization bounds indicate.
Source: §1 · p. 2Method
The proof constructs separable component functions on disjoint bases, making IFO optimization equivalent to optimizing each component with a standard first-order oracle.
Source: §4 · p. 9Results
The lower bound is not far from IFO upper bounds but has no precisely matching upper bound; for i.i.d.-data sums, worst-case near-optimal ASDCA can often be much worse than SAG and SVRG.
Source: §1 · p. 2, §5 · p. 12Takeaways & Limitations
Accounting for problem-dependent constants matters: IFO methods improve on optimal first-order methods that ignore finite-sum structure in ill-conditioned problems.
Source: §5 · p. 13The constructed quadratic can be solved by conjugate gradient with a nearly matching upper bound, so improving the lower bound requires modifying the construction.
Source: §2 · p. 5
Abstract
from arXiv · showhide
This paper presents a lower bound for optimizing a finite sum of $n$ functions, where each function is $L$-smooth and the sum is $\mu$-strongly convex. We show that no algorithm can reach an error $\epsilon$ in minimizing all functions from this class in fewer than $\Omega(n + \sqrt{n(\kappa-1)}\log(1/\epsilon))$ iterations, where $\kappa=L/\mu$ is a surrogate condition number. We then compare this lower bound to upper bounds for recently developed methods specializing to this setting. When the functions involved in this sum are not arbitrary, but based on i.i.d. random data, then we further contrast these complexity results with those for optimal first-order methods to directly optimize the sum. The conclusion we draw is that a lot of caution is necessary for an accurate comparison, and identify machine learning scenarios where the new methods help computationally.
1. Introduction
Finite-sum optimization has structure that distinguishes it from general stochastic and batch optimization, motivating a search for its fundamental complexity limits. The introduction defines an incremental oracle model and previews a lower-bound analysis alongside cautions about comparing complexity guarantees across models.
1. Introduction
- Finite-sum methods can have stochastic-cost iterations and linear convergence, despite stochastic optimization lower bounds of Ω(1/k), because the finite-sum structure differs.The paper calls this setting incremental optimization.Source: §1 · p. 2
- The paper asks how much finite-sum structure can improve optimization and whether existing stochastic or batch lower bounds can be specialized to this function class.It introduces the Incremental First-order Oracle (IFO) model, where an algorithm chooses a component index and point for an oracle query.Source: §1 · p. 2
- The lower bound is described as not far from IFO upper bounds O((n + L/µ)log(1/ε)) for SAG, SVRG, and SAGA [Schmidt et al., 2013].ASDCA and SPDC upper bounds are closer, but those methods are not IFO algorithms; no precisely matching upper bound is known.Source: §1 · p. 2
- The paper argues that comparing standard first-order and IFO complexity models requires caution, since worst-case IFO guarantees may not capture typical machine-learning performance.It also plans to identify regimes where IFO and standard first-order methods have different strengths and weaknesses.Source: §1 · p. 3
- Earlier work on smooth, strongly convex optimization focused on restricted subclasses of first-order methods, including SDCA but excluding accelerated variants.The paper says it discusses the technical distinctions after its main result.Source: §1 · p. 3
- The paper provides a self-contained proof of a variation on smooth, strongly convex black-box first-order complexity, then reuses its construction for each component function.The proof appears in Appendix A and is used to build the main lower-bound construction.Source: §1 · p. 3
2. Setup and main result
The paper studies finite sums with convex smooth components and a smooth, strongly convex aggregate, using indexed component queries through an incremental first-order oracle (IFO). It establishes a query lower bound with an n-dependent cost and further work that grows with tighter accuracy and worse conditioning.
2. Setup and main result
- Each component g_i is convex and (L−µ)-smooth, while their aggregate is µ-strongly convex and L-smooth, placing the finite-sum class inside the general smooth strongly convex class.The paper notes that this inclusion can be strict, particularly when the aggregate has better smoothness than its components.Source: §2 · p. 3
- An IFO algorithm accesses the objective through calls indexed by component, and SAG, SVRG, and SAGA qualify while dual coordinate methods do not.The oracle returns component-level information; the algorithm’s specification depends on the objective only through IFO calls.Source: §2 · pp. 3–4
- At least n queries are needed to see every component, with additional work that grows as the target accuracy tightens, n increases, or conditioning worsens.The lower bound’s first term accounts for one query per component; its accuracy-dependent term increases with n and the L/µ ratio.Source: §2 · p. 4
- Nesterov’s optimal gradient method uses at most O(n√κ log(1/ε)) IFO calls, with at most O(√n) suboptimality against the lower bound.The comparison is qualified because the aggregate objective may have a better condition number than the surrogate κ=L/µ.Source: §2 · p. 5
- SAG, SVRG, and SAGA have O((n+κ)log(1/ε)) guarantees, while ASDCA and SPDC are reported to attain a closer O(n+√(nκ)) upper bound.The paper identifies a remaining gap between known upper bounds and the lower bound.Source: §2 · p. 5
- For the constructed quadratic instance, conjugate gradient descent nearly matches the lower bound, so improving it requires changing the construction.Source: §2 · p. 5
- The infinite-dimensional ℓ2 setting rules out methods that terminate exactly in a number of iterations determined only by dimension, while the bound applies beyond stationary methods.The paper contrasts this scope with Arjevani (2014), whose stationary-method restriction limits adaptive component sampling.Source: §2 · p. 5
- The methods are compared by batch complexity, counting how many batches of n IFO calls are needed to reach the target optimization error.The accompanying table compares batch complexities and indicates whether a method adapts to µ_f or L_f.Source: Table 1 · p. 6
3. Consequences for optimization in machine learning
The comparisons depend on problem-specific smoothness and curvature, so incremental methods’ advantages vary by regime and are subtler than worst-case bounds suggest. The authors caution that their comparisons omit constants and sometimes logarithmic factors, and cover worst-case component functions.
Batch-complexity comparison
- Incremental and batch methods use different problem-dependent constants: incremental methods rely on component smoothness L, while coordinate ascent analyses use μ rather than additional curvature in μ_f.The full objective’s smoothness and strong-convexity constants need not equal L and μ; L upper-bounds L_f and μ lower-bounds μ_f.Source: §3 · p. 6
Problems with κ = O(n)
- When κ = O(n), incremental methods attain ˜O(log(1/ε)); AGM has similar complexity when the population problem is well-conditioned, while incremental methods benefit over batch methods in this regime.For poorly conditioned population problems, the complexities of accelerated ASDCA and SPDC are hard to distinguish from SAG or SVRG.Source: §3 · p. 8
Problems with large κ
- For large κ, ASDCA and SPDC can be disadvantaged because SAG and AGM exploit strong convexity from the average loss, and SAG has a better bound than AGM for poorly conditioned population problems.The passage says Γ_ASDCA can grow arbitrarily large as κ_i grows, while SAG and AGM contraction factors do not grow with n.Source: §3 · p. 8
High-dimensional settings
- In high-dimensional settings with n/d ≪ 1, the averaged-loss Hessian has a non-trivial null space, limiting global strong convexity; restricted curvature conditions may restore comparisons resembling Table 2.The authors leave development of this restricted-structure comparison to the reader.Source: §3 · pp. 8–9
Overall comparison
- SAG has favorable complexity across the regimes considered despite better worst-case bounds for ASDCA and SPDC, reflecting its adaptation to problem curvature.For ill-conditioned population problems with appropriately bounded data, SAG also improves on AGM’s complexity.Source: §3 · p. 9
Scope of comparisons
- The comparisons ignore constants and sometimes logarithmic factors, and incremental worst-case bounds cover arbitrary component functions rather than functions based on i.i.d. data.The authors identify potentially better results for i.i.d. data as an open opportunity.Source: §3 · p. 9
4. Proof of main result
The proof constructs a finite-sum objective whose components act on disjoint coordinate subsets, then relates optimization of the sum to separate first-order problems. A classical smooth, strongly convex lower bound on those component problems yields the finite-sum lower-bound argument, including a separate query-count contribution when fewer than n components are queried.
4. Proof of main result
- The proof builds disjointly supported component functions so that optimizing the finite sum under an IFO can be related to optimizing each component with a standard first-order oracle.The component functions are constructed to be smooth and strongly convex, allowing invocation of the classical first-order lower bound.Source: §4 · p. 9
4.1 Construction of a separable objective
- The construction uses orthonormal coordinate families and defines separable functions; Proposition 1 establishes that the constructed functions belong to the required function class.The bases assigned to the component functions are disjoint.Source: §4.1 · pp. 9–10
4.2 Decoupling the optimization across components
- Because the constructed components act on disjoint coordinate subsets, an algorithm for the sum implicitly solves each component problem, and an IFO query reveals no information about other components.Knowing μ lets the algorithm recover the component oracle information from the IFO response.Source: §4.2 · pp. 10–11
4.3 Proof of Theorem 1
- The proof applies the Nemirovsky–Yudin lower bound to component problems; when K < n, at least one component is unqueried, yielding the n-query contribution to the corollary.The general proof constructs a resisting oracle and combines the componentwise argument with the case where each component has been queried.Source: §4.3 · pp. 11–12
5. Discussion
The paper concludes that finite-sum structure can improve training-error optimization, but that worst-case bounds do not by themselves settle which methods perform best on random-data problems. It leaves open questions about sharper bounds for random data and about incremental methods’ test-error properties.
Main conclusions
- For i.i.d. random-data sums, the comparisons are mixed: worst-case near-optimal methods such as ASDCA can be worse than SAG and SVRG, while SAG improves on optimal first-order methods in ill-conditioned problems.The latter comparison is for methods agnostic to finite-sum structure.Source: §5 · pp. 12–13
- Different methods can have substantially different problem-dependent constants, and accounting for these opportunities may inform further algorithms and analyses.The paper identifies this as a potential direction rather than a demonstrated outcome.Source: §5 · p. 13
Open questions
- The paper does not study test error, and reports no clear comparison of incremental methods’ efficacy on that measure; it identifies direct test-error analysis as future work.The authors distinguish test error on unseen data from optimization of the training objective.Source: §5 · p. 13
- The authors ask whether random-data components permit better complexity bounds or let incremental methods exploit global rather than local smoothness.They also ask whether IFO upper bounds can be improved or whether a gap from dual-coordinate methods is fundamental.Source: §5 · p. 13
Appendix A. Optimization of a strongly convex smooth functions
The appendix gives a derivation of the smooth, strongly convex first-order lower bound without assuming iterates lie in the span of prior gradients. Its proof strategy uses a resisting oracle and a span argument to establish the bound needed for Theorem 1.
Appendix A
- The derivation avoids the usual assumption that successive points lie in the span of previously returned gradients, which is important for Theorem 1.Theorem 1 makes no such assumption.Source: Appendix A · p. 15
- The oracle supplies function values and gradients at algorithmically chosen points, and the formulation applies to strongly convex functions represented using a convex function g.The paper notes that the oracle could equivalently reveal g and its gradient because μ is known.Source: Appendix A · p. 15
- The proof first forces the final query into the span of prior iterates and gradients, then constructs a resisting oracle whose final query lies in that span.These steps reduce the lower-bound argument to a setting where the classical first-order result applies.Source: Appendix A · p. 15
A.1 Restriction of final solution to span
The section shows that, without loss for the lower-bound analysis, an algorithm’s final estimate can be restricted to the span of its queries and oracle gradients. It also establishes symmetry of the compatible-solution set around that span.
A.1 Restriction of final solution to span
- The compatible-solution set Hγ is symmetric around the query-and-gradient span P.The reflection is defined using the orthogonal projection onto P.Source: §A.1 · pp. 15–16
- Restricting the span condition to the final step makes the analysis more general than Nesterov’s assumption that all iterates lie in previous-gradient spans.The paper argues this restriction is imposed almost without loss of generality.Source: §A.1 · p. 16
- Any K-call algorithm can be replaced by one whose final estimate lies in the span of its query points and oracle gradients, with the same number of calls.The proof chooses the center of the smallest ball enclosing the set of compatible minimizers.Source: §A.1 · p. 16
A.2 Construction of a resisting oracle
The resisting oracle builds hard instances by applying Nesterov’s function to coordinates in adaptively constructed orthonormal bases. Its query-and-gradient spans grow in a controlled way, enabling the optimum to be placed far from the algorithm’s information span.
A.2 Construction of a resisting oracle
- The oracle applies Nesterov’s function to rotated coordinates, choosing orthonormal operators so the constructed optimum can lie far from the algorithm’s query-and-response span.The construction uses Gram-Schmidt orthogonalization to extend the basis.Source: §A.2 · p. 17
- At each call, the resisting oracle returns function and gradient values from an objective consistent with all earlier oracle answers.It incrementally constructs orthonormal families and defines each objective using the coordinates of the query in a completed basis.Source: §A.2 · pp. 17–18
- After k calls, the constructed subspace Sk is the span of x0 through xK−1 and their gradients f′(x0) through f′(xK−1), with dimension at most 2k + 2.Property (a) holds by construction.Source: §A.2 · p. 18
A.3 Proof of Theorem 2
The proof combines the span restriction with a resisting oracle that places the optimum far from that span. The resulting black-box lower bound is stated for the dimension-independent guarantee on smooth, strongly convex functions.
A.3 Proof of Theorem 2
- The resisting-oracle construction places the optimum as far as possible from the algorithm’s 2K + 2 dimensional information span, supplying the hard instance for the theorem.The proof then applies the span restriction and selects an appropriate constant ρ.Source: §A.3 · pp. 18–19
- The corollary gives a lower bound on calls needed to guarantee relative error ε for first-order black-box optimization of smooth, strongly convex functions.The supplied statement gives the bound only as an incomplete Ω expression.Source: §A.3 · p. 19
- Because the lower bound is established on ℓ2, it is the best dimension-independent guarantee for first-order black-box algorithms in this function class.The scope is L-smooth, μ-strongly convex functions.Source: §A.3 · p. 19