Research map / Optimization / Nonconvex and smooth optimization
MGDA Converges under Generalized Smoothness, Provably
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that MGDA and its double-sampling stochastic variant converge to epsilon-accurate Pareto stationary points under generalized l-smoothness, with warm start for iteration-wise CA distance and a cheap MGDA-FA variant.
Problem
Convergence of multi-objective optimization (MGDA and stochastic variants) when objectives are only generalized l-smooth (unbounded Lipschitz constant and gradient norm), as is the case for LSTMs and Transformers, rather than standard L-smooth with bounded gradients.
Approach
Analyzes MGDA under generalized l-smoothness without bounded-gradient assumptions by using induction on bounded function values (which bound gradient norms up to M), adds l2 regularization for a unique weight solution, uses double sampling for unbiased stochastic multi-gradients, and a warm start to get iteration-wise CA distance; also proposes MGDA-FA using forward passes to update weights in O(1
Key results
- On NYU-v2 with SegNet, MGDA-warm start achieves the best average rank (MR 2.78) and Delta m% of -4.42, outperforming FAMO (-4.10) and Nash-MTL (-4.04).
- Theory: MGDA reaches an epsilon-accurate Pareto stationary point with O(epsilon^-2) samples (deterministic) and O(epsilon^-4) (stochastic) under generalized l-smoothness.
- With warm start, iteration-wise CA distance O(epsilon) is achieved with O(epsilon^-11) samples (deterministic) and O(epsilon^-17) (stochastic with mini-batches).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use MGDA-warm start instead of FAMO | SegNet multi-task learning · NYU-v2 | Δm%: -4.10 -> -4.42 | Helped |
| add warm start to MoCo | MoCo · Cityscapes | Δm%: 9.90 -> 7.32 | Helped |
| add warm start to MoCo | MoCo · NYU-v2 | Δm%: 0.16 -> -0.88 | Helped |
Surprising findings
- Local smoothness correlates positively with gradient norm when training SegNet on Cityscapes, supporting the generalized smoothness assumption in MOO.
- Adding a warm start to MoCo improves its Delta m% on NYU-v2 from 0.16 to -0.88 and on Cityscapes from 9.90 to 7.32.
Limitations
- Iteration-wise CA distance guarantee requires a warm start and much smaller step sizes, leading to high sample complexity (O(epsilon^-11) / O(epsilon^-17)).
- MGDA-FA's fast approximation may introduce substantial errors in practice and its stochastic convergence is not analyzed.
- Experiments are limited to SegNet on two pixel-wise multi-task datasets.
Experimental setup
Datasets: Cityscapes NYU-v2
Benchmarks: Cityscapes NYU-v2
Metrics: mIoU Pix Acc Abs Err Rel Err Angle Distance Within t degrees Delta m% MR
Baselines: MGDA PCGrad GradDrop CAGrad MoCo MoDo Nash-MTL FAMO LS SI RLW DWA
Builds on: MGDA MoCo MoDo SDMGrad generalized l-smoothness (Li et al. 2024) (L0,L1)-smoothness
Closest papers by meaning
- Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster (ICML 2025 · similarity 0.88)
- PSMGD: Periodic Stochastic Multi-Gradient Descent for Fast Multi-Objective Optimization (AAAI 2025 · similarity 0.87)
- Toward a Unified Theory of Gradient Descent under Generalized Smoothness (ICML 2025 · similarity 0.87)
- Fundamental Benefit of Alternating Updates in Minimax Optimization (ICML 2024 · similarity 0.87)
- Directional Smoothness and Gradient Methods: Convergence and Adaptivity (NeurIPS 2024 · similarity 0.86)
- On the Unstable Convergence Regime of Gradient Descent (AAAI 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.