Abstract
We study the oracle complexity of finding $\varepsilon$-Pareto stationary points in smooth multiobjective optimization with $m$ objectives. The progress metric is the Pareto stationarity gap $\mathcal{G}(x)$ (the norm of an optimal convex combination of gradients). Our contributions are fourfold. (i) For strongly convex objectives, any span first-order method (iterates lie in the span of past gradients) exhibits linear convergence no faster than $\exp(-\Theta(T/\sqrt{\kappa}))$ after $T$ oracle calls, where $\kappa$ is the condition number, implying $\Theta(\sqrt{\kappa}\log(1/\varepsilon))$ iterations; this matches classical accelerated upper bounds. (ii) For convex problems and oblivious one-step methods (a fixed scalarization with pre-scheduled step sizes), we prove a lower bound of order $1/T$ on the best gradient norm among the first $T$ iterates. (iii) Although accelerated gradient descent is outside this restricted class, it is an oblivious span method and attains the same $1/T$ upper rate on a fixed scalarization. (iv) For convex problems and general span methods with adaptive scalarizations, we establish a universal lower bound of order $1/T^{2}$ on the gradient norm of the final iterate after $T$ steps, highlighting a gap between known upper bounds and worst-case guarantees. All bounds hold on non-degenerate instances with distinct objectives and non-singleton Pareto fronts; rates are stated up to universal constants and natural problem scaling.
Abstract (translated)
我们研究了在具有$m$个目标的光滑多目标优化中寻找$\varepsilon$-Pareto平稳点的oracle复杂度。衡量指标是Pareto平稳间隙$\mathcal{G}(x)$（即梯度最优凸组合的范数）。我们的贡献有四个方面： (i) 对于强凸的目标函数，任何span一阶方法（迭代值位于过去梯度张成的空间内）在进行了$T$次oracle调用后最多显示线性收敛速度$\exp(-\Theta(T/\sqrt{\kappa}))$，其中$\kappa$是条件数。这需要$\Theta(\sqrt{\kappa}\log(1/\varepsilon))$轮迭代，与经典的加速上限相匹配。 (ii) 对于凸问题和无记忆单步方法（固定标量化且预设步长），我们证明了在前$T$次迭代中最佳梯度范数的下界为$\Theta(1/T)$。 (iii) 虽然加速梯度下降超出了这个受限类别，但它是无记忆span方法，在固定的标量化上达到了同样的$\Theta(1/T)$上限。 (iv) 对于凸问题和一般span方法，如果采用自适应标量化，则在进行了$T$步之后，最终迭代的梯度范数具有下界$\Theta(1/T^2)$。这揭示了已知的上界与最坏情况保证之间的差距。 所有这些界限适用于目标不相同且非单点Pareto前沿的情况；速率表达到了通用常量和自然问题标度为止。
URL
https://arxiv.org/abs/2509.13550
