Bundle Network: a Machine Learning-Based Bundle Method

2025/09/29 by Demelas, Francesca, Roux, Joseph Le, Frangioni, Antonio +3
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2509.24736

Abstract

This paper presents Bundle Network, a learning-based algorithm inspired by the Bundle Method for convex non-smooth minimization problems. Unlike classical approaches that rely on heuristic tuning of a regularization parameter, our method automatically learns to adjust it from data. Furthermore, we replace the iterative resolution of the optimization problem that provides the search direction-traditionally computed as a convex combination of gradients at visited points-with a recurrent neural model equipped with an attention mechanism. By leveraging the unrolled graph of computation, our Bundle Network can be trained end-to-end via automatic differentiation. Experiments on Lagrangian dual relaxations of the Multi-Commodity Network Design and Generalized Assignment problems demonstrate that our approach consistently outperforms traditional methods relying on grid search for parameter tuning, while generalizing effectively across datasets.

Citations

• Towards Sample-Efficiency and Generalization of Transfer and Inverse Reinforcement Learning: A Comprehensive Literature Review
• Towards Constituting Mathematical Structures for Learning to Optimize
• The Curse of Unrolling: Rate of Differentiating Through Optimization
• A Stochastic Bundle Method for Interpolating Networks
• Learning to Optimize: A Primer and A Benchmark
• Reinforcement Learning for Combinatorial Optimization: A Survey
• Reinforcement learning for combinatorial optimization: A survey
• Reinforcement Learning for Integer Programming: Learning to Cut
• Machine Learning for Combinatorial Optimization: a Methodological Tour\n d'Horizon
• Machine learning for combinatorial optimization: A methodological tour d’horizon
• Attention Is All You Need
• Learning to learn by gradient descent by gradient descent
• Learning to Optimize
• From Softmax to Sparsemax: A Sparse Model of Attention and Multi-Label Classification
• Gradient Estimation Using Stochastic Computation Graphs
• Automatic differentiation in machine learning: a survey
• Adam: A Method for Stochastic Optimization
• Empirical Evaluation of Gated Recurrent Neural Networks on Sequence Modeling
• Neural Machine Translation by Jointly Learning to Align and Translate
• Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation
• Long Short-Term Memory
• A Stochastic Approximation Method

Related

• Non-convex Optimization for Machine Learning
• Algorithms for solving optimization problems arising from deep neural net models: smooth problems
• Optimization Over Trained Neural Networks: Taking a Relaxing Walk
• Non-Convex Optimizations for Machine Learning with Theoretical Guarantee: Robust Matrix Completion and Neural Network Learning
• Algorithms for solving optimization problems arising from deep neural net models: nonsmooth problems