Improved Convergence Rates for Stochastic Multi-Gradient Descent which Close the Gap: A Proof by AI
Abstract
For smooth nonconvex stochastic multi-objective optimization, stochastic multi-gradient descent (SMG) computes an approximate steepest common descent direction of the objectives from stochastic gradients. Under standard assumptions, 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, the expected squared empirical PS measure at the algorithm's output is Õ(T−1) after T iterations. This improves on the Õ(T−1/4) bound obtained by Chen et al. (JMLR, 2024) for linearly growing batches, without requiring bounded gradients. Here, Õ(·) 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ölder continuity of the MGDA direction used by Chen et al. (2024). For variants of MoCo and MoCo+ with exact MGDA updates and constant batch sizes, the analysis gives expected squared empirical PS rates of O(T−1/2) and Õ(T−2/3), respectively. These bounds match the corresponding single-objective momentum rates up to logarithmic factors. The proof was accidentally discovered while the author was preparing homework for a graduate course: ChatGPT 5.4 Thinking Extended generated the initial proof strategy for the main SMG result in response to an author-written homework-solution prompt; the author then verified and reorganized the resulting argument. The appendices document the prompt, summarize the student submissions with LLM disclosures, and present additional proofs and results on momentum-based stochastic MGDA.
Related
- A Rate Transfer Method: Convergence Rates in Stochastic Gradient Descent via Stochastic Calculus
- Convergence rate of stochastic gradient descent under Łojasiewicz type condition and polynomially controlled noise
- Convergence Rates of Factorized Gradient Descent for Overparameterized Asymmetric Matrix Sensing with Balancing Regularization
- Large-Step Last-Iterate Convergence of Random-Reshuffling Stochastic Gradient Descent
- Convergence of stochastic gradient descent for learning linear neural networks
BibTeX
@misc{chen2026improved,
title = {{Improved Convergence Rates for Stochastic Multi-Gradient Descent which Close the Gap: A Proof by AI}},
author = {Lisha Chen},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2607.18174},
eprint = {2607.18174},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.18174},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Improved Convergence Rates for Stochastic Multi-Gradient Descent which Close the Gap: A Proof by AI
AU - Lisha Chen
PY - 2026
DA - 2026/09/06
PB - arXiv
DO - 10.48550/arxiv.2607.18174
UR - https://arxiv.org/abs/2607.18174
AB - For smooth nonconvex stochastic multi-objective optimization, stochastic multi-gradient descent (SMG) computes an approximate steepest common descent direction of the objectives from stochastic gradients. Under standard assumptions, 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, the expected squared empirical PS measure at the algorithm's output is Õ(T^−1) after T iterations. This improves on the Õ(T^−1/4) bound obtained by Chen et al. (JMLR, 2024) for linearly growing batches, without requiring bounded gradients. Here, Õ(·) 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ölder continuity of the MGDA direction used by Chen et al. (2024). For variants of MoCo and MoCo+ with exact MGDA updates and constant batch sizes, the analysis gives expected squared empirical PS rates of O(T^−1/2) and Õ(T^−2/3), respectively. These bounds match the corresponding single-objective momentum rates up to logarithmic factors. The proof was accidentally discovered while the author was preparing homework for a graduate course: ChatGPT 5.4 Thinking Extended generated the initial proof strategy for the main SMG result in response to an author-written homework-solution prompt; the author then verified and reorganized the resulting argument. The appendices document the prompt, summarize the student submissions with LLM disclosures, and present additional proofs and results on momentum-based stochastic MGDA.
ER -