{"id":"96b2be5e-0692-4e8a-8900-ce0e5cc31773","arxiv_id":"1908.08394","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper closes the gap between the Point-SAGA upper bound and the previous PIFO lower bound, proving Ω((n + √(κn)) log(1/ε)) queries are necessary for strongly convex finite sums.","lead":"This paper proves that any proximal incremental first-order algorithm needs at least Ω((n + √(κn)) log(1/ε)) oracle calls in the worst case on strongly convex finite sums. The bound matches the Point-SAGA algorithm's known rate, so proximal access cannot beat plain incremental first-order methods on worst-case smooth problems.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the formal lower bound is sound within Definition 2.4, though the abstract overstates the algorithm class by omitting the i.i.d. sampling restriction.","rationale":"I read the full manuscript including appendices. The central lower-bound construction is sound: the n-group decomposition of the tridiagonal hard matrix, Lemma 2.6's subspace-nesting for both gradient and proximal oracles, and the geometric waiting-time analysis in Lemma 2.9 all check out. The dimension and query counts in Theorem 4.3 match the stated Ω((n+√κn) log(Δ/ε)) complexity. The reader's weakest assumption is the same one I would flag: Definition 2.4 restricts the algorithm class to linear-span iterates with i.i.d. sampling from a fixed distribution. This is the only place where the formal theorem is narrower than the abstract's wording. It is not a soundness problem, because the theorem quantifies over exactly the class defined in Definition 2.4, and the restriction covers the practical methods cited (Point-SAGA, SAGA, SVRG, Katyusha). I also checked the strong-convexity constant in Proposition 2.5: the Hessian of r_i is 2λ1 B_i^T B_i + 2λ2 I, so the true strong-convexity parameter is 2λ2, which makes the Definition 4.1 choice λ2=µ/2 satisfy the theorem's µ assumption; the proposition's 'λ2-strongly convex' is a harmless understatement. Thus the ACCEPT verdict should stand, UNCHANGED. The proposed cyclic-algorithm test would empirically separate the formal theorem from the broader informal claim, but it does not block acceptance.","tokens_in":25569,"tokens_out":35767,"duration_ms":344408,"concrete_test":"Simulate the hard instance of Theorem 4.3 (e.g., n=4, κ=10^6, Δ/ε=10^6) with a deterministic cyclic algorithm that at step t queries component i=(t mod n)+1, using the component labels reversed so the useful component at level k is n-k (the worst-case ordering for this rule). If this algorithm reaches Ef(x)-f*<ε in o((n+√κn) log(Δ/ε)) PIFO calls, then the informal 'any PIFO algorithm' claim is false outside Definition 2.4; if it requires Ω((n+√κn) log(Δ/ε)) calls despite the reversed labels, then the i.i.d. sampling restriction is not the binding limitation and the paper's scope statement should still be made explicit in the abstract.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No load-bearing objection identified. The main proof chain (Definition 4.1, Proposition 4.2, Lemma 2.6, Theorem 4.3) is internally consistent, and I traced no circular step or omitted proof in the strongly convex case. The only substantive concern is scope: Definition 2.4 defines a PIFO algorithm as one whose iterates stay in the linear span of past iterates/oracle outputs and whose query indices i_t are drawn i.i.d. from a fixed distribution (p_1,...,p_n). Corollary 2.7 then represents the time T_k to expand the reachable subspace to F_k as a sum of independent geometric random variables with fixed success probabilities; this is what yields the n term in the lower bound. A deterministic cyclic rule, or any history-dependent/adaptive sampling rule, falls outside this definition, and the abstract's unqualified 'PIFO algorithm' and 'PIFO cannot be more powerful than IFO' therefore overstate the formal result. Because the definition is explicit, the theorem is true as stated; the issue is presentation and scope, not correctness of the proof.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":25643,"tokens_out":19735,"duration_ms":174352,"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":[{"comment":"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'.","section":"Definition 2.4 and Corollary 2.7 (pp. 4-6)"}],"minor_comments":[{"comment":"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.","section":"Definition 4.1 (p. 9)"},{"comment":"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.","section":"Theorem 4.4 proof (p. 11)"},{"comment":"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.","section":"Remark 3.2 (p. 8)"}],"recommendation":"major_revision","confidential_remarks":"The i.i.d. issue in Definition 2.4 is easily fixable and does not indicate a deeper correctness problem: the core derivation is sound once the class of algorithms is stated precisely. I would not treat this as a novelty or scope-of-journal concern, only as a necessary tightening of the main theorem's hypothesis and of the abstract's claims."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThis is a solid and important lower-bound paper. It proves that any PIFO algorithm in the standard linear-span model with i.i.d. component sampling needs Ω((n + √(κn)) log(1/ε)) queries in the strongly convex finite-sum case, matching Point-SAGA and showing PIFO offers no worst-case advantage over IFO. The previous PIFO bound of Woodworth-Srebro had the n term without the log factor; this closes that gap. The main novelty is the n-group decomposition of the tridiagonal hard instance, with Lemma 2.6 showing the proximal oracle advances the reachable subspace by at most one dimension, and only when the matching component is sampled. That is the piece missing in prior IFO-only constructions.\n\nThe paper does several things well. The proximal-nesting lemma is proven directly, and the appendices contain full proofs of the tail bound for geometric sums, the strongly convex and convex constructions, and the average smooth extensions. I traced the key inequalities (Lemma 2.9, Theorems 4.3 and 4.7, Propositions 4.2 and 4.6) and found them consistent. The paper also flags the mismatch between function-value and squared-distance error and resolves it with Theorem 4.4. That is honest.\n\nThe soft spots are real but modest. The main one is scope: Definition 2.4 restricts the algorithm class to iterates in the linear span of past iterates and oracle outputs, with query indices drawn i.i.d. from a fixed distribution. The abstract’s unqualified “PIFO algorithm” overstates the formal result. Deterministic cyclic or adaptive sampling rules are outside the model. This does not undermine the theorem as stated, but the abstract and conclusion should carry the qualification. A second, minor point: the lower bound requires κ ≥ n/2+1 and a small ε/Δ threshold; that is typical in this literature.\n\nThe citation pattern is appropriate, the novelty claim holds up, and there is no circularity: the hard instance is analytic, not fitted to any algorithm.\n\nThis paper is for researchers in incremental and proximal methods and lower-bound theory. The framework may generalize usefully. Send it to peer review; it deserves referee time, and I expect acceptance after the authors qualify the algorithm class in the abstract and introduction.","headline":"Tight PIFO lower bound that closes the Woodworth-Srebro gap, worth refereeing despite the abstract overstating the algorithm class.","tokens_in":26348,"tokens_out":2699,"would_cite":true,"duration_ms":23754,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C60"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["finite-sum optimization","lower complexity bounds","proximal incremental first-order oracle","strongly convex","smooth convex","variance reduction","Point-SAGA","tridiagonal matrix construction"],"falsifier":"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.","tokens_in":25221,"feed_emoji":"🧮","tokens_out":9313,"duration_ms":80723,"temperature":0.7,"pith_summary":"This paper establishes a lower bound on the number of oracle calls needed to minimize the average of n smooth, strongly convex functions when the algorithm may use both gradients and proximal mappings of the individual components. For any such algorithm, there are hard instances on which reaching ε-suboptimality requires at least $\\Omega((n+\\sqrt{\\kappa n})\\log(\\Delta/\\varepsilon))$ queries, where $\\kappa$ is the condition number and $\\Delta$ is the initial gap. That rate exactly matches the known upper bound of the Point-SAGA method and also matches the best gradient-only methods, so the extra power of the proximal oracle does not improve worst-case complexity. The proof builds the hard functions by partitioning the classical tridiagonal matrix into n residue-class blocks, and the same construction gives lower bounds for general convex, average-smooth, and non-convex settings.","feed_headline":"Proximal oracle cannot beat gradients on worst-case finite sums","feed_subtitle":"A matching lower bound closes the gap, making Point-SAGA optimal among proximal incremental methods.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the tridiagonal matrix $A(m,\\omega)$ that the paper partitions into n blocks and uses as the basis of the hard instance.","marker":"Nesterov, 2013"},{"why":"Establishes the previous PIFO lower bound that this paper tightens to match the n-dependence of the Point-SAGA upper bound.","marker":"Woodworth and Srebro, 2016"},{"why":"Provides the IFO lower bound $\\Omega((n+\\sqrt{\\kappa n})\\log(1/\\varepsilon))$ that the new PIFO bound now matches.","marker":"Lan and Zhou, 2017"},{"why":"Gives Point-SAGA, the PIFO algorithm whose upper bound $O((n+\\sqrt{\\kappa n})\\log(1/\\varepsilon))$ is proven optimal by Theorem 3.1.","marker":"Defazio, 2016"},{"why":"Provides the gradient-only algorithm Katyusha with the same optimal rate, showing PIFO cannot beat IFO in the worst case.","marker":"Allen-Zhu, 2017"},{"why":"Supplies the average-smooth lower-bound setting and the non-convex function class that the paper extends to PIFO algorithms.","marker":"Zhou and Gu, 2019"}],"fun_headline_variants":["Tight lower bound shows Point-SAGA optimal for finite sums","Proximal oracle cannot beat gradient methods on finite sums","Optimal complexity for finite sums: proximal oracle does not help","Proximal oracle does not reduce worst-case finite-sum complexity"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Tight lower bound shows Point-SAGA optimal for finite sums","Proximal oracle cannot beat gradient methods on finite sums","Optimal complexity for finite sums: proximal oracle does not help","Proximal oracle does not reduce worst-case finite-sum complexity"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000793,"raw_usage":{"total_tokens":3469,"prompt_tokens":894,"completion_tokens":2575,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":510,"completion_tokens_details":{"reasoning_tokens":2505}},"tokens_in":510,"tokens_out":2575,"duration_ms":17964,"temperature":1.0,"reasoning_tokens":2505,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:42:02.274672+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}