A Fully First-Order Single-Loop Algorithm for Stochastic Multi-Objective Bilevel Optimization

We study stochastic multi-objective bilevel optimization, where each upper-level objective depends on the solution of an objective-specific lower-level problem. Existing methods either require computationally expensive Hessian information, rely on accurate inner-loop solutions, or lack rigorous non-asymptotic convergence guarantees. To this end, we propose FOSMO, a fully first-order single-loop algorithm for stochastic multi-objective bilevel optimization that avoids second-order computations, and establish a non-asymptotic convergence rate of $\tilde{\mathcal{O}}(T^{-2/5})$, yielding an $\tilde{\mathcal{O}}({ϵ}^{-5/2})$ oracle complexity for a fixed number of objectives. Furthermore, we adopt smooth Tchebycheff aggregation for preference-guided trade-offs among different objectives, enabling broader exploration of the Pareto front. Experiments on multi-task representation learning and hyperparameter optimization demonstrate the effectiveness of FOSMO.