{"ID":2870646,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.13550","arxiv_id":"2509.13550","title":"Complexity Bounds for Smooth Multiobjective Optimization","abstract":"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 $\\mathcal{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 $\\mathcal{G}$. We establish: (i) in the $μ$-strongly convex case, any span first-order method has worst-case linear convergence no faster than $\\exp(-Θ(T/\\sqrtκ))$ after $T$ oracle calls, yielding $Θ(\\sqrtκ\\log(1/\\varepsilon))$ iterations and matching accelerated upper bounds; (ii) in the convex case, an $Ω(1/T)$ min-iterate lower bound for oblivious one-step methods and a universal last-iterate lower bound $Ω(1/T^2)$ 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 $Ω(1/T)$ min-iterate lower bound for general adaptive first-order methods; (iii) in the nonconvex case with $L$-Lipschitz gradients, an $Ω(\\sqrt{L}/(T+1))$-type lower bound on $\\mathcal{G}$ (tight in order), implying $Ω(1/\\varepsilon^2)$ iterations to reach $\\mathcal{G}(x)\\le\\varepsilon$ up to natural scaling.","short_abstract":"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 $\\mathcal{G}(x)$, the norm of the best convex combination of objective gradients. Our analysis relies on a non-degenerate liftin...","url_abs":"https://arxiv.org/abs/2509.13550","url_pdf":"https://arxiv.org/pdf/2509.13550v2","authors":"[\"Phillipe R. Sampaio\"]","published":"2025-09-16T21:33:11Z","proceeding":"math.OC","tasks":"[\"math.OC\",\"cs.AI\"]","methods":"[]","has_code":false}