- 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
- Simple idea: a single parameter, the radius, controls robustness and interpolates between data-driven L2O and worst-case PEP.
- Clean theory: the method is presented with mathematical rigor and no hidden heuristics.
- The presentation is mostly easy to follow.
Critical weaknesses
- 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.
- 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.
-
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.
-
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
-
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?
-
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?
-
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?
-
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
[W2 & Q2] Cost of solving an SDP at every SGD step
Yes: for the same , 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 and 7.4 s at , 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 and 57 s at , 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 and about eight hours for TV inpainting at . Second, the SDP size depends only on and the mini-batch size. It does not depend on the training-set size 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 . Replacing each PSD constraint in (DRO-PEP-D) by an SDD constraint gives an SOCP, since the norm constraint is already a second-order conic constraint. Using DD constraints and the stronger norm constraint 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 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 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 , and their ordering is the same at every . In distribution, L2O has the lower test loss at every , as expected, since it fits the training distribution. Out of distribution, DR-L2O has the lower test loss at every and horizon. In logistic regression, its mean loss is about 15 to 400 times smaller. In LASSO, L2O diverges on the shifted instances at and , with mean losses between and , 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 .
[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 . OPT-PEP uses no data so there is no cross-validation there.
Theorem 1 certifies the in-distribution risk for every once , 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 rate: if also and , the DRO risk bounds the expected loss under every test distribution whose algorithm trajectories lie within of those under . Proposition 7 covers shifts of any size and needs no nondegeneracy, but its margin is , where the containment radius of Proposition 6 is of order . 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 -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.
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:
[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-θ guarantee made uniform over a cover of Θ, so it kept their N−1/q rate.
The revised Theorem 1 replaces this argument, which moves to Proposition 6 in Appendix C.4. It lifts each instance z to its trajectory θ↦Aθ(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 θ. The sufficient radius is of order N−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 θ. Its support set Ξθ is cut out by interpolation conditions polynomial in θ, 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/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/2 rate with a moving support set, through one fixed space of trajectories that evaluation at θ maps onto Ξθ (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 Ξθ moves with θ. The reduction above removes this dependence by lifting each instance to its whole trajectory. Evaluation at θ is 1-Lipschitz, so the bound on the trajectory space transfers to each Ξθ (Lemma 7).
[W2] Trade-off between the horizon K and the sample size N
On the dependence on K through N−1/q: the revised Theorem 1 bounds the true risk directly, with a radius of order N−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ˉ of θ↦Aθ(z) and the bound on the iterates can grow exponentially in K, as for any composition of K Lipschitz maps (Appendix C.1), and the critical radius ρcrit can shrink; both enlarge the constants c1 and c2. More data thus always tightens the certificate at rate N−1/2, and a longer horizon raises the constant in front of it.