Improved Convergence Rate for Stochastic Multi-Gradient Descent: A Proof Discovered with AI

Lisha Chen

Improved Convergence Rate for Stochastic Multi-Gradient Descent: A Proof Discovered with AI

T0 review · 0 major / 4 minor · reviewed 2026-08-01 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A new proof establishes that stochastic multi-gradient descent, with a constant step size and linearly growing mini-batches, converges to an empirical Pareto-stationary point at rate O~(1/T), improving the previous O~(T^{-1/4}) guarantee fo

desk verdict Short, correct note: an elementary 1-Lipschitz lemma on the Pareto-stationarity measure improves vanilla SMG's rate from Õ(T^{-1/4}) to Õ(T^{-1}), and the proof checks out line by line. read the letter →

arxiv 2607.18174 v1 pith:3E4KOTC5 submitted 2026-07-20 math.OC

Lisha Chen This is my paper

classification math.OC MSC 90C1590C2690C2990C30

keywords multi-objectiveoptimizationstochasticmulti-gradientdescentMGDAParetostationaritygrowingmini-batchesnonconvexconvergencerateAI-assistedproof

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proves that the vanilla stochastic multi-gradient descent (SMG) algorithm—the simple growing-batch method for multi-objective optimization—drives a natural stationarity measure to zero at rate O~(1/T) on smooth nonconvex problems, where the previous best rate for the same method was O~(T^{-1/4}). The gain comes from treating the squared Pareto-stationarity measure, the norm of the multi-gradient descent direction, as a Lipschitz function of the gradient matrix, so that stochastic errors enter through their second moment instead of a fourth root. A careful telescoping argument shows that the expected stationarity measure at a randomly chosen iterate is bounded by roughly 1/T plus a variance term that decays like (log T)/T when batch sizes grow linearly. This improves the theoretical understanding of a widely used method and suggests that growing batches are more powerful than earlier analyses indicated.

What carries the argument

Lemma 2, the Lipschitz continuity of the Pareto-stationarity measure. For any gradient matrices Q,Q', r(Q)=∥d_Q∥ satisfies |r(Q)-r(Q')| ≤ ∥Q-Q'∥_2 ≤ ∥Q-Q'∥_F. This inequality is the mechanism that replaces the (1/2)-Hölder continuity of the MGDA direction map Q↦d_Q used in the prior analysis. Because the variance bound in Assumption 2 controls the squared Frobenius norm of the mini-batch error E_t, applying Lemma 2 converts the stationarity error into a sum of squared error terms that telescope with the growing batch sizes.

What would settle it

Construct a smooth nonconvex multi-objective problem where the objective gradients grow along the SMG trajectory (e.g., by making the dataset include points with arbitrarily large norms), so that the uniform variance bound fails, and test whether the empirical squared PS measure at the output still decays at the predicted ~1/T rate. Alternatively, run SMG with linearly growing batches on a standard benchmark and average over many seeds: a decay substantially slower than 1/T would contradict the theorem's upper bound.

Watch

Extended reading notes

Core claim

The central claim is that under standard smoothness, unbiasedness, and bounded-variance assumptions, with constant step size α ∈ (0,1/(2L)] and linearly growing mini-batches |Z_t| ≥ b(t+1), the expected squared empirical Pareto-stationarity measure at the algorithm's output satisfies E[R_S(x_τ)] ≤ 8Δ/(αT) + (4+2M)σ²(1+log T)/(bT) = O~(M/T) (Corollary 2, Eq. (27)). The proof's key step is Lemma 2, which shows the PS measure r(Q)=min_{λ∈Δ_M} ||Qλ|| is Lipschitz continuous in the gradient matrix Q: |r(Q)-r(Q')| ≤ ||Q-Q'||_F. This lets the one-step descent bound be expressed in terms of the squared norm of the mini-batch gradient error, whose expectation is the variance bound σ²/|Z_t|. Telescopi

Load-bearing premise

The entire argument rests on a uniform bound on the per-sample gradient variance along the trajectory: for every objective and every history, the conditional variance of the mini-batch gradient is at most σ²/|Z_t|. If this bound does not hold for the problem at hand—for instance, if gradient norms grow without bound—the second-moment control in the proof collapses and the O~(1/T) rate is not guaranteed.

Editorial extensions

If this is right

SMG with constant step size and linearly growing mini-batches achieves E[R_S(x_τ)] = O~(1/T) for the squared empirical Pareto-stationarity measure, with T iterations and an explicit dependence on the number of objectives M.
The bound holds for any smooth nonconvex problem under unbiased, variance-bounded stochastic gradients; no convexity, no bounded-gradient assumption, and no Lipschitz selection of the MGDA weight is needed.
The randomized output of Algorithm 1 (a stepsize-weighted random iterate) carries the guarantee; the terminal iterate x_T is not claimed to converge.
The general theorem gives a rate of O(1/A_T + V_T/A_T) for arbitrary step and batch schedules, so the O~(1/T) rate is recovered whenever batch sizes grow at least linearly.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same Lipschitz-PS-measure inequality may yield improved rates for other stochastic MGDA variants that currently rely on Hölder continuity of the direction, such as methods using variance reduction or adaptive sampling; the clean second-moment error may combine better with momentum.
Because the Lipschitz constant of the PS measure is 1, the proof suggests that the achievable rate for SMG is limited chiefly by how fast the mini-batch variance decays; batch schedules that grow faster than linear would only remove the logarithmic factor, not change the 1/T baseline.
An open question this suggests: whether a similar rate could be obtained without growing batches by using importance sampling or variance reduction to control the gradient-error second moment, which would parallel the single-objective SGD theory.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The main claim holds up. I went through the proof inequality by inequality: Lemma 2 is the elementary fact that r(Q) = min_{λ∈Δ}||Qλ|| is 1-Lipschitz in Q, Lemma 1 is the standard projection argument, and the descent chain (16)–(22) has correct constants — the (4+2M) coefficient, the V_T/A_T term, the (1+log T)/(bT) bound. Corollary 2's Õ(T⁻¹) follows. I couldn't find a circular step or a fitted constant anywhere; the proof is self-contained and the comparison to Chen et al. (2024) is external to the derivation.

What's actually new: replacing the (1/2)-Hölder continuity of the MGDA direction with 1-Lipschitz continuity of its norm. That shifts the stochastic error from a fourth root to a second moment, which is precisely what converts T^{-1/4} into T^{-1}. The observation is simple once stated, but it's the right tool and I don't see it in the cited work. The AI-assistance disclosure is also exemplary: prompt documented, student submissions summarized, and the author takes responsibility. The math does not depend on the provenance.

Soft spots, in proportion. Remark 2 makes two claims about refining Chen et al. and proves neither; neither is load-bearing, but they should be proved in a sentence or deleted. The rate rests on the uniform per-sample variance bound in Eq. (8) holding along the entire nonconvex trajectory — standard in this literature and shared by Chen et al., but it is a real restriction; if the bound decays more slowly, the second-moment control collapses. And the improvement deserves context: with |Z_t| = Θ(t+1), total samples are Θ(T²), so the Õ(T⁻¹) iteration rate means Θ(ε⁻²) sample complexity, and constant-batch variance-reduced methods like MoCo+ still win on total samples. The paper doesn't misstate this, but it's easy to over-read the rate table. Minor: the only corollary is numbered 2, and the side-by-side comparison is explicitly schematic.

Who this is for: researchers working on stochastic multi-objective optimization rates, and anyone tracking LLM-assisted proof discovery — this is a clean, checkable example of the genre. It deserves a real referee, not a desk reject; the proof is short enough that refereeing is cheap. My recommendation: send it out, accept after minor revision.

Referee Report

0 major / 4 minor

Summary. The paper studies vanilla stochastic multi-gradient descent (SMG) for smooth nonconvex multi-objective optimization with stochastic gradients. It proves that, under constant stepsize and growing mini-batches, the expected squared empirical Pareto-stationarity measure of the randomized output is O~(T^{-1}). The main result (Theorem 1, Eq. (15)) bounds the weighted-average PS measure by 8Δ/A_T+(4+2M)σ^2 V_T/A_T; with α_t=α and |Z_t|≥b(t+1), Corollary 2 gives (1+log T)/T. The key novelty is Lemma 2, the 1-Lipschitz continuity of r(Q)=min_λ ||Qλ||, which lets the stochastic error enter through its second moment instead of a fourth root. The proof is self-contained and avoids the 1/2-Hölder continuity of the MGDA direction used in prior work.

Significance. If correct, the result is a genuine improvement: vanilla SMG with linearly growing batches is shown to converge at O~(1/T) in squared Pareto-stationarity, versus the previous O~(T^{-1/4}) from Chen et al. (2024). The proof is elementary and transparent; Lemma 2 is simple but effective, and all constants are explicit. The paper also gives a useful side-by-side comparison of proof mechanisms and unusually transparent documentation of the AI-assisted proof discovery. The rate depends only on standard smoothness and variance assumptions; no fitted parameters or numerical claims are involved. I agree with the stress-test assessment: the proof chain is internally consistent and no load-bearing flaw is apparent.

minor comments (4)

[Abstract / Remark 1] The abstract and Remark 1 state that the rate improves on Chen et al. (2024) 'under the same setting.' The side-by-side comparison in Remark 1 shows Chen et al. specialized to α_t=Θ(T^{-1/2}), whereas Corollary 2 uses a constant stepsize α. Please qualify the comparison: either state explicitly that the constant-stepsize regime is part of the improvement, or cite an exact Chen et al. bound with constant stepsize if one exists.
[Remark 2] The two refinements of the Chen et al. analysis are asserted without proof. They are not used in the main theorem, so they do not affect the central claim, but as written they are unverifiable. Add a brief derivation or explicitly label them as observations/conjectures.
[References] Several bibliographic entries contain the placeholder 'Available at.' with no URL or identifier (e.g., Bubeck et al. 2025, Chen et al. 2024, Chen et al. 2025). Complete the reference list before publication.
[Corollary 2, Eq. (26)] The chain E[min_t R_S(x_t)] ≤ min_t E[R_S(x_t)] is correct, but the first inequality may be non-obvious; a one-sentence justification would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the convergence proof is self-contained and derives the claimed rate from explicitly stated assumptions.

full rationale

The paper's central claim is a finite-time convergence rate for vanilla SMG under Assumptions 1–2. The derivation chain is self-contained: Lemma 1 is proved from projection optimality, Lemma 2 is proved from the triangle inequality and the definition r(Q)=min_{λ∈Δ}||Qλ||, and Theorem 1 follows by combining L-smoothness, the common-descent inequality, Lemma 2, and the variance bounds in Assumption 2. The telescoping step uses only the lower bound on each f_{S,m} and the definition of A_T and V_T; no step assumes the target Õ(T^{-1}) rate. Corollary 2 then specializes the general bound to constant stepsize and the linear batch-growth schedule, with V_T/A_T bounded by O(log T/T). The comparison with Chen et al. (2024) is an external baseline, not a load-bearing premise: the paper re-proves the lemmas it needs and does not rely on the prior paper's conclusions to establish its own inequality. There are no fitted parameters, no quantity defined in terms of the target, and no prediction that reduces to an input by construction. The only possibly noteworthy self-citation is the prior work of the same author, but it is used for context and comparison, not as evidence for the new proof. Therefore no circular step is identifiable.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

No new entities or fitted numerical constants are introduced; the result follows from standard smoothness/variance assumptions and elementary convex analysis. The only hand-chosen hyperparameters are stepsize α and batch-growth constant b, which do not affect the rate order.

free parameters (2)

Constant stepsize α = α ∈ (0, 1/(2L)] (user-selected)
The theorem holds for every admissible constant stepsize; the bound scales as 8(f0−f_inf)/(αT), so α is a tunable hyperparameter, not a fitted constant.
Batch-growth lower bound b = b > 0 with |Z_t| ≥ b(t+1) (user-selected)
The logarithmic factor (1+log T)/(bT) depends on b; any positive b preserves the Õ(T^{-1}) rate, so it is not fitted to data.

assumptions (4)

domain assumption Each per-sample objective f_{z,m} is L-smooth and each empirical objective is bounded below (Assumption 1).
Smoothness drives the descent inequality (17); boundedness below provides the telescoping upper bound. Not checked by the paper; standard in nonconvex smooth optimization.
domain assumption Conditional unbiasedness and variance bound E||q_{t,m}−∇f_{S,m}(x_t)||² ≤ σ²/|Z_t| (Assumption 2, Eq. (8)).
This is the load-bearing bound: it converts the second-moment error term into Σ α_t/|Z_t|, which gives the log/T factor. If variance decayed more slowly, the rate degrades.
domain assumption Mini-batches are sampled uniformly with replacement, independent of the past (Assumption 2).
Used to justify unbiasedness and the 1/|Z_t| variance scaling.
standard math The minimum-norm point of a compact convex set is unique (standard convex analysis).
Ensures d_t = −Q_t λ_t is well-defined even when λ_t is nonunique (stated after Eq. (6)); standard.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Improved Convergence Rate for Stochastic Multi-Gradient Descent: A Proof Discovered with AI." pith.science (2026). https://pith.science/paper/3E4KOTC5

@misc{pith2026260718174,
  author       = {Pith},
  title        = {Pith review of: Improved Convergence Rate for Stochastic Multi-Gradient Descent: A Proof Discovered with AI},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3E4KOTC5}},
  note         = {Machine review of arXiv:2607.18174}
}

abstract

For smooth nonconvex stochastic multi-objective problems, stochastic multi-gradient descent (SMG) computes an approximate steepest common descent direction of the objectives from stochastic gradients. With unbiased, variance-bounded stochastic gradients, this note establishes a new convergence rate for SMG in terms of the squared Pareto-stationarity (PS) measure. With a constant stepsize and linearly growing mini-batches, this measure at the algorithm's output is $\widetilde O(T^{-1})$ after $T$ iterations. This improves on the $\widetilde O(T^{-1/4})$ bound obtained by Chen et al. (2024) under the same setting, where $\widetilde O(\cdot)$ suppresses logarithmic factors. The key to the rate improvement is to exploit the Lipschitz continuity of the PS measure, defined by the norm of the multi-gradient descent algorithm (MGDA) direction, rather than the $(1/2)$-H\"older continuity of the MGDA direction used by Chen et al. (2024). The proof was discovered while the author was preparing homework for a graduate course: ChatGPT 5.4 Thinking Extended generated the initial proof strategy in response to an author-written homework-solution prompt; the author then verified and reorganized the resulting argument. The appendices document the prompt and summarize the student submissions.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

24 extracted references · 4 linked inside Pith

[1]

K., Unutmaz, D., Weil, K., Yin, S., & Zhivotovskiy, N

Spears, B. K., Unutmaz, D., Weil, K., Yin, S., & Zhivotovskiy, N. (2025). Early science acceleration experiments with GPT-5.arXiv preprint arXiv:2511.16072. Available atὑ7

arXiv 2025
[2]

D., Ying, Y., & Chen, T

Chen, L., Fernando, H. D., Ying, Y., & Chen, T. (2024). Three-way trade-off in multi-objective learning: Optimization, generalization and conflict-avoidance.Journal of Machine Learning Research,25(193), 1–53. Available atὑ7

2024
[3]

Chen, W., Lin, B., Zhang, X., Lin, X., Zhao, H., Zhang, Q., & Kwok, J. T. (2025). Gradient-based multi- objective deep learning: Algorithms, theories, applications, and beyond.arXiv preprint arXiv: 2501.10945. Available atὑ7. D´ esid´ eri, J.-A. (2012). Multiple-gradient descent algorithm (MGDA) for multiobjective optimization.Comptes Rendus Math´ ematiqu...

arXiv 2025
[4]

(2005).Multicriteria optimization(2nd ed.)

Ehrgott, M. (2005).Multicriteria optimization(2nd ed.). Springer. Available atὑ7

2005
[5]

D., Chen, L., Lu, S., Chen, P

Fernando, H. D., Chen, L., Lu, S., Chen, P. -Y., Liu, M., Chaudhury, S., Murugesan, K., Liu, G., Wang, M., & Chen, T. (2024). Variance reduction can improve trade-off in multi-objective learning.IEEE International Conference on Acoustics, Speech and Signal Processing, 6975–6979. Available atὑ7

2024
[6]

D., Shen, H., Liu, M., Chaudhury, S., Murugesan, K., & Chen, T

Fernando, H. D., Shen, H., Liu, M., Chaudhury, S., Murugesan, K., & Chen, T. (2023). Mitigating gradient bias in multi-objective learning: A provably convergent approach.International Conference on Learning Representations. Available atὑ7

2023
[7]

Fliege, J., & Svaiter, B. F. (2000). Steepest descent methods for multicriteria optimization.Mathematical Methods of Operations Research,51(3), 479–494. Available atὑ7

2000
[8]

Huang, C., & Chen, L. (2026). Regularity-aware stochastic MGDA with adaptive conflict-avoidant update direction control.arXiv preprint arXiv:2607.15412. Available atὑ7

arXiv 2026

Show all 24 references

[9]

Jang, U., & Ryu, E. K. (2025). Point convergence of Nesterov’s accelerated gradient method: An AI-assisted proof.arXiv preprint arXiv:2510.23513. Available atὑ7

2025
[10]

Kim, S., & Pilanci, M. (2026). AI-assisted discovery of convex relaxations via dual agents.arXiv preprint arXiv:2606.31182. Available atὑ7

2026 arXiv
[11]

Liu, S., & Vicente, L. N. (2024). The stochastic multi-gradient algorithm for multi-objective optimization and its application to supervised machine learning.Annals of Operations Research,339(3), 1119–1148. Available atὑ7

2024
[12]

Liu, Z., Dong, C., Momma, M., Shao, S., Xu, S., Gao, Y., Yang, H., & Liu, J. (2025). STIMULUS: Achieving fast convergence and low sample complexity in stochastic multi-objective learning.Proceedings of the Forty-first Conference on Uncertainty in Artificial Intelligence,286, 2...

2025
[13]

Ma, S. (2026). Convergence of BDRS as a matrix scaling algorithm.Optimization Online preprint. Available atὑ7

2026
[14]

Mercier, Q., Poirion, F., & D´ esid´ eri, J.-A. (2018). A stochastic multiple gradient descent algorithm.European Journal of Operational Research,271(3), 808–817. Available atὑ7

2018
[15]

Mukai, H. (1980). Algorithms for multicriterion optimization.IEEE Transactions on Automatic Control, 25(2), 177–186. Available atὑ7

1980
[16]

Orabona, F. (2026). Last-iterate convergence of optimistic multiplicative weight update.arXiv preprint arXiv:2606.11773. Available atὑ7

2026 arXiv
[17]

Salim, A. (2025). Accelerating mathematical research with language models: A case study of an interaction with GPT-5-Pro on a convex analysis problem.arXiv preprint arXiv:2510.26647. Available atὑ7

2025
[18]

Svaiter, B. F. (2018). The multiobjective steepest descent direction is not Lipschitz continuous, but is H¨ older continuous.Operations Research Letters,46(4), 430–433. Available atὑ7

2018
[19]

Xiao, P., Ban, H., & Ji, K. (2023). Direction-oriented multi-objective learning: Simple and provable stochastic algorithms.Advances in Neural Information Processing Systems,36, 4509–4533. Available atὑ7

2023
[20]

Xu, M., Ju, P., Liu, J., & Yang, H. (2025). PSMGD: Periodic stochastic multi-gradient descent for fast multi-objective optimization.Proceedings of the AAAI Conference on Artificial Intelligence,39(20), 21770–21778. Available atὑ7

2025
[21]

Yang, H., & Kwok, J. (2025). Joint gradient balancing for data ordering in finite-sum multi-objective optimization.International Conference on Learning Representations. Available atὑ7

2025
[22]

Zhang, Q., Xiao, P., Zou, S., & Ji, K. (2025). MGDA converges under generalized smoothness, provably. International Conference on Learning Representations. Available atὑ7

2025
[23]

Zhao, Y., Chen, W., & Yang, X. (2024). Adaptive sampling stochastic multigradient algorithm for stochastic multiobjective optimization.Journal of Optimization Theory and Applications,200(1), 215–241. Available atὑ7

2024
[24]

Zhou, S., Zhang, W., Jiang, J., Zhong, W., Gu, J., & Zhu, W. (2022). On the convergence of stochastic multi-objective gradient manipulation and beyond.Advances in Neural Information Processing Systems,35, 38103–38115. Available atὑ7

2022

Pith tools

Reviewed August 1, 2026 · model on record in the stance chip above.

[1] [1]

K., Unutmaz, D., Weil, K., Yin, S., & Zhivotovskiy, N

Spears, B. K., Unutmaz, D., Weil, K., Yin, S., & Zhivotovskiy, N. (2025). Early science acceleration experiments with GPT-5.arXiv preprint arXiv:2511.16072. Available atὑ7

arXiv 2025

[2] [2]

D., Ying, Y., & Chen, T

Chen, L., Fernando, H. D., Ying, Y., & Chen, T. (2024). Three-way trade-off in multi-objective learning: Optimization, generalization and conflict-avoidance.Journal of Machine Learning Research,25(193), 1–53. Available atὑ7

2024

[3] [3]

Chen, W., Lin, B., Zhang, X., Lin, X., Zhao, H., Zhang, Q., & Kwok, J. T. (2025). Gradient-based multi- objective deep learning: Algorithms, theories, applications, and beyond.arXiv preprint arXiv: 2501.10945. Available atὑ7. D´ esid´ eri, J.-A. (2012). Multiple-gradient descent algorithm (MGDA) for multiobjective optimization.Comptes Rendus Math´ ematiqu...

arXiv 2025

[4] [4]

(2005).Multicriteria optimization(2nd ed.)

Ehrgott, M. (2005).Multicriteria optimization(2nd ed.). Springer. Available atὑ7

2005

[5] [5]

D., Chen, L., Lu, S., Chen, P

Fernando, H. D., Chen, L., Lu, S., Chen, P. -Y., Liu, M., Chaudhury, S., Murugesan, K., Liu, G., Wang, M., & Chen, T. (2024). Variance reduction can improve trade-off in multi-objective learning.IEEE International Conference on Acoustics, Speech and Signal Processing, 6975–6979. Available atὑ7

2024

[6] [6]

D., Shen, H., Liu, M., Chaudhury, S., Murugesan, K., & Chen, T

Fernando, H. D., Shen, H., Liu, M., Chaudhury, S., Murugesan, K., & Chen, T. (2023). Mitigating gradient bias in multi-objective learning: A provably convergent approach.International Conference on Learning Representations. Available atὑ7

2023

[7] [7]

Fliege, J., & Svaiter, B. F. (2000). Steepest descent methods for multicriteria optimization.Mathematical Methods of Operations Research,51(3), 479–494. Available atὑ7

2000

[8] [8]

Huang, C., & Chen, L. (2026). Regularity-aware stochastic MGDA with adaptive conflict-avoidant update direction control.arXiv preprint arXiv:2607.15412. Available atὑ7

arXiv 2026