Multiplicative vs. Additive State Coupling in Learned Optimizer Schedules

AI summary

Overview

• Research area: Machine learning for combinatorial optimization, specifically learned hyperparameter schedules for a classical MAX-CUT solver, with a conceptual link to learned optimizers.
• Technical level: Intermediate (comfortable with gradient descent, unrolling/backpropagation-through-time, and basic notation for optimization objectives; the paper is mathematically explicit but conceptually narrow).
• Scope: A controlled architectural comparison of three learned continuation schedules (state-blind, multiplicative/bilinear state-adaptive, additive state-adaptive) for a penalty relaxation of MAX-CUT, evaluated in-distribution and out-of-distribution over 15 seeds.

What This Paper Is About

Classical solvers for the MAX-CUT relaxation depend on hand-tuned hyperparameters: how fast the penalty strength grows across continuation stages and what step size each stage uses. Instead of tuning these by hand, the authors unroll the entire multi-stage solver and learn the schedule by backpropagating through it. The paper's real question is narrower and more interesting: once you let the schedule see the solver's current state, does it matter how that state enters the schedule — added to it, or multiplied into it?

Key Contributions

1. A controlled three-way comparison. The authors train a state-blind schedule (2K free scalars), a multiplicative/bilinear state-adaptive schedule, and a capacity-matched additive ablation that receives identical inputs and uses identical output heads, differing only in how context and penalty are combined.
2. Evidence that the form of state coupling, not state adaptivity alone, drives out-of-distribution transfer. Two state-adaptive models that are statistically indistinguishable in distribution diverge sharply beyond the training size range, with the bilinear model improving over its own frozen baseline (t = 4.1 over 15 seeds on Biq Mac) and the additive model degrading (t = −11.7).
3. A regularization robustness check. The separation appears without any regularization and persists across a 30-round weight-decay sweep over w_dec ∈ {0, 10⁻⁴, 3×10⁻⁴, 10⁻³, 3×10⁻³}, so it is not an artifact of weight decay.
4. A calibrated baseline comparison. The learned bilinear schedule (Biq Mac ratio 0.9627) is statistically indistinguishable from a grid-searched fixed geometric schedule (0.9624) selected only on the training distribution via a 150-configuration search — framing the contribution as architectural rather than "learning beats tuning."

Main Findings

• In distribution, the models are indistinguishable. On held-out Erdős–Rényi G(n, 0.5) graphs with n ∈ {6, …, 15}, mean discrete cuts range from 19.35 to 19.47 across the three trained schedules, versus 18.72 for the state-blind frozen baseline. On a fixed hard instance with n = 15 and optimum 38, the additive, bilinear, and state-blind schedules hit the optimum in 13/15, 12/15, and 7/15 runs respectively — a difference the authors treat as within run-to-run variation.
• Out of distribution, the bilinear schedule improves on its own untrained baseline. On the 80-instance Biq Mac suite (n = 100), it gains 0.0084 in ratio-to-optimum (paired t = 4.1 over 15 seeds), moving from a frozen 0.9543 to a learned 0.9627.
• The additive ablation degrades out of distribution. Despite starting from a nearly identical frozen baseline (0.9545), it falls by 0.0522 to 0.9023 (t = −11.7) — worse than its own untrained initialization.
• The state-blind schedule improves the most in relative terms but ends up weaker. It gains 0.0161 on Biq Mac (0.9259 → 0.9420), but because it starts from a much weaker baseline, the bilinear schedule remains the strongest trained model in the table.
• Large synthetic instances follow the same pattern. At n = 100, discrete cuts go 1393.1 → 1406.9 (state-blind), 1410.9 → 1415.4 (bilinear), and 1411.0 → 1397.9 (additive).
• The effect is not a weight-decay artifact. Across the sweep, the bilinear change stays positive, ranging from +0.0084 to +0.0134, while the additive change stays negative, from −0.0595 to −0.0478 at nonzero decay (and −0.0522 at zero decay).
• A tuned fixed schedule is a strong competitor. The grid-searched geometric schedule ρ_k = ρ₀g^k with constant α reaches 0.9624 ± 0.0024 on Biq Mac, statistically indistinguishable from the unregularized bilinear result and above both the learned state-blind and additive schedules.
• The knapsack extension shows the coupling asymmetry without the quality separation. The paper reports that a preliminary knapsack experiment shares the structural asymmetry (unsaturated bilinear coupling vs. saturating additive coupling) but does not reproduce the out-of-distribution quality gap — which the authors flag as a limit on generality.

Methodology in Plain English

The setup keeps the classical solver fully intact and learns only its knobs. Relaxed spins are written as tanh(u), giving a soft cut term plus a penalty that pushes spins toward ±1. The solver runs K = 7 continuation stages, each with T = 15 plain gradient-descent steps at a fixed step size α_k and penalty ρ_k, with the penalty increasing stage to stage and the final iterate of each stage initializing the next.

Three schedules decide (α_k, ρ_k):

• State-blind: one learned step size and one learned penalty increment per stage — 2K scalars, no view of the current iterate.
• Bilinear: a size-independent 4-element context [ρ_k/ρ₀, bviol(u), cut(u), k/K] is projected, then multiplied element-wise by a projection of log ρ_k at factor width r = 8; two softplus heads turn the result into a step size and a nonnegative penalty increment (59 parameters).
• Additive: the same context concatenated with log ρ_k, passed through an affine layer and a tanh (67 parameters — slightly more than the bilinear model, not fewer), with identical output heads.

Training samples fresh graphs each batch (batch size 8, n ~ Uniform{6, …, 15}), runs L = 8 parallel spin trajectories per graph under a shared schedule, and backpropagates the negative final soft cut through all K·T = 105 inner updates with the higher-order graph retained, updating schedule parameters with Adam at learning rate 0.05. Stability comes from clamping α_k to [10⁻⁴, 10] and clipping the gradient norm at 1.0. Everything runs in double precision on CPU for 200 epochs, with 15 independent seeds per configuration, and each learned model is measured against a frozen version of itself that keeps its initial geometric penalty ladder and constant step size.

Why This Matters

The paper's contribution is diagnostic rather than a new state-of-the-art solver: it isolates an architectural variable — additive versus multiplicative use of a running state summary — while holding inputs, heads, solver, and capacity roughly fixed. That is the same structural question that separates coordinate-wise adaptive optimizers from structure-preserving ones such as Shampoo, K-FAC, and Muon, so the result suggests a template for a controlled comparison in those families (which the authors explicitly do not claim to have demonstrated). It also cautions against judging learned schedules by in-distribution numbers alone, since the two state-adaptive models are indistinguishable there and diverge under distribution shift.

Real-world applications (context for the problem class, not results reported in this paper):

• VLSI circuit layout and partitioning, a canonical MAX-CUT workload in semiconductor design.
• Network design and community detection in graphs.
• Portfolio diversification and risk-aware asset selection in finance.
• Ground-state estimation for Ising-type models in statistical physics.
• Wireless resource allocation and scheduling problems formulated as cut problems.

Industry relevance: the work comes from Qualcomm AI Research, and its practical angle is efficiency — replacing hand-tuned solver schedules with small learned controllers (59–67 parameters) that remain graph-size-independent and transfer to instances far larger than those seen in training.

Future Directions

• Disentangling activation geometry from multiplicative structure. The authors hypothesize the bilinear path benefits from an unsaturated elementwise product (with ρ_k/ρ₀ and log ρ_k passing through unclamped and compounding across stages) while the additive path's tanh self-limits the same inputs. They state they have not re-verified this trajectory-level effect for MAX-CUT and are currently running a saturating bilinear head and an unsaturated linear additive head.
• Understanding why knapsack does not reproduce the quality separation. Whether the effect depends on the constraint's dual structure, the solver, or the mechanism itself is left open.
• Testing transfer to real learned optimizers. The authors motivate an analogous controlled comparison among Adam, Shampoo, K-FAC, and Muon but explicitly do not claim the mechanism transfers.
• Broadening the evidence base. The paper itself notes the findings are specific to one MAX-CUT relaxation, one continuation solver, one training distribution, and one evaluation suite, with additional untested generalization axes listed in Appendix C.6.

Target Audience

Researchers working on learning-to-optimize, learned optimizers, and differentiable/unrolled solvers; practitioners applying ML to combinatorial optimization who need to know whether a learned controller will hold up on instances larger than those it was trained on; and methodologically minded readers interested in how to design a clean ablation that separates "does the model see the state" from "how does the state enter the model." Readers should be comfortable with backpropagation through unrolled iterative algorithms; the MAX-CUT-specific material is self-contained enough that no prior combinatorial-optimization background is required.

Authors’ abstract

We learn schedules for a continuous penalty relaxation of MAX-CUT by backpropagating through an unrolled classical solver. A state-blind schedule generalizes to instances substantially larger than those used for training. A state-adaptive bilinear schedule also generalizes out of distribution, outperforming its untrained baseline across 15 seeds ($t=4.1$). By contrast, an additive ablation with identical inputs and output heads is statistically indistinguishable from the bilinear model in distribution but performs worse than its own baseline out of distribution ($t=-11.7$). This separation appears without regularization and persists across a $30$ round weight-decay sweep: the bilinear advantage remains significant at every tested value, whereas the additive model never recovers. The results in this setting isolate how solver state enters the schedule, rather than state adaptivity alone, as the architectural distinction associated with out-of-distribution transfer.