Complexity Bounds for Smooth Multiobjective Optimization
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910022675464192 |
|---|---|
| author | Sampaio, Phillipe R. |
| author_facet | Sampaio, Phillipe R. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_13550 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Complexity Bounds for Smooth Multiobjective Optimization Sampaio, Phillipe R. Optimization and Control Artificial Intelligence 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. |
| title | Complexity Bounds for Smooth Multiobjective Optimization |
| topic | Optimization and Control Artificial Intelligence |
| url | https://arxiv.org/abs/2509.13550 |