acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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 , yielding an 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.

Primary area:
optimization
Keywords:
Bilevel Optimization, Multi-Objective, Pareto stationary

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_CGLuOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes a fully first-order, single-loop algorithm for stochastic multi-objective bilevel optimization, combining a penalty formulation, smooth Tchebycheff scalarization, and STORM estimators. It provides a convergence analysis and evaluates a non-variance-reduced variant on multi-task representation learning and hyperparameter optimization.

Critical strengths
  1. The paper is clearly written and easy to follow. It addresses a relevant problem in stochastic multi-objective bilevel optimization.

  2. The fully first-order, single-loop design is appealing, as it avoids Hessian-related computations and nested inner-loop optimization. This is particularly relevant in the multi-objective setting, where the computational burden grows with the number of objectives.

Critical weaknesses
  1. The theoretical guarantees need correction and clearer comparison with prior work. Lemma 7 replaces noise-variance constants with smoothness constants without justification under the stated assumptions, leaving a gap in the main convergence proof. The paper also lacks a systematic convergence-rate and oracle-complexity comparison under comparable assumptions and stationarity criteria, making the significance of the claimed rate unclear.

  2. The experiments do not evaluate the complete proposed algorithm or adequately substantiate its main claims. Section 5 explicitly states that both experiments omit variance reduction, whereas Algorithm 1 and its analysis rely on STORM estimators. The results therefore do not directly validate the analyzed method, including its computational cost. Per-iteration timing alone does not establish an advantage in total computation or runtime to reach comparable solution quality.

Questions for authors
  1. What new theoretical challenges arise from combining the first-order penalty method, smooth Tchebycheff scalarization, and STORM estimators? Which parts of the analysis address these challenges beyond existing results?

  2. What precisely does “preserving the user-specified preference” mean when the effective aggregation weights change dynamically? What theoretical guarantee or empirical evidence supports this claim?

3 comments

Q1. Notation Confusion between Noise-Variance and Smoothness Constants in Lemma 7

A1. We thank the reviewer for the careful review. We have carefully re-examined the proof of Lemma 7 and found that this is a notation error. Specifically, the coefficients lf,12l_{f,1}^2 and lg,12l_{g,1}^2 in Eqs. (20)–(22) and (91)–(93) should be δf2\delta_f^2 and δg2\delta_g^2, respectively. These bounds follow from the bounded stochastic gradient variance in Assumption 3, rather than the gradient smoothness constants.

Importantly, this correction does not change the convergence rate in Theorem 1. Since δf2\delta_f^2 and δg2\delta_g^2 remain finite under Assumption 3, the correction only changes the problem-dependent coefficients in the Lyapunov analysis. Specifically, the affected coupling terms can still be controlled by appropriately adjusting the Lyapunov weights and choosing sufficiently small step-size constants, without changing the prescribed step-size schedules or the asymptotic orders of the error terms. Consequently, the convergence rate O~(T−2/5)\widetilde{\mathcal O}(T^{-2/5}) remains unchanged. We sincerely thank the reviewer for pointing out this notation error. We will correct it and clarify the corresponding proof details in the revised manuscript.

Q2.Comparison with Prior Work

A2. We thank the reviewer for this valuable suggestion. The assumptions adopted in our analysis are standard in the bilevel optimization literature, including the strong convexity of the lower-level objective, smoothness conditions, and bounded stochastic gradient variance. The main contribution of our work is the development of a fully first-order, single-loop, and preference-guided algorithm for stochastic multi-objective bilevel optimization, together with a non-asymptotic convergence guarantee. In contrast, existing methods have certain limitations. Specifically, FORUM focuses on deterministic optimization and generally requires multiple inner-loop updates, while MORBiT relies on hypergradient estimation involving second-order derivative information. We will include a more systematic comparison with existing methods in the final version to better highlight the distinctions and contributions of our approach.

Q3 Why is variance reduction not used?

A3. Thank you for this question. We did not employ variance reduction in our experiments for two reasons: (1) Variance reduction provides only marginal performance improvements, possibly because convergence is also limited by approximation bias and inner-level optimization errors. (2) To ensure a fair comparison with the baselines, which do not employ variance reduction.

Q4 What new theoretical challenges arise, and how do we address them?

A4. It is a good question. The main challenges and our corresponding solutions are summarized as follows:

First, the penalized objective introduces approximation bias relative to the true upper-level objective. In Lemma 1, we exploit strong convexity and smoothness to establish O(1/λ)O(1/\lambda) bounds for both function-value and gradient approximation errors.

Second, the gradient of the penalized value function depends on two optimal solutions, which cannot be computed exactly in a single-loop framework. In Lemmas 8–9, we establish recursive tracking-error bounds using strong convexity and the Lipschitz continuity of the optimal solution mappings.

Third, smooth Tchebycheff scalarization involves nonlinear aggregation of stochastic function-value estimates. Even unbiased function-value estimates can lead to biased aggregation weights, making it difficult to control the resulting aggregation-direction error. In Lemma 2, we exploit the Lipschitz continuity of Softmax to decompose and bound this error in terms of penalty approximation, lower-level tracking, and stochastic estimation errors.

Fourth, STORM-based variance reduction requires controlling time-varying estimation targets and coupled estimation errors. In Lemmas 3–7, we establish recursive estimation-error bounds and develop a coupled Lyapunov analysis with coordinated parameter schedules to jointly control these interacting errors.

Q5 What precisely does “preserving the user-specified preference” mean when the effective aggregation weights change dynamically?

A5. Tnank you for this question. “Preserving the user-specified preference” means that the dynamically adjusted aggregation weights remain explicitly dependent on the user-specified preference vector ww. Specifically, the effective weights pi(x)wip_i(x)w_i are determined jointly by the user-specified preferences and the current objective values, ensuring that the aggregation direction remains guided by the prescribed preferences throughout optimization. Furthermore, Theorem 1 establishes convergence toward preference-guided Pareto stationarity, i.e. ∥∇Φ(xt)∥2=∥∑i=1mpi(xt)wi∇φi(xt)∥2\|\nabla\Phi(x_t)\|^2=\|\sum_{i=1}^{m}p_i(x_t)w_i\nabla\varphi_i(x_t)\|^2.

To further validate the effectiveness of preference-guided optimization, we conduct experiments on QM9 [1], a multi-task learning benchmark for molecular property prediction. Specifically, we consider two molecular property prediction objectives and evaluate our method under different user-specified preference vectors, using the mean absolute error (MAE) as the evaluation metric. The results are presented below:

(9,1)(7,3)(5,5)(3,7)(1,9)
ϵHOMO\epsilon_{\mathrm{HOMO}}59.736061.123763.212270.385076.5198
ϵLUMO\epsilon_{\mathrm{LUMO}}116.6318113.9947109.2589104.561396.3509
(9,1)(7,3)(5,5)(3,7)(1,9)
μ\mu0.09440.10960.11020.11900.1226
α\alpha0.79550.68930.53280.47990.4206

[1]: Ramakrishnan, R., Dral, P., Rupp, M. et al. Quantum chemistry structures and properties of 134 kilo molecules. Sci Data 1, 140022 (2014).

I appreciate the theoretical correction and clarifications. These responses address some of my concerns. I maintain my original rating.

Reviewer_yJrYOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes FOSMO, a fully first-order, single-loop algorithm for stochastic multi-objective bilevel optimization. It combines a penalty-based reformulation with variance reduction to avoid second-order computations and uses smooth Tchebycheff aggregation to incorporate user preferences. Under strongly convex lower-level objectives and standard assumptions, the authors establish non-asymptotic convergence guarantees. Experiments on multi-task representation learning and hyperparameter optimization demonstrate its empirical performance.

Critical strengths
  1. The proofs appear rigorous, and the notation is clearly explained.

  2. The paper is well organized and easy to follow.

  3. The penalty-based formulation enables fully first-order updates for multi-objective bilevel optimization, avoiding second-order computations.

Critical weaknesses
  1. The main technique combines a penalty-based method with variance reduction. What specific challenges arise in the multi-objective bilevel setting, and what new proof techniques are needed to address them?

  2. Penalty-based bilevel methods often use an inner loop to update zz, whereas the proposed algorithm performs only one update per iteration. Could the authors compare the convergence analyses of these two approaches? For simplicity, the authors can omit the variance reduction.

  3. I appreciate the theoretical contribution, but the experiments are relatively simple. Could the authors evaluate the method on larger multi-task benchmarks? Although these datasets are not originally designed for bilevel optimization, adapting them to the proposed formulation would help demonstrate its practical scalability and effectiveness.

I would like to raise my score if the questions are solved.

Questions for authors
  1. The main technique combines a penalty-based method with variance reduction. What specific challenges arise in the multi-objective bilevel setting, and what new proof techniques are needed to address them?

  2. Penalty-based bilevel methods often use an inner loop to update zz, whereas the proposed algorithm performs only one update per iteration. Could the authors compare the convergence analyses of these two approaches? For simplicity, the authors can omit the variance reduction.

  3. I appreciate the theoretical contribution, but the experiments are relatively simple. Could the authors evaluate the method on larger multi-task benchmarks? Although these datasets are not originally designed for bilevel optimization, adapting them to the proposed formulation would help demonstrate its practical scalability and effectiveness.

I would like to raise my score if the questions are solved.

2 comments

Q1. Theoretical Challenges and Techniques.

A1. It is a good question. The main challenges and our corresponding solutions are summarized as follows:

First, the penalized objective introduces approximation bias relative to the true upper-level objective. In Lemma 1, we exploit strong convexity and smoothness to establish O(1/λ)O(1/\lambda) bounds for both function-value and gradient approximation errors.

Second, the gradient of the penalized value function depends on two optimal solutions, which cannot be computed exactly in a single-loop framework. In Lemmas 8–9, we establish recursive tracking-error bounds using strong convexity and the Lipschitz continuity of the optimal solution mappings.

Third, smooth Tchebycheff scalarization involves nonlinear aggregation of stochastic function-value estimates. Even unbiased function-value estimates can lead to biased aggregation weights, making it difficult to control the resulting aggregation-direction error. In Lemma 2, we exploit the Lipschitz continuity of Softmax to decompose and bound this error in terms of penalty approximation, lower-level tracking, and stochastic estimation errors.

Fourth, STORM-based variance reduction requires controlling time-varying estimation targets and coupled estimation errors. In Lemmas 3–7, we establish recursive estimation-error bounds and develop a coupled Lyapunov analysis with coordinated parameter schedules to jointly control these interacting errors.

Q2. The compared to inner-loop method.

A2. Good question. The convergence analysis of methods employing inner-loop optimization is typically affected by inner-loop approximation errors. Consequently, their convergence rates often depend explicitly on the number of inner-loop iterations KK. In contrast, our method requires only a single lower-level update per iteration. Specifically, in Lemma 9, we establish a recursive tracking-error bound with the contraction factor of 1−μgβt/41-\mu_g\beta_t/4. By incorporating this bound into a coupled Lyapunov analysis, we control the tracking errors across iterations and establish convergence without requiring inner-loop updates.

Q3. Could the authors evaluate the method on larger multi-task benchmarks?

A3. We thank the reviewer for this constructive suggestion. To further evaluate our FOSMO on a larger-scale multi-task learning benchmark, we conduct additional experiments on QM9 [1], a molecular property prediction dataset containing approximately 130,000 molecules. Specifically, we consider 11 molecular property prediction tasks. All methods are trained for 150 epochs, and the mean absolute error (MAE) is reported as the evaluation metric. The results are presented in the table below.

Methodsμ\muα\alphaϵHOMO\epsilon_{\text{HOMO}}ϵLUMO\epsilon_{\text{LUMO}}⟨R2⟩\langle R^2 \rangleZPVEU0U_0UUHHGGcvc_v
MORBiT0.42270.6248180.1269122.104111.941427.8981208.6763209.5363209.8871205.57820.2403
FORUM0.24520.5075137.8073133.28695.096214.2585227.0374225.8053227.1837223.61300.1592
Ours0.09780.387059.819399.86754.064313.8837204.3559179.9532186.9472204.20360.1413

[1]: Ramakrishnan, R., Dral, P., Rupp, M. et al. Quantum chemistry structures and properties of 134 kilo molecules. Sci Data 1, 140022 (2014).

Thanks for the detailed response. For the 4 challenges, I think the first two are standard and solved in penalty-based method such as F2SA paper. The last two could relate to the MOBO problem. My other questions are mostly resolved. I would like to keep my score.

Reviewer_JhprOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes FOSMO, a single-loop first-order algorithm for stochastic multi-objective bilevel optimization. The authors use a penalty-based reformulation to avoid computing Hessians, while updating auxiliary variables to track the lower-level solutions. The method also uses STORM-based variance reduction and a smooth Tchebycheff scalarization to handle different preferences across objectives. Under strongly convex lower-level problems and standard smoothness assumptions, the authors establish a convergence rate toward Pareto stationarity. Experiments on multi-task representation learning and hyperparameter optimization compare the method against MORBiT and FORUM.

Critical strengths

The authors propose a novel single-loop algorithm for stochastic multi-objective bilevel optimization.

Critical weaknesses

No Pareto-front plots, complete objective vectors for the different preference settings, or multi-objective indicators (e.g. hypervolume) are reported. The experiments therefore demonstrate good task-specific classification accuracy under selected preference vectors, but do not establish the claimed advantage in Pareto-front exploration and accuracy.

1. Construction of the reference point is insufficiently specified. In Section 5 (p. 7, lines 355–359), the authors state that they obtain each reference value rir_i by setting wi=1w_i=1 and wj=0w_j=0 for j≠ij\neq i, and using the resulting objective value. This describes an approximate ideal point, not a known Pareto-optimal solution. However, the authors do not specify which optimization algorithm is used to obtain these reference values, with what initialization, number of iterations, or stopping criterion. Since these values enter the smooth Tchebycheff objective used by FOSMO, the procedure for obtaining them should be reproducible.

2. The preference vectors used for evaluation are arbitrarily selected. For the classification accuracy results in Tables 1 and 2, the authors explicitly set wi=0.82w_i=0.82 for the task being evaluated and wj=0.02w_j=0.02 for every other task (p. 8, lines 417–420; p. 9, lines 466–470). The paper provides no justification for choosing these particular values. It does not report experiments with other preference vectors or show how the resulting solutions change as the preference weights vary. Moreover, the description suggests that different preference vectors are used to obtain the accuracy reported for different tasks. If so, the reported average accuracy combines results from different optimization runs, rather than measuring the average accuracy of a single multi-task solution. The authors should clarify this protocol and explain how the FORUM and MORBiT results are obtained for comparison.

3. The experiments do not directly establish the claimed Pareto-front exploration capability. The authors explicitly present Tables 1 and 2 as evidence of FOSMO's ability to explore different trade-offs along the Pareto front (p. 8, lines 417–420; p. 9, lines 466–471). However, each table reports only the accuracy of task ii under a preference vector strongly favoring that same task. The authors do not report the performance on the other nine tasks under that preference vector.

4. Variance reduction mismatch. The experiments explicitly use a stochastic variant without variance reduction, but their main convergence theorem relies on STORM-based recursive variance reduction. The authors do not explain this discrepancy or compare the two variants.

5. Theory is highly constant-dependent. The theorem is not quantitatively predictive without its many constants. The constants depend on conditioning, regularity, stochastic noise, initialization etc. etc.. In particular, very small μg\mu_g can be costly. The theorem therefore gives little insight in what will the algorithm behave and which parameters are the most important to allocate the compute budget to.

6. The $m^6$ in Theorem 2 is probably very loose. There is no lower bound showing that the very large $m^6$ dependence in necessary, and a substantial part of the dependence comes from the normalization argument. It seems that m6m^6 is a losse upper bound and not a meaningful prediction of actual scalability.

Questions for authors

Are the solutions obtained using different preference vectors favor FOSMO? Do FOSMO solutions cover different regions of the Pareto front? Does FOSMO produce better trade-offs than FORUM or MORBiT when all tasks are taken into account? Why is STORM omitted from the experiments? Since recursive variance reduction is essential to the convergence analysis, how does the theoretically analyzed algorithm compare empirically with the version without variance reduction?

2 comments

Q1. Construction of Reference Points

A1. Thanks for the question. Since the reference points are not known, we obtain an empirical estimate for each objective by running FOSMO for 5000 iterations with the corresponding preference weight set to 1 and all others to 0. All methods use the same initialization: zero-initialized upper-level hyperparameters and randomly initialized lower-level classifiers for hyperparameter optimization, and randomly initialized upper- and lower-level networks for multi-task representation learning.

Q2. Preference Vector Selection and Baseline Implementations

A2. Thank you for your careful review. The baselines FORUM and MORBiT typically produce a single solution rather than explicitly constructing a set of Pareto-optimal solutions, whereas our FOSMO can obtain different trade-off solutions by adjusting the preference vector. Therefore, our evaluation aims to compare the best achievable performance on each individual objective across all methods. Specifically, we report the solutions obtained by FORUM and MORBiT, while for FOSMO, we set the evaluated objective's preference weight to 0.82 and all others to 0.02 to distinguish it from reference point estimation. The results show that the two baselines yield balanced solutions, whereas FOSMO can achieve superior performance on each individual objective by adjusting the preference vector.

Q3. Evaluation of Pareto-Front Exploration

A3. We thank the reviewer for this valuable comment. Our experiments evaluate the ability of our method to optimize individual objectives, which is closely related to the extreme regions of the Pareto front. To further investigate the preference-based exploration capability of FOSMO, we conduct additional experiments on QM9 [1], a benchmark dataset for multi-property molecular prediction. Specifically, we consider two distinct objectives and report how their performance varies under different preference vectors, using the mean absolute error (MAE) as the evaluation metric. The results are presented below:

(9,1)(7,3)(5,5)(3,7)(1,9)
ϵHOMO\epsilon_{\mathrm{HOMO}}59.736061.123763.212270.385076.5198
ϵLUMO\epsilon_{\mathrm{LUMO}}116.6318113.9947109.2589104.561396.3509
(9,1)(7,3)(5,5)(3,7)(1,9)
μ\mu0.09440.10960.11020.11900.1226
α\alpha0.79550.68930.53280.47990.4206

[1]: Ramakrishnan, R., Dral, P., Rupp, M. et al. Quantum chemistry structures and properties of 134 kilo molecules. Sci Data 1, 140022 (2014).

Q4.Why is Variance Reduction Omitted in the Experiments?

A4. Thank you for the reviewer's comment. We did not employ variance reduction in our experiments for two reasons: (1) Variance reduction provides only marginal performance improvements, possibly because convergence is also limited by approximation bias and inner-level optimization errors. (2) To ensure a fair comparison with the baselines, which do not employ variance reduction.

Q5. Constants in Theorem and Theoretical Guidance for Algorithm Design

A5. Thank you for this comment. It is inherent that problem conditioning, smoothness and stochastic noise affect the theoretical convergence analysis of optimization algorithms. In particular, a small μg\mu_g inherently increases optimization difficulty, rather than reflecting a limitation specific to our theoretical analysis. Our theorem provides two main theoretical insights

(1) Non-asymptotic convergence guarantee. We establish a non-asymptotic convergence rate for the proposed algorithm.

(2) Theoretical guidance on parameter scaling. We characterize the scaling orders of key algorithmic parameters, such as learning rates and penalty parameters, with respect to the iteration index tt, thereby providing guidance for parameter settings in practical implementations.

Q6. Clarification of the m6m^6 result.

A6. The m6m^6 result depends on the assumption that the preference vector remains in the simplex, i.e., w∈Δw \in \Delta. Corollary 2 improves the dependence on the number of objectives from m6m^6 to m7/2m^{7/2} by relaxing the simplex constraint, thereby providing a tighter bound under a more general setting.

Reviewer_JhprOpenReview ↗

Additional concerns raised by the response.

The rebuttal raises another concern. In Equation 12, the regularization term is ∥xρ∘Wy∥2\|x_\rho\circ W_y\|^2. Since in the reposnse you state that "all methods use the same initialization: zero-initialized upper-level hyperparameters", that implies that xρx_\rho is initialized to zero, then its gradient vanishes, preventing the regularization hyperparameter from changing during training? Or do you mean something else by "upper-level hyperparameters"? In that case please specify the exactquantities from your equations and corresponding precise notation.

The comparison in Tables 1 and 2 remains problematic. For FOSMO, you run the method separately for each task, giving that task a much higher weight wi=0.82w_i=0.82, and report its accuracy. For FORUM and MORBiT, you instead report the performance of a single solution across all tasks. This means that FOSMO's average accuracy combines results from 10 different solutions, while the baselines' averages come from just one solution. I don't think these numbers are directly comparable.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.