- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper adapts the multiple gradient descent algorithm (MGDA) to optimizers that takes steps through a LMO (linear minimization oracle) in an arbitrary norm: normalized gradient descent, signup and Muon. Each iteration: 1) blends the K task gradients with the current weight w_t to get G_t; 2) makes one oracle call, D_t = lmo(G_t); 3) score each task by g_{t,i} = <D_t, grad of f_i>; 4) updates the weights by Hedge. The paper provides the convergence of the proposed algorithm for both deterministic and stochastic settings. Experiments show its effectiveness over some benchmark datasets.
Critical strengths
- The analysis use only the oracle identity <g, lmo(g)> = -R |g|_*. One proof covers normalized GD, signup, muon and layer-wise norms.
- the gradient bound is derived in the deterministic case. It is more challenging for the stochastic case, and its design is careful: 1) calling the oracle on the previous buffer makes the noise cross term exactly zero in expectation (I found this technique interesting). 2) take advantages of the proof for the deterministic case and bound the noise term more conveniently.
Critical weaknesses
-
The components of the proposed methods are well-known in optimization: LMO descent (Pethick et al., 2025), single loop weight update for MGDA, and exponentiated gradient weighting (mirror descent). The convergence analysis for deterministic case is simply the combination of results of these components. I particularly like the design and theoretical analysis of stochastic case, which call the oracle on the previous buffer, making the noise cross term exactly zero in expectation. Is this technique used by the authors for the first time?
-
Each step of the proposed method needs K backward passes and storages of K full gradients, which costs K x d memory. The analysis of compute and memory costs should be discussed.
-
Step sizes depend on L, Delta, which requires knowing every f*_i, M and T. That's acceptable for theory, but practical claims should rely on tuned hyperparameters. It would be better if a sensitivity study for the hyperparameterers is provided.
Questions for authors
See the weaknesses.
3 comments
Update after the revision. The revised version (changes in blue) contains the following, in reference to our response:
- Previous-buffer evaluation: Section 4.2 relates it to AdaGrad-type step sizes computed from past gradients only (Li & Orabona, 2019).
- Compute and memory (W2): Section 4 states the cost per iteration, one backward pass and one forward-mode pass with no per-task gradient stored; the comments of Algorithm 1 give the pass counts, and Appendix I gives the cost model, including when this is cheaper than backward passes.
- Hyperparameter sensitivity (W3): Table 7 adds the model step size : MultiMNIST test accuracy is 73.15%, 80.92%, 89.47%, 90.54% and 88.68% for equal to , , , (selected on the validation split) and . Together with Tables 5 and 6 ( and ), this shows that the step size matters most.
Thank you for the rebuttal.
I'd like to thank the authors for the clarification. I'd like to keep my score. Good luck!
Thank you for the careful reading and for the positive assessment of the stochastic analysis.
W1: The components are known. We agree: LMO steps (Pethick et al., 2025), a single-loop weight update and exponentiated gradient are all known. The contribution is their analysis in an arbitrary norm pair, with three steps that do not follow from existing results. Lemma 4.3 derives a gradient bound along the deterministic trajectory, so the deterministic analysis needs no bounded-gradient assumption, which MOON and MSMD make. Lemma 4.7 bounds the expected weight increment by a weighted average of the noisy task scores rather than their maximum, which keeps the leading stochastic term free of K; together with the logK regret of the entropic update, the dependence on the number of objectives K is polylogarithmic, whereas MOON's constants are polynomial in it. Theorem 5.1 gives iteration-wise tracking of the inner optimum with a regularized, clipped weight update.
Is the previous-buffer evaluation new? Not as a device. Analyses of AdaGrad-type step sizes compute the step size from past gradients only, so that it is independent of the current stochastic gradient (Li & Orabona, 2019). Algorithm 2 applies it to the direction: evaluating the oracle at the previous momentum buffer Mt−1 makes Dt independent of the current minibatch, so the noise cross term has zero conditional mean. The device matters more here than in single-objective LMO methods (Pethick et al., 2025), where noise enters only through the momentum tracking error: our weight update also uses the raw task scores, whose noise momentum does not average. With the oracle at the current buffer, Dt would depend on the current minibatch, which makes the expected scores, and hence the cross term, difficult to control. The multi-objective baselines we cite do not use the device, and we are not aware of its use in other multi-objective methods. We will add these references.
W2: K backward passes and K×d memory. These costs come from our implementation, not from the method: when we wrote the paper, we did not realize that the task scores can be computed by a Jacobian-vector product, and using one reduces the cost. Write F=(f1,…,fK) and JF(xt)∈RK×d for its Jacobian. The task scores form the Jacobian-vector product gt=JF(xt)Dt, which one forward-mode pass computes for all K tasks at once, and the blended gradient JF(xt)⊤wt is one backward pass of ∑iwt,ifi. Each iteration therefore needs one backward pass and one forward-mode pass, of comparable cost, and stores no per-task gradient. The shared network is then traversed a constant number of times instead of once per task, and the memory for gradients of the shared parameters no longer grows with K. The task heads are still evaluated once per task, as in any method, so computation drops when the shared network dominates the cost and K≥3; for K=2 it does not drop. Since Algorithm 2 fixes Dt= lmo$(M_{t-1})$ before drawing the minibatch, the forward-mode pass can be fused with the forward pass of the weighted loss. Section 4 will include this discussion.
W3: The step sizes depend on problem constants. We agree, and all reported experiments use tuned hyperparameters: Appendix I lists the search grids, and on MultiMNIST the selection uses a validation split. Tables 5 and 6 already report the sensitivity to the weight step η and to the clipping parameter κ: MultiMNIST test accuracy stays between 89.5% and 91.1% across both grids. We will try our best to add a sensitivity study for the model step size γ. In the theory, the problem constants enter the step sizes only through a multiplicative factor: given a gradient bound along the trajectory, the choices γR=c/T and ηR=c′/T give the O(T−1/2) rate of Theorem 4.4 for any c,c′>0, with a constant that depends on c and c′. In particular, as for single-objective LMO methods (Pethick et al., 2025, Insight 5.1), the rate does not require knowing L.