How Norm-Constrained Geometry Shapes Multi-Objective Optimization with Entropic Weights

The oracle replaces the Euclidean step direction

Multiple-gradient descent normally picks the convex combination of task gradients with the smallest Euclidean norm and steps against it. This paper keeps that weighting logic but changes the geometry of the step: a norm-constrained linear minimization oracle returns a direction D_t inside a radius-R ball of a chosen norm, chosen so that the inner product with the blended gradient G_t equals minus R times the dual norm of G_t. That single identity, plus a bound on the direction's norm, is all the convergence analysis uses.

Because the identity holds for any norm, the analysis covers spectral and sign geometries alongside the Euclidean baseline. The authors describe this as extending the spectral construction studied by concurrent MOON to general norms. The practical cost per iteration is K task-gradient evaluations, one oracle call, and one entropic weight update, with no inner optimization loop.

Entropic weight updates move against aligned tasks

The weights live on the simplex and are updated by entropic mirror descent on scores g_t, with an optional pull toward uniform weights and an optional floor κ on every coordinate. The closed form is a softmax followed by clipping. The sign is counterintuitive: because minus g_t over R is a subgradient of the map sending w to the dual norm of the blended gradient, descending on it ascends in g_t. A task well aligned with the current direction gets a strongly negative score and loses weight, while a task being harmed gains weight.

Setting the pull and the floor to zero reduces the update to exponentiated gradient. The entropy term shrinks logits toward uniform weighting, which the authors relate to MOON's logit decay. With a positive floor, the clipping step needs a monotone recurrence over at most K rounds, or O(K log K) with sorting.

Determinism yields a rate and a derived gradient bound

In the deterministic setting, Theorem 4.4 bounds the average stationarity residual by (sqrt(2ΔL) + M sqrt(log K / 2)) divided by sqrt(T), where Δ measures the initial suboptimality gap, L is the smoothness constant, and M bounds the infinity norm of the scores. The bound holds for any norm pair and does not involve the regularization strength or the floor.

The more distinctive step is Lemma 4.3: for the unregularized, unclipped method, smoothness and lower-boundedness alone imply M = O(sqrt(LΔ log K)), so no separate gradient-bound assumption is needed. Substituting gives O(LΔ log²K / ε²) iterations to reach accuracy ε. This derivation is specific to the deterministic case; the stochastic and iteration-wise results still assume a trajectory gradient bound.

One momentum buffer keeps task count out of the leading term

With stochastic gradients and a bounded-gradient assumption, Theorem 4.9 gives an O(ε^-4) iteration count, equivalently an O(T^-1/4) rate, using a single persistent momentum buffer on the blended gradient. A weighted-average bound on the noisy weight increments keeps explicit K dependence out of the leading T^-1/4 term. Lower-order terms still carry linear K dependence under bounded variance, replaced by log K under a stronger tail assumption.

This is the paper's clearest separation between what the geometry buys and what it does not. The leading stochastic rate is stated without explicit task-count dependence, but that statement is about the leading term only, and it rests on the bounded-gradient assumption rather than a derived bound.

Spectral and sign geometries can make the optimum nonunique

Proposition 3.1 shows that the minimizing blended gradient is unique in every instance exactly when the dual unit ball is strictly convex. For the ℓ1 dual, and for the nuclear norm, the unit ball is not strictly convex, so distinct weight vectors can attain the same minimal dual norm. The paper's construction uses two gradients equal to distinct points of a flat segment of the dual sphere, making every weight optimal.

This matters because a conflict-avoidant distance defined through a particular minimizer becomes selection-dependent. The authors therefore analyze a selection-independent inner gap instead. They also show that inner optimality alone does not certify per-task descent: a conventional sign selection can actively degrade a task at an inner minimizer. Crucially, the average-case stationarity rates do not require the saddle-point condition that rules this out; selection affects per-iteration guarantees, not the rates.

Regularization and a floor buy iteration-wise tracking

On arbitrary bounded gradient sequences, the paper establishes static regret for the inner weighting objective. Adding entropy regularization and a weight floor gives iteration-wise control of the inner gap after a burn-in period, while retaining ergodic stationarity, conditional on a trajectory gradient bound. The authors stress that this every-iterate tracking guarantee, not average-gap convergence alone, is the distinct conclusion of the regularized analysis.

The guarantee comes with stated limits. The tracking exponents are not competitive with Euclidean conflict-avoidant-distance results, and the gradient bound used here is assumed rather than derived. Fixed relative oracle error is tolerated for deterministic stationarity and average gap, but the paper does not extend that tolerance to the stochastic or iteration-wise guarantees, and it does not establish a uniform error level for the five-step Newton–Schulz implementation used in experiments.

Experiments test small task counts without regularization

Experiments compare the method with existing multi-task optimizers on Cityscapes with K = 2 tasks, NYU-v2 with K = 3 tasks, and MultiMNIST with two tasks. The aggregate metric Δm% averages per-task relative changes against single-task baselines, with sign conventions so that higher is better; the single-task row is zero by construction. On MultiMNIST the main configuration averages 90.54% test accuracy with an inner gap of 0.90 over three seeds.

The ablations sharpen the interpretation. For κ up to 0.48 the results coincide with the unclipped run, meaning the floor essentially never binds at that weight step. As κ approaches 1/K = 0.5, mean accuracy rises slightly to 91.11% at κ = 0.495 while the empirical inner gap grows from 0.90 to 1.65. Since κ near 1/K reduces the method to linear scalarization with the same oracle and momentum, and that configuration reaches similar accuracy, the margin over baselines at K = 2 cannot be attributed to adaptive weighting.

Two further boundaries belong with these numbers. All main configurations use zero regularization and zero floor, so the experiments do not test the iteration-wise tracking guarantee. Reported metrics average the final 10 epochs of a single seed, and those epochs are correlated, so they do not estimate variability across independent runs. Gaps for different oracle variants are also not on a common numerical scale, because the underlying geometries differ.

The general-norm guarantee is the paper's durable claim

The most transferable result is not a benchmark margin but the norm-agnostic argument: the stationarity analysis invokes only the oracle identity and a direction-norm bound, so it holds for any finite-dimensional norm pair, and the deterministic gradient bound follows from smoothness and lower-boundedness without an extra assumption. The stochastic leading term's independence from task count is the second claim worth carrying forward, but it is conditional on the bounded-gradient assumption and applies to the leading term only.

The paper's own priority ordering follows from this. The every-iterate inner-gap control after burn-in is the distinct contribution of the regularized analysis, yet it is exactly the part the experiments leave untested, since they run with zero regularization and at most three tasks. Readers weighing this method against Euclidean conflict-avoidant approaches should therefore treat the general-norm deterministic rate and the derived gradient bound as the established core, and the regularized tracking behavior at larger task counts as the open question the evidence does not yet answer.

Sources used in this answer