# Complexity Bounds for Smooth Multiobjective Optimization

arXiv: https://arxiv.org/abs/2509.13550 · HTML: https://mlsanity.com/paper/2509.13550/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 37 references that are in the map.
- First posted on arXiv 16 Sep 2025.

## Builds on (most cited first, 17 of 17)

- [Multi-Task Learning as Multi-Objective Optimization](https://mlsanity.com/paper/1810.04650/) (2018)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017)
- [Lower Bounds for Finding Stationary Points II: First-Order Methods](https://mlsanity.com/paper/1711.00841/) (2017)
- [Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Construction](https://mlsanity.com/paper/2103.08280/) (2021)
- [On the Iteration Complexity of Oblivious First-Order Optimization Algorithms](https://mlsanity.com/paper/1605.03529/) (2016)
- [Lower Bound for Randomized First Order Convex Optimization](https://mlsanity.com/paper/1709.03594/) (2017)
- [Optimal and parameter-free gradient minimization methods for convex and nonconvex optimization](https://mlsanity.com/paper/2310.12139/) (2023)
- [Convergence rates analysis of a multiobjective proximal gradient method](https://mlsanity.com/paper/2010.08217/) (2020)
- [An accelerated proximal gradient method for multiobjective optimization](https://mlsanity.com/paper/2202.10994/) (2022)
- [Dimension-Free Iteration Complexity of Finite Sum Optimization Problems](https://mlsanity.com/paper/1606.09333/) (2016)
- [Conditional gradient method for vector optimization](https://mlsanity.com/paper/2109.11296/) (2021)
- [Multi-objective Portfolio Optimization Via Gradient Descent](https://mlsanity.com/paper/2507.16717/) (2025)
- [Monotonicity for Multiobjective Accelerated Proximal Gradient Methods](https://mlsanity.com/paper/2206.04412/) (2022)
- [Adaptive generalized conditional gradient method for multiobjective optimization](https://mlsanity.com/paper/2404.04174/) (2024)
- [Improved convergence rates for the multiobjective Frank-Wolfe method](https://mlsanity.com/paper/2406.06457/) (2024)
- [Universal nonmonotone line search method for nonconvex multiobjective optimization problems with convex constraints](https://mlsanity.com/paper/2411.09466/) (2024)

## Abstract (arXiv)

We study the oracle complexity of finding varepsilon-Pareto stationary points in smooth multiobjective optimization with m objectives. Progress is measured by the Pareto stationarity gap G(x), the norm of the best convex combination of objective gradients. Our analysis relies on a non-degenerate lifting that embeds hard single-objective instances into MOO instances with distinct objectives and non-singleton Pareto fronts while preserving lower bounds on G. We establish: (i) in the μ-strongly convex case, any span first-order method has worst-case linear convergence no faster than exp(-Theta(T/√kappa)) after T oracle calls, yielding Theta(√kappalog(1/varepsilon)) iterations and matching accelerated upper bounds; (ii) in the convex case, an Omega(1/T) min-iterate lower bound for oblivious one-step methods and a universal last-iterate lower bound Omega(1/T2) for oblivious span methods via polynomial-degree arguments, and we further show this latter bound is loose (for general adaptive methods) by importing geometric lower bounds to obtain an Omega(1/T) min-iterate lower bound for general adaptive first-order methods; (iii) in the nonconvex case with L-Lipschitz gradients, an Omega(√L/(T+1))-type lower bound on G (tight in order), implying Omega(1/varepsilon2) iterations to reach G(x)≤varepsilon up to natural scaling.