State coupling method affects learned solver schedule transfer performance
Multiplicative vs. Additive State Coupling in Learned Optimizer Schedules
Machine LearningArtificial IntelligenceComputation and Language
Summary
The paper looks at ways to teach a computer how to solve a problem called MAX-CUT more efficiently by learning schedules that guide a solver. The authors compare two methods for including the solver's internal state in these learned schedules: one that multiplies inputs (bilinear) and one that adds them (additive). They find the multiplying method helps the schedule work well even on bigger problems it wasn't trained on, while the adding method does not. This shows that the way solver state is incorporated is key to making schedules transfer better to new situations.
What this means in practice
- •For optimization software developers: Design solver control schedules using bilinear state coupling to improve performance on larger problem instances unseen during training.
- •For machine learning engineers: Incorporate bilinear state-dependent mechanisms in learned optimization routines to enhance generalization beyond training problem sizes.
Authors
M. Harper Langston, Pierre-David Letourneau, Dalton Jones, Roland Memisevic, Peter Scott, Mingu Lee, Richard A. Lethin, Christopher Lott, Fatih Porikli, Harris Teague
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.