{"id":"7e43e7f5-8f1f-4145-aa9d-ce9de95f4ead","arxiv_id":"1908.11468","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Nested-SPIDER achieves O(ε^-3) expectation and O(N+√N ε^-2) finite-sum sample complexity for multi-level composite stochastic optimization, polynomial in the number of levels.","lead":"A new algorithm for multi-level stochastic optimization finds near-stationary points with sample complexity that grows polynomially, not exponentially, in the number of composition levels. It applies to risk-averse portfolio selection, policy evaluation in reinforcement learning, and other nested expectation problems.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proof of the claimed rates has arithmetic/sample-accounting errors: Theorem 4.4's complexity line inverts a ratio, and Theorem 4.5's printed epoch count is Nmax-fold too large for its displayed convergence bound and full-batch restart cost.","rationale":"The reader's weakest assumption (uniform per-realization Lipschitz) is legitimate, but I would not put the weight there: the paper explicitly acknowledges it is stronger than MSL, and it is a scope restriction rather than an internal contradiction. The load-bearing issue is that the proof's own accounting does not yield the quoted rates. Both problems are mechanically checkable: one is an inverted ratio in Theorem 4.4's complexity line, the other is a stated K that is Nmax times larger than needed and incompatible with the displayed sample count. These do not show the high-level O(eps^{-3}) / O(N + sqrt(N) eps^{-2}) claims are false — the smaller K in Theorem 4.5 repairably gives the advertised rate — but they mean the theorems as printed are not proven. That keeps the manuscript at CONDITIONAL rather than ACCEPT, and does not warrant REJECT without first checking whether the repairs propagate through Lemma 4.3 unchanged. I therefore leave the reader's CONDITIONAL verdict unchanged, with the reason sharpened.","tokens_in":27101,"tokens_out":32420,"duration_ms":301014,"concrete_test":"Recompute the total cost of Theorem 4.4 with the exact Lemma 4.3 parameters (tau_k = l_F/(2m eps_k), eps_k = m theta L_F/(k l_F), B,S,b,s as in (38)-(39), K = O~(m L_F/(eps l_F))) and check whether the sigma_F^2 and delta_F^2 terms are multiplied by 1/l_F; if so, the theorem needs an additional condition l_F = Omega(1) or a different parameter choice. For Theorem 4.5, substitute K = O~(L_F/(sqrt(Nmax) eps^2)) and K = O~(L_F sqrt(Nmax)/eps^2) into (48); verify that the smaller K already gives E||G|| <= eps and that the larger K makes the full-batch restart cost K sum_i N_i dominate Omega(L_F Nmax^{3/2}/eps^2), contradicting the displayed sample complexity.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Grant Assumption 4.1 fully; the rate proof still needs checking. In Theorem 4.4, Lemma 4.3 sets tau_k = l_F / (2 m eps_k), b_k ~ l_F / eps_k, s_k ~ l_F / eps_k, and eps_k = m theta L_F / (k l_F). A per-stage count is C_k = O(m^3 sigma_F^2 / eps_k^2 + m^3 delta_F^2 / eps_k^2 + m^2 l_F^2 / eps_k^2), and sum_{k<=K} eps_k^{-2} = O(K^3 l_F^2 / (m^2 L_F^2)). With K = O~(m L_F / (eps l_F)) this gives O(m^4 L_F (sigma_F^2 + delta_F^2) / (eps^3 l_F) + m^3 L_F l_F / eps^3), not the stated O(m^4 L_F (sigma_F^2 + delta_F^2 + l_F^2) / eps^3). The displayed intermediate factor L_F^2 / l_F^2 in the proof should be its reciprocal; unless l_F = Omega(1), the claimed constant is not established.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a Normalized Proximal Approximate Gradient (NPAG) meta-algorithm for nonconvex composite optimization with a possibly nonsmooth convex regularizer, requiring only that the approximate gradients satisfy a mean-squared-error bound that decreases with a prescribed sequence. It then instantiates this framework with SARAH/SPIDER, SVRG, and SAGA estimators under mean-squared Lipschitz or uniform Lipschitz conditions, recovering known one-level complexities. The main contribution is a multi-level Nested-SPIDER method for compositions of expectations or finite sums, for which the paper claims an O~(m^4 L_F (sigma_F^2 + delta_F^2 + l_F^2) epsilon^{-3}) sample complexity in the expectation case and O(sum_i N_i + m^4 L_F sqrt(N_max) epsilon^{-2}) in the finite-sum case, with polynomial rather than exponential dependence on the number of composition levels. Numerical experiments on sparse classification and portfolio selection illustrate the methods.","tokens_in":27278,"tokens_out":19073,"duration_ms":159103,"significance":"If the stated complexities are correct, the paper makes a useful contribution: Theorem 2.3 cleanly separates the optimization dynamics from the stochastic estimation problem, and the nested variance-reduction analysis in Section 4 provides one of the first polynomial-in-m sample complexity results for multi-level composite stochastic optimization, improving on the exponential dependence in previous work such as Yang, Wang, and Fang (2019). The explicit MSE conditions in Theorem 2.3 are stated in terms of problem constants rather than being fitted to the convergence criterion, and the analytical parts of the paper are generally coherent. The main theorems, however, contain arithmetic errors in the sample-accounting steps, and one pseudocode line does not match the analyzed estimator. These issues are local and appear fixable, but they must be corrected before the headline claims can be considered established.","major_comments":[{"comment":"The displayed conversion from the per-epoch sums to the final complexity is not algebraically correct. With epsilon_k = m theta L_F / (k l_F), tau_k = l_F / (2m epsilon_k), B_i^k = 12m(m+1) sigma_F^2 / epsilon_k^2, b_i^k = 6(m+1) l_F / epsilon_k, S_i^k = 12m(m+1) delta_F^2 / epsilon_k^2, and s_i^k = 6m(m+1) l_F / epsilon_k, the per-stage cost after summing over i is O(m^3 (sigma_F^2 + delta_F^2) / epsilon_k^2 + m^2 l_F^2 / epsilon_k^2), not the expression printed in the proof. Since sum_{k <= K} epsilon_k^{-2} = O(K^3 l_F^2 / (m^2 L_F^2)) and K = O~(m L_F / (epsilon l_F)), the total is O(m^4 L_F (sigma_F^2 + delta_F^2) / (epsilon^3 l_F) + m^3 L_F l_F / epsilon^3), which differs from the claimed O(m^4 L_F (sigma_F^2 + delta_F^2 + l_F^2) / epsilon^3) by a factor 1/l_F in the first two terms and by a factor m l_F in the last term. The intermediate factor L_F^2 / l_F^2 in the proof should be its reciprocal, and even then the displayed final equality does not follow. The theorem therefore needs a corrected derivation or different parameter choices.","section":"Theorem 4.4, proof (total sample complexity calculation)"},{"comment":"The convergence calculation in the proof of Theorem 4.5 gives E[||G(x_bar)||] <= O~( (L_F / (sqrt(N_max) K))^{1/2} ): from equation (48), the dominant term is O(L_F / (N_max^{1/4} sqrt(theta L_F K))) = O((L_F / sqrt(N_max) K)^{1/2}), with the second term smaller up to log factors. Consequently the required number of epochs is K = O~(L_F epsilon^{-2} / sqrt(N_max)), not the printed K = O~(L_F sqrt(N_max) epsilon^{-2}). If the printed epoch count were used, the per-epoch full-batch cost K sum_i N_i alone would be O(m L_F N_max^{3/2} epsilon^{-2}), which is a factor N_max larger than the claimed bound. With the corrected K, the restart cost becomes O(m L_F sqrt(N_max) epsilon^{-2}), consistent with the stated order up to the m-factor. This correction is load-bearing and should be made explicitly.","section":"Theorem 4.5, proof (epoch count)"},{"comment":"The recursion for y_t^i in the else branch is printed as y_t^i = y_{t-1}^i + f_{i,S_t^i}(y_{t-1}^i) - f'_{i,S_t^i}(y_{t-1}^{t-1}), using the Jacobian f' in the correction term. The analyzed estimator in Lemma 4.3, specifically equations (41) and (44), uses the mapping f_i evaluated at the two points, i.e., the second term should be f_{i,S_t^i}(y_{t-1}^{t-1}). As printed, Algorithm 3 is not the algorithm whose complexity is proven. This is a local typo, but it must be fixed for reproducibility.","section":"Algorithm 3, else branch"}],"minor_comments":[{"comment":"The contribution summary states that the finite-sum complexity is O(N + m^4 sqrt(N) epsilon^{-1}), but the abstract and Theorem 4.5 state O(N + m^4 L_F sqrt(N_max) epsilon^{-2}); these should be reconciled.","section":"Section 1.2"},{"comment":"The displayed bound on E[||G(x_bar)||] appears with a positive exponent as (L_F sqrt(N_max) K)^{1/2}; it should be (L_F / (sqrt(N_max) K))^{1/2} or equivalently (L_F sqrt(N_max) K)^{-1/2}.","section":"Theorem 4.5, proof"},{"comment":"The induction step uses a Young-type inequality whose coefficients appear in the extracted text as `(1 + k - 1)`; this should be written as (1 + k) and (1 + 1/k) to make the algebra transparent.","section":"Lemma 4.3, Step 4"},{"comment":"There are several typographical errors: \"Jessen\" should be \"Jensen\" in Theorem 2.3, \"precsion\" should be \"precision\" in Section 3, \"lager\" should be \"larger\" in Section 3.1, \"consevative\" should be \"conservative\" in Remark 4.6, \"ProxSIDER\" should be \"ProxSPIDER\" in Section 5.1, and \"Jorunal\" should be \"Journal\" in reference [9].","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The two arithmetic issues in Theorems 4.4 and 4.5 are the main obstacles to acceptance. They appear fixable within the manuscript's scope, but the authors should re-derive the sample-accounting lines carefully; if the m^4 L_F (sigma_F^2 + delta_F^2 + l_F^2) epsilon^{-3} claim cannot be recovered under the stated parameter choices, the theorems and abstract should be revised to the actual rates. The pseudocode typo in Algorithm 3 is minor but should be corrected in the same revision. I am not concerned about circularity or novelty: the assumptions are clearly stated and the polynomial-in-m dependence is a genuine contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This paper has one genuinely new idea: nested SPIDER estimators for multi-level composite stochastic optimization, with the optimizer and estimator analyses cleanly separated. The decomposition of vt minus F'(xt) into telescoping terms in Lemma 4.3 is coherent, and the per-stage MSE bound is internally consistent under Assumption 4.1. The one-level results are correctly attributed to prior work; the new part is the nested analysis and the polynomial-in-m claim. The authors also state plainly that their uniform per-realization Lipschitz assumption is stronger than the one-level MSL condition, so that limitation is not hidden. The stress-test note is right, and it matters. In Theorem 4.4, the sample-complexity line visibly inverts a ratio. With epsilon_k = m theta L_F / (k l_F) and K = O~(m L_F / (epsilon l_F)), the displayed factor L_F^2 / l_F^2 should be the reciprocal for the claimed final complexity to come out. As written, the total complexity has an unacknowledged factor of l_F^{-1}; if l_F is small, the claimed m^4 L_F(...) epsilon^{-3} rate is not established. That is not a cosmetic typo, because the theorem states a constant independent of l_F. Theorem 4.5 has a related internal inconsistency. The displayed convergence bound gives K ~ L_F / (sqrt(N_max) epsilon^2), not K ~ L_F sqrt(N_max) epsilon^{-2}. With the printed K, the full-batch restart cost alone puts an extra sqrt(N_max) factor into the sample complexity, contradicting the claimed N + sqrt(N) L_F epsilon^{-2}. The fix looks simple, but it has to be stated and rechecked. Smaller issues: Algorithm 3's else branch writes f' where the y-recursion needs f; this is a typo in the pseudocode, not in the analysis. The Theorem 4.5 proof is sketched rather than fully verified. Neither changes my reading that the main construction is sound in spirit, but the headline rates as printed are not supported by the displayed algebra. Who this is for: people working on stochastic composition, risk-averse optimization, and variance reduction. The central idea deserves a serious referee. I would not desk-reject it, but the authors need a careful revision before anyone cites the complexity theorems. Send it to peer review with instructions to fix the arithmetic and resubmit.","headline":"The nested SPIDER construction is genuinely new and mostly well argued, but both headline complexity theorems have arithmetic that does not close as printed.","tokens_in":774,"tokens_out":1867,"would_cite":false,"duration_ms":73218,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C15","90C26","65K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Multi-level composite stochastic optimization can be solved at near-single-level sample rates, with only polynomial cost in the number of composition levels.","keywords":["multi-level composite stochastic optimization","nested variance reduction","normalized proximal approximate gradient","SPIDER estimator","sample complexity","stochastic nonconvex optimization","finite-sum optimization"],"falsifier":"Compute the exact mean-squared error of the nested Spider estimator after one full epoch for a two-level example satisfying Assumption 4.1, such as $f_{1,\\xi}(x)=a_\\xi x$ with $|a_\\xi|\\le 1$ and $f_2(y)=\\cos(y)+y^2$ on a bounded domain, using the batch sizes and epoch length prescribed by Lemma 4.3; if $\\mathbb{E}[\\|v_t-F'(x_t)\\|^2]\\le \\epsilon_k^2$ fails for some $t$ in the epoch, the MSE bound behind Theorems 4.4 and 4.5 is false. Alternatively, run Algorithm 3 on that example over a geometric range of $\\epsilon$ values and count component evaluations: the observed exponent in $\\epsilon$ should be $-3$ (up to the $N$- and $m$-dependent factors), and a reliably worse exponent would contradict the claimed rate.","tokens_in":26818,"feed_emoji":"🎯","tokens_out":16781,"duration_ms":146317,"temperature":0.7,"pith_summary":"This paper attacks multi-level composite stochastic optimization, where the objective is a composition of expected-value maps (or finite sums) of smooth vector-valued mappings, plus a convex nonsmooth term. It claims that a normalized proximal approximate gradient method, fed by nested SARAH/Spider variance-reduced estimators, finds a point whose expected proximal gradient norm is below $\\epsilon$ with sample complexity $O(\\epsilon^{-3})$ in the expectation setting and $O(N+\\sqrt{N}\\epsilon^{-2})$ in the finite-sum setting, where $N$ is the total number of component functions. The headline structural point is that dependence on the number of levels $m$ is polynomial, $O(m^4)$ up to log factors, rather than having $m$ appear in the exponent of $\\epsilon$ as in earlier multi-level analyses. If this is right, adding composition depth no longer changes the fundamental sample rate, which matters for risk-averse optimization, policy evaluation, and nested risk functionals that previously looked much harder as $m$ grew.","feed_headline":"Drops to O(ε^{-3}) sample cost for multi-level stochastic optimization","feed_subtitle":"Composition depth now costs only a polynomial factor, not an exponential one, in the sample count.","key_machinery":"The load-bearing object is the normalized proximal approximate gradient (NPAG) step combined with the nested Spider estimator, a recursive estimator that corrects the previous estimate by a fresh mini-batch difference. NPAG computes $\\tilde{x}_{t+1}=\\mathrm{prox}_{\\Psi}^{\\eta}(x_t-\\eta v_t)$ and moves with step size $\\gamma_t=\\min\\{\\eta\\epsilon_t/\\|\\tilde{x}_{t+1}-x_t\\|,1\\}$, forcing every step length $\\|x_{t+1}-x_t\\|$ to stay below $\\eta\\epsilon_t$. That bounded step length is what lets the proof propagate deterministic Lipschitz bounds through the composition: Lemma 4.3 first bounds the temporal differences $\\|y_i^t-y_i^{t-1}\\|$ level by level, then applies the standard Spider MSE recursion (Lemma 3.1) to the Jacobian estimators, and finally assembles $v_t=(z_t^1)^T\\cdots(z_t^m)^T$ and verifies the MSE condition. Periodic restarts with epoch length $\\tau=\\ell_F/(2m\\epsilon_k)$ and large snapshot batches at each restart keep the estimator variance at the level required by Theorem 2.3 with near-optimal sample cost.","core_discovery":"The paper's central claim is that variance reduction can be done level by level through the composition, and that a normalized proximal step is what makes the nested estimators tractable. The Normalized Proximal Approximate Gradient (NPAG) method treats the optimizer as a module needing only approximate gradients $v_t$ whose mean-squared error against the true gradient satisfies $\\mathbb{E}[\\|v_t-F'(x_t)\\|^2]\\le \\epsilon_t^2$; Theorem 2.3 then guarantees $O(L\\epsilon^{-2})$ iterations to reach $\\mathbb{E}[\\|G(\\bar{x})\\|]\\le \\epsilon$. The paper constructs such $v_t$ for an $m$-level composition by running independent Spider recursions on the intermediate mappings $F_i(x)$ and on the Jacobians $f_i'$, then multiplying the estimators according to the chain rule. Under a uniform Lipschitz assumption on every random realization (Assumption 4.1), Lemma 4.3 gives explicit epoch lengths and mini-batch sizes that keep the MSE below $\\epsilon_k^2$ inside each epoch. The resulting sample complexities, $O(m^4 L_F(\\sigma_F^2+\\delta_F^2+\\ell_F^2)\\epsilon^{-3})$ in the expectation case and $O(\\sum_i N_i + m^4 L_F\\sqrt{N_{\\max}}\\epsilon^{-2})$ in the finite-sum case, are the paper's main theorems.","pith_inferences":["If the uniform Lipschitz assumption could be weakened to the mean-squared Lipschitz condition used in single-level analyses, the same normalized-step framework might extend to a substantially broader class of random mappings; that would be a natural next step.","The adaptive precision schedule $\\epsilon_k\\propto 1/k$ is what makes the method practical in the paper's experiments, so fine-tuning that schedule for specific problem classes could yield constants far better than the worst-case bound while preserving the rate.","The NPAG abstraction suggests that other recursive estimators, such as SVRG- or SAGA-style updates, could be nested in the same way for multi-level problems, likely with different polynomial dependence on $m$.","The results open the door to empirical benchmarks on three-level and deeper nested risk functionals, where the previous exponential-in-$m$ rate made large-scale computation unattractive."],"forward_implications":["In the expectation setting, finding an $\\epsilon$-stationary point costs $O(\\epsilon^{-3})$ component evaluations up to polynomial-in-$m$ factors, matching the $\\epsilon$-exponent of the best one-level stochastic nonconvex methods.","In the finite-sum setting, the total cost is $O(\\sum_i N_i + m^4 L_F\\sqrt{N_{\\max}}\\epsilon^{-2})$, so the square-root dependence on the largest component count replaces the worse $N^{2/3}$-type terms seen in earlier two-level finite-sum analyses.","Because the per-epoch guarantee is only a mean-squared error bound on the approximate gradient, the NPAG analysis covers Spider, ProxSARAH, SVRG, and SAGA as one-level special cases and then extends the same machinery to any number of levels.","Adding more composition levels changes the sample complexity by a polynomial factor in $m$ but does not change the rate in $\\epsilon$, so deep compositions become as tractable, in rate terms, as shallow ones."],"supporting_citations":[{"why":"Supplies the Spider estimator recursion and Lemma 3.1, the MSE bound that every nested estimator in Algorithm 3 inherits.","marker":"[13]"},{"why":"Provides the ProxSARAH proximal variant and the closest one-level comparison in both theory and the experiments.","marker":"[26]"},{"why":"Establishes the one-level complexity benchmark whose $\\epsilon$-order the multi-level result matches.","marker":"[37]"},{"why":"Gives the earlier multi-level method with $m$ in the $\\epsilon$-exponent, the baseline the paper improves from exponential to polynomial dependence.","marker":"[39]"},{"why":"Supplies the previous best two-level finite-sum complexity that Theorem 4.5 is compared against.","marker":"[41]"},{"why":"Demonstrates that biased gradient estimators can improve complexity for two-level problems, motivating the nested biased estimator here.","marker":"[42]"},{"why":"Gives the single time-scale two-level method whose $O(\\epsilon^{-2})$ complexity the NPAG framework generalizes to $m$ levels.","marker":"[15]"}],"fun_headline_variants":["Polynomial depth cost now: multi-level optimization scales","Nested variance reduction: O(ε^{-3}) for compositions","NPAG method: polynomial in depth, not exponential","Multi-level stochastic optimization: depth cost tamed","Variance reduction level by level: O(ε^{-3}) sample bound"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is Assumption 4.1(a): for every level $i$ and every random realization $\\xi_i$, the mapping $f_{i,\\xi_i}$ and its Jacobian $f'_{i,\\xi_i}$ must each be Lipschitz with uniform constants, and the proof's deterministic step-length propagation collapses if only the mean-squared Lipschitz condition holds.","fun_headline_variants_meta":{"raw":{"variants":["Polynomial depth cost now: multi-level optimization scales","Nested variance reduction: O(ε^{-3}) for compositions","NPAG method: polynomial in depth, not exponential","Multi-level stochastic optimization: depth cost tamed","Variance reduction level by level: O(ε^{-3}) sample bound"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000318,"raw_usage":{"total_tokens":1810,"prompt_tokens":969,"completion_tokens":841,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":585,"completion_tokens_details":{"reasoning_tokens":758}},"tokens_in":585,"tokens_out":841,"duration_ms":7830,"temperature":1.0,"reasoning_tokens":758,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T10:15:25.949782+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the exact mean-squared error of the nested Spider estimator after one full epoch for a two-level example satisfying Assumption 4.1, such as $f_{1,\\xi}(x)=a_\\xi x$ with $|a_\\xi|\\le 1$ and $f_2(y)=\\cos(y)+y^2$ on a bounded domain, using the batch sizes and epoch length prescribed by Lemma 4.3; if $\\mathbb{E}[\\|v_t-F'(x_t)\\|^2]\\le \\epsilon_k^2$ fails for some $t$ in the epoch, the MSE bound behind Theorems 4.4 and 4.5 is false. Alternatively, run Algorithm 3 on that example over a geometric range of $\\epsilon$ values and count component evaluations: the observed exponent in $\\epsilon$ should be $-3$ (up to the $N$- and $m$-dependent factors), and a reliably worse exponent would contradict the claimed rate.","supporting_citations":[{"cited_title":"Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator","cited_arxiv_id":null,"evidence_quote":"Supplies the Spider estimator recursion and Lemma 3.1, the MSE bound that every nested estimator in Algorithm 3 inherits."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the earlier multi-level method with $m$ in the $\\epsilon$-exponent, the baseline the paper improves from exponential to polynomial dependence."},{"cited_title":"A composite randomized incremental gradient method","cited_arxiv_id":null,"evidence_quote":"Supplies the previous best two-level finite-sum complexity that Theorem 4.5 is compared against."},{"cited_title":"A stochastic composite gradient method with incremental variance reduction","cited_arxiv_id":null,"evidence_quote":"Demonstrates that biased gradient estimators can improve complexity for two-level problems, motivating the nested biased estimator here."},{"cited_title":"A Single Time-Scale Stochastic Approximation Method for Nested Stochastic Optimization","cited_arxiv_id":"1812.01094","evidence_quote":"Gives the single time-scale two-level method whose $O(\\epsilon^{-2})$ complexity the NPAG framework generalizes to $m$ levels."}],"review_version":1}