REVIEW 1 major objections 3 minor 24 references
A General Analysis Framework of Lower Complexity Bounds for Finite-Sum Optimization
T0 review · 1 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read Any per-component gradient-proximal optimizer needs at least Ω((n+√(κn)) log(1/ε)) queries on some finite-sum problems, matching the best known upper bound.
desk verdict Tight PIFO lower bound that closes the Woodworth-Srebro gap, worth refereeing despite the abstract overstating the algorithm class. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is a family of hard functions $r_i$ obtained by partitioning the rows of the tridiagonal matrix $B(m,\omega)^\top B(m,\omega)$ into n groups according to the residue of the row index modulo n. The key Lemma 2.6 says that if the current iterate lies in the subspace $F_k$ spanned by the last k coordinates, then both the gradient and the proximal mapping of component i either stay in $F_k$ or, only when $k \equiv i-1 \pmod n$, can move into $F_{k+1}$. Thus advancing one level requires waiting until the matching component is sampled, and the waiting times are geometric. A tail bound for sums of geometric random variables (Lemma 2.8) converts these waiting times into the $\Omega((n+\sqrt{\kappa n})\log(1/\varepsilon))$ query count.
What would settle it
Run the hard instance of Definition 4.1 with n=2 and m=4, and check whether the gradient or proximal output of a component with index other than the level-matching one ever leaves the current subspace $F_k$. If it does, Lemma 2.6 is false and the lower bound collapses; if it does not, then any algorithm within Definition 2.4 that nevertheless finds an ε-solution faster than $\Omega((n+\sqrt{\kappa n})\log(1/\varepsilon))$ queries would refute the theorem.
Extended reading notes
Core claim
The central discovery is a tight lower-bound construction for the Proximal Incremental First-order Oracle (PIFO) model, where each oracle call returns the value, gradient, and proximal mapping of one component. Theorem 3.1 states that whenever $\kappa \ge n/2 + 1$ and $\varepsilon/\Delta \le 0.00327$, there is a dimension $d = O(\sqrt{\kappa/n}\log(\Delta/\varepsilon))$ and a collection of n L-smooth, μ-strongly convex functions whose average has initial gap $\Delta$, such that any PIFO algorithm must make $\Omega((n+\sqrt{\kappa n})\log(\Delta/\varepsilon))$ oracle calls to find a point with expected suboptimality below $\varepsilon$. This closes the gap left by the previous PIFO lower bound, which had the wrong dependence on n, and it shows that the complexity of finite-sum optimization is the same whether or not the algorithm is allowed proximal queries on individual components.
Load-bearing premise
The theorem only covers algorithms whose iterates lie in the linear span of all past gradients and proximal outputs and whose component choices are independent draws from a fixed probability vector; an algorithm that uses nonlinear processing of proximal outputs, adapts its sampling probabilities based on observed values, or exploits the hidden coordinate labels is outside the bound and could in principle be faster.
Editorial extensions
If this is right
- Point-SAGA is worst-case optimal among PIFO algorithms in the strongly convex finite-sum setting, because its $O((n+\sqrt{\kappa n})\log(1/\varepsilon))$ iteration bound matches the new lower bound.
- The lower bound also applies to IFO algorithms, so allowing proximal mappings of components does not reduce worst-case complexity relative to gradient-only incremental methods.
- For general convex functions the same construction gives $\Omega(n + B\sqrt{nL/\varepsilon})$ PIFO queries, with a much smaller required dimension than earlier constructions.
- Under the weaker L-average smooth assumption, the lower bounds are $\Omega((n+n^{3/4}\sqrt{\kappa})\log(1/\varepsilon))$ for strongly convex objectives and $\Omega(n + B n^{3/4}\sqrt{L/\varepsilon})$ for convex objectives.
- A non-convex extension in the appendix yields $\Omega(\Delta L\sqrt{\alpha}/\varepsilon^2)$ queries to reach an ε-stationary point.
Reading between the lines
- The argument depends on the algorithm not being able to mix information nonlinearly; a natural next target is to prove similar bounds for algorithms that use nonlinear processing of proximal outputs or adapt their sampling distribution to observed function values.
- Because the hard instance is built from a one-dimensional chain of subspaces, the same block decomposition may transfer to lower bounds for coordinate-descent, distributed, or private optimization settings that share a one-coordinate-per-round structure.
- A practical reading is that acceleration on finite sums must exploit structure beyond smoothness and strong convexity, such as data statistics or sparsity, since no algorithm can beat the $(n+\sqrt{\kappa n})$ rate on all instances.
- The construction's small dimension in the strongly convex case suggests the hardness is not an artifact of high dimensionality; the difficulty is the information-limited sampling along the coordinate chain.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper develops a lower-bound framework for finite-sum optimization under a proximal incremental first-order oracle (PIFO). The central result is that, for minimizing an average of n L-smooth and μ-strongly convex functions, any algorithm in the analyzed class needs Ω((n+√(κn)) log(Δ/ε)) PIFO queries to reach ε-suboptimality, where κ=L/μ. This matches the upper bound of Point-SAGA and implies that, within the considered oracle model, PIFO does not improve on IFO in the worst case. The proof constructs hard instances by partitioning the classical tridiagonal matrix into n groups, proves a one-dimensional subspace-expansion lemma for gradients and proximal maps, and reduces the argument to a tail bound for sums of geometric random variables. The framework is also applied to general convex, average-smooth, and non-convex settings, with full proofs in Appendices A-E.
Significance. If the main claim is understood as applying to PIFO algorithms with i.i.d. component sampling from a fixed distribution, the paper closes the n-dependence gap for strongly convex finite sums under the PIFO oracle. The construction is original and clean, and the appendices give essentially complete proofs with explicit constants; the lower-bound constants come from the geometry of the instance rather than being fitted to any algorithm's behavior. The dimension bounds are also an improvement over previous constructions. The main caveat is the restrictiveness of the algorithm class: Definition 2.4 is explicit about the linear-span condition, but the proof requires an i.i.d. assumption on the component indices that the definition as written does not state.
major comments (1)
- [Definition 2.4 and Corollary 2.7 (pp. 4-6)] The proof of Corollary 2.7 represents T_k as a sum of independent geometric random variables, writing P(T_k-T_{k-1}=s)=(1-p_{k'})^{s-1}p_{k'} and then asserting that the increments are independent. This requires the sequence (i_t) to be independent and identically distributed across t. Definition 2.4 as written only fixes the marginal law P(i_t=j)=p_j for each t, so it does not exclude history-dependent sampling: for example, after reaching F_1, an algorithm could deterministically query the component that expands the subspace to F_2 and continue one dimension per query, which is compatible with the stated marginal condition but breaks the geometric waiting-time argument. Please add an explicit i.i.d. assumption on (i_t) in Definition 2.4, and consequently qualify the statements in the abstract, Theorem 3.1, and Remark 3.2 so that 'PIFO algorithm' means 'PIFO algorithm with i.i.d. component sampling from a fixed distribution'.
minor comments (3)
- [Definition 4.1 (p. 9)] In the displayed formula for FSC, the linear term appears as -sqrt(2(L-μ)Δ)/(n(α-1)) <e_m,x>; consistency with (10) and with the proof of Proposition 4.2 requires the square root to cover 2(L-μ)Δ/(n(α-1)) rather than only 2(L-μ)Δ. Please correct this typo.
- [Theorem 4.4 proof (p. 11)] In the displayed chain of inequalities, the denominator should be ||x_0-x_*||^2 rather than ||x_t-x_*||^2; as printed, the ratio is tautological.
- [Remark 3.2 (p. 8)] The comparison with Defazio's Point-SAGA bound should state E||x̂-x_*||^2 < ε||x_0-x_*||^2, not Ef(x̂)-f(x_*) < ε||x_0-x_*||^2, which is the statement proved in Theorem 4.4.
Circularity Check
No significant circularity: the lower bound is derived from constructed hard instances and the oracle-span argument, not from the target bound.
full rationale
The derivation chain is self-contained within the stated model. Definition 4.1 fixes the hard functions analytically from L, mu, n, and Delta; Proposition 4.2 computes their smoothness, strong convexity, minimizer, and the gap growth Delta q^{2k} directly from the quadratic structure; Lemma 2.6 is proved from the explicit form of B(m, omega) and the proximal equations; and Corollary 2.7 converts span growth into sums of geometric random variables using only the i.i.d. sampling assumption in Definition 2.4. Lemma 2.9 then converts the independently proved geometric tail bound (Lemma 2.8) into an epsilon-suboptimality lower bound. The rate Omega((n + sqrt(kappa n)) log(Delta/epsilon)) appears as the algebra of N = (M+1)n/4 with M approximately log(Delta/epsilon)/(2 log q), not as an assumed input. Matching upper bounds are cited from Defazio's Point-SAGA and Allen-Zhu's Katyusha, which are external results and are not used to construct the hard instance. No parameter is fitted to any algorithm's observed behavior, and no load-bearing self-citation occurs. The only caveat is interpretive: Definition 2.4 restricts PIFO algorithms to the linear-span model with i.i.d. component sampling, so the abstract's unqualified 'PIFO' phrasing overstates the formal scope; that is a scope/presentation issue, not circularity.
Assumptions & free parameters
assumptions (3)
- standard math Analytic facts about the tridiagonal matrix A(m,ω) = B(m,ω)^T B(m,ω) and about the minimizers of the restricted subproblems (Propositions 4.2 and 4.6).
- domain assumption The span-restricted, zero-respecting model of PIFO algorithms (Definition 2.4).
- domain assumption Regime restrictions: κ ≥ n/2 + 1 and ε/Δ ≤ 0.00327 for the strongly convex case, ε ≤ LB²/4 for the convex case, with analogous conditions for the average-smooth theorems.
Cite this review
Pith. "Pith review of A General Analysis Framework of Lower Complexity Bounds for Finite-Sum Optimization." pith.science (2026). https://pith.science/paper/OEU2TEKC
@misc{pith2026190808394,
author = {Pith},
title = {Pith review of: A General Analysis Framework of Lower Complexity Bounds for Finite-Sum Optimization},
year = {2026},
howpublished = {\url{https://pith.science/paper/OEU2TEKC}},
note = {Machine review of arXiv:1908.08394}
}
abstract
This paper studies the lower bound complexity for the optimization problem whose objective function is the average of $n$ individual smooth convex functions. We consider the algorithm which gets access to gradient and proximal oracle for each individual component. For the strongly-convex case, we prove such an algorithm can not reach an $\varepsilon$-suboptimal point in fewer than $\Omega((n+\sqrt{\kappa n})\log(1/\varepsilon))$ iterations, where $\kappa$ is the condition number of the objective function. This lower bound is tighter than previous results and perfectly matches the upper bound of the existing proximal incremental first-order oracle algorithm Point-SAGA. We develop a novel construction to show the above result, which partitions the tridiagonal matrix of classical examples into $n$ groups. This construction is friendly to the analysis of proximal oracle and also could be used to general convex and average smooth cases naturally.
Reference graph
Works this paper leans on
-
[2]
Denote ξ = √ 2∆ n(α +1)2 (L−µ )(α −1) . Let ∇FSC(x) = 0, that is ( L − µ 2n A (√ 2 α + 1 ) + µ I ) x = L − µ n(α + 1) ξem, or ω 2 + 1 + 2nµ L−µ −1 −1 2 + 2nµ L−µ −1 . . . . . . −1 2 + 2nµ L−µ −1 −1 1 + 2nµ L−µ x = 0 0 . . . 0 2ξ α +1 (21) Note that q = α −1 α +1 is a root of the equation z2 − ( 2...
-
[3]
Let y = xm−k+1:m ∈ Rk and Ak be last k rows and columns of the matrix in Equation (22)
If x ∈ F k, 1 ≤ k < m , then x1 = x2 = · · · = xm−k = 0. Let y = xm−k+1:m ∈ Rk and Ak be last k rows and columns of the matrix in Equation (22). Then we can rewrite F (x) as Fk(y) ≜ FSC(x) = L − µ 4n y⊤Aky − L − µ n(α + 1) ξ⟨em, y⟩. Let ∇Fk(y) = 0, that is 2 + 2nµ L−µ −1 −1 2 + 2nµ L−µ −1 . . . . . . −1 2 + 2nµ L−µ −1 −1 1 + 2nµ L−µ ...
-
[4]
Just recall Proposition 2.5
-
[5]
Let ∇FC(x) = 0, that is L 2n A(1)x = ξ n em, or 2 −1 −1 2 −1
Denote ξ = √ 3 2 BL (m+1)3/ 2n . Let ∇FC(x) = 0, that is L 2n A(1)x = ξ n em, or 2 −1 −1 2 −1 . . . . . . −1 2 −1 −1 1 x = 0 0 . . . 0 2ξ L . (23) Hence, it is easily to check that the solution to Equation (23 ) is x∗ = 2ξ L (1, 2, · · · , m )⊤, and FC(x∗) = − mξ2 nL . Moreover, we have ‖x0 − x∗‖2 2 ...
-
[6]
Thus min x∈Fk FC(x) − FC(x∗) = ξ2 nL (m − k)
By similar calculation to above proof, we have arg min x∈Fk FC(x) = 2ξ L (1, 2, · · · , k )⊤, and min x∈Fk FC(x) = − kξ2 nL . Thus min x∈Fk FC(x) − FC(x∗) = ξ2 nL (m − k). 28 E Non-convex Case In non-convex case, our goal is to find an ε-approximate stationary point ˆx of our objective function f , which satisfies ‖∇f ( ˆx)‖2 ≤ ε. (24) E.1 Preliminaries We ...
work page 2017
-
[7]
Γ( x) is (−45( √ 3 − 1), 180)-smooth and GNC(x; α, m ) is (−45( √ 3 − 1)α, 4 + 180α )-smooth
-
[8]
GNC(0; α, m ) − minx∈Rm+1 GNC(x; α, m ) ≤ √α/ 2 + 10αm
-
[9]
For x which satisfies that xm = xm+1 = 0, we have ‖∇GNC(x; α, m )‖2 ≥ α 3/ 4/ 4. 29 E.2 Our Result Theorem E.3. For any PIFO algorithm A and any L, σ, n, ∆ , ε such that ε2 ≤ ∆ Lα 81648n , there exist a dimension d = ⌊ ∆ L√α 40824nε2 ⌋ + 1 and n (−σ, L )-smooth nonconvex functions {fi : Rd → R}n i=1 such that f (x0) − f (x∗) ≤ ∆ . In order to find ˆx ∈ Rd s...
work page 2019
Show all 24 references
-
[10]
fi(x; α, m, λ, β ) is ( −45( √ 3−1)αλ β 2 , (2n+180α )λ β 2 ) -smooth
-
[11]
F (0; α, m, λ, β ) − minx∈Rm+1 F (x; α, m, λ, β ) ≤ λ(√α/ 2 + 10αm )
-
[12]
Similar to Lemma 2.6, similar conclusion hosts for {fi(x; α, m, λ, β )}n i=1
For x which satisfies that xm = xm+1 = 0, we have ‖∇F (x; α, m, λ, β )‖2 ≥ α 3/ 4λ 4β . Similar to Lemma 2.6, similar conclusion hosts for {fi(x; α, m, λ, β )}n i=1. 30 Lemma E.6. For x ∈ F k, 0 ≤ k < m and γ < √ 2+1 60 β 2 λα , we have ∇fi(x; α, m, λ, β ), proxγ fi(x) ∈ { Gk+1...
-
[13]
if m − s ∈ L j and s satisfies (31), then us = 0
-
[14]
For s which satisfies (31), if m − s ⁄∈ Lj and m − s + 1 ⁄∈ Lj, then the s-th element of Au is (β/γ u s)
if m − s + 1 ∈ L j and s − 1 satisfies (31), then us = 0. For s which satisfies (31), if m − s ⁄∈ Lj and m − s + 1 ⁄∈ Lj, then the s-th element of Au is (β/γ u s). Similarly, by Equation (30), we have β γ us + 120λα β u2 s(us − 1) 1 + u2 s = 0. Following from Lemma E.8, for 120λ...
-
[15]
if s − 1 satisfies (31), then us = 0
-
[16]
Moreover, we have that
if s satisfies (31) and m − s + 1 ⁄∈ Lj, then us = 0. Moreover, we have that
-
[17]
if k = 0 and j = 1, then m − 1, m − 2 ⁄∈ Lj, so u2 = 0
-
[18]
if k = 0 and j > 1, then for s = 1, we have m − s + 1 ⁄∈ Lj, so u1 = 0
-
[19]
if k = 0, then for s > 2, we have s − 1 > 1 satisfies (31), so us = 0
-
[20]
if k > 0, then for s > k + 1, we have s − 1 > k satisfies (31), so us = 0
-
[21]
In short,
if k > 0 and m − k ⁄∈ Lj, then for s = k + 1, we have m − s + 1 ⁄∈ Lj, so uk+1 = 0. In short,
-
[22]
if k = 0 and j > 1, then u ∈ G0
-
[23]
if k = 0 and j = 1, then u ∈ G1
-
[24]
if k > 1 and m − k ⁄∈ Lj, then u ∈ G k. 32
-
[25]
Remark E.7
if k > 1 and m − k ∈ L j, then u ∈ G k+1. Remark E.7. In order to make the operator proxγ fi valid, γ need to satisfy γ < √ 3 + 1 90 β 2 λα < √ 2 + 1 60 β 2 λα . So for any valid PIFO call, the condition about γ in Lemma E.6 must be satisfied. Lemma E.8. Suppose that 0 < λ 2 < ...
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.