How do optimizers compare under unobserved data imbalance in deep learning?

Comparing optimizers when the minority group is hidden

The paper asks a narrow question: if training data contain a minority structure that the optimizer cannot see, how quickly does each optimizer's trajectory stop systematically favoring the majority? The authors model the total loss as L = L1 + L0, where L1 is the majority component and L0 is a minority component, but the optimizer only accesses the aggregate L. Only an amplitude ψ > 0, bounding the effective mass of the latent minority, is assumed known.

This matters because many real imbalances are not labeled. The paper lists latent minority groups tied to acquisition conditions, rare subclasses, demographic attributes, and rare linguistic patterns, and notes that methods requiring minority identities for resampling or reweighting can fail when those identities are unavailable. The comparison is therefore about optimizer geometry under uncertainty, not about reweighting schemes that need group labels.

Idealized geometries stand in for real optimizers

A direct theoretical comparison of modern optimizers is described as out of reach, so the paper uses two idealizations. First, it keeps each optimizer's dominant update geometry and discards weight decay, momentum, and minibatching: gradient descent represents SGD, sign descent matches Adam-type methods, and spectral descent corresponds to Muon and Scion-type methods. Newton descent is included as a second-order reference even though it is intractable in high dimension.

Second, because typical learning rates are below 10^-2, the authors study optimizer vector fields in continuous time. Continuous time creates a clock ambiguity, since rescaling the vector field rescales time. The paper resolves this by returning to discrete updates with step sizes in [η_min, η_max] and a ratio κ = η_max/η_min, so clock discrepancies are controlled by κ. For vision networks, learning rates typically run from about 10^-3 to 10^-2, giving κ ≈ 20; the paper reports κ ≈ 500 for tabular learning and κ ≈ 700 for language modelling, with κ ≈ 1000 in one tabular table.

Entry time measures exposure to imbalance

The paper defines a minority awareness region for each idealized optimizer and studies t_entry, the first time the trajectory enters that region. Inside the zone, at least one admissible decomposition yields minority improvement at the majority's expense. The authors are explicit that this need not mean learning the true latent subgroup: awareness concerns at least one admissible minority at the prescribed level ψ.

So t_entry is an indicator of exposure to imbalance, not a measure of final accuracy or of having recovered the real minority. The paper derives explicit equations for these zones and both upper and lower bounds on entry time for gradient descent, gradient clipping, sign descent, spectral descent, and Newton descent. The central theoretical claim is that these bounds depend more mildly on minority amplitude ψ for sign, spectral, and Newton descent than for Euclidean gradient descent, with additional gains governed by gradient support or matrix rank.

Why normalized geometry delays majority bias

The mechanism the paper proposes is geometric. Euclidean gradient descent's progress is tied to the raw gradient magnitude, so when the minority contribution is small, the aggregate gradient is dominated by the majority and the trajectory stays in the majority-favored region longer. Sign, spectral, and Newton descent rescale the update direction, which changes how the entry-time bound scales with ψ.

The paper also reports a strong-convexity result that sharpens the contrast: for strongly convex objectives, sign descent's entry time is bounded above by sqrt(2(L(θ_init) − L*)/µ), while gradient descent's entry time tends to infinity as ψ tends to 0. That is a statement about idealized dynamics, not about measured deep-network training, and it is derived under the paper's loss assumptions rather than observed directly.

Linear regression tests the scaling prediction

The first empirical test uses linear regression, where the latent decomposition and entry times can be computed. Using PCA to build families of problems across dimensions, the authors vary minority-group size to change ψ = σ_max(∇²L0), measure entry times for gradient descent (GD) and sign descent (SD), and fit the ratio with log–log regression.

On Superconductor they report t_entry(GD)/t_entry(SD) ∝ d^0.65/ψ^0.90, and on YearPredictionMSD ∝ d^0.51/ψ^0.37. The paper's reading is that gradient descent's entry time grows faster than sign descent's in high-dimensional and highly imbalanced regimes. The fitted exponents differ between the two datasets, so the direction of the effect is the stable finding, not a single universal exponent.

Classification and language experiments show minority gaps

In the deep-network experiments, ψ and t_entry are not directly observable, so the authors evaluate the practical counterparts SGD, AdamW, and Muon by measuring minority and majority performance. On Forest Covertype, with the Aspen class as a hidden minority at 1.6% of the dataset, AdamW's early advantage over SGD is much larger on the minority class (63.93% vs 51.40% average accuracy) than on the majority class (90.99% vs 88.25%).

On CIFAR-10, averaged over iterations 1–30, Muon reaches 96.48% minority accuracy and 98.39% majority accuracy, AdamW 91.82% and 95.45%, and SGD 86.04% and 92.92%. In the SmallGPT-2 language modelling run on WikiText-103, tracking the 5% rarest tokens, the paper reports that AdamW and Muon minority losses initially spike before decreasing, whereas SGD's minority loss strictly increases. The authors describe this as corroborating the theoretical finding that standard gradient dynamics delay optimization of the minority signal.

Where the conclusions hold and where they stop

The theoretical results apply to idealized continuous-time optimizer geometries with weight decay, momentum, and minibatching removed, and to losses satisfying the paper's smoothness assumptions. The entry-time comparison is meaningful only up to the clock factor κ, which the authors argue is moderate for deep-learning losses but report as roughly 20 for image classification, 500 for tabular learning, and 700 for language modelling.

The classification and language experiments do not measure ψ or t_entry directly; they measure minority and majority accuracy or loss, which answer a different question from the theoretical entry-time bounds. The paper also notes that the relative performance of AdamW and Muon depends on problem geometry, so the experiments support a systematic advantage of rescaled methods over SGD rather than a fixed ranking between AdamW and Muon.

What to take from the comparison

The paper's most decision-relevant claim is a comparison, not a single winner: when imbalance is latent and only aggregate loss is visible, the geometry of sign, spectral, and Newton descent gives a milder dependence on minority amplitude than Euclidean gradient descent, and the experiments place AdamW and Muon ahead of SGD on minority data while final majority performance stays comparable. The ranking between AdamW and Muon is left to problem geometry.

The practical threshold the paper supplies is the minority amplitude ψ and the clock ratio κ. As ψ becomes small, the theoretical gap between gradient descent and normalized geometries widens, and the empirical minority gaps on Covertype, CIFAR-10, and WikiText-103 appear in the same direction. Readers weighing optimizers for a suspected but unlabeled minority should treat the entry-time scaling and the observed minority-versus-majority split as the relevant evidence, and should not read the results as a guarantee that any specific optimizer recovers the true latent subgroup.

Sources used in this answer