Complexity Bounds and Approaches to Learning Projected Gradient Descent Solver Iterates
2026-07-24 • Machine Learning
Machine Learning
AI summaryⓘ
The authors address the problem of limited data when training models to guess solutions for optimization tasks, which are usually slow to solve. They propose a method that collects not only final solutions but also intermediate steps from the solver to increase training data without extra computation. They analyze this method's effectiveness using a mathematical tool called Rademacher complexity on a specific optimization problem solved by projected gradient descent. Their approach aims to make the data-model-optimization cycle more efficient and connects their findings to a new search method called GLENS.
generative modelsparametric optimizationprojected gradient descentRademacher complexitybox-constrained quadratic programssolver iteratesdata augmentationgeneralization boundDDDDASGLENS
Authors
Anjian Li, Ryne Beeson
Abstract
Data scarcity poses a fundamental challenge in training generative models to produce initial guesses for parametric optimization problems that are otherwise numerically expensive to solve. We therefore study a $k$-neighborhood data collection strategy that augments datasets of converged solutions with intermediate solver iterates, increasing the amount of training data without additional solver runs. To understand the benefits of this approach, we derive a generalization bound based on Rademacher complexity that reveals the role of the $k$-neighborhoods and related parameters. To achieve this result, we focus on one-sided box-constrained quadratic programs solved by projected gradient descent. We illustrate the behavior of this solver on two examples. The approach proposed in this paper enables a more capable DDDAS paradigm by improving the efficiency of the data-model-optimization loop. We finish by discussing two views of learning solver-iterate data and connect our analysis with GLENS, a new data-efficient global search method.