Complexity Bounds and Approaches to Learning Projected Gradient Descent Solver Iterates

Anjian Li; Ryne Beeson

REVIEW 2 major objections 4 minor 13 references

Complexity Bounds and Approaches to Learning Projected Gradient Descent Solver Iterates

T0 review · 2 major / 4 minor · reviewed 2026-08-01 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read For box-constrained QPs solved by projected gradient descent, the paper proves a Rademacher bound showing how the solver's contraction rate, the discount factor, and the retained-neighborhood radius control the generalization gap when train

desk verdict Nice new bound for a useful data-augmentation idea, but Theorem 3's proof has a squared-loss misstep that needs a constant fix. read the letter →

arxiv 2607.22467 v1 pith:VRJK7Z6L submitted 2026-07-24 cs.LG

Anjian Li , Ryne Beeson This is my paper · ORCID

classification cs.LG MSC 68Q3290C2068T07

keywords k-neighborhoodRademachercomplexitygeneralizationboundprojectedgradientdescentsolveriteratesdiffusionmodelsbox-constrainedquadraticprogramsgenerativelearning

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Generative models that propose initial guesses for parametric optimization problems are data-hungry: collecting enough converged solutions requires many expensive solver runs. This paper's central claim is that the intermediate iterates those runs already produce — normally thrown away — can be retained as extra training data, and that for one-sided box-constrained quadratic programs the benefit is analyzable. It proves that projected gradient descent contracts toward the optimum with factor rho = (lambda_max - lambda_min)/(lambda_max + lambda_min), then uses Rademacher complexity to bound the generalization gap of a two-layer noise-prediction network trained on 'k-neighborhood paths' (the final converged solution plus the preceding k iterates). The bound, Theorem 3, makes explicit how the number of solver runs N, the discount gamma, the contraction factor rho, and the neighborhood radius r_k enter: the gap decays as O(N^{-1/2}) with a coefficient that is the discounted average of radii R0 + rho^{k-j} r_k. If correct, this turns a data-augmentation trick into a quantitative design rule for data-collection strategies in learned optimization.

What carries the argument

The load-bearing objects are the k-neighborhood (the set of initial points whose iterates meet the convergence tolerance within k steps), its radius r_k(theta), and the contraction factor rho = (lambda_max - lambda_min)/(lambda_max + lambda_min) of projected gradient descent. Training is organized into k-neighborhood paths: ordered tuples of the final converged solution and the preceding k iterates for each solver run. The analysis uses the discounted path loss J_i(phi) = (1/(k+1)) sum_{j=0}^k gamma^j loss(iterate_j), which lets the bound express the cost of earlier, more distant iterates through gamma^j and rho^{k-j} r_k. The generalization argument is carried by the empirical Rademacher co

What would settle it

Compute the generalization gap empirically for a box-constrained QP whose solver-iterate paths are trained with standard Gaussian diffusion noise; because P(||epsilon||_2 > sqrt(d)) > 0 for every finite d, the theorem's condition is violated, so a gap that reliably exceeds the Theorem 3 bound would confirm the bounded-noise premise is load-bearing. A cleaner test: truncate the noise to the sqrt(d) ball, train the two-layer class G, and check whether the measured worst-case gap respects the bound.

Watch

Extended reading notes

Core claim

The core discovery is Theorem 3. For the family of one-sided box-constrained quadratic programs, projected gradient descent satisfies the contraction inequality ||T(x) - x*|| <= rho ||x - x*|| with rho = (lambda_max - lambda_min)/(lambda_max + lambda_min) < 1. Consequently, if the last k+1 iterates of a run are collected into a k-neighborhood path, the j-th-from-final iterate lies within distance rho^{k-j} r_k of the optimum. The paper then shows that, for a two-layer neural network class with bounded weights and activations, the empirical Rademacher complexity of the discounted path-loss class is at most sqrt(12) A L1 W sqrt(d) / sqrt(N) times the average over j of gamma^j (R0 + rho^{k-j} r

Load-bearing premise

The theorem assumes the diffusion noise vectors satisfy ||epsilon||_2 <= sqrt(d) almost surely; the denoising diffusion probabilistic model uses Gaussian noise with unbounded norm, so the loss class is unbounded and the stated bound does not apply to the actual training distribution.

Editorial extensions

If this is right

If Theorem 3 holds, the train-to-test gap for learning PGD solver iterates decays as O(N^{-1/2}) in the number of independent solver runs, even though each path contains correlated points; k-neighborhoods increase the data per run but do not change this rate.
The bound isolates a concrete tradeoff: increasing k adds more terms to the discounted average, but the weight gamma^j and the contraction factor rho decide how much those earlier, more spread-out iterates contribute, so with rho near 1, early iterates are expensive to include.
Setting gamma < 1 yields a smaller Rademacher term than gamma = 1, so downweighting older iterates is provably beneficial within this class of discounted path losses.
The contraction result itself is a contribution: for one-sided box-constrained QPs, PGD's per-step error contraction is exactly rho, independent of whether the optimum lies in the interior or on an active upper bound.
Because the neighborhood radius r_k is defined through the convergence tolerance, tightening the tolerance shrinks r_k and therefore tightens the generalization bound, giving a principled trade between solver accuracy and sample complexity.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

An immediate practical rule follows from the bound: stop retaining earlier iterates once rho^{k-j} r_k falls near the noise floor of the diffusion model, because further points only enlarge the average radius while the 1/sqrt(N) term stays fixed.
The proof only uses nonexpansiveness of projection and strong convexity, so the same machinery likely extends to other linearly convergent projection or proximal methods; if that extension holds, k-neighborhoods become a general template for augmenting solver data.
The i.i.d. path assumption is the main gap between theory and practice: real parametric families draw correlated instances, and accounting for that correlation could plausibly yield faster rates than N^{-1/2}, but the paper does not address it.
The bounded-noise assumption is violated by standard diffusion training; a truncation argument that conditions on the Gaussian noise landing in the sqrt(d) ball would turn the bound into a high-probability statement for the actual training distribution, at the cost of an extra confidence term.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Two things to know. The paper gives the first formal generalization bound for a genuinely practical trick—training generative models on the last k+1 PGD iterates from each solver run instead of just the converged solution—and the bound, if correct, cleanly explains how the contraction factor and the neighborhood radius trade off. But the central theorem as written isn't derived: the proof conflates the squared DDPM loss with its unsquared norm, which leaves Eq. (15) and (19) missing a factor of order A+√d. That's load-bearing but repairable.

What's new: the k-neighborhood definition and the Rademacher bound with discount, contraction, and radius terms. This is a legitimate extension of standard generalization theory, and it reduces to the usual bound when k=0. The contraction theorem itself is textbook, but using it inside the Rademacher analysis is a fresh application. The vector-contraction inequality is applied correctly apart from the Lipschitz constant issue.

The main issue is in Section 4. The loss is ℓ(s)=||g_φ(z)−ε||². The proof sets B_l = A+√d, which bounds the norm, not the square. The correct bound is (A+√d)², and the map y↦||y−ε_i||² is 2(A+√d)-Lipschitz on the ball, not 1-Lipschitz. So the empirical Rademacher bound in Eq. (15), and hence the key bound in Eq. (19), is missing that factor. This is an internal correctness problem, at least as important as the bounded-noise caveat.

The bounded-noise assumption is genuinely limiting: DDPM uses unbounded Gaussian noise, and the paper explicitly defers that to future work. That's honest but means the main theorem doesn't cover the actual training distribution. There are no experiments beyond two illustrative PGD trajectories, which is fine for a theory paper but limits significance.

Credit: the paper is self-contained, doesn't fit parameters to data, and the contraction proof is correct. The self-citation to GLENS is for motivation only and doesn't make the bound circular. The k-neighborhood bound itself is not in the cited literature.

Bottom line: a solid theoretical core with a fixable constant error. I'd send it to peer review—a serious referee would catch the squared-loss issue quickly—but the authors need to correct B_l and the Lipschitz factor before it's citable.

Referee Report

2 major / 4 minor

Summary. The paper studies a data augmentation strategy for training generative models to produce initial guesses for parametric optimization: instead of keeping only converged solutions from projected gradient descent (PGD) runs, it retains the last k+1 iterates ('k-neighborhood paths'). For one-sided box-constrained quadratic programs, the paper proves a contraction property for PGD and derives a Rademacher-complexity generalization bound for a two-layer neural-network noise predictor in a DDPM-style loss. The bound is meant to quantify how the number of solver runs N, the contraction factor ρ, the neighborhood radius r_k, and the discount γ affect generalization. The paper also illustrates PGD trajectories for interior and active-constraint optima and discusses connections to the authors' GLENS method.

Significance. If the bound were correct as stated, it would provide a useful theoretical account of why solver-iterate data can help generative modeling for optimization: the bound explicitly shows how early-iterate radius, contraction, and discounting enter the sample complexity. The contraction proof (Theorem 1) is elementary and correct, and the overall idea of decomposing the path loss by iterate index is conceptually valuable. The paper is also transparent about several limitations, including the bounded-noise assumption and the need for tighter NN bounds. However, the central generalization bound contains a load-bearing norm-versus-squared-loss error, so the main theorem as written is not established.

major comments (2)

[Section 4, Eq. (15) and Theorem 3 (Eqs. (18)-(19))] The loss in Eq. (2) is ||g_phi(z)-epsilon||^2. The text states B_l = A + sqrt(d) after bounding ||g_phi(z)|| <= A and ||epsilon|| <= sqrt(d). This is a bound on the norm, not on the squared norm; the correct almost-sure bound is B_l = (A+sqrt(d))^2. The same issue appears in the vector-contraction step: the map y -> ||y-epsilon_i|| is 1-Lipschitz, but the function entering the loss class is y -> ||y-epsilon_i||^2, which on { ||y|| <= A } is 2(A+sqrt(d))-Lipschitz. Consequently Eq. (15) and its path version Eq. (19) are missing a multiplicative factor proportional to A+sqrt(d), and the confidence term in Eq. (18) should use the squared bound. As written, Theorem 3 does not follow from the proof. This is fixable by carrying the Lipschitz constant and squared bound through the derivation, but it is load-bearing for the paper's central claim.
[Section 4, first paragraph after Eq. (14)] The theorem assumes ||epsilon||_2 <= sqrt(d) almost surely. This is incompatible with the DDPM loss in Eq. (2), where epsilon ~ N(0, I_d) is Gaussian and therefore unbounded. The stated bound thus does not apply to the actual training distribution of the diffusion model described in Section 2. The paper acknowledges this only in the final sentence of the conclusion ('extend the analysis to unbounded Gaussian diffusion noise'). This restriction should be stated prominently when the bound is advertised as applying to diffusion models, or the theorem should be extended to unbounded noise. As it stands, the practical scope of the central result is narrower than the presentation suggests.

minor comments (4)

[Section 4, Eq. (15)] The derivation of Eq. (15) is very compressed: it invokes 'scalar contraction, the Efron-Stein inequality, and Jensen's inequality' without giving the intermediate steps or the source of the constant sqrt(12). Adding a short appendix or a fuller derivation would help verify the constants.
[Definition 1] The term 'k-neighborhood' may be misleading: membership in N^k_Ttheta is defined by the residual condition ||T^{k-1}(x)-T^k(x)|| <= tol, not by distance to the optimum. The later use of r_k(theta) as a radius clarifies the intent, but the initial definition could be phrased more directly as the set of points that meet the convergence criterion after k steps.
[Introduction and Abstract] The acronyms DDDAS and 'InfoSymbiotic Systems' appear without definition in the abstract; a reader outside the DDDAS community will not know what they refer to. Define them at first use or relegate them to the body.
[Section 6] Reference [10] (GLENS) is described as 'our work' and as 'a new data-efficient global search method.' Since GLENS is not described or evaluated in this manuscript, the connection is programmatic rather than substantive. Consider framing this as future/related work rather than as a contribution of the present paper.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the generalization bound follows from external Rademacher/vector-contraction results and the paper's own explicit PGD contraction proof; GLENS self-citations are motivational only.

full rationale

Walked the claimed derivation chain. Theorem 3 (Eqs. 18-19) is obtained by: (i) applying Theorem 2, which is quoted as [13, Mohri et al.], a standard external result with no fitted constants; (ii) bounding the empirical Rademacher complexity of the NN class via Eq. (15), which applies Maurer's vector-contraction inequality [11] and the paper's explicit weight/activation bounds; and (iii) substituting the input radius bound R_{z,j} <= R0 + rho^{k-j} r_k from Eq. (17), which itself follows from the paper's proven contraction estimate Eq. (11) and Definition 1. The radius r_k, contraction rho, discount gamma, and number of runs N all appear as assumed inputs; none is fitted to data or renamed as a prediction. No parameter is tuned to a subset of data and then 'predicted' on a closely related quantity. The only author-overlapping citations (GLENS [10], DiffuSolve [7], etc.) are used for motivation and related work: Section 6 says the Rademacher bound 'provides a theoretical foundation for GLENS', not that the bound relies on GLENS. Thus there is no load-bearing self-citation and no imported uniqueness/ansatz. The bound does assume bounded diffusion noise (Section 4), and the conclusion defers unbounded Gaussian noise to future work; that is a stated limitation. There is also an apparent proof-level issue that the squared loss is treated as if it were the norm loss (B_l = A + sqrt(d) rather than (A+sqrt(d))^2; the map y -> ||y-epsilon||^2 is not 1-Lipschitz on the ball), but this is an internal correctness/soundness concern, not a circularity. Overall, the derivation chain does not reduce to its own inputs; score 0.

Assumptions & free parameters 0 free parameters · 8 assumptions · 0 invented entities

No fitted parameters; the central bound rests on standard learning-theory tools plus domain assumptions (positive-definite Q, bounded diffusion noise, i.i.d. paths, finite radius) and an ad hoc discounted path loss.

assumptions (8)

domain assumption Q is positive definite with 0 < lambda_min <= lambda_max
Section 3 states lambda_max >= lambda_min > 0; needed for rho<1 and a unique minimizer in the one-sided box problem.
domain assumption Diffusion noise is bounded: ||epsilon||_2 <= sqrt(d) almost surely
Section 4; needed for bounded loss B_l and Theorem 2. Standard Gaussian noise violates this; authors defer extension.
domain assumption The k-neighborhood paths collected in training are i.i.d.
Theorem 3: 'Let the k-neighborhood paths collected in training be i.i.d.'; needed to apply the standard Rademacher bound.
domain assumption r_k(theta) is finite
Definition 1, Eq. (5) 'assumed to be finite'; the bound scales with r_k.
domain assumption NN class bounded: sum ||a_s||<=A, ||w_s||<=W, activation psi in [0,1], L-Lipschitz
Eq. (3); needed for ||g_phi||<=A and the Rademacher bound.
standard math PGD contraction with factor rho
Theorem 1 proved from non-expansiveness of projection and eigenvalue bound; standard for strongly convex quadratics.
standard math Rademacher, vector-contraction, and Efron-Stein bounds
Theorems 2 and Eq. (15) cite [13] and [11]; used as external tools.
ad hoc to paper Discounted path loss J_i is the training objective
Eq. (16) introduces gamma-discounted average loss; the paper does not show this matches any implemented training procedure.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Complexity Bounds and Approaches to Learning Projected Gradient Descent Solver Iterates." pith.science (2026). https://pith.science/paper/VRJK7Z6L

@misc{pith2026260722467,
  author       = {Pith},
  title        = {Pith review of: Complexity Bounds and Approaches to Learning Projected Gradient Descent Solver Iterates},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VRJK7Z6L}},
  note         = {Machine review of arXiv:2607.22467}
}

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.

Figures

Figures reproduced from arXiv: 2607.22467 by the authors.

**Figure 1.** PGD solver iterates for the same QP objective and initial guess under two upper box constraints. The markers show the solver iterates, the dashed lines indicate the upper bounds, and the shaded region is infeasible. The inset in (b) shows the refinement along the active boundary near the optimum. 6 Discussion on Learning from Solver Iterates Training data augmented with intermediate solver iterates can reduce the da… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 1 canonical work pages

[1]

Foun- dations and Trends in Machine Learning16(4), 494–591 (2023)

Angelopoulos, A.N., Bates, S.: Conformal prediction: A gentle introduction. Foun- dations and Trends in Machine Learning16(4), 494–591 (2023)

2023
[2]

arXiv preprint arXiv:2412.20023 (2024)

Beeson, R., Li, A., Sinha, A.: Global search of optimal spacecraft trajectories using amortization and deep generative models. arXiv preprint arXiv:2412.20023 (2024)

arXiv 2024
[3]

The Journal of the Astronautical Sciences72(6), 62 (2025)

Graebner, J., Beeson, R.: Global search for optimal low thrust spacecraft trajectories using diffusion models and the indirect method. The Journal of the Astronautical Sciences72(6), 62 (2025). https://doi.org/10.1007/s40295-025-00535-1

doi:10.1007/s40295-025-00535-1 2025
[4]

Transfer Learning of Multiobjective Indirect Low-Thrust Trajectories Using Diffusion Models and Markov Chain Monte Carlo

Graebner, J., Beeson, R.: Transfer learning of multiobjective indirect low-thrust trajectories using diffusion models and markov chain monte carlo (5 2026). https://doi.org/10.48550/arXiv.2605.09125

work page Pith review arXiv doi:10.48550/arxiv.2605.09125 2026
[5]

Advances in neural information processing systems33, 6840–6851 (2020)

Ho, J., Jain, A., Abbeel, P.: Denoising diffusion probabilistic models. Advances in neural information processing systems33, 6840–6851 (2020)

2020
[6]

In: Blasch, E., Darema, F., Metaxas, D

Li, A., Beeson, R.: Aligning diffusion model with problem constraints for trajectory optimization. In: Blasch, E., Darema, F., Metaxas, D. (eds.) Handbook of Dynamic Data-Driven Applications Systems, vol. 4. Springer, Cham (2025), preprint available as arXiv:2504.00342

arXiv 2025
[7]

In: Ozay, N., Balzano, L., Panagou, D., Abate, A

Li, A., Ding, Z., Dieng, A.B., Beeson, R.: DiffuSolve: Diffusion-based solver for non- convex trajectory optimization. In: Ozay, N., Balzano, L., Panagou, D., Abate, A. (eds.) Proceedings of the 7th Annual Learning for Dynamics & Control Conference. Proceedings of Machine Learning Research, vol. 283, pp. 45–58. PMLR (4–6 June 2025)

2025
[8]

In: Blasch, E., Darema, F., Metaxas, D

Li, A., Ding, Z., Dieng, A.B., Beeson, R.: Constraint-aware diffusion models for trajectory optimization. In: Blasch, E., Darema, F., Metaxas, D. (eds.) Dynamic Data Driven Applications Systems. pp. 308–316. Springer Nature Switzerland, Cham (2026)

2026

Show all 13 references

[9]

In: AAS/AIAA Astrodynamics Specialist Conference

Li, A., Sinha, A., Beeson, R.: Amortized global search for efficient preliminary trajectory design with deep generative models. In: AAS/AIAA Astrodynamics Specialist Conference. Big Sky, MT (August 2023), paper AAS 23-352

2023
[10]

arXiv preprint arXiv:2606.00366 (2026)

Li, A., Stellato, B., Beeson, R.: Glens: Global search via learning from solver iterates with diffusion models. arXiv preprint arXiv:2606.00366 (2026)

2026 arXiv
[11]

In: Inter- national Conference on Algorithmic Learning Theory

Maurer, A.: A vector-contraction inequality for rademacher complexities. In: Inter- national Conference on Algorithmic Learning Theory. pp. 3–17. Springer (2016)

2016
[12]

In: Proceedings of the eleventh annual conference on Computational learning theory

McAllester, D.A.: Some pac-bayesian theorems. In: Proceedings of the eleventh annual conference on Computational learning theory. pp. 230–234 (1998)

1998
[13]

MIT Press, Cambridge, MA, 2 edn

Mohri, M., Rostamizadeh, A., Talwalkar, A.: Foundations of Machine Learning. MIT Press, Cambridge, MA, 2 edn. (2018)

2018

Pith tools

Reviewed August 1, 2026 · model on record in the stance chip above.

[1] [1]

Foun- dations and Trends in Machine Learning16(4), 494–591 (2023)

Angelopoulos, A.N., Bates, S.: Conformal prediction: A gentle introduction. Foun- dations and Trends in Machine Learning16(4), 494–591 (2023)

2023

[2] [2]

arXiv preprint arXiv:2412.20023 (2024)

Beeson, R., Li, A., Sinha, A.: Global search of optimal spacecraft trajectories using amortization and deep generative models. arXiv preprint arXiv:2412.20023 (2024)

arXiv 2024

[3] [3]

The Journal of the Astronautical Sciences72(6), 62 (2025)

Graebner, J., Beeson, R.: Global search for optimal low thrust spacecraft trajectories using diffusion models and the indirect method. The Journal of the Astronautical Sciences72(6), 62 (2025). https://doi.org/10.1007/s40295-025-00535-1

doi:10.1007/s40295-025-00535-1 2025

[4] [4]

Transfer Learning of Multiobjective Indirect Low-Thrust Trajectories Using Diffusion Models and Markov Chain Monte Carlo

Graebner, J., Beeson, R.: Transfer learning of multiobjective indirect low-thrust trajectories using diffusion models and markov chain monte carlo (5 2026). https://doi.org/10.48550/arXiv.2605.09125

work page Pith review arXiv doi:10.48550/arxiv.2605.09125 2026

[5] [5]

Advances in neural information processing systems33, 6840–6851 (2020)

Ho, J., Jain, A., Abbeel, P.: Denoising diffusion probabilistic models. Advances in neural information processing systems33, 6840–6851 (2020)

2020

[6] [6]

In: Blasch, E., Darema, F., Metaxas, D

Li, A., Beeson, R.: Aligning diffusion model with problem constraints for trajectory optimization. In: Blasch, E., Darema, F., Metaxas, D. (eds.) Handbook of Dynamic Data-Driven Applications Systems, vol. 4. Springer, Cham (2025), preprint available as arXiv:2504.00342

arXiv 2025

[7] [7]

In: Ozay, N., Balzano, L., Panagou, D., Abate, A

Li, A., Ding, Z., Dieng, A.B., Beeson, R.: DiffuSolve: Diffusion-based solver for non- convex trajectory optimization. In: Ozay, N., Balzano, L., Panagou, D., Abate, A. (eds.) Proceedings of the 7th Annual Learning for Dynamics & Control Conference. Proceedings of Machine Learning Research, vol. 283, pp. 45–58. PMLR (4–6 June 2025)

2025

[8] [8]

In: Blasch, E., Darema, F., Metaxas, D

Li, A., Ding, Z., Dieng, A.B., Beeson, R.: Constraint-aware diffusion models for trajectory optimization. In: Blasch, E., Darema, F., Metaxas, D. (eds.) Dynamic Data Driven Applications Systems. pp. 308–316. Springer Nature Switzerland, Cham (2026)

2026