PaperlayerView exact revision on arXiv

Source-linked AI summary

Multiplicative vs. Additive State Coupling in Learned Optimizer Schedules

M. Harper Langston, Pierre-David Letourneau, Dalton Jones, Roland Memisevic, Peter Scott, Mingu Lee, Richard A. Lethin, Christopher Lott, Fatih Porikli, Harris Teague

arXiv:2610.32801v1cs.LGcs.AIcs.CLcs.NAmath.NAmath.OC

TL;DR

The paper asks whether a learned MAX-CUT solver schedule generalizes, and whether its behavior depends on how it incorporates solver state. It learns schedules by backpropagating through an unrolled classical solver; out of distribution, bilinear coupling improves over its baseline while the matched additive ablation declines.

  • Problem

    The paper asks whether the architecture of a learned schedule for a classical MAX-CUT solver generalizes beyond the training distribution, and how incorporating solver state affects that transfer.

    Source: §1 · p. 2, §4 · p. 7

  • Method

    The authors unroll a classical MAX-CUT penalty-continuation solve and learn its schedule, comparing state-blind, bilinear, and additive state-adaptive forms.

    Source: §1 · p. 2, §5 · p. 7

  • Results

    On Biq Mac, bilinear improves over its frozen baseline by 0.0084, whereas additive declines by 0.0522 (t = −11.7); the two are statistically indistinguishable in distribution.

    Source: §3 · p. 5

  • Takeaways & Limitations

    In this setting, the out-of-distribution separation is associated with how the schedule incorporates solver state, not state adaptivity alone.

    Source: §1 · p. 2, §5 · p. 7

    The evidence is specific to one MAX-CUT relaxation, continuation solver, training distribution, and evaluation suite; a preliminary knapsack extension does not show the same quality separation.

    Source: §4 · p. 7

Abstract

from arXiv · show

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.

1. Introduction

The paper learns hyperparameter schedules for a classical MAX-CUT penalty solver and compares state-blind schedules with two ways of incorporating solver state. Its central finding is that the bilinear schedule generalizes out of distribution while the matched additive ablation degrades relative to its own baseline.

Contribution.

  • The paper learns a penalty-continuation schedule by unrolling the classical MAX-CUT solver and backpropagating through its full trajectory.The schedule controls how quickly the penalty grows and which step size is used at each stage.Source: §1 · p. 1
  • A state-blind schedule learns one penalty and step-size pair per stage but cannot account for whether the current instance is already close to binary.The schedule knows the stage, not the current state.Source: §1 · pp. 1–2
  • The study contrasts state-blind schedules with additive and multiplicative bilinear ways of incorporating solver state.The two state-adaptive forms follow a minimal sufficient structure identified for non-trivial state tracking in RNNs (Ebrahimi and Memisevic, 2025).Source: §1 · p. 2
  • The bilinear schedule improves out of distribution over its untrained baseline, while the matched additive ablation degrades despite similar in-distribution performance.The separation appears without regularization and persists across a 30-round weight-decay sweep.Source: §1 · p. 2

Related work.

  • Unlike learned solvers that predict cuts or certificates, this work preserves the classical solver and learns its hyperparameter schedule.The resulting question is whether schedule architecture generalizes beyond the training distribution.Source: §1 · p. 2

2. Method

The method learns schedule parameters by differentiating through a classical penalty-continuation solve of the MAX-CUT relaxation. It compares a stagewise state-blind schedule with two state-adaptive schedules that differ in how they combine solver context and penalty.

2. Method

  • For relaxed spins s(u) = tanh(u), the method uses the classical penalty-relaxation solver rather than learning a cut or update rule directly.The first objective term rewards high-value cuts and the second drives spins toward {−1, +1}.Source: §2 · pp. 2–3
  • The learned schedules control a K-stage gradient-descent solve, with fixed step size and penalty within each stage and increasing penalty across stages.The penalty shifts optimization from improving the relaxed cut toward producing a discrete spin assignment.Source: §2 · p. 3

Schedule architectures.

  • The state-blind schedule assigns a step size and penalty increment to each stage, while state-adaptive schedules receive size-independent context and current penalty.The state-blind schedule uses 2K learned scalars but cannot respond to the current trajectory.Source: Schedule architectures · p. 3
  • The bilinear schedule combines projected context and current penalty multiplicatively, whereas the additive ablation concatenates the same inputs before an affine map and tanh.Both architectures use the same output heads for step size and penalty increment.Source: Schedule architectures · p. 3, Figure 1 · p. 4
  • Training unrolls the complete solve and backpropagates through inner updates and stage transitions to optimize schedule parameters.The spin variables are instance-specific states produced by the inner solver, and all architectures share the same objective and gradient-descent solver.Source: Schedule architectures · p. 4

3. Experiments

Schedules trained on graphs with n ≤15 are evaluated on larger synthetic graphs and the Biq Mac suite, as well as on held-out training-size graphs. The main out-of-distribution comparison shows that bilinear coupling transfers better than the additive ablation, while in-distribution performance does not distinguish them reliably.

Out-of-distribution performance.

  • On Biq Mac, the bilinear schedule improves over its frozen baseline by 0.0084, while the additive schedule declines by 0.0522 (t = −11.7).The bilinear improvement has paired t = 4.1 over 15 seeds; Table 1 reports out-of-distribution results without regularization.Source: Table 1 · p. 5, §3 · p. 5

In-distribution performance.

  • The state-blind, bilinear, and additive schedules have similar held-out performance, with mean discrete cuts ranging from 19.35 to 19.47.The state-blind frozen baseline is 18.72; on the fixed n = 15 instance, the three schedules reach the optimum in 7/15, 12/15, and 13/15 runs, respectively.Source: §3 · p. 5

Out-of-distribution performance.

  • The state-blind model’s larger relative improvement still yields a lower final score than bilinear: 0.9420 versus 0.9627.Their frozen baselines are 0.9259 versus 0.9543, respectively.Source: §3 · p. 5

Comparison with a tuned fixed schedule.

  • The unregularized bilinear result, 0.9627, is statistically indistinguishable from the tuned fixed reference score of 0.9624.The geometric fixed schedule was selected by grid search exclusively on the training distribution.Source: §3 · p. 5

Robustness to weight decay.

  • Across the weight-decay sweep, bilinear improvement remains positive (+0.0084 to +0.0134), while additive change remains negative (−0.0595 to −0.0478 at nonzero decay; −0.0522 at zero).The separation is present without regularization and persists across the tested decay values.Source: §3 · p. 6

Summary.

  • The experiments find similar in-distribution performance but divergent out-of-distribution behavior, not a separation on held-out training-size graphs or the single fixed hard instance.The summary also reports that the result is not explained by an untuned reference schedule or the choice of weight-decay strength.Source: §3 · p. 6

4. Discussion and Limitations

The authors propose that unsaturated multiplicative coupling and saturating additive coupling may contribute to the observed separation, but they have not verified that trajectory-level effect in MAX-CUT. They bound the evidence to one relaxation, solver, training distribution, and evaluation suite, and report that a preliminary knapsack extension does not reproduce the quality separation.

Discussion and limitations.

  • The proposed mechanism is that unclamped penalty inputs compound through bilinear coupling, while tanh self-limits the additive path; this trajectory-level effect remains unverified for MAX-CUT.The comparison may vary activation geometry together with multiplicative structure, motivating ablations that disentangle them.Source: §4 · p. 6

Connection to learned optimizers.

  • The authors do not claim that the observed mechanism transfers to Adam, Shampoo, K-FAC, or Muon.They motivate analogous controlled comparisons in those optimizer families.Source: §4 · p. 7

Scope and limitations.

  • The evidence is specific to one MAX-CUT relaxation, continuation solver, training distribution, and evaluation suite.A preliminary knapsack extension shares the coupling asymmetry but not the same out-of-distribution quality separation.Source: §4 · p. 7

5. Conclusion

The paper finds that out-of-distribution behavior depends on how a learned continuation schedule incorporates solver state. It studies this in a classical penalty relaxation of MAX-CUT, where the schedule controls stagewise step sizes and penalties.

5. Conclusion

  • The bilinear schedule improves significantly over its frozen baseline out of distribution, while the capacity-matched additive ablation degrades substantially.The conclusion identifies the form of state coupling, rather than state adaptivity alone, as the architectural distinction associated with this separation.Source: §5 · p. 7

A.1. MAX-CUT relaxation

  • The moment matrix is constructed as a sum of weighted rank-one outer products, making it positive semidefinite without imposing a semidefinite constraint during optimization.The general construction uses atom locations, nonnegative weights, and Chebyshev-basis vectors; MAX-CUT uses its R=1 case.Source: §A.1 · pp. 9–10, Figure 3 · p. 10
  • The particle parameterization is motivated by a contrast between a rugged original objective with many local minima and a smoother moment-space landscape suited to gradient-based search.The landscape illustration is not a MAX-CUT objective.Source: §A.1 · pp. 10–11
  • MAX-CUT uses the rank-one (R=1) special case: each node has one spin variable, and the learned schedule controls its stagewise step size and penalty.The general moment construction is included for context; the paper's claims do not rely on R > 1.Source: §A.1 · p. 10

A.2. Continuation solver

  • Gradually increasing the penalty balances improving the relaxed cut against making spins discrete; rising too quickly risks premature commitment, while rising too slowly can leave spins fractional.The step size likewise balances slow convergence against unstable updates.Source: §A.2 · p. 11

A.3. Context representation

  • The context summarizes soft-cut quality, binary violation, relative penalty progress, and stage progress in a representation whose dimension is independent of graph size.The current absolute penalty also enters state-adaptive schedules as log ρk, while ρk/ρ0 represents relative progress.Source: §A.3 · p. 12

A.4.1. State-blind schedule

  • The state-blind schedule learns a separate step size and penalty increment for each stage but cannot respond to the graph or current optimization trajectory.Its schedule can vary with continuation stage.Source: §A.4.1 · p. 12

A.4.2. Factored bilinear schedule

  • The factored bilinear schedule combines projected context features with a penalty branch through elementwise multiplication before output heads produce step size and penalty increment.Its factor width is r = 8 in all experiments, and its parameter count is independent of graph size.Source: §A.4.2 · p. 12

A.4.3. Additive ablation

The additive ablation retains the bilinear schedule's inputs and output heads but changes how context and penalty interact. This comparison tests whether the form of state conditioning matters, beyond state access alone.

A.4.3. Additive ablation

  • The additive and bilinear schedules use the same context, recurrent penalty state, factor width, and output heads; only the interaction between context and penalty changes.The additive model replaces multiplicative factorization with an additive layer.Source: §A.4.3 · pp. 12–13
  • At r = 8, the additive model has 67 parameters versus 59 for the bilinear model, because it includes r hidden biases.The additive model therefore has slightly more, rather than fewer, parameters.Source: §A.4.3 · p. 13
  • Comparing the two state-adaptive schedules tests whether the form of conditioning matters when state, output parameterization, training procedure, and approximate capacity are held fixed.Source: §A.4.3 · p. 13

A.5. Unrolled training

The schedule is trained by differentiating through the complete continuation solve, with gradient descent updating relaxed spins and an outer optimizer learning schedule parameters. This lets training evaluate schedule decisions through their effects on the later trajectory and final cut.

A.5. Unrolled training

  • A schedule decision at an early stage changes the next stage's iterate and context, affecting subsequent schedule decisions and the full trajectory.The training batch uses freshly sampled graphs, preventing reliance on a fixed collection of instances.Source: §A.5 · p. 13
  • Training averages the objective across eight independent rank-one spin trajectories per graph, while evaluation discretizes all replicas and reports the best cut.Source: §A.5 · p. 13

A.6. Nested optimization and gradient flow

  • The inner loop applies plain gradient descent to the penalized MAX-CUT relaxation, with step size and penalty fixed within each stage; no inner-loop parameters are learned.The solve uses K = 7 stages and T = 15 updates per stage.Source: §A.6 · pp. 13–14
  • The outer optimization learns the schedule parameters that determine the inner solver's sequence of penalties and step sizes, minimizing the final-iterate loss.Minimizing that loss corresponds to maximizing the final cut value achieved by the schedule.Source: §A.6 · p. 14
  • Backpropagation traverses the complete unrolled solve of KT = 105 gradient-descent updates to produce gradients for all schedule parameters.The outer Adam optimizer updates the schedule parameters based on final cuts averaged over the training distribution.Source: §A.6 · p. 14

A.7. Training hyperparameters and stability

The bilinear schedule improves over its frozen baseline out of distribution, whereas the additive schedule degrades; this pattern is reported without weight decay and across the regularization sweep. The schedule controls how far the solver moves within stages and how quickly the penalty shifts it toward discrete spins.

A.7. Training hyperparameters and stability

  • A step-size clamp prevents extremely large inner updates and steps that collapse toward zero, while gradient-norm clipping limits abrupt schedule-parameter changes.Source: §A.7 · p. 15

A.8. Regularization sweep

  • The regularization comparison uses decoupled weight decay across 15 independent seeds for every architecture and weight-decay setting.The sweep tests robustness of the architectural comparison rather than selecting a separate architecture for each evaluation regime.Source: §A.8 · p. 15

A.9. How the schedule affects MAX-CUT performance

  • The schedule affects MAX-CUT performance through the fixed solver by controlling within-stage movement and the pace of the shift from relaxed cut optimization to discrete spins.Source: §A.9 · p. 15
  • The additive schedule combines soft-cut value, binary violation, stage, and penalty through an affine layer; the bilinear schedule lets penalty scale modulate projected context features multiplicatively.Source: §A.9 · p. 15
  • Out of distribution, the state-blind and bilinear schedules improve relative to their own frozen baselines, while the additive schedule degrades substantially; in distribution, bilinear and additive are statistically indistinguishable.The opposing out-of-distribution trends are reported without weight decay and remain unchanged across the regularization sweep.Source: §A.9 · pp. 15–16

Appendix B. Additional In-Distribution Results

Held-out training-size graphs show little separation among the learned schedules, while the out-of-distribution Biq Mac evaluation separates the additive model from the state-blind and bilinear schedules. A single fixed hard instance slightly favors the additive schedule, so that result and the broader suite provide complementary measurements.

Held-out random instances

  • On held-out training-distribution graphs, trained schedules score 19.35–19.47 versus frozen-baseline scores of 18.72–19.34, with trained-model differences within run-to-run variation.The evaluation covers held-out Erdős–Rényi G(n, 0.5) graphs with n ∈ {6, …, 15} across 15 seeds.Source: Appendix B · p. 16

Fixed hard instance

  • The fixed hard-instance result slightly favors the additive model, unlike the pooled Biq Mac evaluation, and the two evaluations are reported as complementary measurements.Performance on either evaluation need not predict performance on the other.Source: Appendix B · p. 16

Out-of-distribution comparison

  • On the Biq Mac evaluation, the state-blind and bilinear schedules improve over their frozen baselines (Δ = +0.0161 and +0.0084), while the additive schedule degrades (Δ = −0.0522, paired t = −11.7).The separation appears under distribution shift, not on held-out graphs from the training distribution.Source: Appendix B · pp. 16–17, Figure 5 · p. 17

Appendix C. Fixed-Schedule Search and Weight-Decay Sweep

The robustness checks compare learned schedules with a stronger fixed reference and test whether weight decay changes the bilinear–additive separation. The bilinear schedule matches the tuned reference, and the reported controls support the separation across tested regularization strengths, while the evidence remains specific to the studied setting.

Appendix C. Fixed-Schedule Search and Weight-Decay Sweep

  • Across the tested regularization strengths, the bilinear–additive separation remains significant; all 10 learned-versus-frozen comparisons across 15 seeds are significant, and between-architecture Welch statistics are at least 11.6.The sweep includes the unregularized condition reported in Table 1.Source: Appendix C · p. 17
  • The reported tests establish reliability of the observed differences, but do not establish their mechanism or generality; the evidence is specific to the studied architectures, training distribution, and solver.The authors leave open when and why the state-coupling choice improves transfer.Source: Appendix C · p. 18

C.1. Tuned Fixed-Schedule Reference

  • The tuned fixed schedule obtains a mean Biq Mac ratio of 0.9624 ± 0.0024, exceeding the learned state-blind (0.9420 ± 0.0053) and additive (0.9023 ± 0.0166) results; the unregularized bilinear result, 0.9627 ± 0.0078, is statistically indistinguishable from it.The tuned reference is selected by grid search using only training-distribution instances.Source: §C.1 · p. 18
  • The frozen state-blind initialization ranks 98th among 150 grid points and obtains a Biq Mac ratio of 0.9259, supporting the conclusion that this baseline is untuned.The grid-searched schedule provides a substantially stronger fixed reference.Source: §C.1 · p. 18

C.2. Weight-Decay Protocol

  • The weight-decay check retrains both state-adaptive architectures from scratch with 15 seeds at each of four nonzero strengths spanning a 30-round range, alongside the unregularized reference.The same regularization protocol is applied to learned parameters in both architectures; frozen schedules do not change with weight decay.Source: Appendix C · p. 17, §C.2 · p. 19

C.3. Statistical Tests

The section distinguishes training effects against each architecture’s own baseline from differences between architectures, using paired and Welch t-tests. These tests support opposite within-architecture effects and a between-architecture difference, but do not compare absolute learned scores.

Paired t-test within an architecture

  • Paired t-tests compare each learned schedule with its own frozen baseline under matched seeds, instances, and initial conditions.The seedwise change is summarized over 15 seeds; positive and negative changes indicate improvement and degradation, respectively.Source: §C.3 · pp. 20–21

Between-architecture comparison

  • Welch’s two-sample test compares the architectures’ seedwise training effects without assuming equal variances; its statistic is 12.3 at zero weight decay and 11.6–23.5 at other tested values.A positive statistic indicates a more favorable training change for the bilinear architecture.Source: §C.3 · p. 21

Interpretation of the two tests

  • The paired statistics show bilinear improvement and additive degradation relative to their own baselines, while neither test compares the models’ absolute learned scores.Absolute learned scores are reported separately in Table 1.Source: §C.3 · p. 21

Multiplicity and the unit of replication

  • Inference summarizes variation across training seeds conditional on the fixed 80-instance suite, not sampling uncertainty over problem instances.The 10 paired tests are reported without a stated multiplicity correction; the cited Bonferroni calculation leaves their significance intact.Source: §C.3 · pp. 21–22
  • Every paired statistic remains significant under a Bonferroni threshold of 0.005 for 10 tests; the smallest reported absolute statistic is 4.1.The correction does not address uncertainty over problem instances.Source: §C.3 · pp. 21–22

C.4. Weight-Decay Results

The weight-decay sweep preserves the opposing out-of-distribution training effects of bilinear and additive schedules, while fixed-instance and knapsack checks qualify the interpretation. The evidence is limited to the tested MAX-CUT setting, and the coupling mechanism remains unresolved.

C.4. Weight-Decay Results

  • At zero weight decay, bilinear training improves over its baseline (t = 4.1), while additive training degrades (t = −11.7); the opposite signs persist across all five tested values.At zero weight decay, the additive change is −0.0522; bilinear improvement and additive degradation are both present throughout the sweep.Source: §C.4 · p. 22

C.5. Relationship to the Fixed Hard Instance

  • On the fixed n = 15 instance, the additive schedule reaches the optimum in 13–15 of 15 runs versus 12–13 for bilinear, unlike their opposing average effects across the 80 larger graphs.The text attributes the difference to the fixed graph and pooled suite measuring different aspects of solver behavior.Source: §C.5 · pp. 22–23
  • The additive model matches bilinear performance on held-out training-size graphs and reaches the fixed-instance optimum at least as often, so the reported separation is associated with coupling form rather than inability to optimize the training problem.The mechanism behind the different out-of-distribution behavior remains an open question.Source: §C.5 · p. 23

C.6. Untested Generalization Axes and a Cross-Problem Check

  • The evaluation covers one MAX-CUT relaxation, continuation solver, training distribution, and suite, leaving other graph structures, scales beyond n = 100, solvers, and competing MAX-CUT methods untested.The training distribution is Erdős–Rényi G(n, 0.5).Source: §C.6 · p. 23
  • The preliminary knapsack check shares the bilinear/additive coupling asymmetry but finds no out-of-distribution quality separation, so that structural asymmetry alone does not predict the MAX-CUT result.The knapsack study is separate, preliminary, and reported only in summary.Source: §C.6 · p. 23

Related papers

Loading 2610.32801v1…