acceptodds
Under review as a conference paper at ICLR 2027

Stochastic Aligned Multi-Objective Optimization

Abstract

Aligned Multi-Objective Optimization (AMOO) studies how to minimize multiple objectives that share a common optimum. Existing deterministic guarantees do not directly cover noisy minibatch updates. Unrestricted weight scaling can amplify noise, while choosing weights from the update batch can bias the combined gradient. We propose delayed update normalized AMOO (DunAMOO), which selects nonnegative weights that sum to one and applies them one iteration later. This controls weight scaling and separates the applied weights from fresh gradient noise, using one minibatch per iteration. We provide, to our knowledge, the first convergence analysis of stochastic AMOO that handles noisy Polyak weight selection and delayed updates. Under the stated curvature and noise conditions, we prove finite expected entry into a near region. After entry, the expected squared error contributed by paths with no earlier exit has a geometrically decaying bound down to a noise-dependent level. Experiments on tasks with loss-scale imbalance show favorable convergence trends for DunAMOO.

Primary area:
optimization
Keywords:
Multi objective optimization, Optimization, Multi-task Learning

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_vEfKOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies stochastic aligned multi-objective optimization, where several objectives share a common optimum. The authors propose DUNAMOO, which constrains objective weights to the probability simplex and applies the weights one iteration after selection to avoid same-batch gradient bias. They derive a two-phase stochastic convergence guarantee and a global convex maximum-gap bound. Experiments on loss-imbalanced Multi-MNIST and analytical examples illustrate the proposed approach. However, the assumptions of this paper are restrictive and the experiments are insufficient.

Critical strengths
  1. The paper addresses a meaningful theoretical problem: extending aligned multi-objective optimization to noisy minibatch feedback. The delayed-weight formulation is simple and clearly motivated.
  2. The convergence analysis is detailed, including a noisy weight-selection bound, a one-step delay argument, and explicit limits on the resulting guarantees. The analytical experiments offer some useful verification.
Critical weaknesses

1. Limited algorithmic novelty and restrictive theoretical guarantees. The proposed algorithm mainly combines simplex normalization and delayed updates with the existing PAMOO framework. Since these techniques are already well established, the algorithmic novelty should be better justified. Moreover, the convergence analysis relies on restrictive assumptions, including a common optimum, aligned, convex, smooth, and self-concordant objectives, as well as known optimal objective values. These conditions are difficult to satisfy in practical deep learning applications and are not verified in the Multi-MNIST experiments. Furthermore, Theorem 1 only establishes finite expected entry into a neighborhood of the optimum, while its subsequent geometric bound excludes trajectories that have already exited this region. Therefore, the theoretical results do not establish global mean-square convergence in the general nonlinear setting. The authors should further clarify the theoretical advances over existing methods, relax the assumptions where possible, and strengthen the connection between theory and practice.

2. Insufficient experimental validation and unconvincing performance advantages. The experimental evaluation is relatively limited and does not adequately demonstrate the effectiveness and generality of the proposed method. The experiments mainly focus on a constructed Multi-MNIST benchmark with a small number of objectives, and the reported results primarily concern training losses rather than test accuracy or generalization performance. More importantly, the proposed delayed-update method does not consistently outperform the same-batch method, particularly in the two- and four-objective settings. In addition, the PAMOO-SGD baseline differs from its original implementation, and comparisons with other competitive stochastic multi-objective optimization methods are insufficient. The algorithm also assumes known optimal objective values, which are simply set to zero in the experiments without verifying their accuracy. More comprehensive experiments, stronger baselines, and additional ablation studies are needed to substantiate the claimed advantages.

Questions for authors
  1. How can the required optimal objective values be obtained or estimated in practical applications? How sensitive is the proposed algorithm to estimation errors in these values?

  2. Can the authors relax the restrictive theoretical assumptions, such as a common optimum, self-concordance and positive mixture curvature, while retaining meaningful convergence guarantees? Alternatively, can the authors better justify the necessity of these assumptions and discuss the applicability of the theoretical results to more general optimization problems?

  3. Can the authors provide a more challenging stochastic benchmark that satisfies the theoretical assumptions and compare the predicted convergence behavior, including the noise floor and expected entry time, with empirical results?

5 comments
AuthorsOpenReview ↗

Official Comment by Authors [1/3]

Thank you for your careful review and thoughtful questions about our contribution, assumptions, and experiments. We address each of your points in turn below. We are grateful to have the opportunity to clarify the paper’s contributions and explain their significance in greater detail. We address our contributions (W1, Q2) in Comment 1, the empirical comparisons (W2) in Comment 2, and reference sensitivity (Q1) and stochastic validation (Q3) in Comment 3.

Technical contribution and weaker assumptions

W1. Contribution beyond simplex normalization and delay.

Our contribution is the stochastic analysis of Polyak weighting selected from jointly noisy losses and gradients. The QP optimality condition gives a population-gap retention bound despite this dependence. We then transfer the bound across the intervening update, which shares the selection batch, without assuming continuity of the QP optimizer. An adapted conditional energy gives finite expected entry and localized geometric second-moment control. These steps address the dependence introduced by noisy selection and delayed application. Delay fixes the applied weights before fresh gradients are drawn, while the analysis still accounts for loss-selection error.

The distance theorem allows singular individual Hessians. Its curvature condition concerns a normalized mixture at the shared minimizer: μL=max⁡w∈Δmλmin⁡(∑iwi∇2fi(x⋆))>0.\mu_L=\max_{w\in\Delta_m}\lambda_{\min}\left(\sum_iw_i\nabla^2f_i(x^\star)\right)>0. It does not require global strong convexity. This curvature condition originates in deterministic AMOO. Our advance is the stochastic analysis under the stated geometric and oracle assumptions.

W1. Why the nonlinear distance guarantee is localized?

Proposition A.3 shows that a global MSE guarantee for the default fixed-step, fixed-batch algorithm would be false over the stated class: an admissible nonlinear instance has divergent ordinary MSE even with arbitrarily small noise variance. Theorem 1 instead gives almost-sure entry with finite expected time when E∞<R2E_\infty<R^2, followed by a localized geometric second-moment estimate. That estimate includes the first-exit iterate and excludes paths that exited earlier. Corollary A.3 provides finite-horizon exit control. These statements identify the attainable guarantee for this algorithm and class.

Q2. Which assumptions can be relaxed?

Corollary 1 removes self-concordance and positive mixture curvature. Under smooth convex alignment and its stated oracle, reference, and stepsize conditions, EM(xˉK)=O(βV0K+σgV0NK+νΔN),\mathbb E M(\bar x_K)=O\left(\frac{\beta V_0}{K}+\sigma_g\sqrt{\frac{V_0}{NK}}+\frac{\nu_\Delta}{\sqrt N}\right), where M(x)=max⁡i[fi(x)−fi⋆]M(x)=\max_i[f_i(x)-f_i^\star] and V0=∣x0−x⋆∣2V_0=\\|x_0-x^\star\\|^2. This is a global averaged-gap guarantee with an explicit finite-batch residual. The stronger geometric assumptions support the distance conclusion of Theorem 1.

The shared-minimizer assumption defines the AMOO target. Removing it would require a different optimization target. We have not verified exact population alignment or the geometric assumptions for the CNN. Its experiments evaluate optimization behavior beyond verified theoretical assumptions. Comment 3 provides an admissible nonlinear stochastic construction with known constants.

AuthorsOpenReview ↗

Official Comment by Authors [2/3]

Benchmarks, delay, and baseline comparisons

W2. Limited experiments on Multi-MNIST benchmark.

We also evaluate DunAMOO on the SARCOS inverse-dynamics dataset, a seven-objective regression task using real robot data. The dataset has 21 inputs (joint positions, velocities, and accelerations) and seven outputs corresponding to joint torques. The data contains 35,551 training, 4,484 validation, and 4,449 test samples. Each joint is one objective, measured by NRMSE (normalized root MSE). All methods use the same 21–128–128–128–7 ReLU MLP and plain SGD with batch size 32 for 10,000 updates (approximately 9 epoch-equivalents); the learning rate is halved at updates 4,000 and 8,000. We select each method’s learning rate using 2 development seeds and worst-joint validation NRMSE, then evaluate over 30 paired confirmation seeds using the same initialization and minibatch sequence for each seed.

MethodWorst-joint NRMSE
EW-SGD0.1601
PAMOO-SGD0.1587
Simplex (same batch)0.1610
DunAMOO (ours)0.1581

DunAMOO achieves the lowest worst-joint error among the evaluated methods. In this experiment, it assigns larger weights to objectives with higher losses, while the losses of the other objectives also decrease. This balanced progress appears to help reduce the worst-joint error without sacrificing performance on the other joints. We add these results in the revised paper (Appendix D.4.1).

W2. Additional Measurement for Multi-MNIST experiment.

We agree that the current paper reports only cross-entropy loss on the Multi-MNIST dataset. Since this is a classification task, we will add accuracy results, including the worst-objective accuracy (the minimum accuracy across objectives). At the end of training, DunAMOO and EW reach at least 99.4% worst-objective accuracy, while PAMOO reaches only 40~91%. However, DunAMOO reaches 99% worst-objective accuracy faster than the EW. This faster convergence appears to be associated with DunAMOO assigning larger weights to objectives with lower accuracy, prioritizing the underperforming objectives. We include these results in the revised paper (Appendix D.3.3).

W2. Delay and same-batch performance In our experiments, we agree that the same-batch method achieves lower final losses in some Multi-MNIST settings, particularly with (m=2) and (m=4). However, these empirical results do not theoretically establish that same-batch updates are uniformly better than delayed updates. Below is the toy experiment that delayed-update achieves faster convergence than same-batch. We add this additional toy example in our paper (Appendix D.4.2).

MethodWorst-objective MSE
Simplex (same batch)0.500
DunAMOO (ours)0.014

Other than the experimental results, we use a one-step delay for a theoretical analysis: it makes the weight applied to the current gradient independent of the current minibatch, allowing us to analyze noisy weight selection and its interaction with the update. Thus, the delay is not intended to guarantee lower empirical loss in every setting. Rather, it enables the convergence analysis that is a central contribution of our work. The one-step delay itself is not a contribution of our work.

W2. PAMOO-SGD baseline differs from its original implementation. The previous experimental implementation of PAMOO differs from its theoretical formulation[1]. We revised the code to better align with the theoretical PAMOO update and ran the experiments under our Multi-MNIST setup.

W2. Comparisons with other competitive stochastic multi-objective optimization. We did not include methods developed for general stochastic multi-objective optimization because they typically target Pareto-stationary solutions for potentially conflicting objectives, whereas our setting assumes a shared minimizer and studies convergence toward that common optimum. Their objectives and theoretical guarantees therefore differ from those of AMOO, making a direct comparison under our convergence criterion potentially misleading. We will clarify this distinction and the resulting scope of our baseline selection.

References

[1] Efroni et al. Aligned Multi Objective Optimization. ICML 2025

AuthorsOpenReview ↗

Official Comment by Authors [3/3]

Reference sensitivity and stochastic validation

Q1. Experimental assumptions and practical relevance.

We use zero as an idealized lower-bound reference for Multi-MNIST cross-entropy: zero loss would imply 100% accuracy, but we have not established that the model can attain it. Prior work also uses zero or a known lower bound as a Polyak reference [1,2].

AMOO addresses objectives that share a minimizer, a specific regime rather than general MOO. Multi-reward applications in image generation, tool use, and reinforcement learning illustrate its practical relevance [3–6]; some explicitly study rewards sharing an optimal policy [6].

For our Multi-MNIST experiments, zero is a lower-bound reference. We have not verified zero population cross-entropy or a shared population minimizer. Perfect classification alone does not establish either claim. Prior stochastic Polyak results do not certify these task-level population references.

Q1. Effect of inaccurate relative references.

Appendix A.5.2 quantifies the effect directly. If ϵval\epsilon_{\rm val} bounds the range of differential reference errors, the certified residual becomes E′=E+32ϵval3μL.E'=E+\frac{32\epsilon_{\rm val}}{3\mu_L}. Increasing batch size does not remove this fixed differential error. To test reference sensitivity, we use the known-optimum nonlinear family specified under Q3 below and vary the supplied references with paired stochastic paths. Each condition uses 512 paths and 2,048 updates, batch size N=256N=256, s=u=0.001s=u=0.001, η=0.5\eta=0.5, solver residual budget 10−910^{-9}, and initial maximum true gap 1:

ReferenceFinal mean MSEMonte Carlo SE
Exact2.50×10−92.50\times10^{-9}9.13×10−119.13\times10^{-11}
Error range 0.0010.0010.00140.00144.20×10−64.20\times10^{-6}
Error range 0.010.010.01570.01574.62×10−64.62\times10^{-6}
Error range 0.050.050.08380.08386.58×10−66.58\times10^{-6}
Error range 0.10.10.18020.18025.22×10−65.22\times10^{-6}
Zero, unequal true minima0.87500.87503.85×10−63.85\times10^{-6}

A common +0.1+0.1 shift barely changed mean final MSE, but 1/512 paths exceeded the declared 10−610^{-6} coordinate tolerance, with maximum difference 4.79×10−64.79\times10^{-6}. This numerical discrepancy remains unresolved. Exact common-offset cancellation is an algebraic property, and we do not claim that the pathwise numerical check passed.

Q3. An admissible stochastic benchmark: entry time and finite-run error

The alignment setting is difficult to verify in real-data problems. We use a synthetic benchmark with known optima to test the theory under its assumptions. The benchmark has 8 objectives in 32 rotated coordinates, y=Qxy=Qx, with

\phi(t)=t\arctan t-\tfrac12\log(1+t^2).$$ Here $c_i=i/8$, and $A_{ij}=1$ iff $((j\bmod 8)-i)\bmod 8<4$, using zero-based indices. Each objective activates half the coordinates; component Hessians have rank 16, while a normalized mixture has curvature $\mu_L=0.5$. The shared minimizer is $x^\star=0$, with known minima $f_i^\star=c_i$. Independent Rademacher perturbations $sZ_i\sin y_i+uV_i$ provide known noise constants. With $s=u=0.001$, $\eta=0.5$, batch size $N=16$, and 512 paths of 2,048 updates, every path entered the outer region without censoring: | Initial distance | Bound on $\mathbb E T$ | Observed mean $T$ | |---:|---:|---:| | 2 | 82.17 | **2** | | 8 | 345.58 | **8** | | 32 | 1488.36 | **22** | Here $T=\inf\\{k:L_k\le R^2\\}$. For initial distance 8, the observed second-half mean MSE decreased with batch size: | Batch $N$ | Residual $E_\infty$ | Mean MSE | Monte Carlo SE | |---:|---:|---:|---:| | 1 | $0.0799$ | **$2.33\times10^{-7}$** | $3.18\times10^{-10}$ | | 16 | $0.0200$ | **$3.64\times10^{-8}$** | $8.82\times10^{-11}$ | | 256 | $0.0050$ | **$2.54\times10^{-9}$** | $6.17\times10^{-12}$ | The observed entry times are below the theoretical bounds, and the finite-run MSE decreases as the batch grows. These results illustrate the theory in an admissible aligned setting. The conservative residual bounds and finite-run averages do not establish a stationary noise floor or global ordinary-MSE convergence. **References** [1] Loizou et al. Stochastic Polyak Step-size for SGD. AISTATS 2021. [2] Orvieto et al. Dynamics of SGD with Stochastic Polyak Stepsizes. NeurIPS 2022. [3] Lee et al. Parrot: Pareto-optimal Multi-Reward Reinforcement Learning Framework for Text-to-Image Generation. ECCV 2024. [4] Li et al. Towards Pareto-Optimal Tool-Integrated Agents with Pareto Ranking Policy Optimization. ICML 2026. [5] Liu et al. GDPO: Group reward-Decoupled Normalization Policy Optimization for Multi-reward RL Optimization. ICML 2026. [6] Dann et al. Reinforcement Learning Can Be More Efficient with Multiple Rewards. ICML 2023.
Reviewer_GKy3OpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

This paper addresses the problem of noisy minibatch updates in the stochastic AMOO setting. Specifically, stochasticity induces biases in gradients and function values, which prevent the conventional AMOO algorithm from converging. The proposed method weights per-iteration gradients using asynchronous weights to remove synchronous coupling, thereby intuitively resolving the associated convergence issues.

Critical strengths
  1. The paper is well written, and the target problem can be understood readily.
  2. The stochastic AMOO problem studied in this work is indeed formulated for the first time in this paper.
Critical weaknesses
  1. The paper claims to present the first convergence analysis for stochastic AMOO. While this may be novel within the AMOO setting, substantial related work already exists for general MOO. After comparing the two settings, I do not find the convergence analysis for AMOO to be substantially more involved than that for MOO, which limits the significance of this work.
  2. The paper compares against CAMOO and PAMOO. Even though these baselines are developed for deterministic gradients, the authors cannot claim that they fail to converge in theory without providing counterexamples demonstrating their non-convergence.
  3. Regarding the motivation: prior MOO literature has already identified that stochastic convergence suffers from coupling between weights and gradient noise. Therefore, the idea of decoupling them via delayed/asynchronous weights appears somewhat straightforward, which further diminishes the novelty of this submission.
  4. Experiments are only reported on Multi-MNIST, and the empirical evaluation is insufficient.
Questions for authors

Is the AMOO setting rarely encountered in practice? Is this direction of interest to industry practitioners?

4 comments
AuthorsOpenReview ↗

Official Comment by Authors [1/2]

Thank you for the careful review and thoughtful questions about significance and stochastic convergence. We address the reviewer’s concerns one by one, providing detailed responses to the novelty (W1) and theoretical concerns (W2, W3) here and to the benchmark and practical-relevance questions (W4, Q1) in our second comment.

Theoretical contribution and explicit counterexamples

W1: Novelty over general MOO.

We are more than happy to explain the novelty of AMOO setting. AMOO studies problems with aligned objectives, a structure that general MOO does not study. This structure allows algorithms to exploit curvature across objectives, yielding faster convergence guarantees than general MOO. Many convergence analyses for MOO impose assumptions on each component objective: convex analyses typically assume that every objective is convex, while strongly convex analyses often require every objective to be strongly convex. In contrast, our analysis does not require each objective to be strongly convex; it requires only that a normalized weighted combination have positive curvature at the shared minimizer. This mixture-curvature condition yields a geometric convergence bound. To the best of our knowledge, existing general MOO analyses do not establish this type of guarantee for stochastic AMOO setting.

W2. Explicit counterexamples for direct stochastic plug-ins.

The direct stochastic plug-ins need not converge to the common minimizer. Consider two identical tasks with ℓi(x,Z)=12x2+Zx+12Z+1,\ell_i(x,Z)=\tfrac12x^2+Zx+\tfrac12Z+1, where fresh i.i.d. Z=±1Z=\pm1, equally likely, is shared across tasks. Then fi(x)=x2/2+1f_i(x)=x^2/2+1, x⋆=0x^\star=0, fi⋆=1f_i^\star=1, and x+Zx+Z is an unbiased gradient with variance one.

For CAMOO, identical Hessians make every normalized mixture equivalent. With constant 0<η<20<\eta<2,

\lim_k\mathbb E[x_k^2]=\frac{\eta}{2-\eta}>0.$$ For raw same-minibatch PAMOO with one sample, no ridge, and no external damping, set $\widehat\Delta=\ell_i-f_i^\star$, $\widehat g=x+Z$, and $s=u_1+u_2$. Its QP and update are $$\max_{s\ge0}\\{2\widehat\Delta s-\widehat g^2s^2\\},\qquad x^+=x-\widehat g s.$$ When $Z=+1$, $\widehat\Delta=(x+1)^2/2$, so near zero $s=1/2$ and $x^+=x/2-1/2$. If $x_k\to0$, infinitely many $Z_k=+1$ updates force a subsequence $x_{k+1}\to-1/2$, a contradiction. Thus $\Pr(x_k\to0)=0$. **W3. Technical contribution beyond delaying weights.** Our technical contribution is the analysis of noisy Polyak selection and its interaction with delayed application. - **Noisy selection.** The QP first-order condition gives a population-gap retention bound even though the losses and gradients used to select weights share a minibatch. - **One-step transfer.** Newly selected weights also share that minibatch with the intervening parameter update. We transfer the retention bound across this update without assuming continuity of the QP optimizer. - **Localized convergence.** Local mixture curvature produces a nonlinear drift for which Jensen's inequality alone does not close an ordinary-MSE recursion. An adapted conditional energy yields finite expected entry under the stated noise condition and localized geometric second-moment control. The analysis retains loss-selection error explicitly. Delay separates the applied weights from fresh gradient noise, while the remaining selection dependence is handled by the proof. **Clarification. Unbiased estimates and delayed weights.** The minibatch estimators of each objective and its gradient are unbiased. Using weights with the same minibatch from which they were selected can bias the weighted gradient. Our method delays only the weights and applies them to fresh minibatch gradients. **Execution is synchronous.**
AuthorsOpenReview ↗

Official Comment by Authors [2/2]

Additional benchmarks and practical relevance

W4. Real-data evaluation beyond Multi-MNIST.

We also evaluate DunAMOO on the SARCOS inverse-dynamics dataset, a seven-objective regression task using real robot data. The dataset has 21 inputs (joint positions, velocities, and accelerations) and seven outputs corresponding to joint torques. The data contains 35,551 training, 4,484 validation, and 4,449 test samples. Each joint is one objective, measured by NRMSE (normalized root MSE). All methods use the same 21–128–128–128–7 ReLU MLP and plain SGD with batch size 32 for 10,000 updates. The learning rate is halved at updates 4,000 and 8,000. We select each method’s learning rate using 2 development seeds and worst-joint validation NRMSE, then evaluate over 30 paired confirmation seeds using the same initialization and minibatch sequence for each seed.

MethodWorst-joint NRMSE
EW-SGD0.1601
PAMOO-SGD0.1587
Simplex (same batch)0.1610
DunAMOO (ours)0.1581

DunAMOO achieves the lowest worst-joint error among the evaluated methods. In this experiment, it assigns larger weights to objectives with higher losses, while the losses of the other objectives also decrease. This balanced progress appears to help reduce the worst-joint error without sacrificing performance on the other joints. We add these results in the revised paper (Appendix D.4.1).

Q. Why is the AMOO setting important to study?

Aligned Multi-objective and multi-reward optimization is relevant to current machine-learning applications. For example, Parrot jointly optimizes four image-quality rewards, including aesthetics, human preference, text-image alignment, and image sentiment, and reports improvements across all four metrics [1]. ParetoPO considers answer accuracy and tool-use efficiency on mathematical reasoning and multi-hop QA tasks, and reports better accuracy-efficiency trade-offs [2]. GDPO reports that jointly optimizing multiple rewards improves performance over GRPO across multiple tasks [3]. Dann et al. analyze multiple reward formulations that share an optimal policy and show that using them can improve sample efficiency [4].

Many applied studies optimize multiple rewards that capture complementary aspects of a shared goal. Although some criteria may conflict, this is not always the case. Multiple objectives can be compatible and improve together. Alignment setting is a meaningful practical regime, but not studied much yet. We will clarify that AMOO setting does not apply to general MOO without the shared-optimum assumption.

References

[1] Lee et al. Parrot: Pareto-optimal Multi-Reward Reinforcement Learning Framework for Text-to-Image Generation. ECCV 2024.

[2] Li et al. Towards Pareto-Optimal Tool-Integrated Agents with Pareto Ranking Policy Optimization. ICML 2026.

[3] Liu et al. GDPO: Group reward-Decoupled Normalization Policy Optimization for Multi-reward RL Optimization. ICML 2026.

[4] Dann et al. Reinforcement Learning Can Be More Efficient with Multiple Rewards. ICML 2023.

Thanks for the rebuttal. Most of my concerns have been addressed. I maintain my score. It would be better if the authors could discuss in more detail how the theory connects with practical use.

Dear Reviewer GKy3,

The rebuttal period is about to close. We would be grateful if you could review our response and share any further comments. To summary our replies, our main clarifications are:

  1. AMOO as a distinct setting. AMOO has a shared-minimizer structure that raises questions distinct from those in general MOO and merits dedicated theoretical study.
  2. Theoretical contribution. To our knowledge, this is the first convergence analysis of stochastic AMOO that addresses both noisy Polyak weight selection and delayed updates. Normalized weights control their scale, while delayed application avoids the bias caused by selecting and applying weights using the same minibatch.
  3. Practical motivation. AMOO arises in empirical studies, motivating an theoretical analysis of how adaptive weighting behaves with noisy minibatch feedback.

In light of these clarifications, we respectfully ask you to consider whether our contributions merit reconsideration of your rating. Thank you for your time and consideration.

Sincerely,

The authors

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

The paper studies stochastic aligned multi-objective optimization for objectives sharing a common minimizer. It proposes DUNAMOO, which selects normalized Polyak weights from one minibatch and applies them to the next. The paper provides theoretical analysis of noisy weight selection and delayed updates, establishing finite expected entry into a neighborhood and localized error decay to a noise-dependent level under stated assumptions. A separate result bounds the global averaged objective gap under smooth convexity. It conducts synthetic and Multi-MNIST experiments to evaluate convergence under loss-scale imbalance.

Critical strengths
  • Writing: Clearly states the scope of the guarantees and illustrates their limits with counterexamples.
  • Novelty: Develops a stochastic AMOO analysis that handles noisy weight selection and delayed updates.
  • Significance: Clarifies the convergence behavior and limitations of adaptive weighting under minibatch noise.
Critical weaknesses
  1. The nonquadratic distance guarantee is localized. Theorem 1 controls error only through the first exit, with useful survival horizons depending on noise. The separate global objective-gap result does not provide global mean-square control. (pp. 5-7, 21-22)

  2. Dependence on optimal-value references limits applicability. The basic guarantee requires minima up to a common offset; differential errors may leave a residual allowance despite larger batches. The experiments' zero references are unverified. (pp. 24-25, 41)

  3. The QP's added cost lacks a general justification. The generic selection certificate gives no advantage over delayed maximum-gap selection; demonstrated benefits are limited to particular examples and benchmarks. (pp. 7-8, 27-28)

Questions for authors
  1. What accuracy, confidence, and positive integer horizon does the inner-entry corollary yield for a representative admissible noise level?

  2. Which intended applications provide relative optimal objective values, and how large can their estimation errors be before the guarantee becomes uninformative?

  3. Beyond the supplied examples, what problem characteristics predict a benefit from the QP over delayed maximum-gap selection?

3 comments
AuthorsOpenReview ↗

Official Comment by Authors [1/2]

Thank you for carefully reviewing our paper and for the thoughtful questions. We appreciate your recognition of our contributions, especially our analysis of stochastic AMOO, and discussion of adaptive weighting under minibatch noise. We address W1/Q1 and W2/Q2 here, and W3/Q3 in the next comment.

Guarantees and optimal-value references

W1/Q1. General accuracy, confidence and horizon guarantees.

The probability guarantee applies across the admissible class. We are happy to show that our result guarantees almost-surely enter into the inner region in finite expected time and high-probability progress over a finite horizon after entry. Write EE for the certified residual and LkL_k for the analysis energy. For 0<r<R0<r<R with 2r2>E(1+r/R)2r^2>E(1+r/R), define Sr=inf⁡k≥0:Lk≤r2S_r=\inf \\{k\ge0:L_k\le r^2\\} and τr=inf⁡j≥Sr:Lj>R2\tau_r=\inf\\{j\ge S_r:L_j>R^2\\}. Corollary A.3 gives almost-sure entry with finite expected time. Conditional Markov's inequality gives, for accuracy a>0a>0 and integer horizon h≥1h\ge1, Pr⁡(τr>Sr+h, ∣xSr+h−x⋆∣≤a∣FSr)≥1−dh(a),\Pr(\tau_r>S_r+h,\ \\|x_{S_r+h}-x^\star\\|\le a\mid\mathcal F_{S_r})\ge1-d_h(a), dh(a)=r2+qEhR2+(1−q)hr2+E[1−(1−q)h]a2.d_h(a)=\frac{r^2+qEh}{R^2}+\frac{(1-q)^hr^2+E[1-(1-q)^h]}{a^2}. Thus, confidence 1−δ1-\delta is certified whenever dh(a)≤δ<1d_h(a)\le\delta<1, almost surely over entry histories. Choosing r2=Er^2=E for 0<E<R20<E<R^2 gives dh(a)=E[(1+qh)/R2+1/a2]d_h(a)=E[(1+qh)/R^2+1/a^2]. For fixed geometry, accuracy and horizon, this post-entry failure bound vanishes with EE. It controls survival throughout the window and distance at the endpoint.

For a concrete Q1 calculation, consider a synthetic nonlinear problem with 8 objectives in 32 coordinates and known shared minimizer x⋆=0x^\star=0. It has β=Mf=1\beta=M_f=1, μL=0.5\mu_L=0.5, σg=0.001\sigma_g=0.001, νΔ=14×0.001\nu_\Delta=\sqrt{14}\times0.001, N=256N=256, η=0.5\eta=0.5 and solver residual budget 10−910^{-9}. These give q=1/24q=1/24, R2=2R^2=2 and E≃0.0050E\simeq0.0050. The inner-entry condition holds at r2=0.005r^2=0.005.

Horizon after inner entryEndpoint distanceJoint probability lower bound
60 updates≤0.4\le0.4about 96.01%

Proposition A.3 shows why the finite-horizon scope is necessary: the default fixed-step, fixed-batch algorithm can have divergent global MSE on an admissible nonlinear instance despite arbitrarily small noise variance. The global averaged-gap result controls a different error criterion.

W2/Q2. Certifiable references and an explicit error allowance.

Only relative optimal values are required. In single-objective settings, many Polyak-type algorithms use zero as the reference loss; [1,2] are examples. We set the reference value to zero for each Multi-MNIST objective. This was a practical choice based on our expectation that the shared model could predict all digits simultaneously. The cited methods motivate our choice but do not establish that zero is the population optimum for Multi-MNIST.

A common reference offset cancels on the simplex. A certifiable application is consistent block least squares fi(x)=∣Aix−bi∣2/2+cif_i(x)=\\|A_ix-b_i\\|^2/2+c_i. Joint consistency gives known minima cic_i, and a full-rank stacked operator gives positive mixture curvature. A shared centered finite-variance perturbation ⟨ζ,x⟩\langle\zeta,x\rangle gives bounded gradient-noise variance and zero loss-contrast noise. Let E′=E+32ϵval3μL.E'=E+\frac{32\epsilon_{\rm val}}{3\mu_L}. For Q1's setting, if ϵval\epsilon_{\rm val} bounds the range of differential reference errors, then ϵval<0.0935\epsilon_{\rm val}<0.0935 suffices for outer entry. For its 95% joint target at h=60,a=0.4,r2=0.005h=60,a=0.4,r^2=0.005, ϵval≤6.73×10−5\epsilon_{\rm val}\le6.73\times10^{-5} suffices. These are sufficient budgets, not maximum tolerances. Larger batches do not remove fixed differential error.

To test sensitivity to inaccurate optimal-value references, we used the same known-optimum problem and varied the supplied task references. We paired the stochastic paths across reference choices. Each condition used 512 paths and 2,048 updates, with batch size N=256N=256 and initial maximum true gap 1.

ReferenceFinal mean MSEMonte Carlo SE
Exact2.50×10−92.50\times10^{-9}9.13×10−119.13\times10^{-11}
Error range 0.0010.0010.00140.00144.20×10−64.20\times10^{-6}
Error range 0.010.010.01570.01574.62×10−64.62\times10^{-6}
Error range 0.050.050.08380.08386.58×10−66.58\times10^{-6}
Error range 0.10.10.18020.18025.22×10−65.22\times10^{-6}
Zero, unequal true minima0.87500.87503.85×10−63.85\times10^{-6}

A common +0.1+0.1 shift barely changed mean final MSE, but 1/512 paired paths exceeded the declared 10−610^{-6} coordinate tolerance (maximum 4.79×10−64.79\times10^{-6}). This pathwise numerical discrepancy remains unresolved.

References

[1] Loizou et al. Stochastic Polyak Step-size for SGD. AISTATS 2021.

[2] Orvieto et al. Dynamics of SGD with Stochastic Polyak Stepsizes. NeurIPS 2022.

AuthorsOpenReview ↗

Official Comment by Authors [2/2]

QP rationale and empirical benefit

W3/Q3. Gradient-aware weighting within the stochastic AMOO framework.

Our main contribution is the stochastic convergence analysis of noisy Polyak weighting. Both QP weighting and delayed MaxGap satisfy our generic convergence certificate; we do not claim that QP weighting generally outperforms delayed MaxGap. QP-based Polyak weighting originates in PAMOO [1]. The subsequent MG-AMOO work [2] gives deterministic convex guarantees and leaves stochastic AMOO open.

For DunAMOO, both QP and delayed MaxGap fit our generic convergence certificate. QP additionally uses gradient magnitudes and pairwise alignment. Comparable objective gaps and complementary gradients can favor QP, because a mixture can reduce the gradient norm without sacrificing much weighted gap. This identifies favorable selection geometry. Our empirical comparison tests its benefit with delayed application.

The controlled comparison in Appendix D.4.2 provides direct empirical evidence for retaining QP weighting. The comparison uses 10 paired seeds with matched initialization, minibatch sequences and learning-rate schedules. At 1600 Multi-MNIST updates, we report the seed-averaged maximum unweighted training cross-entropy across tasks:

MethodFinal maximum training loss
QP0.0037
Delayed MaxGap0.0067

QP's loss is 44.1% lower. The paired difference is −0.0029-0.0029, with a 95% paired-bootstrap confidence interval [−0.0043,−0.0019][-0.0043, -0.0019]. A smaller benefit remains under matched training time. This supports gradient-aware QP weighting in our stochastic framework for the tested setting.

References

[1] Efroni et al. Aligned Multi Objective Optimization. ICML 2025

[2] Kretzu et al. Simple Optimizers for Convex Aligned Multi-Objective Optimization

Thanks for the rebuttal. Some concerns have been addressed. I maintain my score.

Comments on the paper

1 comment

Dear Reviewers,

With only two days remaining in the discussion period, we would be grateful if you could review our responses. We understand how busy this time can be, especially for fellow reviewers, and have therefore kept our replies concise and focused.

Thank you again for the time and care you have devoted to reviewing our paper.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.