We propose a novel family of decision-aware surrogate losses, called Perturbation Gradient (PG) losses, for the predict-then-optimize framework. The key idea is to connect the expected downstream decision loss with the directional derivative of a particular plug-in objective, and then approximate this derivative using zeroth order gradient techniques. Unlike the original decision loss which is typically piecewise constant and discontinuous, our new PG losses is a Lipschitz continuous, difference of concave functions that can be optimized using off-the-shelf gradient-based methods. Most importantly, unlike existing surrogate losses, the approximation error of our PG losses vanishes as the number of samples grows. Hence, optimizing our surrogate loss yields a best-in-class policy asymptotically, even in misspecified settings. This is the first such result in misspecified settings, and we provide numerical evidence confirming our PG losses substantively outperform existing proposals when the underlying model is misspecified.
Paper
Similar papers
Peer review
Summary
The paper introduces a new family of surrogate losses to the DFL with linear costs, called perturbation gradient losses (PG loss). It provides theoretical analysis to bound the approximation errors and regret bounds and uses extensive experiments to demonstrate the advantages of the proposed method.
Strengths
- The proposed loss is more efficient than the standard DFO loss. It only requires the computation of the optimal decision variable without the need for implicit differentiation through $\hat{\pi}(t)$. - The approximation error of the surrogate functions decreases as the number of samples increases, which is advantageous for large-sample applications. - In the numerical experiment section, the PG losses perform very well even in the misspecification case.
Weaknesses
- The (sub)differentiability of the PG loss is not well-established. In Line 172, the differentiability is doubtful. I don’t think the subgradient is well defined when $\hat{\pi}$ is not unique. The paper should make more efforts to develop the theory rigorously and in writing. - In Line 148, the directional derivative is not well-defined. If $V(t)$ is non-smooth, you should take infimum over all the $\hat{\pi}(t)$. - The paper presents a continuous relaxation of the DFL objective, with the error bounded by the finite difference error h. However, the resulting problem is still nonconvex and nonsmooth, which may not be efficiently solved in theory. It seems more effective to use direct smoothing by random perturbation or by adding a regularization term (e.g., [30]). I encourage the authors to compare their approach with other smoothing methods in theory. - Both experiments are for discrete decision variables and simulated data. The paper does not sufficiently address the performance of the proposed method when decisions are continuous.
Questions
- Lemma 2.2 Can you develop the result when $\ell_h^b$ is nonsmooth? - Line 176, what is $Y_j$?
Rating
5
Confidence
3
Soundness
2
Presentation
2
Contribution
3
Limitations
Not applicable
Proof for Eq 4
Thank you for your response! We are glad to hear about the positive feedback on our new empirical results. We apologize for the confusion about the blog post. The citation we would use in a galley proof is Prop B.22, *Bertsekas DP. Nonlinear Programming. 2nd ed. Athena Scientific; 1999.* We provided the website for the rebuttal period as it provides the same version of Danskin's theorem as the above textbook, but the textbook might not be available to everyone. In particular, the blog post copies the result nearly verbatim from the textbook, modulo some light formatting. (The blogpost also cites the textbook above.) **Line by line proof of Eq. (4)** To more clearly match the notation of the reference, first rewrite $V(t) \equiv \min_{z \in \mathcal Z} t^{\top}z = - \max_{z \in \mathcal Z} -t ^\top z$, and define $\phi(t, z) \equiv -t^\top z$ and $f(t) \equiv \max_{z \in \mathcal Z} \phi(t, z)$. Then with these new notations, $V(t) = -f(t)$ and $\hat \pi(t) \in \arg \max_{z \in \mathcal Z} \phi(t, z)$. (We provide the transformation because we are dealing with a "min" and the theorem is for a "max.") Note $\mathcal Z$ is a compact set, $\phi(t, z)$ is convex in its first argument, and $t \mapsto \phi(t, z) = -t^\top z$ is (everywhere) differentiable in $t$ for any $z$ because it's just a linear function. Let us first consider the case where there is a unique maximizer at $t_0$, i.e., $\hat \pi (t_0)$ is unique. Recall that $t \mapsto \phi(t, z)$ is differentiable in $t$ for all $z$, and in particular, is differentiable in $t$ at $z = \hat \pi(t_0)$. By part 3 of the blog post (equiv. the statement "If Z(x) consists of a unique point $\bar z \ldots$ " in the Bertsekas textbook), we have that $ \nabla f(t_0) = \frac{\partial \phi(t, \hat \pi(t_0) ) }{\partial t} = -\hat \pi(t_0), $ from the definition of $\phi$. Then, since $V(t) = -f(t)$, we conclude that $\nabla V(t_0) = - \nabla f(t_0) = \hat \pi(t_0)$ for any $t_0$ where $\hat\pi(t_0)$ is the unique optimizer. Hence the map $\lambda \mapsto V(t_0 + \lambda y)$ is differentiable (in $\lambda$), and by the chain-rule, $\frac{\partial}{\partial \lambda} V(t_0 + \lambda y) = \langle \nabla V(t_0 + \lambda y), \frac{\partial}{\partial \lambda } (t_0 + \lambda y) \rangle = y^\top \nabla V(t_0 + \lambda y) = y^\top \hat \pi(t_0 + \lambda y)$. Evaluating at $\lambda = 0$ proves Eq. 4 in this case. We now prove the statement when $\hat \pi (t_0)$ is not the unique maximizer. Recall again that $t \mapsto \phi(t, z) = -t^\top z$ is differentiable in $t$ for all $z$, and the derivative $\frac{\partial \phi}{\partial t} = -z$ is continuous in $z$ for all $t$ (because it's just a linear function). Hence, by part 4 of the blogpost (equiv. part b of the Bertsekas Textbook) the set of subgradients of $f(t_0)$ is $\partial f(t_0) \ = \ \text{conv} \\{ \frac{\partial \phi(t, z)}{\partial t} \mid_{t = t_0} : z \text{ is a solution to } \max_{z \in \mathcal Z} \phi(t_0, z) \\} \ = \ \text{conv} \\{ -z : z \text{ is a solution to } \max_{z \in \mathcal Z} \phi(t_0, z) \\} .$ Thus, since $\hat \pi (t_0) \in \arg\max_{z \in \mathcal Z} \phi(t_0,z)$, we have $-\hat \pi (t_0)$ is a subgradient of $f(t_0)$. This implies that for any $\lambda$, $ f(t_0 + \lambda y) - f(t_0) \geq -\lambda \hat \pi(t_0)^\top y$. Recalling $V(t) = -f(t)$ and multiplying by $-1$ shows, $ V(t_0 + \lambda y) - V(t_0) \leq \lambda \hat \pi(t_0)^\top y$, i.e., $\hat \pi(t_0)^\top y$ is a subdifferential of $\lambda \mapsto V(t_0 + \lambda y)$. This concludes the proof of Eq. 4.
Hi, thank you for the detailed reply. When V is nonsmooth, you showed $\hat{\pi}(t_0)^\top y$ is a subgradient, and the finite-difference (line 152,153) is approximating this value. But which $\hat{\pi}(t_0)$ is specifically chosen? As h converges to zero, the finite-difference must converge to a specific limit, and hence there must be a specific $\hat{\pi}(t_0)$. Should you consider the directional derivative where $\hat{\pi}(t_0)$ is the one that aligns with $y$ most?
Thank you for the positive signals and the new question. We apologize for editing this response; we discussed internally and think we now better understand the heart of your question. (If we still misunderstood, please accept our apologies. We are eager to clarify once we better understand the question.) How we currently understand your question is: Fix a $t_0$ such that $\hat \pi(t_0)$ is **not** the unique optimizer. Then, we have shown that $y^\top\hat \pi(t_0)$ is **a** subgradient of $\lambda \mapsto V(t_0 + \lambda y)$ at $\lambda = 0$. It's also clear that the finite difference $\frac{1}{h} (V(t_0) - V(t_0- hy))$ approximates **a** subgradient of this function at $\lambda = 0$. Why is it that these are the same two subgradients (since there are multiple subgradients)? In other words, why is it that $\lim_{h\rightarrow 0} \frac{1}{h} (V(t_0) - V(t_0 - hy)) = \hat \pi(t_0)^\top y$? This is an excellent and subtle question that highlights the role of Assumption 3.1 in our results. First, it is **not** the case that we can guarantee that $\lim_{h\rightarrow 0} \frac{1}{h} (V(t_0) - V(t_0 - hy)) = \hat \pi(t_0)^\top y$. This is a ``path-by-path" requirement that is very strong. Why is this not a problem for our results? Note, Eq. (4) is meant to be motivation (it does not occur as a formal theorem or in a proof). It illustrates the intuition behind our PG losses. The formal result is given in Lemma 3.2 (and subsequent results that build on it). The key idea is that although the above limit doesn't hold path by path, under Assumption 3.1, it **does** hold in expectation, i.e., $\lim_{h\rightarrow 0} \mathbb E[ \frac{1}{h}(V(f(X)) - V(f(X) - hY))] = \mathbb E[ \ell(f(X), Y)]$. (Lemma 3.2 actually proves a stronger statement by explicitly giving the rate.) Here the role of $t_0$ is played by $f(X)$ which is random. Holding in expectation is a weaker requirement, and since the ERM approximation concentrates at its true expectation uniformly (Thm 3.4 and Thm 3.7), it's enough that it holds in expectation. This of course raises an interesting question of whether one could make a stronger assumption than Assumption 3.1 and derive a path-by-path result. We have not explored this idea. Did we correctly understand your question? We're happy to clarify further however we can.
My main point is you can use the definition of the directional derivative of a convex function to find out the specific $\hat{\pi}(t_0)$, then the whole thing can go through. I don't understand why this is difficult. Although I am still a bit skeptical about the argument and proof of Lemma 3.2, the conclusion of Lemma 3.2 appears reasonable, as the nonsmooth point has a zero measure and when you do the integration, you should expect a smooth behavior.
Overall, I believe the paper's revision shows some improvement, and I am inclined to raise the score based on the updates. However, I still believe the authors need to put significant effort into making their paper more rigorous.
Summary
This paper considers a predict-then-optimize framework for solving contextual optimization problems, in particular for the case where the set of decisions is combinatorial or polyhedral, or when the loss is non-differentiable. They define a family of surrogate losses that connect the loss to the directional derivative of a plug-in function, and use zero-th order gradients to approximate the derivative. Simple numerical examples are provided.
Strengths
The paper is well written and considers a principled approach.
Weaknesses
The role of $h$ in the approximations of $\ell$ appearing in Theorem 2.1 should be made clear -- $\hat\ell^b$ and $\hat\ell^c$ have not been defined. Please give details of the proof of part c). The main weakness is that the method appears to work well on a very simple synthetic problem. The performance appears to deteriorate on a slightly more complex problem, and then no interesting example is provided. I feel that for this outlet, this is a major weakness and would like to see how the method performs on a real world and/or large-scale problem. There are a number of such examples in the cited supporting literature.
Questions
Can you please address the issues above?
Rating
5
Confidence
3
Soundness
3
Presentation
3
Contribution
3
Limitations
Limitations are not addressed. Potential negative societal impact is negligible.
Summary
This paper addresses the predict-then-optimize problem by proposing a new family of surrogate loss functions. The key motivation is derived from Danskin's Theorem, which connects the expected downstream decision loss with the directional derivative of a particular plug-in objective. This objective is then approximated using zero-order gradient methods. The paper includes numerical experiments conducted on both a synthetic environment and a shortest path problem.
Strengths
1. The paper is well-motivated. 2. The properties of the proposed surrogate loss are thoroughly derived. 3. Theoretical analysis shows that the approximation error of the proposed loss diminishes as the number of samples increases. Consequently, it can outperform existing surrogate losses even in misspecified settings.
Weaknesses
1. The experimental section of the paper is relatively weak. 2. While the proposed method performs well in a simple synthetic environment, it does not demonstrate a clear advantage over FYL and SPO+ in the shortest path problem. 3. More experiments are needed to illustrate the advantages of the proposed method in real-world scenarios.
Questions
1. How should the parameter h be selected in practice? Have you empirically studied how it affects performance? 2. In the shortest path experiment, why does FYL perform so well? Theoretically, the PG losses should be superior to FYL. Could you provide insights into this discrepancy?
Rating
5
Confidence
3
Soundness
2
Presentation
2
Contribution
2
Limitations
I would suggest the paper add a limitation section.
Summary
This paper proposes a family of "perturbation gradient" losses for Predict-than-Optimize (PtO) that, if optimized for, can lead to best-in-class performance, even under model misspecification. On the theoretical side, this paper provides risk bounds that build on past theoretical work in PtO + the literature on using perturbation-based approaches for estimating out-of-sample performance. Importantly, it shows that the excess risk goes to zero when the number of data points $n \to \infty$. On the empirical side, they show that their loss functions outperform others from the literature in one synthetic domain and perform comparably to other loss functions in one domain from a popular benchmark.
Strengths
* The paper identifies and addresses an important problem in the PtO literature--performance guarantees under model misspecification. * I'm not a theoretician, but the theoretical results seem non-trivial and relevant to practice. * On the empirical side, they compare to a reasonable set of baselines from the literature.
Weaknesses
I have reviewed this paper in the past, and my two major issues were (a) that it overclaimed and (b) it had weak empirical analysis. While the paper has improved significantly on both fronts, I still have some gripes: * _Regarding Claims:_ While the paper has added a paragraph about the approach's limitations in the introduction, I'm not sure that I understand it. My issue with the approach is that if the _true_ loss is non-convex in the policy parameters, it will be hard to optimize for, even in the limit of infinite data when $n \to \infty$. This isn't the same as the issue you describe for small $n$ in Figure 2(b), or even the statistical complexity issue of cleverly choosing $h$ as discussed in Section 3.2. It's that if the true loss $\ell(t(\theta), y)$ is piecewise constant, then for small $h$ the PG-loss $\hat{\ell}^b_h$ will indeed be close to $\ell$ but that means it will be close to piecewise constant and, as a result, hard to optimize for. The current theory assumes that you can optimize for $\hat{\ell}^b_h$ but not $\ell$, but that's a big assumption that should be discussed. Using the analogy of the ramp loss from the introduction, if your initial prediction is sufficiently far from $t = 0$, the gradient of the ramp loss will still be 0 (same as the $sgn$), and you won't be able to use first-order methods to learn a good model $\hat{f}$. Perhaps this is something that comes under your buckets of (a) the difficulty of optimizing for a "difference of convex functions" in the introduction or (b) the bias-complexity tradeoff in choosing $h$ that you allude to in the conclusions, but I couldn't immediately see the connection. Could you talk more about this? * _Empirical Evaluation:_ I appreciate that you have included $SPO+$ and $PFYL$ as baselines, and also added a PyEPO domain. However, the results aren't conclusive even under significant model misspecification (e.g., you do no better than PFYL in either case, even when PFYL has no guarantees under misspecification, and SPO+ does roughly the same for uniform noise). Given that you've implemented one domain, running tests on the other domains in the benchmark should be fairly easy. Have you run those experiments? What do they look like?
Questions
Could you address my comments in the weaknesses section?
Rating
7
Confidence
4
Soundness
4
Presentation
3
Contribution
3
Limitations
The paper does an okay job of addressing the limitations of the proposed approach.
Response to Rebuttal
Thank you for clarifying the theoretical contributions and adding new experiments. **While I still have a few questions, I will increase my score to a 7 and recommend acceptance.** I think that (even without the theoretical properties) the paper has proposed a novel predict-then-optimize surrogate and shown improved performance on (variants) of standard domains in the literature. This is the bar to which papers in this domain have been held in the past. As for my remaining questions/concerns: ### Experiments **[Q1]** Why didn't you run experiments on the other domains from PyEPO (knapsack and TSP) or even existing implementations of the Portfolio Optimization problem? I find this a bit confusing because it should have been easier than creating the new domains that you have presented in your paper. Additionally, it would allow us to compare the effectiveness of the proposed approach to a much larger set of surrogates, which have also been evaluated on these more standard datasets. Even if it seems like PGC doesn't really beat SPO+ or alternatives, it would be (IMO) useful to know. **[Q2]** How are the features generated in the new shortest path example? In the old version of the problem, the features for each edge seem to be generated independently (from a normal distribution). But if this were the case, I don't see how any model would be able to isolate the "safe" paths based on just the features. Also, I have run experiments on the portfolio optimization domain from [26, 32] and have never seen improvements as large as those you've found in your paper. I hope you release your code, and look forward to investigating this version of the problem in more detail! ### Theoretical Properties I think these clarifications are super useful, and I hope that they will be included in the final version of the paper. However, I still have some basic questions. **[Q3]** When you say: > "What we are trying to argue in our paper is that although optimizing our surrogate is NP-Hard (as it MUST be), even simple gradient descent algorithms recover very high-quality local minima that are suitable for applications." > "However, in practice, some NP-Hard problems admit algorithms that find high-quality solutions very efficiently for practical instances, and we argue our loss leads to one such problem." I don't understand how your theorems show this (although your experiments do). From my understanding, your theorems show that _if you can optimize the surrogate loss_ for some value/schedule of $h$, you will be able to optimize the true loss. However, it says nothing about being able to optimize for the surrogate with gradient descent, which seems to be critical to these arguments that you're making above. Am I misunderstanding something? Could you also link me to the theorem statement that shows: > One of the takeaways of our theoretical analysis is characterizing precise conditions and how large we can make $h$ (to minimize the chances of reaching a flat region) while still guaranteeing a good enough approximation to learn the best-in-class policy, and how this should scale with $n$. **[Q4]** When you say: > However, when we have $n$ data points, the empirical loss is only flat if we are more than away from ALL $n$ data points. Hence, for large $n$, our loss is unlikely to be flat in regions of high data density. This still does not guarantee that you will be able to optimize for the surrogate loss function. What stops gradient descent from reaching a local optimum in which you do better for the subset of points that have a non-zero gradient and do badly for those with zero gradients? **[Q5]** Also, when you talk about optimizing for the PG losses as solving a "difference in convex functions" problem, (based on my skimming the abstracts) the papers that you link seem to use some sort of clever smoothing to solve the problem. However, you don't seem to be smoothing your PG losses. Why can you still solve the optimization problem for PG losses, then?
Thank you for the positive feedback. To be clear (for future AC's that might be skimming): when you say "even without the theoretical properties," did you mean 1) That the empirical/methodological contributions merit publication on their own, and the theoretical contributions are "bonus" or 2) that you have some unresolved questions about the proof/statements of the theoretical results? If it's 2), please flag the questions for us and we are happy to address them. From our own viewpoint, we provide some of the first theoretical guarantees for best-in-class behavior in a misspecified setting using a surrogate that supports gradient descent, and we see this as an important contribution. **[Q1]** >Why didn't you run experiments on the other domains from PyEPO (knapsack and TSP) or even existing implementations of the Portfolio Optimization problem? .... We agree that more benchmarking is undoubteldy helpful. Our choice of experiments in the response document was determined by 1) space constraints 2) requests from Reviewers LgZs and CTUs for real data and 3) Computational time limits in the rebuttal period. We intend to present a full set of benchmarks in a journal version of the paper for researchers to use. More specifically, the PyEPO experimental set up for both knapsack and TSP is based on synthetic, random data. Given the other reviwer requests for real data, we thought this would add little to our (existing) synthetic data experiments. We *do* use a standard formulation of the portfolio optimization problem from [26]. We change the data set used to the Fama French dataset because we wanted a setting with high misspecification. Indeed, for the QuandlWIKI dataset from [26, Table 1], 2 Stage MSE does almost as well as the best decision-focused methods, suggesting (to us) that the dataset is close to well-specified. In other words, there's seemingly not a lot of "room" for *any* decision-focused method to shine. We conjecture this might be because for daily stock returns i) the time scale is short enough that yesterday's stock price is a good predictor for today's stock price ii) the various stocks are very highly correlated. By contrast, the longer timescale of the monthly Fama-French returns make predictions more difficult and the different asset classes makes the signal weaker. **[Q2]** > How are the features generated in the new shortest path example?... In the original shortest path problem [6, 29], each problem instance is generated with 5 features $\mathbf{X} \in \mathbb{R}^5$ drawn from multivariate normal distribution and edge weight $i$ is $f_i(\mathbf{X}) = \frac{1}{3.5^6} \left( (\frac{1}{\sqrt{p}}\beta_i^{\top}\mathbf{X} + 3)^6 + 1 \right)$ and $\beta_i \in \mathbb{R}^5$ are independently generated Bernoulli vectors. In the new experiment, we add a new feature so $\mathbf{X} \in \mathbb{R}^6$ and assume the new feature $X_6$ is drawn from a uniform distribution with support $[0,2]$. We modify $f_i$ for the two paths highlighted in the global response doc. For red path we let $f_i(\mathbf{X}) = 2$ for all $i$ on the path and for the blue path we let $f_i(\mathbf{X}) = 4X_6$ if $0 \le X_6 \le 0.55$ and $f_i(\mathbf{X}) = 2.2$ otherwise. Finally, for all other edges, we let $f_i(X) = \frac{1}{3.5^6} \left( (\frac{1}{\sqrt{p}} \sum_{j=1}^5 \beta_{ij}^{\top}X_j + 3)^6 + 1 \right) + 2.2$ which is the same as the original shortest path experiment but shifted up by $2.2$. This shift ensures the red and blue paths are better than the rest in expectation, and the best one depends on the value of $X_6$. Finally, we add independent noise (Gaussian or Uniform) to all edges just as in original experiment.
**[Q3]** > When you say:``What we are trying to argue $\ldots$" > Am I misunderstanding something? You are not misunderstanding. Our theory does say something ***slightly*** stronger -- namely because we prove uniform convergence, we've shown that if you can find a hypothesis $f(\cdot)$ that has low empirical PG loss, then it will also have low expected decision loss. So one need not perfectly optimize the PG Loss; just find a ``good enough" sub-optimal solution. But again, our theory does not guarantee that gradient descent will necessarily find such a $f(\cdot)$. What we meant by our original comment (which you also correctly summarized) is that the ***empirical*** experiments suggest that simple gradient descent procedures do find high-quality, sub-optimal solutions. Unfortunately, in light of the NP-Hardness of the problem, it seems difficult (or impossible?) to formulate a theoretically rigorous tractability result that would apply generally. (This difficulty applies to ***any*** surrogate that achieves best-in-class performance, not just ours.) So these empirical demonstrations are all we can (currently) offer. In many ways, this mirrors the state of the art with deep learning, where theory suggests the problem is hard/intractable, but empirical experience suggests we can reliably find high-quality local optima with (multi-start) stochastic gradient descent. **[Q3] Continued** > Could you also link me to the theorem statement that shows $\ldots$ Happily! Please see Theorems 3.4 and 3.7. Without the theorems, intuition suggests that if we want the empirical PG loss to well-approximate the expected decision loss as $n\rightarrow \infty$, we need $h_n \rightarrow 0$. Indeed, any such sequence should suffice. Since we want $h_n$ to be big (to avoid the flat regions), this suggests choosing a large $h$ that decays slowly. This is essentially the suggestion in [24], which advocates for very large $h$, like $h=10$. Experiments from [29] suggest this doesn't work well. By contrast, our Theorem 3.7 gives a tighter result and hence more insight. It shows the error between the empirical PG loss and expected decision-loss is roughly $\tilde O(\min(h, 1/\sqrt n))$. Hence, taking $h$ larger than $O(1/\sqrt n)$ slows the convergence rate. Thus, we might choose $h = 1/\sqrt n$, i.e., as large as possible without affecting the convergence rate. (See also line 242). Our theorems provide this kind of practical insight, and choosing $h$ in this manner drives (some of) our numerical improvements. A similar analysis holds for Theorem 3.4 and relates $h$ to the Rademacher complexity of the chosen class. See Line 227.
**[Q4]** > When you say "However, when we have $\ldots$" $\ldots$ > What stops gradient descent from reaching a local optimum $\ldots$ ? You are correct: On its own, there is no guarantee we can find the global optimum of our surrogate by gradient descent, and the NP-Hardness result suggests we can't globally optimize any surrogate that consistently achieves best-in-class performance. All we are hoping for is a high-quality local optimum. This mirrors the case of training a neural network. One reason to *intuitively* believe that we should be able to find good local optima is that under Assumption 3.1, as $n\rightarrow \infty$, the decision-loss curves become smoother/more well-behaved. In other words, there are fewer "flat" locations and fewer bad local minima. See Right Panel of Fig. 2. In fact, implicit in the proof of Lemma 3.1, is the fact that (under Assumption 3.1) the function $t \mapsto \mathbb E[\ell(t, y)]$ (expected decision-loss) is differentiable with Lipschitz gradients. Since, by Theorem 3.4 and Theorem 3.7, the empirical PG loss looks closer and closer to this function, this gives us some hope for gradient descent methods for large $n$. (Again, this is not a proof we can find the optimum, just intuition that we should converge to a stationary point.) We discuss this implicit fact on the bottom of pg. 5 with respect to how it affects approximation error, but we are happy to i) make this implicit fact explicit as a standalone lemma (with proof) and ii) connect this fact to the (intuitive) performance of first-order methods if you think it would help with the intuition.
**[Q5]** > Also, when you talk about optimizing the PG Losses as solving a ``difference in convex functions" problem $\ldots$. Why can you still solve the optimization problem or PG losses, then? We apologize for any confusion. First, in our experiments, we are not explicitly leveraging any special DC structure; we're just doing SGD. SGD can be run ``out of the box" without smoothing. Our comment indicated that exploiting the DC structure through specialized algorithms can only improve the empirical performance. Second, the most classical approach to DC problems is some form of DCA [F7], which solves a sequence of convex upper bounding problems to find a local optimum. DCA also does not require that the constituent DC functions be differentiable or smooth; it can also be applied ``out-of-the-box" in our case (but we didn't do this.) The references we gave on smoothing ([F3], [F4], [F5]) are recent works that argue that clever smoothing of the constituent functions does not affect stationary points/local optima. They are part of an area of research focusing on using first-order methods to optimize DC functions (see references). They show that this smoothing induces various nice properties (Lipschitz differentiability, coercivity/level boundedness, etc.), and that, as a consequence, various first-order methods (on the smoothed function) converge to a stationary point of the original (non-smooth) function. Thus, we believe smoothing the PG loss in this way before running SGD is a promising area of future research. Again, intuition suggests that it can only improve our numerical performance, but we have not yet tried it. Again, these results do not guarantee we find the global optimum, just that we should be able to identify a stationary point. - [F7]: Lipp, Thomas, and Stephen Boyd. "Variations and extension of the convex-concave procedure." Optimization and Engineering 17 (2016): 263-287.
Thank you for the detailed feedback! As for your question about what I mean by "even without the theoretical properties," it's closer to 1 than 2. I am more of an empiricist, and while I appreciate the fact that these are some of the first theoretical results for this problem, I don't see how these results will impact practice; this is a complaint I also have with some deep learning theory, and the AC is free to overrule me. Specifically, the NP-Hardness of it all means that, unlike the (limited) regret bounds for other convex surrogates (e.g., SPO+), which you *can* easily optimize for, the fact that you aren't guaranteed to be able to optimize the PG-losses means that you can't give any real guarantees about the performance of your proposed surrogate. Empirically, you show that you actually achieve low PG-loss regret in practice and that it implies good predict-then-optimize performance, but you don't actually need any regret bounds to show that. This is why I feel like the theory is more of a "bonus"... As for the specific questions that I had: **[Q1]** That's fair! I look forward to your benchmarking results. Also, the "monthly" prediction being harder than the "daily" ones is an interesting insight and one that's quite testable on the QuandlWIKI dataset; I will try it out! **[Q2]** I see. So even though the features are "independently" generated, the features of edges that aren't on these two paths are just a "distraction". However, because the $X_6$ values for those edges are also drawn from $U[0, 2]$ (as opposed to, say, $X_6 = -1$), you will never be able to exactly pick the "safe path" (or even the "risky path"). But that's why you end up having such a large regret, even for PG losses, I guess. **[Q3]** Responded above. Let me know how you disagree with my opinion about the theoretical results. **[Q4]** Re: "losses getting smoother as $n \to \infty$", I broadly agree with your intuition. However, if we want to make things quantitative, I imagine that the number of samples grows exponentially with the number of feature dimensions for "a certain level of smoothness" because of the curse of dimensionality. In Fig: 2, things are nice and 1-d, but I don't know how well this would work for more complex problems... **[Q5]** Thank you for the additional information about the DC literature!
Response
I have read the response, and it has helped clarify things. I am satisfied that these additions have improved the paper, and adjusted my score accordingly
Thank you for your detailed response, which partially addresses my concerns. The new empirical results look promising, and I am hopeful of increasing the score. As for Line 148 and eq 4, can you derive the directional gradient more carefully using Danskin's theorem, line by line? Also, please do not cite a blog post, please use more formal citations.
Decision
Accept (poster)