Complexity Bounds for Smooth Multiobjective Optimization

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.