Tight Complexity Bounds for Optimizing Composite Objectives

Blake Woodworth; Nathan Srebro

Source-linked AI summary

Tight Complexity Bounds for Optimizing Composite Objectives

Blake Woodworth, Nathan Srebro

arXiv:1605.08003v3May 25, 2016math.OCcs.LGstat.ML

TL;DR

The paper asks how efficiently averages of convex component functions can be minimized under gradient and prox-oracle access, especially across deterministic and randomized algorithms. It develops upper and lower bounds, including smoothing-based non-smooth methods, and shows matching complexity up to logarithmic factors. The results establish optimality for accelerated finite-sum methods and show that prox access helps non-smooth optimization but is not needed for optimal smooth rates.

Problem
The paper studies complexity bounds for minimizing the average of m convex functions under component gradient and prox-oracle access, including the gap between deterministic and randomized optimization.
Method
The paper combines upper-bound algorithms, prox-based smoothing for non-smooth components, and general lower bounds over algorithms making gradient and prox queries.
Results
The bounds are matching up to logarithmic factors, establish optimality for accelerated SDCA, SVRG, and SAG in randomized finite-sum optimization, and establish optimality for deterministic smoothing algorithms on non-smooth objectives.
Takeaways & Limitations
Prox access can improve non-smooth complexity, whereas smooth optimal complexity is attainable with gradient access alone; deterministic non-smooth methods can also be fully parallelizable.
Takeaways & Limitations
The lower bounds require large dimension when algorithms are not assumed to keep queries in the span of previous oracle responses.

Abstract

from arXiv · show

We provide tight upper and lower bounds on the complexity of minimizing the average of $m$ convex functions using gradient and prox oracles of the component functions. We show a significant gap between the complexity of deterministic vs randomized optimization. For smooth functions, we show that accelerated gradient descent (AGD) and an accelerated variant of SVRG are optimal in the deterministic and randomized settings respectively, and that a gradient oracle is sufficient for the optimal rate. For non-smooth functions, having access to prox oracles reduces the complexity and we present optimal methods based on smoothing that improve over methods using just gradient accesses.

1 Introduction

The paper studies oracle complexity for minimizing averages of convex component functions, comparing deterministic and randomized algorithms and gradient versus prox access. It develops matching upper and lower bounds, showing that prox access helps for non-smooth objectives while gradient access suffices for optimal smooth rates.

The problem is to minimize the average of m ≥2 convex component functions using component gradient and prox oracles.
Matching upper and lower bounds hold up to a log factor across the considered function and algorithm classes.
Non-smooth prox access reduces the polynomial dependence on ǫ from 1/ǫ2 to 1/ǫ, or from 1/(λǫ) for λ-strongly convex functions.
For smooth functions, optimal worst-case complexity can be attained with component gradient access alone, using accelerated gradient methods.
Randomization can reduce the dependence on the number of components from linear in m to √m in the typically significant term.
The lower-bound analysis covers randomized algorithms making arbitrary gradient and prox queries without requiring iterates to lie in the span of prior responses.

2 Optimizing Smooth Sums

For smooth component functions, the paper reviews gradient-based methods that achieve the stated upper complexity bounds. Deterministic AGD uses exact full gradients, while randomized variance-reduced methods sample components and accelerate their convergence.

Component gradients can be combined into exact gradients of F, enabling AGD to achieve the deterministic upper bounds for smooth problems.
SAG, SVRG, and related randomized methods sample components while controlling gradient-estimator variance using the finite-sum structure.
Catalyst acceleration gives strongly convex objectives the randomized complexity summarized in Table 1.
Katyusha accelerates SVRG directly and avoids extraneous log factors.
Only component gradients are required by Katyusha and Catalyst-accelerated SAG or SVRG, while accelerated SDCA uses gradient and prox access.

3 Leveraging Prox Oracles for Lipschitz Sums

For Lipschitz components, prox access is used to smooth each function and optimize the resulting smooth sum. This improves over subgradient-only methods, while stochastic gradient descent can be preferable in large-component regimes.

Smoothing with prox oracles: Prox oracles smooth each L-Lipschitz component, enabling optimization of a new smooth sum that approximates the original objective.The approach uses gradients of the β-Moreau envelope obtained through prox access.
Algorithms: The resulting deterministic smoothing algorithm is presented as an explicit method for non-smooth composite optimization.The paper notes that this achieves the deterministic upper complexity indicated in Table 1.
Smoothing with prox oracles: Setting β = L^2/ε controls the smoothing error and reduces ε-optimization to optimizing the smoothed problem to ε/2 accuracy.The approximation satisfies ˜F(β)(x) ≤ F(x) ≤ ˜F(β)(x) + L^2/(2β).
Algorithms: AGD provides the deterministic upper complexity for the smoothed problem, while accelerated randomized methods such as Katyusha provide randomized bounds.Strongly convex objectives use increasing smoothing parameters to avoid a spurious logarithmic factor.
Regime comparison: O(L^2B^2/ε^2) or O(L^2/(λε)) makes stochastic gradient descent a better randomized alternative when m exceeds the corresponding threshold.The thresholds are m > L^2B^2/ε^2 and m > L^2/(λε), respectively.

4 Lower Bounds for Deterministic Algorithms

Deterministic lower bounds are constructed adversarially, forcing algorithms to discover orthogonal directions across query rounds. The resulting bounds cover non-smooth and smooth components under bounded-domain and strongly convex settings.

Adversarial construction: A deterministic adversary constructs a hard function adaptively from the algorithm’s behavior, keeping the algorithm far from optimality until sufficient oracle queries occur.The construction treats optimization as a game in which the oracle responses define the hard function progressively.
Adversarial construction: Each round ends after ⌈m/2⌉ distinct component functions are queried, independently of the algorithm’s querying strategy.Rounds partition the query sequence for the lower-bound analysis.
Non-smooth components: The construction chooses new orthonormal directions orthogonal to prior queried points, so the algorithm can learn direction v_r only after completing round r.The minimum is expressed through a sum of these directions, making undiscovered directions preserve suboptimality.
Non-smooth components: Ω(m) queries are required in every round because each newly relevant absolute-difference term appears in m/2 components but is hidden from deterministic query sequences.This yields the deterministic lower-bound mechanism for Lipschitz non-smooth objectives.
Non-smooth components: Theorems 1 and 2 establish deterministic lower bounds for convex L-Lipschitz objectives on bounded domains and for L-Lipschitz λ-strongly convex objectives.The bounds apply to algorithms accessing the component oracle hF.
Smooth components: For smooth objectives, replacing absolute differences with squared differences yields analogous deterministic lower bounds in both bounded-domain and strongly convex settings.Theorems 3 and its strongly convex counterpart use convex γ-smooth components.

5 Lower Bounds for Randomized Algorithms

Randomized lower bounds require hard instances chosen independently of the algorithm’s random choices. The constructions use many orthogonal subproblems or information-theoretic arguments to retain dependence on m.

Randomized constructions: Randomized lower-bound constructions must choose the hard function before observing the algorithm’s random choices, preventing adaptive orthogonality and query-order tricks.Random orthonormal directions provide near orthogonality with high probability in sufficiently large dimension.
Randomized constructions: A randomized algorithm can discover a term hidden in half the components with only two expected queries, so deterministic hiding does not preserve an m-dependent lower bound.This motivates replacing component-level hiding with many separate optimization problems.
Lipschitz components: Ω(m) separate optimization problems are created using pairs of functions operating on orthogonal subspaces.Each pair resembles the deterministic construction while preventing the algorithm from solving the full objective through a few component queries.
Lipschitz components: At least k + 1 queries are needed for each of at least m/4 function pairs, yielding Ω(mk) total queries before an ε-suboptimal solution can be found.The algorithm learns each pair’s new directions only through alternating queries to its two components.
Scope of the construction: Large dimension is required because the lower bounds omit the assumption that query points lie in the span of previous oracle responses.Under the span assumption, the necessary dimension is only on the order of the number of required oracle queries.

6 Conclusion

The paper gives a tight, up-to-log-factor understanding of finite-sum optimization with component prox oracles, including deterministic and randomized lower bounds. Its results establish optimality for accelerated randomized methods, deterministic smoothing methods, and a randomized lower-bound technique applicable beyond this setting.

6 Conclusion: Tight upper and lower bounds characterize finite-sum optimization with component prox-oracle access.The bounds match up to a logarithmic factor.
6 Conclusion: Randomization reduces the significant dependence on the number of components from linear in m to √m.The randomization is performed by the algorithm rather than by a stochastic oracle.
6 Conclusion: The deterministic non-smooth method is fully parallelizable, unlike optimal stochastic methods such as SDCA.It computes all m prox operations in parallel, averages smoothed-function gradients, and takes an accelerated gradient step.
6 Conclusion: The paper introduces a simple construction for randomized lower bounds that avoids requiring iterates to lie in the span of previous oracle responses.The construction uses ε-insensitive differences and may apply to randomized lower bounds in other settings.

A Upper bounds for non-smooth sums

Smoothing converts non-smooth finite sums into smooth approximations using prox access, enabling accelerated optimization with improved oracle complexity. The resulting methods achieve the stated upper bounds, while smoothing helps only when combined with acceleration.

A Upper bounds for non-smooth sums: A prox oracle yields the gradient of a smoothed component, allowing an L-Lipschitz finite sum to become an L^2/ε-smooth finite sum.Optimizing the smoothed objective to ε/2-suboptimality gives an ε-suboptimal solution for the original objective.
A Upper bounds for non-smooth sums: For λ-strongly convex components, AdaptSmooth solves O(log 1/ε) smooth strongly convex subproblems to avoid an extra logarithmic factor.Each subproblem reduces the suboptimality of a β_t-smooth, λ-strongly convex function by a factor of four.
A Upper bounds for non-smooth sums: Theorem 10 applies AdaptSmooth with AGD to obtain an ε-suboptimal solution for Lipschitz, strongly convex components using prox-oracle queries.The theorem covers arbitrary L, λ, ε > 0 and m ≥ 1.
A Upper bounds for non-smooth sums: Smoothing improves oracle complexity only when combined with accelerated methods.Non-accelerated gradient descent on the smoothed objective is no better than gradient descent applied directly to the original objective.

B.1 Non-smooth and not strongly convex components

For non-smooth, non-strongly-convex components, the paper constructs deterministic hard instances showing lower bounds for algorithms with gradient and prox access. The proofs use adversarially generated orthogonal directions and establish consistency of the oracle responses.

B.1 Non-smooth and not strongly convex components: Theorem 1 constructs convex L-Lipschitz components requiring Ω oracle queries to reach ε-suboptimality for deterministic algorithms.The construction chooses orthogonal directions adversarially according to the algorithm’s queries.
B.1 Non-smooth and not strongly convex components: Each deterministic oracle round queries about half the components, so progress is limited by both component coverage and the number of rounds.The lower-bound construction keeps unqueried directions hidden from the algorithm.
B.1 Non-smooth and not strongly convex components: The hard-instance oracle responses remain valid because the constructed subgradients and prox outputs agree with those of the fixed component functions.Lemmas 2 and 3 establish this consistency for queried vectors during each round.
B.1 Non-smooth and not strongly convex components: Theorem 2 extends the lower-bound construction to λ-strongly convex components through a reduction from the non-strongly-convex case.The proof adds a regularizer and derives a contradiction if the strongly convex problem could be solved too efficiently.

B.3 Smooth and not strongly convex components

The paper develops lower bounds for smooth finite-sum optimization against deterministic and randomized algorithms. Deterministic constructions hide orthogonal directions adversarially, while randomized constructions use random high-dimensional directions that each oracle response can reveal only one at a time.

B.3 Smooth and not strongly convex components: Theorem 3 gives a deterministic lower bound for convex γ-smooth components using a high-dimensional orthogonal-direction construction.The hard instance keeps the relevant direction orthogonal to the algorithm’s first m−1 queries.
B.3 Smooth and not strongly convex components: The simple smooth construction forces at least m queries before the algorithm can learn the hidden direction and reach an ε-suboptimal solution.Before identifying the direction, every iterate has objective value zero while the optimum is lower.
B.3 Smooth and not strongly convex components: Theorem 7 extends the smooth lower bound to γ-smooth, λ-strongly convex components with prescribed initial suboptimality.The added norm term scales query-point information without revealing the hidden directions.
B.3 Smooth and not strongly convex components: Randomized lower bounds replace adversarial orthogonalization with randomly drawn important directions in high dimensions.A query has a small inner product with a random unit vector with high probability, preventing the deterministic adversarial construction from being used directly.
B.3 Smooth and not strongly convex components: Each oracle access reveals at most one important direction with high probability, yielding an Ω(mk) access requirement for optimization.The component pairs are designed to satisfy the one-direction-per-query property.

C.1 Non-smooth and not strongly convex components

This section proves lower bounds for minimizing averages of convex, Lipschitz, non-smooth, non-strongly-convex components through the composite oracle. The construction yields hard instances whose required oracle complexity scales with the number of components and target accuracy.

Lower-bound construction: Theorem 5 constructs convex, L-Lipschitz component functions for which finding an ϵ-suboptimal point requires Ω oracle queries to hF.The hard instance is defined over a bounded domain, with dimension chosen sufficiently large.
Lower-bound construction: The proof uses randomly chosen orthonormal directions and paired component functions whose information is revealed progressively through oracle queries.Each pair acts on a separate subspace, and the construction controls the spans exposed by subgradients and prox queries.
Lower-bound argument: If too few directions are revealed, the iterate remains insufficiently aligned with the minimizer, so it cannot be ϵ-suboptimal for a substantial fraction of components.The argument bounds the number of vectors that can have sufficiently large inner products with an iterate after N queries.
Query-norm assumption: The lower-bound argument initially assumes bounded query norms, but a function modification makes queries outside the domain no more informative than queries on the boundary.Thus allowing unbounded query vectors does not improve the convergence rate for the constructed instances.
Strong convexity extension: Theorem 6 extends the lower bound to L-Lipschitz, λ-strongly convex components by adding a regularizer and reducing from the non-strongly-convex construction.The reduction preserves the relevant oracle-complexity contradiction for the strongly convex objective.

C.3 Smooth and not strongly convex components

This section establishes lower bounds for smooth, non-strongly-convex finite-sum optimization using randomized oracle algorithms. The construction hides component-specific directions so that insufficient queries leave the objective measurably suboptimal.

Lower bound: Theorem 7 constructs smooth convex components for which randomized algorithms require Ω oracle queries to reach expected ϵ-suboptimality.The lower bound is proved in sufficiently large dimension using randomly selected orthonormal directions.
Construction: Each component pair is built from a smooth helper function that is flat near zero, limiting the information revealed about unqueried directions.The helper is convex, everywhere differentiable, and 4-smooth, while remaining constant on a central interval.
Lower-bound argument: If at least m/4 component pairs remain insufficiently queried, the iterate cannot be ϵ-suboptimal, yielding the stated query lower bound with constant probability.The proof counts how many directions can be revealed after N queries and converts that limitation into objective suboptimality.
Information restriction: The gradients and prox outputs generated before sufficient queries lie in spans of previously exposed directions.This span property enables the random-direction argument used to control the iterate’s correlations with unseen vectors.
Component-count term: The construction also gives an Ω(m) lower-bound term for all ϵ through smooth components whose information must be obtained across the finite sum.A separate argument handles the regime where the component-count term dominates.
Unbounded queries: Modifying the functions outside the domain shows that arbitrarily large query vectors cannot make these instances easier to optimize.Restricted algorithms can simulate the oracle responses of unrestricted queries.

C.4 Smooth and strongly convex components

This section proves lower bounds for smooth, strongly convex components, where the construction must capture both component-count and accuracy dependence. It uses explicit paired functions and random hidden directions to retain hardness under strong convexity.

Lower bound: Theorem 8 constructs γ-smooth, λ-strongly convex components for which reaching expected ϵ-suboptimality requires Ω oracle queries.The theorem specifies an initial gap and a sufficiently large dimension for the hard instance.
Information restriction: The squared-norm terms reveal no additional information about hidden directions beyond what is already contained in the query point.This preserves the span-based information restriction used in the lower-bound argument.
Lower-bound argument: After too few queries, many component pairs remain nearly orthogonal to the iterate, forcing a nontrivial objective gap.With constant probability, the algorithm must query each of at least m/4 pairs sufficiently many times.
Construction: The proof modifies paired component functions so that all terms affecting each hidden direction’s optimum are concentrated in the corresponding pair.This bundling simplifies the suboptimality analysis while preserving smoothness and strong convexity.
Unbounded queries: The construction can be extended beyond bounded query norms while retaining smoothness and strong convexity, because outside-domain queries can be simulated from boundary queries.Therefore, unrestricted query access does not invalidate the lower bound.

C.5 Non-smooth components when ǫ is large

This section proves a lower bound for non-smooth optimization when the target accuracy is large. The argument reduces optimization to identifying the sign of a hidden random variable from noisy oracle information.

Lower bound: Theorem 11 constructs convex, L-Lipschitz functions on a one-dimensional bounded domain for which randomized algorithms require Ω oracle queries to obtain expected ϵ-suboptimality.The lower bound applies for sufficiently large m and the stated accuracy regime.
Construction: The construction samples component slopes from a distribution whose aggregate determines the optimizer through the sign of a random variable Y.When |Y| is sufficiently large, choosing the wrong sign causes a constant-factor larger suboptimality.
Information argument: Before enough oracle queries, the algorithm cannot predict sign(Y) accurately enough to guarantee low expected suboptimality.An information-theoretic reduction converts sign prediction into distinguishing two nearby slope distributions.
Query complexity: The resulting hypothesis-testing problem requires at least 1/(128ϵ^2) queries to hF.This establishes the accuracy-dependent lower-bound term for the large-ϵ analysis.
Broader implication: The same lower bound also implies an Ω(m) term for smooth functions because the construction’s component functions are linear and therefore 0-smooth.Scaling the functions can make the algorithm require increasingly precise sign information.