- 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
-
The paper is clearly written and easy to follow. It addresses a relevant problem in stochastic multi-objective bilevel optimization.
-
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
-
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.
-
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
-
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?
-
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
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 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 . Specifically, the effective weights 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. .
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) | |
|---|---|---|---|---|---|
| 59.7360 | 61.1237 | 63.2122 | 70.3850 | 76.5198 | |
| 116.6318 | 113.9947 | 109.2589 | 104.5613 | 96.3509 |
| (9,1) | (7,3) | (5,5) | (3,7) | (1,9) | |
|---|---|---|---|---|---|
| 0.0944 | 0.1096 | 0.1102 | 0.1190 | 0.1226 | |
| 0.7955 | 0.6893 | 0.5328 | 0.4799 | 0.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.
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,12 and lg,12 in Eqs. (20)–(22) and (91)–(93) should be δf2 and δg2, 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 and δg2 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) 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.
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.
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.