acceptodds
Under review as a conference paper at ICLR 2027

ClipVR-MGDA: Optimal Stochastic Algorithm for Generalized-Smooth Multi-Objective Optimization

Abstract

Multi-objective optimization (MOO) has become increasingly important in modern machine learning applications. While many stochastic multi-gradient descent algorithms (MGDA) have been developed for MOO, they typically suffer from suboptimal sample complexity for finding a Pareto stationary point. This has motivated MOCO+, a variance-reduced algorithm for MOO. However, its convergence guarantee relies on restrictive assumptions and applies only to smooth objective functions that are uncommon in applications with complex models. We develop ClipVR-MGDA, an optimal stochastic algorithm for non-convex MOO under a broad class of generalized-smooth objectives. ClipVR-MGDA integrates a matrix-valued SPIDER estimator with MGDA-type updates to construct variance-reduced multi-gradient estimates across all objectives. To enable effective multi-gradient variance reduction under generalized-smooth objectives, we further introduce carefully designed gradient-clipping schemes for both the parameter update and the preference vector update. Under standard assumptions, we prove that ClipVR-MGDA converges to an -Pareto stationary point with the optimal sample complexity. Experiments on multi-task learning benchmarks demonstrate improved performance over existing stochastic MOO baselines.

Primary area:
optimization
Keywords:
Stochastic Optimization, Multi-objective Optimization

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_qqqpOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper considers a variant of MGDA to address the stochastic multi-objective optimization (MOO) problem. It combines the variance reduction method SPIDER with a clipping technique to improve upon the sample complexity of existing methods. Also, the paper claims to achieve this better complexity result under a generalized smoothness condition, which relaxes the commonly used Lipschitz smoothness assumption. After the theoretical part, some numerical results are reported.

Critical strengths

The theoretical results are impressive: the paper not only achieves better sample complexity but also removes some assumptions.

Critical weaknesses

The paper is not well organized. Specifically, many parts are redundant (for example, the formulation in Line 202 repeats the equation in Line 36), the comparison with related work is relegated to Section 4.2 without any explanation, and the theoretical insights are not clearly explained.

The main result does not clearly resolve the KK-dependence. The claim in the FAQ is not supported and may be incorrect. Specifically, the appendix requires the initial value of FF to depend on KK, which, combined with the choice of MM, may introduce additional KK-dependent terms into the final results. Also, the exponent of KK (5/2, and may be even larger) is large, which limits the scalability of the algorithm.

The numerical experiments are limited to small datasets and unrealistic settings. An LLM-based experiment with more objectives can substantially strengthen the numerical evidence.

Questions for authors

In Line 49, the authors consider the CA, while the subsequent contexts ignore this issue. I wonder if this proposed method still has some guarantee on CA?

Minor mistake in Line 15: Term “MGDA” should not be used here.

2 comments

We thank the reviewer for recognizing the theoretical contribution, and we will reorganize our paper.

Dependence on KK. Our primary focus is the oracle-complexity dependence on ϵ\epsilon for a fixed number of objectives KK, motivated by applications with a small, fixed set of objectives. Our ϵ−3\epsilon^{-3} optimality result concerns this regime, with constants depending on KK, the confidence level, and problem parameters. We will clarify this scope and distinguish accuracy optimality from optimal joint dependence on KK and ϵ\epsilon.

Experimental scope. Beyond the synthetic and Multi-MNIST experiments, the appendix includes Office-31 ablations using a pretrained ResNet-18. These evaluate query efficiency and the contribution of double clipping. We acknowledge that scalability to many-objective LLM training remains empirically unverified.

CA guarantee. Most MGDA algorithms feature a CA direction, and the update directions in our algorithm also inherit this property.

Thank you for your rebuttal. I'll maintain my rating.

Reviewer_h9qsOpenReview ↗
Rating
1(−1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes ClipVR-MGDA for stochastic nonconvex multi-objective optimization under generalized smoothness. The method combines a matrix-valued SPIDER estimator with clipping mechanisms for both the model parameter and task-weight updates. Under suitable assumptions, the authors establish an O(ϵ−3)O(\epsilon^{-3}) sample complexity for Pareto stationarity. Experiments on synthetic data and Multi-MNIST, supplemented by clipping ablations, support the claims.

Critical strengths
  1. The paper studies a meaningful theoretical question: achieving improved sample complexity for multi-objective optimization under generalized smoothness.

  2. The theoretical analysis is rigorous and supported by detailed proofs after a brief check.

Critical weaknesses
  1. Limited algorithmic novelty. The method mainly achieves variance reduction over DS-MGDA, and the improvement from O(ϵ−4)O(\epsilon^{-4}) to O(ϵ−3)O(\epsilon^{-3}) is somewhat expected. Please clarify the main technical challenges beyond combining these techniques.

  2. Large-batch/stepsize requirement. Can the method avoid large-batch refreshes while retaining its convergence guarantee? Also, the β\beta is very large in theory, but it is chosen as a small value of 0.3.

  3. Limited experiments. The main comparisons focus on synthetic data and Multi-MNIST. Evaluation on larger, more diverse multi-task datasets would strengthen the conclusions. For example, DS-MGDA chooses Cityscapes, NYU-v2, etc.

Questions for authors
  1. Unclear stability gains. Why does ClipVR-MGDA have a relatively smooth curve in Figure 1 while the baselines fluctuate sharply? Please clarify any smoothing and the shaded regions. Besides, in Table 3, double clipping achieves similar mean accuracy to primal-only and no clipping but has the largest final-accuracy standard deviation.

  2. Presentation. Page 8 contains excessive blank space and uneven formatting. Please reorganize the layout.

2 comments

Beyond the synthetic and Multi-MNIST experiments, the appendix includes Office-31 ablations using a pretrained ResNet-18. These evaluate query efficiency and the contribution of double clipping.

1. Unclear stability gains. Why does ClipVR-MGDA have a relatively smooth curve in Figure 1 while the baselines fluctuate sharply? Please clarify any smoothing and the shaded regions. Besides, in Table 3, double clipping achieves similar mean accuracy to primal-only and no clipping but has the largest final-accuracy standard deviation.

The smoother curve is consistent with ClipVR-MGDA’s use of SPIDER-based variance reduction, which reduces noise in the gradient estimates. Double clipping further limits the impact of gradient fluctuations on updates to both the model parameters and preference weights. Compared with primal-only clipping, double clipping achieves similar mean performance but larger final-performance SDs. One possible explanation is that clipping the weight updates slows preference adaptation in some runs, leaving different seeds at different stages of convergence under a fixed training budget.

2. Presentation. Page 8 contains excessive blank space and uneven formatting. Please reorganize the layout.

We agree and will reorganize the layout on Page 8 to remove excessive blank space and improve formatting consistency.

My points in the weakness part are not answered and I insist those are important. In this case, I would like to lower my rating.

Reviewer_FHRPOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
3
Soundness
2(+1)
Read review
Paper summary

The paper studies stochastic nonconvex multi-objective optimization under mean-square generalized smoothness. It proposes ClipVR-MGDA, which combines matrix-valued SPIDER gradient estimation, simplex-weight updates, and coordinated clipping. The paper provides a convergence analysis claiming a high-probability bound on the averaged stationarity residual with O(ϵ−3)O(\epsilon^{-3}) gradient-query complexity. It conducts experiments on noisy quadratic problems, Multi-MNIST, and Office-31 to evaluate query efficiency, training stability, and the effects of primal and dual clipping.

Critical strengths
  • The paper addresses a relevant challenge: stabilizing stochastic multi-objective updates while limiting gradient-query costs.
  • Coordinated clipping and matrix-valued gradient tracking form a promising algorithmic design for adaptive objective weights.
Critical weaknesses
  1. The stopping-time proof leaves a central gap. Lemma 4 is localized to t<τt<\tau, but the proof uses unrestricted moments after dropping survival indicators. The required stopped-estimator bound, including the first threshold crossing, is not established. (pp. 21, 23, 26)

  2. The synthetic oracle is biased as written. With h^=max⁡{h+512z,0.1}\widehat h=\max\{h+512z,0.1\} and z∼U[−1,1]z\sim U[-1,1], h=1h=1 gives Eh^≈128.55\mathbb E\widehat h\approx128.55. This estimates a different quadratic from the stated objective; the implementation has not been verified. (pp. 30-31)

  3. The experimental clipping rule need not satisfy the theorem. The stated scales permit αt/γt\alpha_t/\gamma_t to vary between 11 and 55, whereas the proof requires a constant ratio. Whether the actual trajectory remains in a proportional regime is unclear. (pp. 7, 31)

Questions for authors
  1. What is the full oracle-complexity dependence on objective count and confidence, including the choices of F,M,n0F,M,n_0?

  2. Which representative non-globally-smooth learning objectives satisfy Assumption 3's global two-point condition?

1 comment

1. Stopping-time analysis.

We agree that the localization argument is incomplete as written. Using the indicator It=1{t≤τ}I_t=\mathbf1_{\{t\le\tau\}}, which is measurable before the current batch is sampled, the SPIDER recursion gives

E[It∥vtk−∇fk(xt)∥2]≤η12.\mathbb E[I_t\|v_t^k-\nabla f^k(x_t)\|^2]\le\eta_1^2.

This includes the first threshold crossing. We will provide this derivation and replace the unrestricted-moment applications throughout the proof.

2. Synthetic oracle.

The stated truncation indeed introduces bias. We will correct the implementation to satisfy unbiasedness and bounded variance, and rerun the affected comparisons.

3. Oracle complexity.

Our primary focus is the oracle-complexity dependence on ϵ\epsilon for fixed KK and a fixed confidence level, not a optimal joint dependence on all parameters. We will clarify this in later revision.

4. Assumption 3.

A representative example is the joint reformulation of χ2\chi^2-regularized DRO. With uniformly Lipschitz, smooth sample losses and uniformly bounded loss variance, a direct calculation yields Assumption 3 with g(u)=A+Bug(u)=A+Bu, although the joint objective need not be globally smooth. We will add this verification and specify the sufficient conditions.

Comments on the paper

1 comment

Human assessment: Below are some major points that I think remain unaddressed.

The paper addresses some technical challenges in adapting existing techniques rather than introduce a fundamentally new optimization mechanism or new analysis technique.

Overall I think the method is like combining A (MGDA) with B (Clipping) and C (variance reduction like STORM), along with the analysis techniques. Though sound and useful, I do not find it very interesting.

Also regarding the CA guarantee asked by Reviewer qqqp, I believe it is not guaranteed automatically. The noise or error in the objective gradients propagate to the computed CA direction, which thus has error compared to the true CA direction given the true full-batch gradient.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.