Complexity Bounds for Smooth Multiobjective Optimization

2025/09/16 by Phillipe R. Sampaio, Sampaio, Phillipe R.
Computer Science · Engineering · Mathematics · #Advanced Multi-Objective Optimization Algorithms #Advanced Optimization Algorithms Research #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Process Optimization and Integration

paper · pdf · doi:10.48550/arxiv.2509.13550

openalex publication_date 2025/09/16 · openalex created_date 2025/10/18 · openalex updated_date 2026/08/01

Abstract

We study the oracle complexity of finding ε-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(-Θ(T/√κ)) after T oracle calls, yielding Θ(√κlog(1/ε)) 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²) 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 Ω(√(L)/(T+1))-type lower bound on G (tight in order), implying Ω(1/ε²) iterations to reach G(x)≤ε up to natural scaling.

Citations

• Multi-objective Portfolio Optimization Via Gradient Descent
• Universal nonmonotone line search method for nonconvex multiobjective optimization problems with convex constraints
• Improved convergence rates for the multiobjective Frank-Wolfe method
• Adaptive generalized conditional gradient method for multiobjective optimization
• Optimal and parameter-free gradient minimization methods for convex and nonconvex optimization
• Globally convergent Newton-type methods for multiobjective optimization
• Monotonicity for Multiobjective Accelerated Proximal Gradient Methods
• Conditional gradient method for vector optimization
• Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Construction
• Multi-Task Learning as Multi-Objective Optimization
• Lower Bounds for Finding Stationary Points II: First-Order Methods
• Lower bounds for finding stationary points I
• Lower Bound for Randomized First Order Convex Optimization
• Dimension-Free Iteration Complexity of Finite Sum Optimization Problems
• On the Iteration Complexity of Oblivious First-Order Optimization Algorithms
• Performance of first-order methods for smooth convex minimization: a\n novel approach

Related

• Complexity of Highly Parallel Non-Smooth Convex Optimization
• Lower Bounds for Linear Minimization Oracle Methods Optimizing over Strongly Convex Sets
• The Complexity of Making the Gradient Small in Stochastic Convex\n Optimization
• On Lower Complexity Bounds for Large-Scale Smooth Convex Optimization
• Complexity iteration analysis for strongly convex multi-objective optimization using a Newton path-following procedure