{"id":"7e448fd9-5948-4b52-984f-3e273dcabf87","arxiv_id":"2506.19883","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"STIMULUS adapts the SPIDER variance-reduction estimator to multi-gradient descent, achieving O(1/T) non-convex convergence and O(n + sqrt(n)/epsilon) sample complexity for multi-objective learning.","lead":"This paper introduces STIMULUS, a variance-reduced stochastic algorithm for multi-objective optimization with promised O(1/T) non-convex convergence and linear convergence in the strongly convex case. Its claimed O(n + sqrt(n)/epsilon) sample complexity is relevant for large-scale multi-task learning, but the extended variants rest on fragile assumptions.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Assumption 4 makes the strongly convex result vacuous: it forces every objective to have its minimizer at the same point x*, so the O(e^{-μT}) claim does not cover genuine MOO trade-offs, though the non-convex analysis is unaffected.","rationale":"The reader's conditional verdict is appropriate, and the stress-test sharpens rather than overturns it. The core non-convex claim, that STIMULUS achieves O(1/T) Pareto-stationarity with O(n + sqrt(n)/epsilon) sample complexity, appears to be a plausible SPIDER-based analysis whose key lemmas are honestly cited, and I found no internal inconsistency in that argument. The load-bearing weakness is in the strongly convex branch: Assumption 4 is not merely a Polyak-Lojasiewicz-like condition that anticipates the desired linear convergence; it actually implies every objective has its unique minimizer at the same Pareto point x*, so the multi-objective problem collapses to the common-minimizer case. Thus the advertised O(exp(-mu T)) result for 'strongly convex MOO' does not address trade-offs between conflicting objectives, which is the defining challenge of MOO. This is a correctness-risk issue in the central claim as stated, not a disagreement with community consensus. Because the non-convex contribution likely remains valid and the strongly convex claims could be fixed by either removing them or replacing Assumption 4 with a genuine Pareto-PL condition whose constant appears in the rate, the appropriate disposition stays conditional rather than accept. The reader already flagged Assumption 4; my analysis agrees on the location and adds the sharper observation that the assumption trivializes the setting, so agreement is partial rather than full.","tokens_in":39647,"tokens_out":9288,"duration_ms":96994,"concrete_test":"Take S=2, f_1(x)=x^2, f_2(x)=(x-1)^2, both 2-strongly convex, and choose the Pareto-stationary point x*=1/2. Compute f_2(0.6)-f_2(0.5) = -0.09 < 0, while (c_2/2)||0.6-0.5||^2 >= 0, violating Assumption 4. More generally, verify analytically that for any x* with ∇f_j(x*) != 0, strong convexity plus L-smoothness yields a neighbor with smaller f_j, so Assumption 4 holds only when ∇f_j(x*)=0 for all j. If the authors instead intend a weaker quadratic-growth condition, re-derive Theorems 2/4/6 with the c_j constants included and check whether the linear rate then depends on min_j c_j.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader's weakest-assumption identification is correct and can be sharpened. Assumption 4 states that for a fixed Pareto-optimal x*, every objective satisfies f_j(x)-f_j(x*) >= (c_j/2)||x-x*||^2 for all x. If ∇f_j(x*) != 0, then by L-smoothness (Assumption 1) and strong convexity (Assumption 3), moving a small step δ along -∇f_j(x*) gives f_j(x*-δ∇f_j(x*)) < f_j(x*), since the first-order decrease is -δ||∇f_j(x*)||^2 + O(δ^2). This makes the left-hand side of Assumption 4 negative while the right-hand side is nonnegative, a contradiction. Therefore Assumption 4 forces ∇f_j(x*)=0 for every j, i.e., every strongly convex objective attains its unique minimum at the same point x*. The multi-objective problem then has a common minimizer, so Pareto optimality and Pareto stationarity are trivial, and the claimed linear convergence in Theorems 2, 4, and 6 is vacuous for any genuine trade-off setting. Notably, the proof of Theorem 2 never uses the constants c_j or a lower bound on their minimum, and the final rate O(μ exp(-μT)) contains no dependence on the quadratic-growth constant; under any meaningful relaxation of Assumption 4 to a Pareto-PL-type condition, such a constant would necessarily enter the rate. The non-convex result (Theorem 1 and Corollary 1) is a standard SPIDER-style argument and is not implicated by this concern.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes STIMULUS, a stochastic multi-gradient algorithm for multi-objective optimization that uses a SPIDER-style recursive variance-reduced gradient estimator, together with momentum (STIMULUS-M) and adaptive-batching (STIMULUS+/STIMULUS-M+) variants. It claims an O(1/T) Pareto-stationarity convergence rate and O(n + sqrt(n)/epsilon) sample complexity for non-convex MOO, and linear convergence O(exp(-mu T)) with O(n + sqrt(n) log(mu/epsilon)) sample complexity for strongly convex MOO. The non-convex analysis follows the standard SPIDER proof template, with the improved sample complexity coming from setting the inner loop length and batch size to sqrt(n). The strongly convex analysis is based on a quadratic-growth assumption (Assumption 4) and a weighted-averaging output rule.","tokens_in":39988,"tokens_out":8504,"duration_ms":91007,"significance":"If the technical issues were repaired, the paper would be a useful contribution: applying variance reduction to the multi-gradient direction is natural, and the claimed O(n + sqrt(n)/epsilon) sample complexity for non-convex MOO is the expected near-optimal finite-sum complexity. The momentum and adaptive-batching extensions are practically motivated, and the non-convex part of the analysis is structurally sound and closely follows Fang et al. (2018). However, the strongly convex results as stated are not a genuine MOO contribution, because Assumption 4 forces all objectives to share a common minimizer and hence removes the Pareto trade-off. The paper contains no code or machine-checked proofs, so its value rests on the correctness and precision of the written proofs.","major_comments":[{"comment":"Assumption 4 is not a benign addition to strong convexity; it makes the strongly convex results vacuous for MOO. If ∇f_j(x*) ≠ 0 for some j, then by L-smoothness, for small δ > 0 the point x* − δ∇f_j(x*) satisfies f_j(x* − δ∇f_j(x*)) ≤ f_j(x*) − δ‖∇f_j(x*)‖² + (L/2)δ²‖∇f_j(x*)‖² < f_j(x*) when δ < 2/L, while Assumption 4 requires f_j(x) − f_j(x*) ≥ (c_j/2)‖x − x*‖² ≥ 0 for all x. Hence Assumption 4 forces ∇f_j(x*) = 0 for every j, so every strongly convex objective has its unique minimizer at the same point x*. In that regime the multi-objective problem has a common minimizer, there is no Pareto trade-off, and the linear rates in Theorems 2, 4, and 6 do not cover genuine strongly convex MOO. The proof of Theorem 2 also never uses the constants c_j or their minimum, and the final rate O(μ exp(−μT)) is independent of any quadratic-growth constant; under a non-vacuous relaxation such as a Pareto-PL condition, that constant would necessarily enter the rate. The authors should either replace Assumption 4 with a meaningful condition and re-derive the strongly convex rates with the correct dependence on the quadratic-growth constants, or remove the strongly convex optimality claims and restrict the paper's claims to the non-convex setting.","section":"Section 4.1, Assumption 4 and Theorems 2, 4, 6"},{"comment":"The stationarity measure bounded in the proof of Theorem 1 is not the measure stated in Definition 3. The proof controls (1/T) Σ_t E‖Σ_s λ_t^s ∇f_s(x_t)‖², where λ_t is the data-dependent minimizer of ‖Σ_s λ u_t^s‖². However, Definition 3 concerns min_{λ∈C} E‖λ^T∇F(x_t)‖², in which the minimization is over a fixed weight vector before the expectation is taken. Since λ_t is random and is chosen using the stochastic estimators u_t rather than the true gradients, the inequality min_{λ∈C} E‖λ^T∇F(x_t)‖² ≤ E‖Σ_s λ_t^s ∇f_s(x_t)‖² is not justified and can fail: a pointwise-adaptive weight can make the expected squared norm smaller than every fixed-weight expectation. If the intended metric is instead E[min_{λ∈C}‖λ^T∇F(x_t)‖²], then Definition 3 and the theorem statements should be changed accordingly, and the output rule and sample-complexity statement should be aligned with that corrected metric.","section":"Section 4.1, Theorem 1 proof and Definition 3"}],"minor_comments":[{"comment":"Figure 1 and Table 3 use the name \"STIMULATE\" instead of \"STIMULUS\", and Table 3 also uses \"SGMD\" instead of \"SMGD\"; these should be corrected.","section":"Throughout, figures and tables"},{"comment":"The definition of the adaptive batch size uses γ_t with subscripts and summations that are hard to parse, and the text switches between n_k and n_t; please clarify the indexing and restate γ_{t+1} unambiguously.","section":"Section 3.3, Eq. (6)"},{"comment":"Assumption 4 is stated for \"any x in R^n\" although the ambient dimension is d, and x* is not explicitly defined as common to all objectives; please state the assumption in R^d and clarify the status of x*.","section":"Section 4.1, Assumption 4"},{"comment":"The experimental comparison reports training loss only and does not include variances or multiple seeds; adding error bars or a brief statement about variability would strengthen the empirical claims.","section":"Section 5"}],"recommendation":"major_revision","confidential_remarks":"The strongly convex results are the main liability: Assumption 4 is effectively as strong as the conclusion and removes the multi-objective trade-off, so a referee will likely see those theorems as vacuous. If the authors cannot repair this, the non-convex contribution could still be publishable with the strongly convex claims removed. The min/expectation issue in Theorem 1 is also worth fixing at the definitional level; it is a formal gap but appears repairable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the paper's non-convex result is a correct, if unsurprising, application of SPIDER variance reduction to multi-gradient descent: O(1/T) convergence with O(n+sqrt(n)/epsilon) sample complexity, matching the deterministic MGD rate. Second, the strongly convex theorems are not what they appear. Assumption 4 makes them vacuous, and the stress-test note is exactly right.\n\nThe contribution that is real: this is the first time the SPIDER estimator is combined with the multi-gradient common-descent direction. The proof of Theorem 1 follows Fang et al. closely, and the key lemmas are cited in the appendix. That part is solid. The paper also proposes momentum and adaptive-batching variants, and the non-convex analyses of those variants are the same SPIDER machinery with extra bookkeeping.\n\nThe problem is Assumption 4. It states that for a fixed Pareto-optimal x*, every objective satisfies f_j(x) - f_j(x*) >= (c_j/2) ||x - x*||^2 for all x. That inequality forces f_j(x*) to be a global minimum of f_j. For strongly convex f_j, the minimizer is unique, so every objective shares the same minimizer x*. There is no Pareto trade-off left. The multi-objective problem collapses to a single-objective one. The proof of Theorem 2 never uses the constants c_j, which is the tell: any meaningful Pareto-PL assumption would put those constants in the rate. So the O(exp(-mu T)) claims in Theorems 2, 4, and 6 do not cover genuine MOO trade-offs.\n\nSmaller issues: the SPIDER estimator is presented as new in the main text with the citation buried in an appendix, which is misleading. The experiments report fixed batch sizes even for the adaptive-batching variants and have no error bars, so they do not faithfully test the claimed practical benefit.\n\nBottom line: the non-convex contribution is worth publishing; the strongly convex claims need to be fixed or removed. This paper deserves a serious referee, but the referee should send it back for major revision. The authors should either relax Assumption 4 to a genuine Pareto-PL condition with the constants appearing in the rate, or clearly state that the strongly convex setting assumes a common minimizer and reframe it as a single-objective special case.","headline":"The non-convex half of STIMULUS is a solid SPIDER-for-MOO result; the strongly convex half is vacuous because Assumption 4 collapses the problem to single-objective.","tokens_in":40571,"tokens_out":4848,"would_cite":false,"duration_ms":46764,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C29","90C15","90C26","90C25"],"pacs":[],"model":"deepseek-v4-flash","headline":"STIMULUS is a stochastic multi-objective optimization algorithm that claims deterministic-level convergence and near-linear sample complexity through recursive variance-reduced multi-gradient estimation.","keywords":["multi-objective optimization","Pareto stationarity","stochastic multi-gradient descent","variance reduction","sample complexity","linear convergence","adaptive batching","momentum"],"falsifier":"On the two-objective strongly convex pair $f_1(x)=(x+1)^2$, $f_2(x)=(x-1)^2$ with $x^*=0$, Assumption 4 fails even though both objectives are $\\mu$-strongly convex; simulating STIMULUS and checking whether $\\mathbb{E}\\|x_t-x^*\\|^2$ still decays at the claimed $3\\eta\\mu/4$ rate would show whether the linear rate is a property of strong convexity or only of the extra quadratic-growth condition.","tokens_in":39398,"feed_emoji":"⚖️","tokens_out":9556,"duration_ms":90601,"temperature":0.7,"pith_summary":"STIMULUS is a stochastic algorithm for multi-objective optimization that claims the convergence rate of deterministic multi-gradient descent while keeping per-iteration cost low. For non-convex objectives it achieves $O(1/T)$ Pareto-stationarity convergence, and for $\\mu$-strongly convex objectives it achieves linear $O(\\exp(-\\mu T))$ convergence; the corresponding sample complexities are $O(n+\\sqrt{n}/\\epsilon)$ and $O(n+\\sqrt{n}\\ln(\\mu/\\epsilon))$. A recursive estimator of the multi-gradient, refreshed by the full gradient every $\\lceil\\sqrt{n}\\rceil$ steps, suppresses the noise that makes plain stochastic multi-gradient descent stall at $O(1/\\sqrt{T})$. The paper further adds momentum (STIMULUS-M) and adaptive-batching (STIMULUS+ and STIMULUS-M+) variants that retain these rates and avoid exact full-gradient evaluations.","feed_headline":"Stochastic MOO hits O(1/T) with sqrt(n)-scale samples","feed_subtitle":"STIMULUS's recursive gradient estimator cuts sample complexity to O(n + sqrt(n)/epsilon) in non-convex multi-objective learning.","key_machinery":"The object that carries the argument is the recursive multi-gradient estimator $u_t^s = u_{t-1}^s + \\frac{1}{|A|}\\sum_{j\\in A}(\\nabla f_{sj}(x_t) - \\nabla f_{sj}(x_{t-1}))$, reinitialized to the full multi-gradient every $q$ iterations. This estimator keeps the mean-square error $\\mathbb{E}\\|\\nabla f_s(x_t)-u_t^s\\|^2$ bounded by $L^2/|A|$ times the sum of squared step lengths over the current window, so the error does not accumulate across the whole trajectory. The descent direction $d_t=\\sum_s \\lambda_t^s u_t^s$ is chosen by minimizing $\\|\\sum_s \\lambda_s u_t^s\\|^2$ over the simplex, and the key descent lemma $f_s(x_{t+1}) \\le f_s(x_t) + \\frac{\\eta}{2}\\|\\nabla f_s(x_t)-u_t^s\\|^2 - \\frac{\\eta}{4}\\|d_t\\|^2$ converts estimator error into a telescoping bound. In the strongly convex analysis, the contraction factor $1-3\\mu\\eta/4$ comes from combining this descent inequality with Assumption 4 and averaging outputs with weights $w_t=(1-3\\mu\\eta/4)^{1-t}$.","core_discovery":"On its own terms, the paper's central discovery is that a path-integrated recursive estimator can carry variance reduction into multi-objective optimization without biasing the search across the Pareto front. Using this estimator in a multi-gradient descent loop yields a Pareto-stationarity gap $\\frac{1}{T}\\sum_{t=0}^{T-1}\\min_{\\lambda\\in C}\\mathbb{E}\\|\\lambda^\\top\\nabla F(x_t)\\|^2 = O(1/T)$ for non-convex finite-sum problems, and $\\mathbb{E}\\|x_t-x^*\\|^2 = O(\\mu \\exp(-3\\eta\\mu T/4))$ in the strongly convex case. With $q=|A|=\\lceil\\sqrt{n}\\rceil$ the method needs $O(n+\\sqrt{n}\\epsilon^{-1})$ incremental first-order oracle calls for $\\epsilon$-stationarity and $O(n+\\sqrt{n}\\ln(\\mu/\\epsilon))$ for $\\epsilon$-optimality. STIMULUS+ replaces the periodic exact gradient with an adaptively sized stochastic batch, so the algorithm applies even when exact gradients are unavailable, with the same order bounds.","pith_inferences":["If the bounds are tight, the $\\sqrt{n}$ term in the sample complexity suggests that data parallelism or approximate gradient oracles could be pushed further; one could derive lower bounds to see whether $O(n+\\sqrt{n}/\\epsilon)$ is optimal for stochastic MOO.","The strong-convexity analysis depends on Assumption 4 relative to one fixed Pareto point; for objectives with distinct minimizers this may not hold, so practitioners should check quadratic growth before expecting linear convergence.","The recursive estimator could be combined with other multi-gradient aggregation schemes, such as min-norm solvers with different regularizers, and with adaptive step sizes, potentially improving constant factors.","A natural testable extension is to use the adaptive-batching size rule as a heuristic in single-objective multi-task training, where the batch size grows in response to large recent gradient norms."],"forward_implications":["Stochastic multi-objective training can match the $O(1/T)$ rate of deterministic MGD, so a full-gradient refresh every $\\sqrt{n}$ steps is enough to remove the stochastic bottleneck.","The sample complexities $O(n+\\sqrt{n}/\\epsilon)$ and $O(n+\\sqrt{n}\\ln(\\mu/\\epsilon))$ improve on the $O(\\epsilon^{-2})$ and $O(\\epsilon^{-1})$ costs of prior stochastic MOO methods, helping in large-$n$ regimes.","The strongly convex result gives a stochastic MOO algorithm with logarithmic sample dependence on $1/\\epsilon$, so high-precision Pareto solutions become plausible with finite-sum or online objectives.","The adaptive-batching variants mean the algorithm no longer requires exact full gradients, making it applicable to expectation-form and streaming objectives while retaining the same order of sample complexity.","Momentum and adaptive batching are compatible in one family, giving practitioners a tuning knob between convergence speed and per-iteration cost."],"supporting_citations":[{"why":"Supplies the path-integrated estimator and Lemma 1 that bounds the recursive estimator's mean-square error by a windowed sum of step lengths.","marker":"Fang et al. [2018]"},{"why":"The deterministic MGD baseline whose O(1/T) rate and O(n/epsilon) complexity STIMULUS is designed to match.","marker":"[Fliege et al., 2019]"},{"why":"Provides the convex-hull property used in the descent lemmas to show the common direction d_t is a descent direction for every objective.","marker":"Désidéri [2012]"},{"why":"Provides the weighted-averaging lemma that converts the contraction inequality into the exponential bound in the strongly convex proofs.","marker":"[Karimireddy et al., 2020]"},{"why":"A prior stochastic multi-objective gradient-manipulation method and the source of the SMGD divergence example that motivates variance reduction.","marker":"[Zhou et al., 2022]"},{"why":"Defines the stochastic multi-gradient algorithm (SMGD) whose slow O(1/sqrt(T)) rate is the comparison baseline.","marker":"[Liu and Vicente, 2021]"},{"why":"Supplies the random-output weighting and stopping-clock idea used in Theorems 2 and 4.","marker":"[Ghadimi and Lan, 2013]"}],"fun_headline_variants":["MOO algorithm hits O(1/T) with sqrt(n) sample complexity","Recursive variance reduction speeds up stochastic MOO","STIMULUS reduces MOO sample needs to O(n+sqrt(n)/eps)","Adaptive-batch MOO keeps low sample complexity without full gradients"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"For the strongly convex results, the load-bearing assumption is that every objective grows at least quadratically from one fixed Pareto-optimal point $x^*$, an assumption stronger than strong convexity that can fail when objectives have different minimizers.","fun_headline_variants_meta":{"raw":{"variants":["MOO algorithm hits O(1/T) with sqrt(n) sample complexity","Recursive variance reduction speeds up stochastic MOO","STIMULUS reduces MOO sample needs to O(n+sqrt(n)/eps)","Adaptive-batch MOO keeps low sample complexity without full gradients"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001312,"raw_usage":{"total_tokens":5419,"prompt_tokens":1087,"completion_tokens":4332,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":703,"completion_tokens_details":{"reasoning_tokens":4255}},"tokens_in":703,"tokens_out":4332,"duration_ms":34729,"temperature":1.0,"reasoning_tokens":4255,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T18:36:01.784055+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On the two-objective strongly convex pair $f_1(x)=(x+1)^2$, $f_2(x)=(x-1)^2$ with $x^*=0$, Assumption 4 fails even though both objectives are $\\mu$-strongly convex; simulating STIMULUS and checking whether $\\mathbb{E}\\|x_t-x^*\\|^2$ still decays at the claimed $3\\eta\\mu/4$ rate would show whether the linear rate is a property of strong convexity or only of the extra quadratic-growth condition.","supporting_citations":[{"cited_title":"Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator","cited_arxiv_id":null,"evidence_quote":"Supplies the path-integrated estimator and Lemma 1 that bounds the recursive estimator's mean-square error by a windowed sum of step lengths."},{"cited_title":"Complexity of gradient descent for multiobjective optimization","cited_arxiv_id":null,"evidence_quote":"The deterministic MGD baseline whose O(1/T) rate and O(n/epsilon) complexity STIMULUS is designed to match."},{"cited_title":"SCAFFOLD : Stochastic controlled averaging for federated learning","cited_arxiv_id":null,"evidence_quote":"Provides the weighted-averaging lemma that converts the contraction inequality into the exponential bound in the strongly convex proofs."},{"cited_title":"The stochastic multi-gradient algorithm for multi-objective optimization and its application to supervised machine learning","cited_arxiv_id":null,"evidence_quote":"Defines the stochastic multi-gradient algorithm (SMGD) whose slow O(1/sqrt(T)) rate is the comparison baseline."}],"review_version":2}