Complexity Bounds and Approaches to Learning Projected Gradient Descent Solver Iterates

• URL: http://arxiv.org/abs/2607.22467v1
• Date: Fri, 24 Jul 2026 16:31:30 GMT
• Title: Complexity Bounds and Approaches to Learning Projected Gradient Descent Solver Iterates
• Abstract summary: We study a $k$-neighborhood data collection strategy that augments datasets of converged solutions with intermediate solver iterates.<n>We propose a more capable DDDAS paradigm by improving the efficiency of the data-model-optimization loop.<n>We finish by discussing two views of learning solver-iterate data and connect our analysis with GLENS, a new data-efficient global search method.
• Score: 0.3093890460224435
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• GLENS: Global Search via Learning from Solver Iterates with Diffusion Models [1.7495196015896808]
  We consider the problem of generating a large collection of initial guesses for local minima non- continuous optimization problems.<n>We propose GLENS, a data-efficient global search method that leverages intermediate solvers as data.
  arXiv  Detail & Related papers  (2026-05-29T21:09:56Z)
• Optimal Data Acquisition for Reinforcement Learning: A Large Deviations Perspective [5.848643785361479]
  We introduce the exponential decay rate of the policy-selection error probability as a principled efficiency metric.<n>We formalize two complementary notions of optimality in terms of the optimal solution of the nested problem.<n>We prove that the resulting reinforcement learning algorithm is near-robustly optimal under our optimality criterion, up to a constant factor.
  arXiv  Detail & Related papers  (2026-05-27T16:08:56Z)
• Parallel Diffusion Solver via Residual Dirichlet Policy Optimization [88.7827307535107]
  Diffusion models (DMs) have achieved state-of-the-art generative performance but suffer from high sampling latency due to their sequential denoising nature.<n>Existing solver-based acceleration methods often face significant image quality degradation under a low-dimensional budget.<n>We propose the Ensemble Parallel Direction solver (dubbed as EPD-EPr), a novel ODE solver that mitigates these errors by incorporating multiple gradient parallel evaluations in each step.
  arXiv  Detail & Related papers  (2025-12-28T05:48:55Z)
• Learning to Pose Problems: Reasoning-Driven and Solver-Adaptive Data Synthesis for Large Reasoning Models [54.29243291958429]
  We develop a problem generator that reasons explicitly to plan problem directions before synthesis.<n>We treat the solver's feedback on synthetic problems as a reward signal, enabling the generator to calibrate difficulty.<n>Our method achieves an average improvement of 2.5% and generalizes to both language and vision-language models.
  arXiv  Detail & Related papers  (2025-11-13T03:08:51Z)
• Exact and Heuristic Algorithms for Constrained Biclustering [0.0]
  Biclustering, also known as co-clustering or two-way clustering, simultaneously partitions the rows and columns of a data matrix to reveal submatrices with coherent patterns.<n>We study constrained biclustering with pairwise constraints, namely must-link and cannot-link constraints, which specify whether objects should belong to the same or different biclusters.
  arXiv  Detail & Related papers  (2025-08-07T15:29:22Z)
• iTool: Reinforced Fine-Tuning with Dynamic Deficiency Calibration for Advanced Tool Use [56.31110409360567]
  Augmenting large language models with external tools is a promising approach to enhance their capabilities.<n>We show that training gains significantly decay as synthetic data increases.<n>We propose an iterative reinforced fine-tuning strategy designed to alleviate this limitation.
  arXiv  Detail & Related papers  (2025-01-15T04:52:34Z)
• Constructing Gaussian Processes via Samplets [0.0]
  We examine recent convergence results to identify models with optimal convergence rates. We propose a Samplet-based approach to efficiently construct and train the Gaussian Processes.
  arXiv  Detail & Related papers  (2024-11-11T18:01:03Z)
• Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling [0.0]
  This study proposes a different approach that integrates gradient-based update through continuous relaxation, combined with Quasi-Quantum Annealing (QQA) Numerical experiments demonstrate that our method is a competitive general-purpose solver, achieving performance comparable to iSCO and learning-based solvers.
  arXiv  Detail & Related papers  (2024-09-02T12:55:27Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods. Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
  arXiv  Detail & Related papers  (2023-10-08T23:39:38Z)
• DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems [41.57773395100222]
  Deep reinforcement learning (DRL) models have shown promising results in solving NP-hard Combinatorial Optimization problems. This paper addresses the scalability challenge in large-scale optimization by proposing a novel approach, namely, DIMES. Unlike previous DRL methods which suffer from costly autoregressive decoding or iterative refinements of discrete solutions, DIMES introduces a compact continuous space for parameterizing the underlying distribution of candidate solutions. Extensive experiments show that DIMES outperforms recent DRL-based methods on large benchmark datasets for Traveling Salesman Problems and Maximal Independent Set problems.
  arXiv  Detail & Related papers  (2022-10-08T23:24:37Z)
• Neural Improvement Heuristics for Graph Combinatorial Optimization Problems [49.85111302670361]
  We introduce a novel Neural Improvement (NI) model capable of handling graph-based problems where information is encoded in the nodes, edges, or both. The presented model serves as a fundamental component for hill-climbing-based algorithms that guide the selection of neighborhood operations for each.
  arXiv  Detail & Related papers  (2022-06-01T10:35:29Z)
• A deep learning method for solving stochastic optimal control problems driven by fully-coupled FBSDEs [1.0703175070560689]
  We first transform the problem into a Stackelberg differential game problem (leader-follower problem) We compute two examples of the investment-consumption problem solved through utility models. The results of both examples demonstrate the effectiveness of our proposed algorithm.
  arXiv  Detail & Related papers  (2022-04-12T13:31:19Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)
• Semi-Supervised Learning with Meta-Gradient [123.26748223837802]
  We propose a simple yet effective meta-learning algorithm in semi-supervised learning. We find that the proposed algorithm performs favorably against state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-07-08T08:48:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.