You Shall Pass: Dealing with the Zero-Gradient Problem in
Predict and Optimize for Convex Optimization

Grigorii Veviurko 1 Wendelin Böhmer 1 Mathijs de Weerdt 1

Abstract

the number of active constraints. Hence, the zero-gradientoccurs when the solution approaches the boundary of thefeasible set, activating the constraints. We propose a methodthat combines quadratic programming approximation similar to [6] with projection distance regularization from [7]and a novel idea of local smoothing. The resulting algorithm
has a simple geometric interpretation and is theoreticallyjustified. Using a portfolio optimization problem [8], we
demonstrate that a) the zero-gradient problem indeed occurs in the non-linear setup, and b) the proposed solution
resolves this problem and significantly outperforms the approach using the exact Jacobian.

In predict and optimize, machine learning models
are trained to predict parameters of optimization
problems using task performance as the objective.
A key challenge is computing the Jacobian of thesolution with respect to its parameters. While linear problems typically use approximations due toa zero or undefined gradient, non-linear convex
problems often utilize the exact derivative. This
paper demonstrates that the zero-gradient problem
also occurs in the non-linear case and introduces
a smoothing technique which, combined withquadratic approximation and projection distanceregularization, solves the zero-gradient problem.
Experiments on a portfolio optimization problem
confirm the method’s efficiency.

2. Related work
The P&O framework was first introduced by Elmachtoub et
al. [1], who consider combinatorial optimization problems
and derive a convex sub-differentiable approximation of thetask performance function to enable training. Vlastelica et
al. [3] obtain a piecewise-linear approximation of the task
performance, Berthet et al. [9] employ stochastic perturbations to approximate the Jacobian, and Sahoo et al. [4] showthat using projections on top of the predictor enables using
the identity matrix as an approximation of the Jacobian.

1. Introduction
Predict and optimize (P&O) [1] combines machine learning(ML) with mathematical programming, focusing on optimization problems with unknown parameters that need to bepredicted before solving the problem. Instead of training ML
models to match the distribution of unknown parameters,
P&O uses task performance as the objective for training. To
train P&O models with gradient descent [2], the Jacobian of
the optimization problem solution with respect to the parameter should be computed. For linear problems, this Jacobian
is either zero or undefined and is usually approximated [1],[3], [4]. In the non-linear case, differential optimization
method introduced by Agrawal et al. [5] allows for exact
computation of the Jacobian.

In convex optimization, exact differentiation is possible [5]for disciplined convex programs [10]. This result gave riseto new applications of P&O in convex optimization, such as
the portfolio optimization problem [11] and surrogate model
learning [8]. Moreover, several studies use this technique toapproximate the Jacobian of combinatorial problems. For
example, Wilder et al. [6] construct a quadratic approximation of the problem and use its Jacobian. This approach isthen extended by using logarithmic approximations [12].

This paper demonstrates that the zero-gradient problem
occurs not only in the linear case but also in general nonlinear convex settings. Specifically, the null space of thetrue Jacobian of a convex optimization problem depends on

3. Problem formulation
In this section, we define the P&O problem. We refer readers
to Elmachtoub et al. [1] for further details. In predict andoptimize, the original optimization problem is of the form
arg max f (x, w) s. t. x ∈ C,
(1)

1
Delft University of Technology. Correspondence to: Grigorii
Veviurko <g.veviurko@tudelft.nl>.

x

Published at the 2 nd Differentiable Almost Everything Workshop
at the 41 st International Conference on Machine Learning, Vienna, Austria. July 2024. Copyright 2024 by the author(s).

where x ∈ Rn is the decision variable, w ∈ Ru is a vectorof unknown parameters, f : Rn × Ru → R is the objective1

Dealing with the Zero-Gradient Problem in Predict and Optimize for Convex Optimization

Assumption 4.3. The objective function f (x, w) is twice
continuously differentiable in w.
Next, we establish some crucial properties of ∇ŵ x∗ (ŵ).
4.1. The zero-gradient theorem
Let ni := ∇x gi (x̂), i = 1, . . . , l be the normals of theconstraints at x̂, and let α1 , . . . , αl be the KKT multipliers [13]. According to Theorem 2.1 by Fiacco et al. [14],strict complementary slackness (SCS) conditions (i.e., αi >0 ∀i ∈ I(x)) are sufficient for differentiability of x∗ (ŵ).
We concentrate on these, since the points violating SCS area measure-zero set, and can thus be neglected in practice.

Figure 1. Gradient cones x̂ + G(x̂) (orange cones) and internal
gradients ∇x f (x̂, ŵ) (black arrows) at different points x̂ (red dots)
in different feasible sets C (blue cube and cylinder).

function, C is the feasible set, and w are unknown parameters. P&O employs predictions ŵ and the decision can becomputed by solving the internal problem:x∗ (ŵ) = arg max f (x, ŵ) s. t. x ∈ C.
(2)First, we obtain a geometrical perspective of the KKT conditions by introducing the following definition:
Definition 4.4. For x ∈ C let I(x) = {i|gi (x) = 0} be
the set of indices of the constraints active at x. Let ni =∇x gi (x) be the normal vectors of thesen Pconstraints for io∈
I(x). The gradient cone, G(x) :=i∈I αi ni |αi ≥ 0 ,is the positive linear span of normal vectors ni .

x

As the true parameters w are unknown, we assume that we
observe a feature vector o that in some way relates to w. We
employ a prediction model ϕθ to compute predictions ŵ, i.e.,ŵ = ϕθ (o). To train ϕθ , we have a dataset D = {(ok , wk )}.
In P&O, the predictive model ϕθ is trained to maximize
the task performance f (x, w) and not to accurately predictthe unknown parameters. Therefore, the loss function minimized during training is

 
P
1
L(θ) = − |D|f x∗ ϕθ (o) , w .
(3)

Combining the KKT conditions with Definition 4.4, we
immediately arrive at the following property:
Property 4.5. Let x ∈ C and let ∇x f (x, ŵ) be the internal
gradient at x. Then, x is a solution to the problem in Eq. (2)if
Pand only if ∀i ∈ I(x), ∃αi ≥ 0, such that ∇x f (x, ŵ) =i∈I(x) αi ni ∈ G(x), where I(x) is the set of indices ofactive constraints, I(x) = {i|gi (x) = 0}.

(o,w)∈DTo train ϕθ with a gradient-based algorithm, we need todifferentiate L over θ, and hence we need to compute the∗gradient ∇θ f x (ŵ), w , where ŵ = ϕθ (o). Applying thechain rule, it can be decomposed into three terms:
∇θ f x∗ (ŵ), w =∇x f x∗ (ŵ), w ∇ŵ x∗ (ŵ) ∇θ ŵ (4)While trivial, this property provides a geometrical interpretation of the problem: a point x is a solution to the problem
in Eq. (2) if and only if the internal gradient at this point lies
inside its gradient cone. Figure 1 illustrates this property.

The term ∇ŵ x∗ (ŵ) is the Jacobian of the solution of the
optimization problem with respect to the prediction ŵ. In
non-linear convex problems, it can be computed exactly [5].
However, properties of this Jacobian are not well studied.
In the next section, we show that ∇ŵ x∗ (ŵ) can have a large
null space thereby causing suboptimal performance.

Now, we have all the necessary tools to describe the structure of the Jacobian ∇ŵ x∗ (ŵ). Assume that we perturb ŵ
and obtain ŵ′ . Let x̂′ = x∗ (ŵ′ ). Strict complementaryslackness implies that the constraints active at x̂ will remain
active at x̂′ if the difference ∥ŵ′ − ŵ∥22 is small enough.
Therefore, the decision x̂′ can only move within the tangent space of C at x̂, i.e., orthogonally to all ni , i ∈ I(x̂).
Hence, when more constraints are active, x̂′ can move inless directions. Formally, we obtain the following lemma:
Lemma 4.6. SupposePthat the SCS conditions hold at x̂
and let ∇x f (x̂, ŵ) = i∈I(x̂) αi ni , αi > 0, ∀i ∈ I(x̂) be
the internal gradient. Let N (x̂) = span({ni | i ∈ I(x̂)})be the linear span of the gradient cone. Then N (x̂) is
contained in the left null space of ∇ŵ x∗ (ŵ).

4. Differentiable optimization
Without loss of generality, we consider a single instance ofthe problem, i.e., one sample (o, w) ∈ D. We denote theprediction by ŵ = ϕθ (o) and the corresponding decision x̂
is then computed as a solution to the internal problem (2).
We make the following assumptions:
Assumption 4.1. The objective function f (x, w) is concave
and twice continuously differentiable in x for any w.
Assumption 4.2. The feasible set C = {x|gi (x) ≤ 0,
i = 1, . . . , l} is convex, i.e., gi (x) are convex and differentiable. Also, the gradients {∇x gi (x)|gi (x) = 0} of theactive constraints are linearly independent1 ∀ x ∈ C.

The proof can be found in Appendix A. Lemma 4.6 is very
important, as it specifies in what directions x∗ (ŵ) can moveas a consequence of changing ŵ. The first term in the chain
rule in Eq. (4), ∇x f (x̂, w), specifies in what directions

1
For clarity, Assumption 2 does not include equality constraints.
In the appendix, we show that all our results hold with those, too.

2

Dealing with the Zero-Gradient Problem in Predict and Optimize for Convex Optimizationa diagonal matrix. Its first |I(x̂)| entries are zero, and theothers are one.
While providing computational benefits, QP approximation
does not address the zero-gradient problem. Below, we
introduce a smoothing technique that reduces the size of thenull space to one.
Figure 2. Left: Illustration of the QP approximation. Right: Illustration of local smoothing.

4.3. Local smoothingx∗ (ŵ) should move in order for the true objective to increase. Naturally, if these directions are contained in thenull space of ∇ŵ x∗ (ŵ), then the total gradient in Eq. (4) iszero. This constitutes the main result of this paper:
Theorem 4.7 (Zero-gradient theorem). Let ŵ be a prediction, and x̂ be the internal problem in Eq. (2). Suppose the
SCS conditions hold at x̂ and let N (x̂) = span({ni | i ∈I(x̂)}) be the linear span of the gradient cone at x̂. Then,∇x f (x̂, w) ∈ N (x̂) =⇒ ∇θ f (x̂, w) = 0.

Above, we concluded that the null space of the Jacobian∇ŵ x(ŵ) depends on the number of constraints active at x̂.
Therefore, to solve the zero-gradient problem, we propose a
local smoothing method, that reduces the number of active
constraints to one during the Jacobian computation.
P
Let ∇x fQP (x̂, ŵ) = i∈I(x̂) αi ni be the internal gradientat x̂ for some αi ≥ 0, ∀i ∈ I(x̂). Then, we introduce thefollowing definition:∇ f(x̂,ŵ)QP
Definition 4.9. Let c = x̂ − r ∥∇xxfQP(x̂,ŵ)∥2 , with realnr > 0, and let Cr (x̂, ŵ) := {y|y ∈ R , ∥y − c∥2 ≤ r}. The
local smoothed problem Pr (x̂, ŵ) with parameters x̂, ŵ isdefined as x∗r (ŵ) := arg maxx∈Cr (x̂,ŵ) fQP (x, ŵ).

This theorem claims that the gradient of the P&O loss in
Eq. (3) can be zero in points outside the optimal solution.
Hence, any gradient-following method “shall not pass” thesepoints. In particular, this phenomenon happens in pointsx̂ where the true gradient ∇x f (x̂, w) is contained in thespace N (x̂) spanned by the gradient cone G(x̂). As thedimensionality of this space grows with the number of active
constraints, the zero-gradient issue is particularly importantfor problems with a large number of constraints. In the worst
case, N (x̂) can be as big as the whole decision space Rn ,thereby making the total gradient ∇θ f (x̂, w) from Eq. (4)zero for any value of the true gradient ∇x f (x̂, w).

Now, let x̂r = x∗r (ŵ) denote the solution of Pr (x̂, ŵ). By
construction, x̂r = x̂. The main purpose of smoothingis to approximate the gradient in Eq. (4) by substituting∇ŵ x∗QP (ŵ) with ∇ŵ x∗r (ŵ). We emphasize that the decisions are still computed using the non-smoothed problem.
Thus, we use the following approximation for Eq. (4):∇θ f (x∗ (ŵ), w) ≈ ∇x f x̂, w ∇ŵ x∗r (ŵ) ∇θ ŵ (6)Applying Lemma 4.8, we obtain the following:
Property 4.10. Let x̂ = x∗QP (ŵ) be a decision derived
via QP. Suppose that the SCS conditions hold for Pr (x̂, ŵ)and let e1 = ∇x fQP (x̂, ŵ) be the internal gradient. Let{e2 , . . . , en } be a complement of e1 to an orthogonal basisof Rn . Then, the Jacobian ∇ŵ x∗r (ŵ) of the locally smoothed
problem in the basis {e1 , e2 , . . . , en } is a diagonal matrix.
Its first entry is zero, others are ones.

4.2. Quadratic programming approximation
The models trained with predict and optimize can output ŵ
that is significantly different from the true w, yet result ingood decisions. Hence, we claim that the objective function
f (x, ŵ) in the internal problem also does not need to be
the same as the true objective f (x, w). In particular, wesuggest computing decisions using a quadratic program(QP) resembling the method proposed in Wilder et al. [6]:x∗QP (ŵ) = arg max −∥x − ŵ∥22 s.t. x ∈ C.
(5)
x
|
{z
}

Using this property, we can show that the smoothed Jacobian
is consistent with the loss function:
Theorem 4.11. Let x̂ = x∗QP (ŵ) be the decision obtained
via QP and let ∇ŵ x∗r (ŵ) be the Jacobian of the local
smoothed QP problem. Let ∆ŵ = ∇x f (x̂, w) ∇ŵ x∗r (ŵ)
be the prediction perturbation obtained by using this Jacobian and let ŵ′ (t) = ŵ + t∆ŵ be the updated prediction. Then, for t → 0+ , using ŵ′ (t) results in a
non-decrease in the task performance.
In other words,f x∗QP (ŵ′ (t)), w ≥ f x∗QP (ŵ), w .

fQP (x,ŵ)The main advantage of using QP is that it has the smallest reasonable prediction vector ŵ (one scalar per decisionvariable). Besides, QP approximation can represent any
solution, and its Jacobian has a simple analytic form, whichallows computing it cheaply and allows for studying its theoretical properties. Specifically, the Jacobian ∇ŵ x∗QP is
described by the following lemma:
Lemma 4.8. Let {ej |j = 1, . . . , n − |I(x̂|)} be an orthogonal complement of vectors {ni |i ∈ I(x̂)} to a basis of Rn .
Then, the Jacobian ∇ŵ xQP (ŵ) in the basis {ni } ∪ {ej } isAs we see from Property 4.10, the value of r does notaffect the Jacobian. We keep it only for clarity of the notation. As Cr (x̂, ŵ) is defined by a single constraint, the nullspace of ∇ŵ x∗r (x̂, ŵ) is always one-dimensional. Hence,3

Dealing with the Zero-Gradient Problem in Predict and Optimize for Convex Optimization
6

QP
Smoothed QP
True problem
MSE

0.07
0.06
0.05

4

0.04

Regret0.03

Smoothed QP = 0.1
QP
MSE
True problem

Smoothed QP
QP
MSE
True problem

64|| f ||2|| f ||2

2

2

=1

0.02
0.01

=0.0

=0.1

=0.25

Value of

=0.5

=1.0

0

=2.0

0 10 20 30 40 50 60 70 80

Training epoch00 10 20 30 40 50 60 70 80

Training epoch(a)(b)
Figure 3. Results on the portfolio optimization problem: (a) the final test regret for each of the algorithms for varying λ’s. (b) Evolution of
the l2 norm of the gradient during training for λ = 0.1 and λ = 1.

the zero-gradient problem only occurs when the internal
gradient ∇x fQP (x̂, ŵ) and the true gradient ∇x f (x̂, w) arecollinear. To deal with this case, we use the projection
distance regularization method first suggested in [7]. Specifically, we add a penalty p(ŵ) = α∥x̂ − ŵ∥22 , where α ∈ R+
is a hyperparameter. Minimizing this term, we push ŵ along
the null space of the Jacobian towards the feasible set andeventually move x̂ inside C.

True problem
QP
Smoothed QP

Regret0.834 ± 0.120
0.506 ± 0.009
0.438 ± 0.009

Runtime (sec)7965 ± 52
762 ± 52
801 ± 54

Table 1. Final (normalized) test regret and training time for thedifferent methods on the LogSumExp portfolio problem.

true problem), the gradient norm decreases rapidly withtraining. In accordance with theory, this effect is more significant for smaller values of λ. In the more quadratic cases,
the relative difference in performance becomes smaller.

5. Experiments
We consider the portfolio optimization problem [8], where
we aim to maximize the immediate return but minimize therisk penalty under the budget constraint:nP
xi = 1, x ≥ 0. (7)arg max p⊤ x − λ x⊤ Qx s. t.
{z
}
|
x
i=1

Figure 3 suggests that the QP approximation is sufficient in
portfolio optimization. However, it might be explained by
the fact that the true problem in Eq. (7) is also quadratic. To
gain more insight into the performance of our method, we
also consider a LogSumExp objective function:Xflse (x, p, Q) = − log
e−pi xi(9)f (x,p,Q)

The decision x ∈ Rn is the investment, p ∈ Rn is theimmediate return, and Q ∈ Rn×n is the covariance matrix.
The unknown parameters are defined as w := (p, Q) andλ ≥ 0 represents the risk-aversion weight. We use historical
data from QUANDL WIKI [15] and we refer the readers to
the appendix for more details. We consider different valuesof λ from the set {0, 0.1, 0.25, 0.5, 1, 2}, in order to obtaina spectrum of problems, from the linear (λ = 0) to the“strongly quadratic” (λ = 2).

i

The LogSumExp function acts as a soft maximum, and thecorresponding problem can be interpreted as maximizationof the most profitable investment. The results in Table 1
demonstrate that the QP approximation outperforms the true
problem in terms of regret and significantly reduces the computation time. Moreover, smoothed QP again outperforms
the other approaches, which suggests that the zero-gradientproblem occurs in the LogSumExp case as well.

We compare the performance of four methods: minimizationof the MSE of the prediction (labeled “MSE”); differentiation of the original problem in Eq (7) (“True problem”);
differentiation of the QP approximation (“QP”); and combination of QP, smoothing, and projection distance regularization (“Smoothed QP”). For the performance metric, we use
regret [1], defined as regret(o, w) = f x∗ ϕθ (o) , w − max f x, w . (8)6. Conclusions
In this work, we theoretically demonstrate that the zerogradient problem in the non-linear convex P&O setting extends beyond the linear case. To address this, we introduce
a Jacobian approximation method by smoothing the feasible set, thereby reducing the null space’s dimensionality toone. This approach, combined with ideas from prior work,
enables effective gradient updates and escapes from zerogradient cones. Our experiments with portfolio optimization
problem confirm that the zero-gradient issue impedes standard differential optimization and show that our smoothed
QP method solves it effectively.

x

The results in Figure 3 demonstrate that the smoothed QP
approach is dominant – it outperforms the competitors bya significant margin across all values of λ. Figure 3 (b)suggests the reason for this result is indeed the zero-gradientproblem: for the methods using the exact Jacobian (QP and

4

Dealing with the Zero-Gradient Problem in Predict and Optimize for Convex Optimization

References
[1]
[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

A. N. Elmachtoub and P. Grigas, “Smart” predict, then
optimize”,” arXiv preprint arXiv:1710.08005, 2017.
J. Kiefer and J. Wolfowitz, “Stochastic estimation of the
maximum of a regression function,” The Annals of Mathematical Statistics, pp. 462–466, 1952.
M. Vlastelica, A. Paulus, V. Musil, G. Martius, and
M. Rolı́nek, “Differentiation of blackbox combinatorial
solvers,” pp. 1–19, 2019.
S. S. Sahoo, A. Paulus, M. Vlastelica, V. Musil, V.
Kuleshov, and G. Martius, Backpropagation through combinatorial algorithms: Identity with projection works, 2023.
arXiv: 2205.15213 [cs.LG].
A. Agrawal, B. Amos, S. Barratt, S. Boyd, S. Diamond, andJ. Z. Kolter, “Differentiable convex optimization layers,”
Adv. Neural Inf. Process. Syst., vol. 32, 2019.
B. Wilder, B. Dilkina, and M. Tambe, “Melding the DataDecisions pipeline: Decision-Focused learning for combinatorial optimization,” en, AAAI, vol. 33, no. 01, pp. 1658–
1665, Jul. 2019.
B. Chen, P. L. Donti, K. Baker, J. Z. Kolter, and M. Bergés,“Enforcing policy feasibility constraints through differentiable projection for energy optimization,” e-Energy 2021 Proceedings of the 2021 12th ACM International Conference on Future Energy Systems, pp. 199–210, 2021.
K. Wang, B. Wilder, A. Perrault, and M. Tambe, “Automatically learning compact quality-aware surrogates for
optimization problems,” Jun. 2020. arXiv: 2006.10815[cs.LG].
Q. Berthet, M. Blondel, O. Teboul, M. Cuturi, J. P. Vert,and F. Bach, “Learning with differentiable perturbed optimizers,” Adv. Neural Inf. Process. Syst., vol. 2020-Decem,
pp. 1–24, 2020.
M. Grant, S. Boyd, and Y. Ye, “Disciplined Convex Programming,” in Global Optimization: From Theory to Implementation, L. Liberti and N. Maculan, Eds. Boston, MA:
Springer US, 2006, pp. 155–210, ISBN: 978-0-387-305288.
A. S. Uysal, X. Li, and J. M. Mulvey, “End-to-End risk
budgeting portfolio optimization with neural networks,” Jul.
2021. arXiv: 2107.04636 [q-fin.PM].
J. Mandi and T. Guns, “Interior point solving for LPbased prediction+optimisation,” Oct. 2020. arXiv: 2010.
13943 [cs.NE].
H. W. Kuhn and A. W. Tucker, “Nonlinear programming,”
In Berkeley Symposium on Mathematical Statistics andProbability, vol. 2, pp. 481–492, 1951.
A. V. Fiacco, “Sensitivity analysis for nonlinear programming using penalty methods,” Mathematical programming,
vol. 10, no. 1, pp. 287–311, 1976.
QUANDL, Quandl wiki prices, 2020. 2020.

5

Dealing with the Zero-Gradient Problem in Predict and Optimize for Convex Optimization

A. Proofs
Proof of Lemma 4.6. Let ∆ŵ denote an arbitrary direction and let d = ∇ŵ x∗ (ŵ) ∆ŵ be the corresponding directional
derivative of the decision. The existence of d is guaranteed by the strict complementary slackness conditions. Let t → 0+ .
Then, we havex̂′ (t) := x∗ (ŵ + t∆ŵ) = x̂ + td + ox (t),2
= 0. To prove the lemma, we first want to show that d⊤ ni =where ox (t) is the “little o” notation, i.e., limt→0+ ∥ox (t)∥t0, ∀i ∈ I(x̂). Then, we will show that it implies the lemma’s claim.

By definition, ni = ∇x gi (x̂).
 Then, since gi (·) is differentiable and gi (x̂) = 0, ∀i ∈ I(x̂), we have the following first-orderapproximation for gi x̂′ (t) :gi x̂′ (t) = gi x̂ + td + o(t) =⊤gi (x̂) + tn⊤
i d + og (t) = tni d + og (t).
Since x̂′ is the solution of the internal optimization problem, the inequality gi (x̂′ (t)) ≤ 0 holds. Hence, the equation above⊤⊤
implies that n⊤
i d ≤ 0. Now, we want to show that, in fact, ni d = 0. For a proof by contradiction, suppose that ni d < 0.
Then, by definition of og (t), there exists ϵ > 0, such that
0 < t < ϵ =⇒ gi x̂′ (t) < 0.
Now, we will to show that gi x̂′ (t) < 0 contradicts the complementary slackness condition at x̂. From the work by Fiacco′
et al. [14], we know that the KKT multiplier,function of t. On the one hand, from αi (t) := αi (′ŵ + t∆ŵ), is a continuous′
the KKT conditions, we know that gi x̂ (t) < 0 =⇒ αi (t) = 0. Therefore, αi′ (t) = 0 for t < ϵ. Hence, we havelim αi′ (t) = 0.

t→0+On the other hand, the continuity implies that limt→0+ αi′ (t) = αi′ (0) = αi and, due to strict complementary slackness,
αi > 0. Hence, we also havelim+ αi′ (t) > 0.
t→0

We arrived at a contradiction and therefore can claim that d⊤ ni = 0 for all ni . Since {ni |i ∈ I(x̂)} is a basis of N (x̂),
this implies that for any direction v ∈ N (x̂) and for any ∆ŵ, we have v ⊤ ∇ŵ x∗ (ŵ) ∆ŵ = 0. In other words, vectorv ⊤ ∇ŵ x∗ (ŵ) is orthogonal to the whole space of ŵ and hence it must be zero, v ⊤ ∇ŵ x∗ (ŵ) = 0, ∀v ∈ N (x̂). Hence
N (x̂) is contained in the left null space of ∇ŵ x∗ (ŵ).
Proof of Lemma 4.8. First, consider the case when the unconstrained maximum ŵ is in the interior of C. By definition ofx∗QP , it means that x̂ = x∗QP (ŵ) is also in the interior of C and x̂ = ŵ. Then, x∗QP is the identity function around ŵ, andhence x∗QP (ŵ + ∆ŵ) = x(ŵ) + ∆ŵ for small enough ∆ŵ. Hence, ∇ŵ x∗QP (ŵ) = I. Since no constraints are active in thiscase (I(x̂) = ∅), the lemma’s claim holds.
Now, consider the case when some constraints are active, and thus x̂ lies on the boundary of C. To get the exact form of theJacobian ∇x x∗QP (ŵ), we will compute limt→0 x∗QP (ŵ + t∆ŵ) for all possible ∆ŵ. As in the QP case the predictions ŵ
lie in the same space as x̂, we can do it first for ∆ŵ ∈ N (x̂) and then for ∆ŵ ⊥ N (x̂).
1. ∆ŵ ∈ N (x̂). For ∆ŵ ∈ N (x̂), we want to show that the corresponding directional derivative is zero. We begin bycomputing the internal gradient ∇x fQP (x̂, ŵ) :∇x fQP (x̂, ŵ) = −∇x ∥x − w∥22 = 2(ŵ − x̂).
Using this formula, we can write the internal gradient for the perturbed prediction ŵ + t∆ŵ at the same point x̂:∇x fQP (x̂, ŵ + t∆ŵ) = ∇x fQP (x̂, ŵ) + 2t∆ŵ.
By definition, N (x̂) is a linear span of the vectors {ni |i ∈ I(x̂)}. Hence, since ∆ŵ ∈ N (x̂), it can be expressed asX∆ŵ =δi ni , δi ∈ R.

(∗)

By Property 4.5, the internal gradient has the following representation:X∇x fQP (x̂, ŵ) =αi ni , αi > 0.

(∗∗)

i∈I(x̂)i∈I(x̂)6

Dealing with the Zero-Gradient Problem in Predict and Optimize for Convex Optimization

Then, combining (∗) and (∗∗), we obtain∇x fQP (x̂, ŵ + t∆ŵ) = ∇x fQP (x̂, ŵ) + 2t∆ŵ =X(αi + 2tδi )nii∈I(x̂)Since αi > 0, ∀i ∈ I(x̂), there exists ϵ > 0, such that αi − 2tδi > 0 for |t| < ϵ. Therefore, ∇x fQP (x̂, ŵ + t∆ŵ) lies in
the gradient cone of x̂, and hence, by Property 4.5, x∗QP (ŵ + t∆ŵ) = x̂ for |t| < ϵ. Therefore, the directional derivative ofx∗QP (ŵ) along ∆ŵ ∈ N (x̂) is zero.
2. ∆ŵ ⊥ N (x̂).

Next, let ∆ŵ be orthogonal to N (x̂). We begin with the first order approximation of x̂′ (t) :x̂′ (t) = x̂ + td + o(t).
From the proof of Lemma 4.6, we know that d ⊥ N . By definition of x∗QP , we know that x̂ is the point on C closest toŵ. Likewise, x̂′ (t) is the point on C closest to ŵ + t∆ŵ. Hence, d = ∆ŵ. Therefore, for any ∆ŵ ⊥ N , the directional
derivative of xQP (ŵ) along ∆ŵ is one.
So, we have shown that∇ŵ x∗QP (ŵ) ∆ŵ =

(

0
∆ŵ

for ∆ŵ ∈ N (x̂)
for ∆ŵ ⊥ N (x̂).

Therefore, the lemma is proven.
Proof of Theorem 4.11. First, we want to construct an orthogonal basis {e1 , . . . en } of Rn that will greatly simplify thecalculations. We start by including the internal gradient in this basis, i.e., we define e1 = ∇x fQP (x̂, ŵ). Then, let I(x̂) ={i|gi (x̂) = 0} be the set of indices of the active constraints of the original problem and let N (x̂) = span({ni |i ∈ I(x̂)})be a linear span of their normals. By the liner independence condition from Assumption 2, dim N (x̂) = |I(x̂)|. Moreover,by Property 4.5, we know that e1 ∈ N (x̂). Then, we can choose vectors e2 , . . . , e|I(x̂)| that complement e1 to an orthogonalbasis of N (x̂). The remaining vectors e|I(x̂)|+1 , . . . , en , are chosen to complement e1 , . . . , e|I(x̂)| to an orthogonal basisof Rn . The choice of this basis is motivated by Lemma 6: e1 is a basis of the null-space of the r−smoothed Jacobian,e1 , . . . , e|I(x̂)| form a basis of the null space of the true QP Jacobian, and the remaining vectors form a basis of space inwhich we can move x∗QP (ŵ).
For brevity, let fx = ∇x f (x̂, w) denote the true gradient vector. By definition, ∆ŵ = fx ∇ŵ x∗r (x̂, ŵ) is obtained via ther−smoothed problem. From Property 4.10, we know that ∆ŵ is a projection of fx on the vectors e2 , . . . , en . Then, since
e1 , . . . , en is an orthogonal basis, we havenX
βi ei , βi = fx⊤ ei , i = 2, . . . , n.
∆ŵ =
i=2

Now, let’s see how this ∆ŵ affects the true decision x∗QP (ŵ + t∆ŵ) for t → 0+ . First, we have a first-order approximationx∗QP (ŵ + t∆ŵ) = x̂ + td + o(t),for some d ∈ R. From Lemma 4.6, we know that d is actually a projection of ∆ŵ onto the vectors e|I(x̂)|+1 , . . . , en .
Therefore, we haven
X
x∗QP (ŵ + t∆ŵ) = x̂ +βi ei + o(t).
i=|I(x̂|+1

Finally, the change in the true objective can be expressed as





f x∗QP (ŵ + t∆ŵ), w − f x∗QP (ŵ), w = tfx⊤=tnXi=|I(x̂|+1nX

i=|I(x̂|+1
βi ei + o(t) =βi fx⊤ ei + o(t) = tnXβi2 + o(t) ≥ 0.

i=|I(x̂|+1

Therefore, perturbing prediction along ∆ŵ does not decrease the true objective f (x̂, w), and hencef x∗QP (ŵ + t∆ŵ), w ≥ f x∗QP (ŵ), w
for t → 0+ .

7

Dealing with the Zero-Gradient Problem in Predict and Optimize for Convex Optimization

Parameter
Learning rate
Training epochs
Batch size
xshif txscaleSearch space{0.5, 1, 5, 10}×10−5{40, 80, 160}
{1, 4, 8, 32}{0, 0.1, 1}{0.1, 1}Best value
5 × 10−5
80
1
0.1
1

Table 2. Hyperparameters for methods from Figure 3 for standard portfolio optimization problem with different λ’s.

B. Equality constraints
Assumption 2 postulates that for any x ∈ C, the gradients of active constraints, {∇x gi (x)|gi (x) = 0}, are linearly
independent. Now, suppose we include equality constraints in our problem. e.g., we have a constraint g eq (x) ≤ 0 and−g eq (x) ≤ 0 for some g. Clearly, the gradients of g eq (x) and −g eq (x) violate the independence assumption. However, we
claim that it does not affect our results. Let ŵ and x̂ be a prediction and a corresponding decision and let neq = ∇x g eq (x̂).
Suppose the equality constraint g eq (x̂) = 0 is active. Let I(x̂) be the set of indices of the active constraints not including
g eq (x). Then, we have a representation of the internal gradient,X∇x f (x̂, ŵ) = α1eq neq − α2eq neq +α i ni .
i∈I(x̂)Suppose that α1eq ̸= α2eq , e.g., without loss of generality, α1eq > α2eq . Then,X∇x f (x̂, ŵ) = (α1eq − α2eq )neq +α i nii∈I(x̂)and hence removing the constraint −g eq (x) ≤ 0 would not change the optimality of x̂. The remaining problem would
satisfy complementary slackness and hence would have all the properties demonstrated in Section 3. Therefore, for the casewith equality constraints, we need to extend the complementary slackness conditions by demanding α1eq ̸= α2eq .

C. Experimental details
In this section, we provide the details of the experiments reported in the paper. All experiments were conducted on a machinewith 32gb RAM and NVIDIA GeForce RTX 3070. The code is written in Python 3.8, and neural networks are implemented
in PyTorch 1.11. For methods requiring differentiation of optimization problems, we use the implementation by Agrawal et.
al [2019].
Experimental results reported in Figures 3 and 4 show the average and the standard deviation (shaded region) of the measured
quantities across 4 random seeds. For each seed, we randomly split data into train, validation, and test sets by using 70%,
20%, and 10% of the whole dataset respectively. In Figure 3a, for each method and at each run, we take the model version
corresponding to the best performance on the validation set and report its performance on the test set. In Figure 4, we do thesame procedure at each training iteration.
In all experiments and methods, the predictor ϕθ is represented by a fully connected neural network with two hidden layersof 256 neurons each, and LeakyReLU activation functions. The output layer has no activation function. Instead, the outputof the neural network is scaled by the factor xscale and shifted by xshif t . For the methods using QP approximation, theoutput layer predicts vector ŵ of the same dimensionality as the decision variable. For the method using the true model, theprediction size is defined by the number of unknown parameters in the true objective function. For training, we used theAdam optimizer from PyTorch, with custom learning rate and otherwise default parameters.
Hyperparameters of all methods were chosen based on the results of the grid search reported in Tables 2-3. The weight
α of the projection distance regularization term is λ−dependent. Specifically, α = 0 for λ ∈ {0, 0.1}, α = 0.01 forλ ∈ {0.25, 0.5}, and α = 0.1 for λ ∈ {1, 2}. Configuration files to reproduce the experiments and the code can be found atplaceholder for GitHub link.
Portfolio optimization problem
Following Wang et. al [2020], we use historical data from QUANDL WIKI prices [15] for 505 largest companies on
the American market for the period 2014-2017. The dataset is processed and for every day we obtain a feature vector
8Dealing with the Zero-Gradient Problem in Predict and Optimize for Convex Optimization

Parameter
Learning rate
Batch size
xshif txscaleSearch space{0.5, 1, 5, 10}×10−5{1, 4, 8, 32}{0, 0.1, 1}{0.1, 1}Best value
5 × 10−51
0.1
0.1

Table 3. Hyperparameters for methods from Table 1 for LogSumExp portfolio optimization problem.

summarizing the recent price dynamic. For further details on the processing, we refer readers to the code and to Wang et. al[2020]. The processed dataset contained historical data describing the past price dynamics for each of the 505 securities. For
every random seed, 50 securities (thus, 50 decision variables) were chosen randomly. The experiments on the LogSumExp
variation of the portfolio optimization problem were conducted similarly. The hyperparameters for normal and LogSumExp
portfolio problems are reported in Tables 2 and 3.

9