Improved Convergence Rates for Stochastic Multi-Gradient Descent: A Human-Verified AI Proof

For smooth nonconvex stochastic multi-objective optimization, stochastic multi-gradient descent (SMG) computes an approximate steepest common descent direction from stochastic gradients. Under standard smoothness and variance assumptions, this paper establishes an $\widetilde{O}(T^{-1})$ bound on the expected squared empirical Pareto-stationarity (PS) measure at the randomized output after $T$ iterations. With a constant stepsize and linearly growing mini-batches, this improves on the $\widetilde{O}(T^{-1/4})$ bound of Chen et al. (2024) without requiring bounded gradients. Here, $\widetilde{O}$ suppresses logarithmic factors. The key is to exploit Lipschitz continuity of the PS measure, defined by the norm of the multi-gradient descent algorithm (MGDA) direction, rather than Hölder continuity of the direction itself. The $\Theta(T^2)$ sampled-gradient cost gives a corresponding $\widetilde{O}(N^{-1/2})$ sample rate for a fixed number of objectives. Appendix D extends the analysis to exact-MGDA variants of MoCo and MoCo+. The proof arose during graduate homework preparation: ChatGPT 5.4 Thinking Extended generated the initial SMG proof strategy from an author-written prompt and mathematical context; the author then verified, corrected, and reorganized the argument and manually drafted the comparison with the prior proof.