ClipVR-MGDA: Optimal Stochastic Algorithm for Generalized-Smooth Multi-Objective Optimization

Multi-objective optimization (MOO) has become increasingly important in modern machine learning applications. While many stochastic multi-gradient descent algorithms (MGDA) have been developed for MOO, they typically suffer from suboptimal sample complexity for finding a Pareto stationary point. This has motivated MOCO+, a variance-reduced algorithm for MOO. However, its convergence guarantee relies on restrictive assumptions and applies only to smooth objective functions that are uncommon in applications with complex models. We develop ClipVR-MGDA, an optimal stochastic algorithm for non-convex MOO under a broad class of generalized-smooth objectives. ClipVR-MGDA integrates a matrix-valued SPIDER estimator with MGDA-type updates to construct variance-reduced multi-gradient estimates across all objectives. To enable effective multi-gradient variance reduction under generalized-smooth objectives, we further introduce carefully designed gradient-clipping schemes for both the parameter update and the preference vector update. Under standard assumptions, we prove that ClipVR-MGDA converges to an $ϵ$-Pareto stationary point with the optimal $\mathcal{O}({ϵ}^{-3})$ sample complexity. Experiments on multi-task learning benchmarks demonstrate improved performance over existing stochastic MOO baselines.