acceptodds
Under review as a conference paper at ICLR 2027

Learning Distributionally Robust First-Order Methods for Convex Optimization

Abstract

We propose a distributionally robust approach for learning hyperparameters (e.g., step sizes and momentum coefficients) for first-order methods in convex optimization. Given a dataset of problem instances, we minimize a Wasserstein distributionally robust version of the performance estimation problem (PEP). Our framework unifies two extremes. As the robustness radius vanishes, we recover the empirical risk minimization problem commonly encountered in learning to optimize (L2O), and as it grows we recover the PEP worst-case algorithm design problem. We solve the resulting problem with stochastic gradient descent, differentiating through the solution of an inner semidefinite program at each step. We prove high-probability bounds showing that the true risk of the learned algorithm is at most the in-sample L2O optimum plus a slack that shrinks with the sample size, and is no worse than the worst-case PEP bound. On logistic regression, LASSO, and linear programming examples, our learned algorithms achieve strong out-of-sample performance with certifiable robustness, outperforming both worst-case optimal and vanilla L2O baselines.

Primary area:
optimization
Keywords:
First-order methods, Data-driven optimization, Wasserstein distributionally robust optimization, Performance estimation problem

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_eGboOpenReview ↗
Rating
2
Confidence
4(+1)
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

The paper learns hyperparameters such as step sizes and momentum coefficients for first-order methods by minimizing a Wasserstein DRO version of the L2O problem. The DRO-PEP-P formulation is from Park et al. (2025), who used it to evaluate a fixed algorithm; this paper minimizes it over the algorithm parameters theta with SGD, differentiating through the inner SDP at every step. The radius controls robostness of the proposed DRO method, hence, playing a middle groud between plain L2O and worst-case PEP design. Theorem 1 gives an out-of-sample guarantee uniform over all theta, and Theorem 2 bounds the true risk of the learned method. Experiments on logistic regression, LASSO, and TV inpainting with shifted test sets show DR-L2O is more robust to the shift than other methods.

Critical strengths
  1. Simple idea: a single parameter, the radius, controls robustness and interpolates between data-driven L2O and worst-case PEP.
  2. Clean theory: the method is presented with mathematical rigor and no hidden heuristics.
  3. The presentation is mostly easy to follow.
Critical weaknesses
  1. Insufficient novelty. The main idea is to apply a Wasserstein DRO version of the L2O problem (or OPT-PEP problem), and the resulting formulation almost entirely depends on the existing SDP formulation. As acknowledged in the paper, the DRO-PEP SDP is from Park et al. (2025), and the SDP derivative also seems to exist. What's new is running SGD on the existing SDP formulation.

Wasserstein DRO is by now a popular and well-studied topic. Given its maturity, I think DRO should be viewed as just one way of evaluating an objective under uncertain data, in the same way one applies CVaR instead of the expectation. As an exmaple, in my opininon, no one should claim their work is novel in their application just because they were the first to replace the empirical expectation with CVaR whose reformulation already exists. The same applies here: the empirical expectation is replaced with the worst-case expectation, and the resulting SDP formulation is already there. I think simply making this replacement is not sufficiently novel for a conference like ICLR. So, without a significant methodological contribution, I think at least one of the theoretical or practical contributions should be significant for me to raise my evaluation.

On the theory side, Theorem 1 takes Park's fixed-theta guarantee, puts a grid on the parameter set, and applies a union bound; hence, same rate with some extra terms. Given that the formulation already existed and its algorithmic extension (running SGD on it) is quite simple, I'd expect a strong theoretical result to carry the paper, and unfortunately, this doesn't seems to be the case. So I believe the paper has to stand on practical value, and the next point is why it doesn't.

  1. This is my main concern on practicality of the proposed method. Every SGD step solves an SDP that grows with K, and SDPs are well known to be slow for large matrix sizes. For example, in Tables 1,2,3, the DR-L2O time per each step already goes from 0.062 s at K = 1 to 7.4 s at K = 15. Stopping all experiments at K = 15 doesn't fully display the limitation of the method.

I understand the experiments only consider convex problems (logistic regression, LASSO, an LP). But many convex problems in practice may run hundreds or thousands of first-order iterations, and I don't see how the proposed method remains scalable at, say, K = 1000. On top of that, if the outer problem is nonconvex, so SGD may need even more iterations, each paying the full SDP cost. So DR-L2O may beat the vanilla method at small K with tolerable extra computations cost, but for large K the computation may be too expensive for the added robustness.

On top of that, Theorem 1 has an exponential dependence on K, as in N^(-1/q) with q = O(K^2). So as K grows, adding more data does essentially nothing for the certificate. Larger K means paying much more per training step for a guarantee that improves less. This N-vs-K trade-off should be stated up front, and the absence of any larger K in the numerical results makes me suspect it doesn't work there, not providing clear tradeoff.

  1. N is never shown or varied. The main text never states how many in-sample data N are used (only in the Appendix). I suspect the gain over L2O depends on N. Without a plot of the gap vs. N, I can't tell whether the improvement from DRO is really about robustness or just the particular choice of N.

  2. Cross-validating the radius seems strange with shifted test sets. If the radius is tuned on in-distribution validation data (which seems to be the case), it's tuned for the wrong distribution, since the test data is shifted. So the tuning prefers a radius that performs well on the wrong data? While cross-validating the radius is standard, tuning it this way for shifted test data seems strange to me. If any shifted data is used, that's obviously unfair to L2O. The authors should clearly discuss how cross-validation is performed in this shifted-data setting.

Overall, I do not ask the authors to develop more efficient SDP solvers, (which is too much of ask let alone out of the scope of this paper), since SDPs struggling with large matrices is well known, iteratively solving such problems seems practically not relevant: I am evaluating whether the practical benefit outweights price of solving large SDPs. Unfortunately, the accompanying theoretical results and numerical results do not add any motivation to use the method as a stand-alone framework for L2O in practice.

The above is only my own perspective. Please provide any counter arguments for any disagreements with the author's perspective.

Questions for authors
  1. In your experiments, the problems can be solved to the required accuracy within 15 iterations. Do you think this is the case for other applications too? If so, can you name a few practical applications that the proposed method can efficiently handle?

  2. For TV inpainting, both L2O and DR-L2O are trained with SGD, but L2O's gradient is just backpropagation, while DR-L2O has to solve an SDP to get each gradient. Is this correct? Isn't it the case that DR-L2O takes more time than L2O for the same K?

3.The method seems to require solving the SDP formulation each step. Can it possible to replace it with a second-order cone or linear program, which would be far more scalable?

  1. Theorem 1 looks like a standard extension of the existing result, and the proof is a union bound over the parameter space. Setting aside the learning-to-optimize context, is there any theoretical result that is new to the distributionally robust optimization literature?

  2. Can you describe how you do cross-validation in the numerical experiments? I am not familiar with tuning a parameter for a shifted test set, so this part is a bit confusing to me.

5 comments

We thank the reviewer for the careful and thorough review, and for inviting counterarguments. The review asks whether the method is novel, whether the theory is strong, and whether the robustness is worth an SDP solve at every training step. In short:

  • Theory. The revised Theorem 1 improves the sufficient radius from N−1/qN^{-1/q}, with q=O(K2)q=O(K^2), to N−1/2N^{-1/2} (common response). It rests on a reduction that handles an ambiguity set moving with θ\theta, which existing DRO guarantees do not cover (W1 & Q4).
  • Cost. Training is offline, its SDP size does not depend on NN or on the instance dimension, and the learned method costs nothing extra at deployment. The method targets fixed budgets of tens of iterations, as in embedded MPC (W2, Q1 to Q3).
  • Experiments. The new NN-sweep shows that the out-of-distribution gain persists at every NN, and no shifted data enters training or cross-validation (W3, W4, Q5).

[W1 & Q4] Novelty of our approach

We agree with the reviewer on three facts. The DRO-PEP formulation and its tractable SDP are from Park et al. (2025), and differentiating through a conic program is an existing tool (Agrawal et al., 2019). The submitted Theorem 1 was Park et al.'s fixed-θ\theta guarantee made uniform over a cover of Θ\Theta, so it kept their N−1/qN^{-1/q} rate.

The revised Theorem 1 replaces this argument, which moves to Proposition 6 in Appendix C.4. It lifts each instance zz to its trajectory θ↦Aθ(z)\theta\mapsto\mathcal A_\theta(z) and applies the exact generalization theorem of Le and Malick (2025) once, on this common trajectory space. Lemma 7 then carries the bound back to the DRO risk at each θ\theta. The sufficient radius is of order N−1/2N^{-1/2} for each fixed horizon (see our common response on Theorem 1).

On Q4, the new element for the DRO literature is this reduction, not a new concentration inequality. In DR-L2O the ambiguity set moves with θ\theta. Its support set Ξθ\Xi^\theta is cut out by interpolation conditions polynomial in θ\theta, and its samples are lifted by the algorithm being learned. Decision-dependent ambiguity sets are not new (Luo and Mehrotra, 2020), but the finite-sample guarantees we know of for them rest on containment of the true distribution in the ball (Zhu, Yu, and Bayraksan, 2024), whose rate in our setting is N−1/qN^{-1/q}. In the guarantees we know of, the decision moves the nominal distribution on a fixed sample space. Exact generalization results (Azizian et al., 2023; Le and Malick, 2025) avoid containment but assume a sample space and an empirical distribution that do not depend on the decision. Our reduction gives their N−1/2N^{-1/2} rate with a moving support set, through one fixed space of trajectories that evaluation at θ\theta maps onto Ξθ\Xi^\theta (Lemma 4).

The CVaR analogy describes the formulation but not the guarantee. Replacing an expectation by CVaR leaves the sample space fixed, so a generalization bound on that space applies to every decision directly. Here the sample space Ξθ\Xi^\theta moves with θ\theta. The reduction above removes this dependence by lifting each instance to its whole trajectory. Evaluation at θ\theta is 1-Lipschitz, so the bound on the trajectory space transfers to each Ξθ\Xi^\theta (Lemma 7).

[W2] Trade-off between the horizon K and the sample size N

On the dependence on KK through N−1/qN^{-1/q}: the revised Theorem 1 bounds the true risk directly, with a radius of order N−1/2N^{-1/2} for each fixed horizon under a new nondegeneracy assumption (Assumption 3); see our common response on Theorem 1. The statement up front that the reviewer asks for is the paragraph after Theorem 1 in Section 4.1. The horizon still enters through the constants. The Lipschitz constant Lˉ\bar L of θ↦Aθ(z)\theta\mapsto\mathcal A_\theta(z) and the bound on the iterates can grow exponentially in KK, as for any composition of KK Lipschitz maps (Appendix C.1), and the critical radius ρcrit\rho_{\mathrm{crit}} can shrink; both enlarge the constants c1c_1 and c2c_2. More data thus always tightens the certificate at rate N−1/2N^{-1/2}, and a longer horizon raises the constant in front of it.

[W2 & Q2] Cost of solving an SDP at every SGD step

Yes: for the same KK, a DR-L2O training step costs more than an L2O step, because L2O backpropagates through the iterations while DR-L2O solves and differentiates an SDP (Q2). Tables 1 to 3 (Appendix F) report the wall time per SGD step. In logistic regression, a DR-L2O step takes 0.062 s at K=1K=1 and 7.4 s at K=15K=15, against 0.001 s and 0.009 s for L2O. In LASSO, it takes 0.14 s and 14.7 s, against 0.006 s and 0.037 s. In TV inpainting, it takes 0.41 s at K=1K=1 and 57 s at K=10K=10, against 0.12 s and 0.85 s.

Three features determine what this cost means in practice. First, training is offline and runs once per problem family and horizon. With 500 SGD steps, a run takes about one hour for logistic regression at K=15K=15 and about eight hours for TV inpainting at K=10K=10. Second, the SDP size depends only on KK and the mini-batch size. It does not depend on the training-set size NN or on the instance dimension, because PEP works with the Gram matrix of the iterates and gradients. Third, at deployment the learned algorithm has the same per-iteration cost as the untuned method, so the training cost is amortized over every instance solved afterwards.

We agree that horizons in the hundreds or thousands are out of reach with generic interior-point SDP solvers. The SOCP and LP restrictions of Q3 and first-order SDP solvers are natural next steps. This paper targets the regime of Q1, where a fixed budget of tens of iterations is the binding constraint.

[Q1] Do other applications also need only about 15 iterations? Which practical applications can the method handle efficiently?

We expect this regime wherever the same type of convex problem is solved repeatedly under a hard time budget, so that the budget rather than a target accuracy fixes the number of iterations. Model predictive control (MPC) is the main example. At every control step, a controller solves a parametric quadratic program whose data change with the measured state and the reference (Borrelli, Bemporad, and Morari, 2017). The solve must finish within the sampling period, often on embedded hardware, so solvers are warm-started and stopped after a small, fixed number of first-order iterations. For example, TinyMPC (Nguyen et al., 2024, Section IV-B) tracks a figure-eight trajectory on a quadrotor microcontroller at 500 Hz; every solve converged within seven ADMM iterations, inside the 2 ms budget set by the control rate. Its prediction horizon of 15 is a separate quantity from the iteration count. Furthermore, Richter, Jones, and Morari (2012) certify the number of fast gradient iterations needed for real-time MPC.

[Q3] Can the SDP be replaced by a second-order cone program or a linear program?

Yes, by a conservative restriction following Ahmadi, Dash, and Hall (2017). Their diagonally dominant (DD) and scaled diagonally dominant (SDD) cones satisfy DD⊆SDD⊆S+\mathrm{DD} \subseteq \mathrm{SDD} \subseteq \mathbb{S}_+. Replacing each PSD constraint in (DRO-PEP-D) by an SDD constraint gives an SOCP, since the norm constraint ∥(Xi,Yi)∥≤λ\lVert (X_i,Y_i) \rVert \le \lambda is already a second-order conic constraint. Using DD constraints and the stronger norm constraint ∥(vec(Xi),Yi)∥1≤λ\lVert (\mathrm{vec}(X_i),Y_i) \rVert_1 \le \lambda gives an LP.

Both restrict the feasible set of the minimization problem (DRO-PEP-D), so on the event of Theorem 1 their optimal value R~ε\widetilde{\mathcal R}_\varepsilon still bounds the true risk:

\quad\text{for every }\theta\in\Theta.$$ The restriction is always feasible: $y_i=0$, $\tau_i=0$, and $(X_i,Y_i)=-(A_{\mathrm{obj}},b_{\mathrm{obj}})$ make the matrix slack zero, and large enough $\lambda$ and $s_i$ satisfy the remaining constraints. Column generation (Ahmadi et al., 2017) reduces the gap by adding eigenvectors of negative eigenvalues of the dual matrix variables as new atoms. Each refined bound remains valid and is no larger than the previous one. We have not implemented these alternatives, so we claim neither a measured speedup nor a measured gap. The restricted problem still has $O(K^2)$ variables per sample; the gain would come from replacing the PSD cones by simpler cones. It also changes the training objective, so its effect on the learned method remains to be evaluated.

[W3] How does the gain over L2O depend on the sample size N?

We added this experiment in Appendix E.5 with the new Tables 7 and 8. For logistic regression and LASSO, we vary N∈100,200,500,1000,2000N\in\\{100,200,500,1000,2000\\} and keep all other settings fixed (we omit TV inpainting because its training set is a small fixed set of images). In both experiments, the test losses of both methods change little with NN, and their ordering is the same at every NN. In distribution, L2O has the lower test loss at every NN, as expected, since it fits the training distribution. Out of distribution, DR-L2O has the lower test loss at every NN and horizon. In logistic regression, its mean loss is about 15 to 400 times smaller. In LASSO, L2O diverges on the shifted instances at K=10K=10 and K=15K=15, with mean losses between 10310^3 and 10710^7, while the mean loss of DR-L2O stays below 7. The gain under shift therefore comes from the robust formulation, not from the choice of NN.

[W4 & Q5] How is the radius cross-validated when the test set is shifted?

The validation set is drawn from the training distribution, independently of the training set, and contains no shifted instances: 250 instances for logistic regression and LASSO, and the 40 images of 4 held-out Olivetti faces for TV inpainting. All hyperparameters of L2O (learning rate and weight decay) and of DR-L2O are selected on this same validation set. No shifted data enters training or the selection of ε\varepsilon. OPT-PEP uses no data so there is no cross-validation there.

Theorem 1 certifies the in-distribution risk for every ε>c2log⁡(4/δ)/N\varepsilon > c_2\sqrt{\log(4/\delta)/N} once N>c1log⁡(4/δ)N > c_1\log(4/\delta), but both thresholds depend on the unknown distribution, so we select the operating radius by cross-validation (Appendix D). This selection uses no information about the shift, so the gain under the shift is not an artifact of tuning. Under a shift, two results apply. The new Remark 6 keeps the N−1/2N^{-1/2} rate: if also N>4c1log⁡(4/δ)N > 4c_1\log(4/\delta) and ε≤ρcrit/8\varepsilon \le \rho_{\mathrm{crit}}/8, the DRO risk bounds the expected loss under every test distribution whose algorithm trajectories lie within ε−c2log⁡(4/δ)/N\varepsilon - c_2\sqrt{\log(4/\delta)/N} of those under P\mathbb P. Proposition 7 covers shifts of any size and needs no nondegeneracy, but its margin is ε−ε‾(δ)\varepsilon-\overline\varepsilon(\delta), where the containment radius ε‾(δ)\overline\varepsilon(\delta) of Proposition 6 is of order N−1/qN^{-1/q}. In both results, a larger radius certifies a larger shift.

We thank the reviewer again for the candid and detailed review. We hope that the improved rate, the cost analysis, and the new NN-sweep lead the reviewer to reconsider the evaluation.

References

  • Agrawal, Barratt, Boyd, Busseti, and Moursi (2019). Differentiating through a cone program. Journal of Applied and Numerical Optimization. arXiv:1904.09043.
  • Ahmadi, Dash, and Hall (2017). Optimization over structured subsets of positive semidefinite matrices via column generation. Discrete Optimization. PDF.
  • Azizian et al. (2023) and Le and Malick (2025): see the common response.
  • Borrelli, Bemporad, and Morari (2017). Predictive Control for Linear and Hybrid Systems. Cambridge University Press. DOI.
  • Luo and Mehrotra (2020). Distributionally robust optimization with decision dependent ambiguity sets. Optimization Letters. arXiv:1806.09215.
  • Nguyen, Schoedel, Alavilli, Plancher, and Manchester (2024). TinyMPC: Model-predictive control on resource-constrained microcontrollers. ICRA. arXiv:2310.16985.
  • Park et al. (2025). Data-driven analysis of first-order methods via distributionally robust optimization. arXiv:2511.17834.
  • Richter, Jones, and Morari (2012). Computational complexity certification for real-time MPC with input constraints based on the fast gradient method. IEEE Transactions on Automatic Control. DOI.
  • Zhu, Yu, and Bayraksan (2024). Residuals-based contextual distributionally robust optimization with decision-dependent uncertainty: theoretical guarantees and decomposition algorithm. arXiv:2406.20004.
Reviewer_RGS4OpenReview ↗
Rating
2
Confidence
1
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes a method for learning step sizes and momentum for first-order method using Wassertstein-DRO over the PEP problem. The robustness risk changes from L2O to the worst case PEP bound. Numerical experiments validate findings for SGD over the logistic regression, LASSO and TV LP problems.

Critical strengths

1)The paper reformulate the hyperparameter choice problem to a tractable formulation.

2)Painting reconstruction experiments are neat.

Critical weaknesses

1)There are no examples for deep learning architectures, where hyperparameter tuning is really a sensitive problem.

2)The dependence on NN in Theorem 1 suffers from the curse of dimensionality.

Questions for authors

1)Why does DR-L2O curve in the figure 1 crosses the PEP curve and not strictly below it?

2)In the theorem 1 the diameter of the hyperparameter set is introduced. How is it measured, if hyperparameters have different structure and/or dimensionality?

3)What is the trade-off between the risk minimization and computational costs, if we compare costs for SGD with tuned hyperparameters to vanilla SGD. At least for logistic regression. Can we, or shall we find the suboptimal hyperparameters to lower the overall complexity.

4)What is the novelty compared to existing Wassertein DRO methods [1]?


[1] Distributionally Robust Optimization, D. Kuhn et al.

3 comments

We thank the reviewer for finding the formulation tractable and the inpainting experiments neat. We answer W1, W2, Q1, and Q2 here, and Q3 and Q4 in the next comment, which also lists the references.

[W1] Deep learning architectures

We first clarify the scope, which also bears on Q3. DR-L2O tunes the scalar step sizes and momentum coefficients of a classical first-order method offline; it does not learn a deep architecture. The learned algorithms are deterministic methods with exact gradients: Nesterov's fast gradient method (FGM) for logistic regression, ISTA for LASSO, and PDHG for TV inpainting. The problems they solve are convex. Stochastic gradient descent appears only in the offline training loop that updates the parameters θ\theta, not in the learned algorithm.

Step-size tuning for convex first-order methods is an active topic on its own. Recent work designs step-size schedules with provably faster worst-case rates, such as long steps (Grimmer, 2024; Grimmer, Shu, and Wang, 2025) and the silver schedule (Altschuler and Parrilo, 2025). Other work learns step sizes and warm starts from data for parametric convex problems, with generalization guarantees (Sambharya et al., 2024; Sambharya and Stellato, 2025; 2026). DR-L2O sits between these two lines: it learns the parameters from data, and its radius controls the robustness to distribution shift, up to the worst-case design.

Deep network training is nonconvex and stochastic, which is outside the scope of this paper. Assumption 1 requires exact gradients, and the interpolation conditions that make our inner SDP exact (Taylor et al., 2017) are those of convex function classes. The setting we target is the repeated solution of similar convex problems under a fixed iteration budget, as in our three experiments.

[W2] Curse of dimensionality in NN

We agree that the submitted Theorem 1 had this problem: its radius was of order N−1/qN^{-1/q} with q=O(K2)q=O(K^2), because it required the Wasserstein ball to contain the true distribution. The revised Theorem 1 bounds the true risk directly, following Azizian et al. (2023) and Le and Malick (2025); its radius is of order N−1/2N^{-1/2} for each fixed horizon KK, which enters only the constants, under one additional nondegeneracy assumption (Assumption 3). The statement, the new assumption, and what the containment route still provides are in our common response on Theorem 1.

[Q1] Why the DR-L2O curve in Figure 1 crosses the OPT-PEP curve

OPT-PEP is the schedule that minimizes a worst-case upper bound over the whole function class, but its curve in Figure 1, like the other two, is that schedule's empirical test loss on sampled instances. No result in the paper orders these empirical curves. Theorem 2 (now Corollary 1.1) compares the true risk of DR-L2O with the worst-case bound that OPT-PEP minimizes, and that bound is at least the OPT-PEP curve on instances in the function class. DR-L2O can therefore lie above the OPT-PEP curve at some KK without contradicting the theory. In the LASSO data of Figure 1 this happens only for K≤6K\le 6; from K=7K=7 on, DR-L2O is below OPT-PEP on both test sets.

[Q2] How the diameter of the hyperparameter set is measured

Every hyperparameter in our framework is a real scalar: a step size, a momentum coefficient, or a primal or dual step size of PDHG. We stack them over the horizon into one vector θ∈Rp\theta\in\mathbb R^p, with p=Kp=K for ISTA, p=2Kp=2K for FGM, and p=3Kp=3K for PDHG. The parameter set is a box Θ=∏j=1p[lj,uj]\Theta=\prod_{j=1}^p[l_j,u_j] (Assumption 2), and its diameter is Euclidean, diam(Θ)=(∑j=1p(uj−lj)2)1/2\mathrm{diam}(\Theta)=\big(\sum_{j=1}^p(u_j-l_j)^2\big)^{1/2}. Coordinates of different kinds may have different scales; the bound accounts for this through the Lipschitz constant Lˉ\bar L of the map from θ\theta to the lifted output, measured in the same norm. In the revised Theorem 1, diam(Θ)\mathrm{diam}(\Theta) enters only through Lip(ℓ),Lˉ,diam(Θ)p\mathrm{Lip}(\ell)\\,\bar L\\,\mathrm{diam}(\Theta)\sqrt p, which bounds an entropy integral (Lemma 5); it changes the constants but not the rate N−1/2N^{-1/2}.

[Q3] Training cost versus the cost of the tuned method

As noted in W1, the tuned method in logistic regression is FGM with exact gradients; training starts from its standard parameters, step size 1/L1/L and the standard momentum sequence. Training is offline and runs once per problem family and horizon. At K=15K=15, one outer step takes 7.4 s for DR-L2O and 0.009 s for L2O (Table 1); with 500 outer steps, a DR-L2O training run takes about one hour. Deployment costs the same as untuned FGM: the learned method is FGM with fixed scalars, using the same two matrix-vector products per iteration. The training cost is thus amortized over every instance solved afterwards.

Early stopping of the outer loop is a valid way to save training cost. Because Theorem 1 holds uniformly over Θ\Theta, it applies to an early-stopped parameter as well: evaluating the DRO risk there gives a high-probability bound on its true risk. Early stopping loses optimality of the DRO risk, not the certificate.

[Q4] Novelty compared to existing Wasserstein DRO methods (Kuhn et al.)

Kuhn et al. survey DRO as a general framework; we apply that framework to algorithm design. Two features of this application are, to our knowledge, not covered by existing DRO results.

  1. The learning objective is the optimal value of an SDP. For each θ\theta, the worst-case expected loss over the Wasserstein ball is computed by a semidefinite program. Its support set (interpolation conditions) and its samples (lifted trajectories) both depend nonconvexly on θ\theta. With a loss convex in the decision, standard Wasserstein DRO reformulations minimize over the decision and the dual variables jointly in one convex program, which is impossible here, so we differentiate through the SDP.
  2. The N−1/2N^{-1/2} guarantee is uniform over an ambiguity set that moves with θ\theta. Exact generalization results are uniform over the decision but assume a fixed sample space. The revised Theorem 1 embeds the lifted outputs of all θ\theta in a common space of algorithm trajectories θ↦Aθ(z)\theta\mapsto\mathcal A_\theta(z).

These features also separate our work from recent methods that train through DRO problems by differentiable optimization, such as Costa and Iyengar (2023) and Ma et al. (2024). There, the DRO problem is a decision layer whose solution enters an empirical task loss, and the learned object is a predictor or the ambiguity set. In DR-L2O, the learning objective is the DRO risk itself. It is the exact worst case over the ambiguity set, because the interpolation conditions are exact, and by Theorem 1, for a radius above its threshold, it upper-bounds the true risk of every schedule in Θ\Theta with high probability.

References

  • Altschuler and Parrilo (2025). Acceleration by stepsize hedging: silver stepsize schedule for smooth convex optimization. Math. Programming. DOI.
  • Azizian, Iutzeler, and Malick (2023). Exact generalization guarantees for (regularized) Wasserstein distributionally robust models. NeurIPS. arXiv:2305.17076. New in the revised paper.
  • Costa and Iyengar (2023). Distributionally robust end-to-end portfolio construction. Quantitative Finance. arXiv:2206.05134.
  • Grimmer (2024). Provably faster gradient descent via long steps. SIAM J. Optim. DOI.
  • Grimmer, Shu, and Wang (2025). Accelerated objective gap and gradient norm convergence for gradient descent via long steps. INFORMS J. Optim. DOI.
  • Kuhn, Shafiee, and Wiesemann (2025). Distributionally robust optimization. Acta Numerica. arXiv:2411.02549.
  • Le and Malick (2025). Universal generalization guarantees for Wasserstein distributionally robust models. ICLR. arXiv:2402.11981. New in the revised paper.
  • Ma, Ning, and Du (2024). Differentiable distributionally robust optimization layers. ICML. PMLR.
  • Sambharya and Stellato (2025). Data-driven performance guarantees for classical and learned optimizers. JMLR 26(171).
  • Sambharya and Stellato (2026). Learning algorithm hyperparameters for fast parametric convex optimization. SIAM J. Math. Data Sci. DOI.
  • Sambharya, Hall, Amos, and Stellato (2024). Learning to warm-start fixed-point optimization algorithms. JMLR 25(166).
  • Taylor, Hendrickx, and Glineur (2017). Smooth strongly convex interpolation and exact worst-case performance of first-order methods. Math. Programming. arXiv:1502.05666.

We hope our response has been helpful. Since the public discussion closes today, we would be grateful to know whether it addresses your concerns, in particular:

  • Scope (W1). We tune step sizes and momentum offline for deterministic first-order methods on convex problems, in line with recent work on learned and long step-size schedules. Deep architectures are outside this scope.
  • Theorem 1 (W2). The common response and our exchange with Reviewer 7sDj compare the revised N−1/2N^{-1/2} guarantee with the containment guarantee, which we keep as Proposition 6.

We are happy to clarify anything further.

Reviewer_7sDjOpenReview ↗
Rating
3
Confidence
1(−2)
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper addresses configuring the (scalar) parameters of first-order convex optimization algorithms under a strict linear span assumption. The new thing is that they account for (problem) distribution shifts using a Distributionally Robust Optimization (DRO) framework built directly upon Performance Estimation Problem (PEP) machinery. The authors then establish theoretical OOS guarantees for their proposed methods and demonstrate their application through several classical optimization examples.

Critical strengths

Disclosure: I reviewed this paper before, so my review below will inevitably contain a certain degree of comparison between the old and new drafts.

The paper is well written and easy to follow. Compared to the last time, I think the presentation/writing of this new draft has been improved significantly. There is no overclaiming of contributions, and the technical foundation/limitation (PEP) have been addressed adequately. So I am happy with this aspect now.

Critical weaknesses

A. Still, there are inherent weaknesses of this framework, which I mentioned before, that have not been addressed. ​

  1. The guarantee in Theorem 1 is still vacuous: qq is still of order K2K^2, and with small KK, the bound will be immediately vacuous. I mentioned this issue last time, though. I think it would be nice if the authors could come up with some lower bound for this one. Though it might not be trivial, with the help of AI, maybe the authors can try to work it out to make the draft complete. I think compared to the last NeurIPS deadline, AI has been much better at math, and maybe it can give the authors some good clues about how to proceed.

  2. Theorem 2's guarantee is still trivial to me: it still rather follows directly from the DRO formulation, the Wasserstein Lipschitz bound, and the minimization over θ\theta.

So, compared to the last time, the theoretical contribution of this paper is still a bit limited for me. But again, I will still try not to put too much weight on this one.

B. Some other issues, including narrow algorithm class comparisons, missing comparisons against adaptive methods, and mainly demonstrative experiments, are partially addressed, though they are still not fully convincing to me. But again, as for me, the new framework/problem setting is the main credit of this paper, so I again put less weight on those issues.

Final Comments

Overall, I am good with this draft now. I think that, though the problem setting is niche and the contribution is not that significant, this is still a nice draft that considers a missing aspect (distribution shift) in data-driven algorithm design. Though I keep my original assessment, which is weak accept, I will increase my confidence score to support this draft. Good luck with the submissions! ​


After the rebuttal, I unfortunately have to reduce my confidence score to 1.

Questions for authors

See weaknesses.

4 comments

We thank the reviewer for reading the paper again and for raising their confidence. We answer A1 here, and A2 and B in the next comment.

[A1] Finite-sample rate and a lower bound

The revised Theorem 1 no longer relies on Wasserstein containment: it bounds the true risk directly, following Le and Malick (2025), and a radius of order N−1/2N^{-1/2} suffices for each fixed horizon under a new nondegeneracy assumption (Assumption 3). The statement, the comparison with the containment route, and why we keep the latter in the appendix are in our common response on Theorem 1.

On the lower bound: for the containment route, the rate N−1/qN^{-1/q} cannot be improved in general. For a fixed parameter, Weed and Bach (2019, Theorem 1 and Proposition 7) show that W1(P^Nθ,Pθ)≳N−1/tW_1(\widehat{\mathbb P}_N^\theta,\mathbb P^\theta)\gtrsim N^{-1/t} for every tt below the lower Wasserstein dimension of the lifted distribution. This dimension equals qq when the lifted distribution has a density on Rq\mathbb R^q, and can be smaller when it is supported on a lower-dimensional set. This lower bound concerns the containment route only. The new Remark 6 follows the route of Theorem 1 instead, via Le and Malick (2025, Theorem E.1). For ε\varepsilon below a distribution-dependent constant, the DRO risk also certifies every test distribution whose algorithm trajectories lie within ε−O(N−1/2)\varepsilon-O(N^{-1/2}) of those under P\mathbb P, for all θ\theta at once. Whether larger shifts admit this rate we do not pursue here.

References: Weed and Bach (2019), Le and Malick (2025).

[A2] Theorem 2 follows directly from the DRO formulation

We agree that Theorem 2 follows directly from Theorem 1, the DRO risk ordering, the Wasserstein–Lipschitz bound, and minimization over θ\theta. Theorem 1 bounds the true risk of the learned method by its DRO risk, but does not explicitly compare it with the L2O and OPT-PEP baselines. We include Theorem 2 to make these comparisons explicit: the true risk is at most the in-sample L2O optimum plus ε Lip(ℓ)\varepsilon\,\mathrm{Lip}(\ell), and at most the worst-case optimal value of OPT-PEP. To clarify its role, the revised paper states Theorem 2 as Corollary 1.1 of Theorem 1.

[B] Algorithm classes, adaptive methods, and experiments

We thank the reviewer for weighing the framework itself, and agree that these points are only partially addressed.

Adaptive methods. Appendix E.4 compares the learned schedules with backtracking line search. In logistic regression, DR-L2O has a lower mean test loss than backtracking at every horizon, in and out of distribution. In LASSO, backtracking is better per iteration, but each of its iterations can use extra matrix-vector products. At an equal budget of 30 products, DR-L2O has a lower mean loss in distribution (8.9⋅10−28.9\cdot10^{-2} vs. 9.9⋅10−29.9\cdot10^{-2}) and out of distribution (0.820.82 vs. 1.771.77) (Figure 14). We still do not claim that fixed schedules replace adaptive methods in general-purpose solving (Section 6). Learning the parameters of adaptive rules is harder. The PEP formulations of exact line search and Polyak steps encode the rule through conditions on the iterates, not through step-size variables, so they leave no coefficient to learn. We leave this to future work.

Algorithm classes. The linear span condition of Assumption 1 covers FGM, ISTA, and PDHG in our experiments. The LASSO experiment also compares with ALISTA, a learned method with a different structure. At K=15K=15, DR-L2O has a lower mean loss than ALISTA in and out of distribution.

Experiments. In response to Reviewer eGbo, the new Appendix E.5 varies the training size from N=100N=100 to N=2000N=2000. The out-of-distribution advantage of DR-L2O over L2O persists at every NN.

We are glad to elaborate on any of these points.

Reviewer_7sDjOpenReview ↗

Response by Reviewer 7sDj

Hi,

I thank the author for the response. Here are some thoughts:

(1) I saw that you changed something in the revised draft. Next time, please mark it in red so that we, the reviewers, can see what happened.

(2) Second, I saw that the authors provide a new statement for Theorem 1. Ostensibly, it looks like the authors provide a tighter bound that removes the vacuousness on KK, but on closer inspection, it feels like sweeping dust under the rug. Concretely, the form of the guarantees fundamentally changed: (1) previously, the bound is something like: “there exists ϵ\epsilon such that for any distribution PP”, but (2) now it is: for any distribution PP, there exist c1,c2c_1, c_2 depending on PP. The issue is that we do not know c1c_1, c2c_2, nor is it quantifiable. It is not right for a “certificate”, as how would I know if, say, 1000 exceeds c1log⁡4/δc_1 \log 4/\delta or whether ϵ\epsilon exceeds c2log⁡log⁡(4/δ)/Nc_2 \log \sqrt{\log (4/\delta)/N}.

The new statement does not make sense to me. I hope that the authors know about this difference and realize the issues. For now, I think it is just better to present it as a pure optimization paper, and no need to incorporate learning theory there if it does not help.

Due to this change, I unfortunately have to reduce my confidence score to 1 (I will be reasonable and keep the score 3). Good luck with the submission.

AuthorsOpenReview ↗

Response to Reviewer 7sDj

We thank the reviewer for the follow-up.

(1) Highlighting. We have uploaded the revision with all changes relative to the submission highlighted in red (see our general comment).

(2) The two guarantees. We agree that the revised Theorem 1 and the submitted one are different kinds of statements, and we should have said so more directly.

  • Containment (submitted Theorem 1, now Proposition 6 in Appendix C.4). The radius is of order N−1/qN^{-1/q}. Its constants depend on P\mathbb P only through qq and a bound on the support of the lifted data. This bound follows from the compact support of the problem data and of Θ\Theta. No other knowledge of P\mathbb P is needed.
  • Revised Theorem 1. The radius is of order N−1/2N^{-1/2}, but the constants depend on P\mathbb P through the critical radius ρcrit\rho_{\mathrm{crit}}, which cannot be computed from samples. This result describes how the sufficient radius scales with NN. It is not a computable certificate. Section 4.1 states this right after the theorem:

    "The constants depend on the true distribution and can grow exponentially in KK, so neither threshold in (4) can be computed from the samples."

Both results are in the paper, and they trade off. The first needs only a support bound, but suffers the curse of dimensionality, which cannot be avoided in general (Weed and Bach, 2019). The second has a rate in NN that does not depend on KK, at the price of constants that depend on unknown properties of P\mathbb P and can grow exponentially in KK. The DRO literature has the same tradeoff: compare the measure-concentration guarantees of Mohajerin Esfahani and Kuhn (2018) with the N−1/2N^{-1/2} guarantees of Gao (2023) and Le and Malick (2025).

In our experiments neither radius is used directly. As in the submission, we select ε\varepsilon by cross-validation.

The revised PDF now states this difference explicitly in the discussion of Theorem 1 in Section 4.1.

References: Mohajerin Esfahani and Kuhn (2018), Gao (2023), Le and Malick (2025), Weed and Bach (2019).

Comments on the paper

2 comments
AuthorsOpenReview ↗

Common response to all reviewers

We thank the reviewers and the Area Chair. This comment addresses the rate of Theorem 1, raised in all three reviews (7sDj A1, RGS4 W2, eGbo W2). The OpenReview pdfdiff shows all changes.

Finite-sample guarantee: rate of Theorem 1 in the horizon KK

All three reviews note that the submitted Theorem 1 suffers from the curse of dimensionality: it needed a radius of order N−1/qN^{-1/q}, where qq is of order K2K^2. We agree, and the revised Theorem 1 now has a radius of order N−1/2N^{-1/2} for each fixed horizon.

Why the submitted rate was N−1/qN^{-1/q}. The submitted theorem chose the radius so that the empirical Wasserstein ball contains the lifted true distribution, uniformly over θ\theta. Containment rests on measure concentration (Fournier and Guillin, 2015), whose radius scales as N−1/qN^{-1/q} in the dimension qq of the lifted data (G,F)(G,F). This rate cannot be improved in general: when the lifted distribution has a density on Rq\mathbb R^q, W1(P^Nθ,Pθ)≳N−1/qW_1(\hat{\mathbb P}_N^\theta,\mathbb P^\theta)\gtrsim N^{-1/q} (Weed and Bach, 2019).

The revised Theorem 1. We now bound the true risk by the DRO risk directly, following the exact generalization results of Azizian et al. (2023) and Le and Malick (2025). To keep the bound uniform in θ\theta, we apply their result once on a common space of algorithm trajectories θ↦Aθ(z)\theta\mapsto\mathcal A_\theta(z), instead of separately on each lifted space Ξθ\Xi^\theta. This needs a new assumption.

Assumption 3. (i) z↦Aθ(z)z\mapsto\mathcal A_\theta(z) is measurable for every θ\theta in a countable dense subset of Θ\Theta. (ii) For every θ∈Θ\theta\in\Theta, P(ℓ(Aθ(z))=max⁡Z∈Ξθℓ(Z))<1\mathbb P\big(\ell(\mathcal A_\theta(z))=\max_{Z\in\Xi^\theta}\ell(Z)\big) < 1.

Theorem 1 (revised). Under Assumptions 1–3 (and Assumption 4 for proximal methods), there exist constants c1,c2>0c_1,c_2 > 0, depending on the algorithm class and P\mathbb P but not on NN or δ\delta, such that for every δ∈(0,1)\delta\in(0,1), PN(R(θ,P)≤Rε(θ,P^N) for every θ∈Θ)≥1−δ\mathbb P^N\Big(\mathcal R(\theta,\mathbb P)\le\mathcal R_\varepsilon(\theta,\hat{\mathbb P}_N)\ \text{for every }\theta\in\Theta\Big)\ge 1-\delta whenever N>c1log⁡(4/δ)N > c_1\log(4/\delta) and ε>c2log⁡(4/δ)/N\varepsilon > c_2\sqrt{\log(4/\delta)/N}.

The sufficient radius is of order N−1/2N^{-1/2}, and KK enters only the constants (Appendix C.3). Theorem 2 (now Corollary 1.1) is restated under the same conditions. The constant c1c_1 is proportional to 1/ρcrit21/\rho_{\mathrm{crit}}^2, where the critical radius ρcrit\rho_{\mathrm{crit}} of Le and Malick (2025) is the expected distance from a random trajectory to the trajectories that attain the worst-case loss. Assumption 3(ii) excludes parameters at which the algorithm attains its worst-case loss almost surely, which makes ρcrit\rho_{\mathrm{crit}} positive.

What remains. The constants can grow exponentially in KK, since θ↦Aθ(z)\theta\mapsto\mathcal A_\theta(z) composes KK Lipschitz maps. They also depend on the unknown distribution, so we still select ε\varepsilon by cross-validation. Guarantees of this type share both features: the N−1/2N^{-1/2} radii of Gao (2023), Azizian et al. (2023), and Le and Malick (2025) have distribution-dependent constants, and generalization bounds for deep networks grow with the product of the layers' Lipschitz constants (Bartlett et al., 2017). Improving these constants is not the goal of this paper. The new Remark 6 extends Theorem 1 to test distributions within ε−O(N−1/2)\varepsilon-O(N^{-1/2}) of P\mathbb P (Le and Malick, 2025, Theorem E.1). Propositions 6 and 7 (containment, in the appendix) need no nondegeneracy and cover shifts of any size, but only within ε−O(N−1/q)\varepsilon-O(N^{-1/q}).

Changes in the paper. Section 4.1 (Assumption 3, Theorem 1), Corollary 1.1 (formerly Theorem 2), Appendix C.3 (new: Theorem 1 proof, Remark 6), Appendix C.4 (Propositions 6–7), Appendix A.3 (finite-sample DRO guarantees).

References

  • Azizian, Iutzeler, and Malick (2023). Exact generalization guarantees for (regularized) Wasserstein distributionally robust models. NeurIPS. arXiv:2305.17076.
  • Bartlett, Foster, and Telgarsky (2017). Spectrally-normalized margin bounds for neural networks. NeurIPS. arXiv:1706.08498.
  • Fournier and Guillin (2015). On the rate of convergence in Wasserstein distance of the empirical measure. PTRF. arXiv:1312.2128.
  • Gao (2023). Finite-sample guarantees for Wasserstein distributionally robust optimization: breaking the curse of dimensionality. Operations Research. DOI.
  • Le and Malick (2025). Universal generalization guarantees for Wasserstein distributionally robust models. ICLR. arXiv:2402.11981.
  • Weed and Bach (2019). Sharp asymptotic and finite-sample rates of convergence of empirical measures in Wasserstein distance. Bernoulli. PDF.
AuthorsOpenReview ↗

Revised manuscript updated with highlighted relative changes from original manuscript

We have uploaded a revised manuscript with changes relative to the original submission highlighted in red. This update adds highlighting only; the manuscript content is unchanged from the previously uploaded revision. We apologize that the changes were not highlighted earlier, and thank Reviewer 7sDj for pointing this out.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.