Combining Analytical Smoothing with Surrogate Losses for Improved Decision-Focused Learning
predict-then-optimize;decision-focused learning;contextual stochastic optimization;surrogate loss
Yes
No ethics review needed.
See suggested relevant literature that you may wish to cite in Section 3.1 (lines 136-147):


- [Berthet 2020] *Learning with Differentiable Perturbed Optimizers*.
- [Blondel 2020] *Fast differentiable sorting and ranking*
- [Jang 2016] *Categorical Reparameterization with Gumbel-Softmax*.
- [Peterson 2024] *Generalizing Stochastic Smoothing for Differentiation and Gradient Estimation*
- [Stewart 2023] *Differentiable Clustering with Perturbed Spanning Forests*.
- [Peterson 2024] *Differentiable Top-k Classification Learning*

From my limited understanding, it appears [Berthet 2020] addresses some of the problems discussed in this paper.
The paper is well written, with a good structure and presents the mathematics in a clear and coherent way to the reader. The proposed minimization of a surrogate function (Sections 3 & 4) is well reinforced with the experiments section, and the motivations in Section 5 are pertinent for such methods to be deployed at scale in the future.
The paper concerns itself with combinatorial optimization (CO) problems, in the predict-then-optimize (PtO) regime.  The authors advocate that two main approaches are used to train ML models to minimize downstream CO error (Decision Focused Learning):

1. Minimizing a differentiable (convex) surrogate function, (instead of the regret).
2. Smoothing the problem to a PQ, and minimizing this proxy instead.

The authors argue that whilst the latter is differentiable, its gradient is zero almost everywhere, except at transition points. The paper suggests that minmizing a surrogate loss even after smoothing, and provides supporting empirical evidence (in the form of toy data sets) in addition to the presented theory.
Whilst the paper is well written, and produces a coherent argument, I am reluctant to accept on contribution grounds. From what I can see, the majority of the paper is pulling together prior works, with limited novel contribution; (please note I am new to this exact line of research and could be missing something here, hence my low confidence score). 

More precisely, a large portion of the paper is compiling prior problems / works, the surrogate losses in 3.2.1 and 3.2.2 are from existing works, and the experiments (whilst nice and supporting the argument), are toy-experiments and with little differing the cited literature. This should not detract from the papers clear strengths, and hence I politely suggest further contribution could be added either via i) further experimentation ii) novel theory / mathematics for surrogates  (or novel surrogates), which would render the paper acceptable to the conference upon resubmission.
Yes
No ethics review needed.
Please see the questions in weakness.
The paper has the following strengths:
+ The paper provides a good summary on the existing works of DFL for combinatorial optimization.
+ The paper propose to combine the methods of smoothing the cost and using a surrogate loss and apply DYS-Net to solve the scalability issue.
+ Numerical results on common DFL benchmarks are given.
This paper studies decision-focused learning (DFL) for combinatorial optimization problems. The authors summarize the previous methods of DFL for combinatorial optimization.  To overcome the challenges, previous works either employ a differentiable surrogate loss or tuning the combinatorial optimization to a differentiable mapping. However, the authors point out that the derivative remains nearly zero for a large region by existing methods. To address this issue, the authors combine both approaches of smoothing the cost function and using a surrogate loss. The authors verified the performance of the proposed method by four DFL benchmarks.
The paper can be improved in the following aspects.
- The paper argues that the derivative remains nearly zero for a lot of combinatorial problems but this argument is not verified. It would be better if the authors can give some illustrations based on some examples.
- The authors propose to combine the two existing methods of DFL for combinatorial optimization. However, the combination looks straightforward. Can the authors present if there are some technical challenges to combine the two methods?
- The authors apply DYS-Net in [D. McKenzie 2024] to address the scalability of DFL. However, it is unclear about the novelty about applying DYS-Net here. Is it just an application?
- The empirical results will be more convincing if more ablation empirical studies are given.
Yes
No ethics review needed.
1. The proof on page 5 assumes that there exists choices of $\hat{\mathbf{y}}$ such that $\mathcal{L}\_{SCE}(\mathbf{v}^*(\hat{\mathbf{y}}), \mathbf{y})$ is 0 (such as $\hat{\mathbf{y}} = \mathbf{y}$). However, in most cases this is not true if your hypothesis class is misspecified or  if $\mathbf{y} = \mathbb{E}[\mathbf{y}] + \epsilon$ where $\epsilon$ is independent noise. Thus, how important is this result practically? Is often the case your surrogate loss equal or below 0? Also, in general, the surrogate loss is summed over samples, i.e. $\sum_{i=1}^n \mathcal{L}_{SCE}(\mathbf{v}^*(\hat{\mathbf{y}}_i), \mathbf{y}_i)$. It maybe beneficial to present the result relative to the empirical task-based loss.

2. What is the motivation for applying the QP smoothing to SPO+? SPO+ is already convex so it doesn't have any vanishing gradient issues. This seems to also be confirmed numerically since the QP smoothing does not provide significant performance gains when applied to SPO+

3. How does QP smoothing tune $\mu$ in the quadratic term? Presumably larger $\mu$ has more smoothing, but is more different from the solution of the original problem. Does this affect performance and how does affect the computation time?

4. Is there a reason DYS-net is only applied to SCE? Can DYS-net be applied to SPO+ as well or other surrogate losses that require solving an LP?

5. Is there a reason why you don't consider other approaches for eliminating zero gradients issues such as adding a regularizer directly to the surrogate loss or combining MSE loss with the surrogate loss? Both solutions would seem to produce "better" gradients.
The paper highlights two popular decision-focused learning approaches, smoothing and surrogate losses, and points out reasonable drawbacks of learning with both approaches. It then shows how combining the two approaches may potentially help address weaknesses found in the two approaches. They also show how recently proposed approaches for making DFL more scalable can be combined with surrogate losses to improve scalability and the quality of the learned decisions. They then justify their claims with numerical experiments of a popular set of benchmarks found in PyEPO which highlights some robustness.
The paper studies decision-focused learning (DFL) for tasks where the parameters appear linearly in the objective. Specifically, the paper proposes applying QP smoothing to existing decision-focused learning surrogate losses such as SPO+ and the self-contrastive estimation (SCE) loss. They motivate this application by pointing out that the typical approach of applying smoothing directly to the non-convex task loss may still have vanishing gradients, which makes optimizing the decision-focus loss challenging. In addition to smoothing, the paper also studies recently proposed approaches to making DFL more scalable. For both approaches, the paper provides numerical experiments demonstrating the efficacy of applying more heuristic approaches.
The paper's weaknesses can be broken down into two categories: i) issues related to theoretical justification and ii) issues with the numerical experiments. 

Theoretical Issues
- The theoretical justification issues stem from the main argument of the paper--that smoothing task loss directly may not solve a zero-gradient issue which hampers gradient-based optimization techniques. The paper seems to claim that the benefit of combining smoothing and surrogate losses addresses this problem and produces losses with "better" gradients. However, the surrogate losses the paper proposes combining with smoothing are inherently convex, so it is unclear why smoothing would be beneficial. The authors could address this issue by analyzing the newly proposed surrogate loss directly. Perhaps they can verify whether the new surrogate loss formed by combining QP smoothing is convex or non-convex. In the latter case, it may make sense why "better" gradients may be beneficial for the surrogate loss. For the former, perhaps it suggests that QP smoothing adds some form of regularization instead providing better gradients. It may also be helpful to then compare the approach with combining surrogate losses directly with regularizers instead of replacing non-smooth components with smoothed components. 

- On page 5 there is a proof, but no formal statement. Adding a formal statement that is proved as a lemma or proposition would improve the presentation and precision of the section. 

Numerical Experiment Issues
- The overall more extensive numerical experiments could be performed. The recently accepted work to NeurIPS [1] has proposed a new smoothing approach that outperforms surrogates such as SPO+ and SCE for misspecified settings. Their numerics show this is true especially for settings where a zero regret policy can be learned. For example, in their experiments they propose a simple weighted classification problem and a shortest path problem where the optimal decision can always be learned from the context using a linear plug-in model. Including these experiments would be helpful since it could be implied that directly applying QP smoothing to the task loss would also perform well in these settings. This would further highlight the benefits or drawbacks of combining smoothing with the surrogate losses. 

-The numerical experiments could also be expanded to include other methods such as the proposed surrogate loss in [1] and other approaches such as combining regularizers with the surrogate losses and the QP smoothed task loss. The latter approach would also help eliminate zero-gradient issues since the gradient of the regularizer may be non-zero almost everywhere. 

--------
[1] Huang, Michael, and Vishal Gupta. "Decision-Focused Learning with Directional Gradients." arXiv preprint arXiv:2402.03256 (2024).
Yes
No ethics review needed.
1. Given that current exact solvers like Gurobi are highly efficient for solving QP problems, have you considered or conducted any comparisons between DYS-Net and other exact QP solvers in the forward pass?
2. Could the authors offer more insights or practical guidelines on choosing $\mu$?
3. Does DYS-Net need to be pre-trained before starting the main PtO training process? If so, could the authors provide some description and training time?
4. To improve reader comprehension, providing more details on DYS-Net would be highly beneficial.
1. **Novelty:** This paper first introduces a combination of smoothing techniques and a surrogate loss function within the predict-then-optimize framework for combinatorial optimization.
2. **Efficiency:** Solving the optimization problem is often the computational bottleneck in PtO. This paper demonstrates the advantages of using DYS-Net, a differentiable solver significantly reducing training time without compromising decision quality.
3. **Clarity:** The paper is well-organized and provides clear and thorough explanations. Additionally, visualizations and examples clarify the results and effectively support the theoretical insights.
In the predict-then-optimize framework, this paper introduces an approach that combines smooth optimization, which transforms the solver into a smooth and differentiable form, with a surrogate loss that approximates regret. This combination allows the learning model to maintain meaningful gradient flow even in flat regions, enhancing stability during training. Additionally, the paper leverages DYS-Net, a fast differentiable solver, to significantly reduce training time while preserving decision quality.
1. **Lack of Theoretical Supports:** While the QP-based relaxation for ILP has shown promise in experimental results, the paper lacks a theory supporting the effectiveness of this relaxation approach. (I acknowledge that providing such theoretical support is challenging.)
2. **Lack of Comparison with Related Speed-Up Techniques:** While one of the main contributions of this paper is its focus on enhancing solver speed, it does not compare its approach with other established methods that also aim to accelerate predict-then-optimize (PtO) processes by leveraging ILP relaxations and caching strategies. For instance, 'Differentiation of Blackbox Combinatorial Solvers' and 'Pyepo: A PyTorch-Based End-to-End Predict-Then-Optimize Library for Linear and Integer Programming' utilize LP relaxations of ILP problems as an oracle to speed up solution times. Additionally, 'Contrastive Losses and Solution Caching for Predict-and-Optimize' introduces solution caching to improve efficiency. Comparing this paper’s approach with these alternative acceleration methods, rather than just focusing on ILP solvers, would provide a more comprehensive evaluation of the proposed method’s effectiveness in reducing computation time.
3. **Insufficient Scalability Demonstration:** Although the paper emphasizes computational efficiency, the experiments are conducted on relatively small instances (e.g., 11-node TSP). This may limit the understanding of the scalability for larger combinatorial problems. 
4. **Missing Hyperparameter Details:** The paper does not provide explicit details on specific hyperparameters used for training, such as learning rate, batch size, or optimizer configurations. Thus, it is difficult for readers to reproduce the results. Most critically, there is a lack of information on the smoothing parameter $\mu$, which directly influences gradient flow and solution quality.
Yes
No ethics review needed.
1. The paper would benefit greatly from a thorough revision to enhance clarity and readability. Please see my first comment in the weaknesses section. 

2. Can you provide more theoretical grounds for your claims? Specifically around the issues of the gradients for the smoothed solvers. And why does your method resolve these issues? 

3. Please provide more details on the experimental results. Again, please see my comments in the weakenesses section. 

4. Can we see some experiments about the behavior of the gradients? Especially if you cannot provide theoretical results. For example, how does the magnitude of the gradients for your proposed approach compare with those of existing methods. Can we also see results on accuracy/regret as a function of the number of training epochs used. 

5. Ideally, the same base model is used across all experiments and only the training method changes. That is, use the same base neural network and optimization solver for each dataset. Then, use each training method (smoothed, surrogate loss, your proposed combination). This way, everything is even across experiments for the same dataset, instead of using for instance both CVXPYlayers and DYS-Net etc.
The ideas are simple and can be easily implemented by practitioners. You present a good outline of past work and background on existing methods. The experimental results are promising as well and show improvements of your proposed method against some of the main existing literature.
This paper considers a new training method for decision-focused learning, also known as end-to-end learning or joint predict-then-optimize. They explain two existing methods to approach these problems: surrogate loss approaches such as the smart predict the optimize (SPO) and contrastive loss as well as smoothing methods. The authors propose to combine the two methods, minimizing a surrogate loss with a smoothed solver. They run experiments on some optimization tasks like shortest path, knapsack and TSP.
The exposition and contribution is not very clearly expressed in the paper. As a starting point, it is difficult to find where your proposed method is written. I'm guessing your proposed approach is to solve an empirical version of problem (2). The actual empirical problem is never introduced. I also assume that, given features $x$, you would construct a model to make predictions $f(x)$ of $y$. This is also not explained well. Finally, you solve the empirical problem by gradient descent using (12). All of this needs to be made clear and cohesive. I would suggest a section to explain the full problem and proposed method. 

For example, the statement "smoothing addresses the non-differentiability at the transition points, but the derivative dv⋆( ˆy)
d ˆy still remains zero far from these points" is not well-supported. The illustration in Figure 1b that the authors point to does not give adequate support for these claims as a single low-dimensional example does not generalize. Similarly, your subsection "A deep dive into the gradient landscape" does not adequately explain the behavior of your approach. Why should it generalize to more complex problems? Please provide some theoretical analysis on the gradient behavior in higher dimension. Alternatively, you can also provide computational results on gradient behavior for various optimization tasks and higher dimension.

I'm a little confused why section 5 exists. This is only explaining the methods used in a different paper to implement your proposed method. It is not a contribution of your work, as far as I can tell. It may be better to place this discussion in the appendix, if at all. Moreover, the work in [1] may be a good additional reference as it seems to be a more generalized version of the work you cite.

Finally, for the experiments, please give more details on the problems addressed. For example, provide information about:
    1. Problem sizes for each experiment
    2. Exact mathematical formulations of the optimization problems
    3. Architecture details of the neural networks used
    4. Hyperparameters for both the models and optimization algorithms
    5. Data generation process and dataset statistics 


[1] Cristian,  Rares,  et al.  "End-to-end learning for optimization via constraint-enforcing approximators."  AAAI 2023
We propose minimizing surrogate losses instead of a task loss like regret for decision-focused learning, even when a differntiable optimization layer is used, due to the fact that the derivative of regret remains approximately zero almost everywhere.
@inproceedings{
anonymous2024combining,
title={Combining Analytical Smoothing with Surrogate Losses for Improved Decision-Focused Learning},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=ln6QnzBd8o},
note={under review}
}
Many combinatorial optimization problems in routing, scheduling, and assignment involve parameters such as price or travel time that must be predicted from data; so-called predict-then-optimize (PtO) problems. Decision-focused learning (DFL) is a family of successful end-to-end techniques for PtO that trains machine learning models to minimize the error of the downstream optimization problems. For each instance, this requires computing the derivative of the optimization problem’s solution with respect to the predicted input parameters.
Previous works in DFL employ two main approaches when the parameters appear linearly in the objective: (a) using a differentiable surrogate loss instead of regret; or (b) turning the combinatorial optimization problem into a differentiable mapping by smoothing the optimization to a quadratic program or other smooth convex optimization problem and minimizing the regret of that. We argue that while smoothing makes the optimization differentiable, for a large part, the derivative remains approximately zero almost everywhere, with highly non-zero values near the transition points. To address this plateau effect, we propose minimizing a surrogate loss even after smoothing. We experimentally demonstrate the advantage of minimizing surrogate losses instead of the regret after smoothing across a series of problems. Furthermore, we show that by minimizing a surrogate loss, a recently developed fast, fully neural optimization layer matches state-of-the-art performance while dramatically reducing training time up to five-fold. Thus, our paper opens new avenues for efficient and scalable DFL techniques.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
predict-then-optimize decision-focused learning contextual stochastic optimization surrogate loss
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/e726c4190fa9cec7443ac342d375d7997cf6f545.pdf
optimization
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
Combining Analytical Smoothing with Surrogate Losses for Improved Decision-Focused Learning
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission