Weak cosmic censorship conjecture in BTZ black holes with scalar fields

Deyou Chen

School of Science, Xihua University, Chengdu 610039, China

E-mail<EMAIL_ADDRESS>
Abstract: The weak cosmic censorship conjecture in the near-extremal BTZ black
hole has been tested by the test particles and fields. It was claimed that
this black hole could be overspun. In this paper, we review the thermodynamics
and weak cosmic censorship conjecture in BTZ black holes by the scattering of
the scalar field. The first law of thermodynamics in the non-extremal BTZ
black hole is recovered. For the extremal and near-extremal black holes, due
to the divergence of the variation of the entropy, we test the weak cosmic
censorship conjecture by evaluating the minimum values of the function $f$.
Both of the extremal and near-extremal black holes cannot be overspun.

Keywords: Weak cosmic censorship conjecture, scalar field, thermodynamics.

##  1 Introduction

It is widely believed that spacetime singularities are formed at the end of
gravitational collapses. At the singularities, all physical laws break down.
To avoid the destruction caused by the singularities, Penrose proposed the
weak cosmic censorship conjecture (WCCC) in 1969 [1]. This conjecture states
that naked singularities cannot be produced in a physical process from regular
initial conditions. For black holes, their singularities should be hidden
behind event horizons without any access to distant observers. Since the
conjecture was put forward, a lot of research has been done on its validity.
However, no concrete evidence has been found to prove it and no unanimous
conclusion has been reached.

The Gedanken experiment proposed by Wald is the first attempt to test the
validity of the WCCC [2]. In this experiment, a test particle with energy,
large enough charge and angular momentum is thrown into a Kerr-Newman black
hole to test whether the black hole exceeds its extremal limit. The Kerr-
Newman solution describes a charged and rotating spacetime. Its charge and
angular momentum per unit mass are bounded by the mass as $a^{2}+Q^{2}\leq
M^{2}$. When $M^{2}<a^{2}+Q^{2}$, the black hole exceeds its extremal limit
and the event horizon disappears. Thus the singularity is naked and the WCCC
is violated. Following this seminal work, people investigated the validity
from the aspects of particles and fields. Jacobson and Sotiriou studied the
absorption of an object with spin and orbital angular momentum in a near-
extremal Kerr black hole. They found that the black hole could be overspun
without consideration of the radiative and self-force effects [3]. The
overcharge of the near-extremal Reissner-Nordstrom black hole was first found
in [4] and then investigated with consideration of the tunnelling effects in
[5]. However, when the radiative, backreaction and self-force effects are
taken into account, particles may be escaped from black holes and naked
singularises can be avoided [6, 7, 8, 9, 10, 11, 12]. This result was
confirmed again in the recent work where the self-force and finite size
effects were considered [13, 14]. A counterexample to the WCCC in four-
dimensional anti de Sitter (AdS) spacetime was presented in [15]. In this
spacetime, constant time slices have planar topology. It was shown that it is
just a pure AdS in the past. In the future, the curvature grows without bound
and leaves regions of spacetime with arbitrarily large curvatures. These
regions are naked to boundary observers. This work is important to the weak
gravity conjecture [16].

The validity of the WCCC was researched from the aspect of fields [17, 18, 19,
20, 49]. In the research, the field has a finite energy, which indicates the
existence of the wave packet. Initially, the field does not exist and there is
only a black hole. The field comes in from infinity and interacts with the
black hole. Due to the interaction, the energy, charge and angular momentum
are transferred between the field and the black hole. Part of the field is
reflected back to infinity. Finally, the field decays away leaving behind
another spacetime with the new energy, charge and angular momentum [18].
Whether the black hole is overspun or overcharged can be judged by the change
of event horizon. Based on this view, the interaction between a dyonic Kerr-
Newman black hole and a complex massive scalar field was discussed [19]. It
was found that this interaction did not destroy the WCCC. The same result was
derived by Toth [18]. His derivation is based on a null energy condition,
conservation laws and the electromagnetic field of the black hole. In the
recent work, Gwak calculated the variations of the energy and angular momentum
of the Kerr-(Anti-)de Sitter black hole during a infinitesimal time interval
by the fluxes of energy and angular momentum of the scalar field [20]. He
found that the black hole kept the initial states and was not overspun. This
result is different from that of the near-extremal black hole by throwing a
test particle into it. When initial data are non-generic, naked singularities
can be developed [21, 22, 23, 24, 25, 26, 27]. Other tests of the WCCC are
referred to [28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43,
44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54] and the references in them.

The Ba$\tilde{n}$ados, Teitelboim and Zanelli (BTZ) black hole is a solution
of Einstein field equations in three-dimensional spacetime and describes a
rotating AdS geometry [55, 56]. The related properties of BTZ black holes were
researched in [49, 57, 58, 59]. In [57], Rocha and Cardoso tested the WCCC in
the extremal BTZ black hole by using the test particle. They found that this
black hole could not be overspun. In this work, the initial black hole was
designated as an extremal one. However, D$\ddot{u}$ztas claimed that a near-
extremal black hole had the possibility to exceed its extremal limit whether
or not the superradiation occurred [49]. If the superradiation did not occur,
overspinning becomes generic and also applies to the extremal BTZ black hole.
If there was the superradiation, the black hole is overspun in a certain range
of frequencies. He elaborated this result from the massive test particles and
the test fields, respectively. Due to the similarities of rotating black
holes, the same result was gotten in the Kerr black hole [17]. Obviously, this
result is different from that derived by Wald and Sorce [13, 14].

In this paper, we review the thermodynamics and WCCC in BTZ black holes by the
scattering of a scalar field. The BTZ black holes are generic in the sense of
constituting an open set in the space of solutions to the Einstein equation.
The change of the energy and angular momentum of the black hole during a time
interval relies on the fluxes of energy and angular momentum of the ingoing
wave function. To get the wave function, we introduce a tortoise coordinate
and solve the second-order differential equation at the event horizon. Here
the time interval is infinitesimal. For the non-extremal BTZ black hole, the
increase of the event horizon ensures that the WCCC is valid. The first law of
thermodynamics is recovered by the scattering. For the near-extremal and
extremal BTZ black holes, Eq.(21) is divergent at their event horizons.
Therefore, we need to resort to other methods to test the validity. The
validity is tested by evaluating the minimum value of the function $f$. It is
found that their horizons do not disappear and the singularities are always
hidden behind the horizons.

The rest is organized as follows. The BTZ black hole solution is given and its
thermodynamics are discussed in the next section. In section 3, the first law
of thermodynamics in the non-extremal BTZ black hole is recovered by the
scattering of the scalar field. In section 4, the validity of the WCCC in the
extremal and near-extremal BTZ black holes is tested by the minimum values of
the function $f$. Section 5 is devoted to our discussion and conclusion.

##  2 BTZ black holes

The BTZ metric is given by [55, 56]

$\displaystyle ds^{2}$ $\displaystyle=$ $\displaystyle-
fdt^{2}+\frac{1}{f}dr^{2}+r^{2}(d\varphi-\frac{J}{2r^{2}}dt)^{2},$ (1)

where

$\displaystyle f$ $\displaystyle=$ $\displaystyle
f(M,J,r)=-M+\frac{r^{2}}{l^{2}}+\frac{J^{2}}{4r^{2}}.$ (2)

It describes a locally three-dimensional rotating AdS spacetime. The parameter
$l^{2}$ is related to the cosmological constant $\Lambda$ as
$l^{2}=-\frac{1}{\Lambda}$. $M$ and $J$ are the ADM mass and angular momentum,
respectively. They determine the asymptotic behavior of the spacetime. The
event (inner) horizons locate at $r_{+}(r_{-})$ and satisfy the relations

$\displaystyle Ml^{2}=r_{+}^{2}+r_{-}^{2},\quad\quad
J^{2}l^{2}=4r_{+}^{2}r_{-}^{2}.$ (3)

When $r_{+}=r_{-}$, the two horizons are coincident with each other and the
black hole becomes an extremal one.

The entropy, Hawking temperature, angular velocity and ADM mass are

$\displaystyle S$ $\displaystyle=$ $\displaystyle 4\pi r_{+},\quad\quad
T=\frac{r_{+}}{2\pi l^{2}}-\frac{J^{2}}{8\pi r_{+}^{3}},$
$\displaystyle\Omega$ $\displaystyle=$
$\displaystyle\frac{J}{2r_{+}^{2}},\quad\quad
M=\frac{r_{+}^{2}}{l^{2}}+\frac{J^{2}}{4r_{+}^{2}},$ (4)

respectively. Here, the expression of the entropy used in [55] is adopted,
which shows that the entropy is equal to twice the perimeter length of the
horizon. When the mass of a BTZ black hole varies, other thermodynamic
quantities of the black hole, such as entropy, temperature and angular
velocity, and so on, will also vary. These thermodynamic quantities obey the
first law of thermodynamics

$\displaystyle dM=TdS+\Omega dJ.$ (5)

We will find that the first law is recovered by the scattering of the scalar
field in the next section. These variations are caused by the interaction
between the scalar field and the black hole. Due to the interaction, the
energy and angular momentum are transferred and they are evaluated by the
energy flux and angular momentum flux. Therefore, we first write the action
and calculate the energy-momentum tensor.

##  3 Thermodynamics of non-extremal BTZ black holes

The action for the minimally coupled complex scalar field under the BTZ
spacetime is

$\displaystyle
I=\int{dtdrd\varphi\sqrt{-g}\mathcal{L}}=-\frac{1}{2}\int{dtdrd\varphi\sqrt{-g}[\partial_{\mu}\Phi\partial^{\mu}\Phi^{\star}+\mu_{0}^{2}\Phi\Phi^{\star}]},$
(6)

where $\mathcal{L}$ is the Lagrangian density and $\mu_{0}$ is the mass [60].
Then the energy-momentum tensor is obtained from the action, namely,
$T_{\mu\nu}=-\frac{2}{\sqrt{-g}}\frac{\delta I}{\delta g^{\mu\nu}}$. We get

$\displaystyle
T_{\nu}^{\mu}=\frac{1}{2}\partial^{\mu}\Phi\partial_{\nu}\Phi^{\star}+\frac{1}{2}\partial^{\mu}\Phi^{\star}\partial_{\nu}\Phi+\delta_{\nu}^{\mu}\mathcal{L}.$
(7)

To evaluate the energy-momentum tensor, we need to know the expression of the
wave equation $\Phi$ which obeys the equation of motion for the scalar field.
This equation is obtained from the action (6) and takes on the form

$\displaystyle\frac{1}{\sqrt{-g}}\frac{\partial}{\partial
x^{\mu}}\left(\sqrt{-g}g^{\mu\nu}\frac{\partial\Phi}{\partial
x^{\nu}}\right)-\mu_{0}^{2}\Phi=0.$ (8)

Due to the existence of the killing vectors $(\frac{\partial}{\partial
t})^{a}$ and $(\frac{\partial}{\partial\varphi})^{a}$ in the BTZ background
spacetime, we carry out the separation of variables

$\displaystyle\Phi=e^{-i(\omega t-j\varphi)}R(r),$ (9)

where $\omega$ and $j$ denote the energy and angular momentum, respectively.
Inserting the contravariant components of the BTZ metric and the separation of
variables (9) into the Klein-Gordon equation (8) yields the second-order
differential equation. To solve this equation, we introduce a tortoise
coordinate [61]

$\displaystyle r_{\star}=r+\frac{1}{2\kappa}ln\frac{r-r_{+}}{r_{+}},$ (10)

where $\kappa=2\pi T$ is the surface gravity at the event horizon and $T$ is
the Hawking temperature. Then the second-order differential equation becomes

$\displaystyle\frac{d^{2}R(r)}{dr_{\star}^{2}}$ $\displaystyle+$
$\displaystyle\frac{f^{2}+f(2\kappa r+1)}{(f+1)^{2}r}\frac{dR(r)}{dr_{\star}}$
(11) $\displaystyle+$ $\displaystyle\frac{4\omega^{2}r^{4}-4\omega
Jjr^{2}+4j^{2}r^{2}f-J^{2}j^{2}-4f\mu_{0}^{2}r^{4}}{4(f+1)^{2}r^{4}}R(r)=0.$

Since we are interested in the scattering near the event horizon, the equation
is going to be solved at the horizon. Let $r\rightarrow r_{+}$. Eq.(11) is
reduced to

$\displaystyle\frac{d^{2}R(r)}{dr_{\star}^{2}}+(\omega-j\Omega)R(r)=0.$ (12)

In the above equation, $\Omega=\frac{J}{2r_{+}^{2}}$ is the angular velocity
at the event horizon. From Eq.(12), we get the radial solutions

$\displaystyle R(r)\sim e^{\pm i(\omega-j\Omega)r_{\star}},$ (13)

where the solutions with $+(-)$ denote the outgoing (ingoing) radial waves.
Therefore, the standard wave equations are

$\displaystyle\Phi=e^{-i(\omega t-j\varphi)\pm i(\omega-j\Omega)r_{\star}}.$
(14)

The interaction between the field and the black hole transfers the energy and
angular momentum. Since we are discussing the horizon changes after the black
hole absorbs the energy and angular momentum, we focus our attention on the
ingoing wave equation.

Two Killing vectors $(\frac{\partial}{\partial t})^{a}$ and
$(\frac{\partial}{\partial\varphi})^{a}$ correspond to two local conservation
laws in the BTZ spacetime. The corresponding conservative quantities are
energy $E$ and angular momentum $L$. When the fluxes of energy and angular
momentum flow into the event horizon and are absorbed by the black hole, the
energy and angular momentum of the hole change. The energy flux and angular
momentum flux are

$\displaystyle\frac{dE}{dt}=\int{T_{t}^{r}\sqrt{-g}d\varphi},\quad\frac{dL}{dt}=-\int{T_{\varphi}^{r}\sqrt{-g}d\varphi},$
(15)

respectively. Combining the fluxes with the energy-momentum tensor and the
ingoing wave equation yields

$\displaystyle\frac{dE}{dt}=2\pi
r_{+}\omega(\omega-j\Omega),\quad\frac{dL}{dt}=2\pi r_{+}j(\omega-j\Omega).$
(16)

In the derivation, $\frac{dr_{\star}}{dr}=\frac{f+1}{f}$ obtained from Eq.(10)
was used. The energy of the black hole is its ADM mass and the angular
momentum is expressed as $J$. Therefore, the increases of the energy and
angular momentum during the time interval $dt$ are

$\displaystyle dM=2\pi r_{+}\omega(\omega-j\Omega)dt,\quad dJ=2\pi
r_{+}j(\omega-j\Omega)dt,$ (17)

which may be negative or positive values depending on the sign of the value of
$\omega-j\Omega$. When $\omega>j\Omega$, the energy and angular momentum of
the black hole increase and the fluxes flow into the event horizon. There is
no change of the energy and angular momentum for $\omega=j\Omega$.
$\omega<j\Omega$ implies the decrease of the energy and angular momentum. Then
the energy and angular momentum are extracted by the scattering and the
superradiation occurs. In fact, the appearance of superradiation should
satisfy that the boundary condition of the scalar field is in the asymptotic
region. Here we follow the work of Gwak and focus on the infinitesimal change
in the BTZ spacetime [20]. Therefore, our discussion does not rely on the
asymptotic boundary conditions.

In the following discussion, the time interval is assumed to be infinitesimal.
Correspondingly, the variations of the energy and angular momentum are also
infinitesimal. The scattering varies the function $f$ and the horizon radius
$r_{+}$. The variations are labeled as $\delta f$ and $dr_{+}$, respectively.
These variations satisfy

$\displaystyle\delta f$ $\displaystyle=$ $\displaystyle
f(M+dM,J+dJ,r_{+}+dr_{+})-f(M,J,r_{+})$ (18) $\displaystyle=$
$\displaystyle\left.\frac{\partial f(M,J,r)}{\partial
M}\right|_{r=r_{+}}dM+\left.\frac{\partial f(M,J,r)}{\partial
J}\right|_{r=r_{+}}dJ+\left.\frac{\partial f(M,J,r)}{\partial
r}\right|_{r=r_{+}}dr_{+},$

where

$\displaystyle\left.\frac{\partial f(M,J,r)}{\partial M}\right|_{r=r_{+}}$
$\displaystyle=$ $\displaystyle-1,\quad\quad\left.\frac{\partial
f(M,J,r)}{\partial J}\right|_{r=r_{+}}=\frac{J}{2r_{+}^{2}},$
$\displaystyle\left.\frac{\partial f(M,J,r)}{\partial r}\right|_{r=r_{+}}$
$\displaystyle=$ $\displaystyle 4\pi T.$ (19)

To derive $dr_{+}$, one can assume that the final state is still a black hole
after the absorption of the infinitesimal energy and angular momentum [35,
20]. This implies $f(M+dM,J+dJ,r_{+}+dr_{+})=f(M,J,r_{+})=0$. Thus, the
variation of the horizon radius is

$\displaystyle dr_{+}=\frac{r_{+}(\omega-j\Omega)^{2}dt}{2T}.$ (20)

When $\omega\neq j\Omega$, we get $dr_{+}>0$. When $\omega=j\Omega$, we have
$dr_{+}=0$. Therefore, the horizon radius does not decrease when the black
hole absorbs the ingoing wave. It implies that the singularity is hidden
behind the event horizon and can not be observed by external observers of the
black hole. Using the relation between the entropy and horizon radius, we get

$\displaystyle dS=\frac{2\pi r_{+}(\omega-j\Omega)^{2}dt}{T}.$ (21)

It shows that the entropy does not decrease under the scattering of the field.
This result supports the second law of thermodynamics and is a simple
consequence of the fact that the system satisfies the null energy condition.
From Eqs.(17) and (21), we get

$\displaystyle dM=TdS+\Omega dJ.$ (22)

Therefore, the first law of thermodynamics in the non-extremal BTZ black hole
is recovered by the scattering of the scalar field.

In the thought experiment, people usually prefer to study systems which
inferentially close to the critical condition. In the next section, we will
investigate this case, namely, near-extremal and extremal BTZ black holes. For
these black holes, Eq.(21) is divergent at their event horizons. Thus, the
above method can not be applied to the extremal and near-extremal BTZ black
holes. We need to resort to other methods to test the WCCC.

##  4 WCCC in near-extremal and extremal BTZ black holes

The WCCC in the near-extremal and extremal BTZ black holes has been tested. It
was found that the near-extremal BTZ black hole had the possibility to be
overspun [49]. But the extremal BTZ black hole could not be overspun [57]. In
this section, we review the validity of the WCCC in the near-extremal and
extremal BTZ black holes by the minimum values of the function $f$ at the
final states. Due to the interaction between the black hole and the field, the
energy and angular momentum of the black hole change. Correspondingly, the
value of the function $f$ changes. In the metric, there are two roots
(correspond to the inner and event horizons, respectively) for $f<0$ and a
root (corresponds to the event horizon) for $f=0$. When $f>0$, the event
horizon disappears and the singularity is naked.

In this section, the time interval is also infinitesimal. Correspondingly, the
transferred energy and angular momentum via the scattering is also
infinitesimal. The minimum value of $f$ is expressed as
$f_{0}=f(M,J,r_{0})=-M+\frac{r_{0}^{2}}{l^{2}}+\frac{J^{2}}{4r_{0}^{2}}$,
where $r_{0}$ is the location corresponding to $f_{0}$. $r_{0}$ is not an
independent variable, depending on $M$ and $J$. Thus we get

$\displaystyle f(M+dM,J+dJ,r_{0}+dr_{0})$ (23) $\displaystyle=$ $\displaystyle
f_{0}+\left.\frac{\partial f(M,J,r)}{\partial
M}\right|_{r=r_{0}}dM+\left.\frac{\partial f(M,J,r)}{\partial
J}\right|_{r=r_{0}}dJ+\left.\frac{\partial f(M,J,r)}{\partial
r}\right|_{r=r_{0}}dr_{0}$ $\displaystyle=$
$\displaystyle-\left(\frac{\omega}{j}\right)^{2}2\pi
j^{2}r_{+}dt+\left(\frac{\omega}{j}\right)2\pi
j^{2}r_{+}\left(\Omega+\Omega_{0}\right)dt+f_{0}-2\pi
j^{2}r_{+}\Omega\Omega_{0}dt,$

where

$\displaystyle\left.\frac{\partial f(M,J,r)}{\partial
M}\right|_{r=r_{0}}=-1,\quad\left.\frac{\partial f(M,J,r)}{\partial
J}\right|_{r=r_{0}}=\frac{J}{2r_{0}^{2}},\quad\left.\frac{\partial
f(M,J,r)}{\partial r}\right|_{r=r_{0}}=0,$ (24)

and $\Omega_{0}=\frac{J}{2r_{0}^{2}}$ is the angular velocity at the location
$r_{0}$. The formulae in Eq.(17) was used to derive Eq.(23). The above
equation is a quadratic equation about $\frac{\omega}{j}$ and has a maximal
value by adjusting the value of $\frac{\omega}{j}$. If this maximal value is
greater than zero, there is no horizon. Instead, the event horizons exist.

For the extremal BTZ black hole, the event and inner horizons are coincident
with each other and the temperature is zero. Thus, the term $TdS$ in Eq.(5)
disappears and $dM=\Omega dJ$. Using Eq.(17), we can easily get
$\omega=j\Omega$. The location of the event horizon is coincident with that of
the minimum value of the function $f$, namely, $r_{0}=r_{+}$. Thus, Eq.(23) is
written as

$\displaystyle f(M+dM,J+dJ,r_{0}+dr_{0})=-2\pi
r_{+}\left(\omega-j\Omega\right)^{2}dt=0.$ (25)

This result shows that the extremal black hole is also extremal one with the
new mass and angular momentum under the scattering. Therefore, the extremal
BTZ black hole cannot be overspun. This result is full in accordance with that
gotten by Rocha and Cardoso in [57], where the WCCC is tested by throwing a
point particle into the black hole.

For the near extremal BTZ black hole, there are $f_{0}<0$ and $|f_{0}|\ll 1$.
To get the maximal value of the function, we order $r_{+}=r_{0}+\epsilon$,
where $0<\epsilon\ll 1$. Meanwhile, we let $dt$ be on the infinitesimal scale
and $\epsilon\sim dt$. Thus, the function $f_{0}$ is simplified to

$\displaystyle
f_{0}=-\frac{2r_{+}}{l^{2}}\epsilon+\frac{J^{2}}{2r_{+}^{3}}\epsilon<0.$ (26)

For convenience of discussion, we rewrite Eq.(23) as a function about
$\frac{\omega}{j}$ and get

$\displaystyle f\left(\frac{\omega}{j}\right)$ $\displaystyle=$
$\displaystyle-2\pi j^{2}r_{+}\epsilon\left(\frac{\omega}{j}\right)^{2}$ (27)
$\displaystyle+2\pi
j^{2}r_{+}(\Omega+\Omega_{0})\epsilon\left(\frac{\omega}{j}\right)-\frac{2r_{+}}{l^{2}}\epsilon+\frac{J^{2}}{2r_{+}^{3}}\epsilon-2\pi
j^{2}r_{+}\Omega\Omega_{0}\epsilon.$

The maximum value, which locates at
$\frac{\omega}{j}=\frac{\Omega+\Omega_{0}}{2}$, is

$\displaystyle
f\left(\frac{\omega}{j}\right)_{max}=-\frac{2r_{+}}{l^{2}}\epsilon+\frac{J^{2}}{2r_{+}^{3}}\epsilon+\mathcal{O}(\epsilon),$
(28)

where $\mathcal{O}(\epsilon)=\frac{2\pi J^{2}j^{2}}{r_{+}^{5}}\epsilon^{3}$
can be neglected. Using Eq.(26), we find
$f\left(\frac{\omega}{j}\right)_{max}<0$. This implies that there are two
roots existed in the function. Therefore, the event and inner horizons do not
disappear under the scattering of the scalar field and the singularity is
hidden behind the event horizon. In [49], D$\ddot{u}$ztas found that the near-
extremal BTZ black hole could be overspun via the research of the particle
absorption and field effects. Clearly, our result is different from that
gotten by him.

##  5 Discussion and Conclusion

In this paper, we investigated the thermodynamics and WCCC in the BTZ black
holes by the scattering of the scalar field. The variations of the energy and
angular momentum in the black holes during an infinitesimal time interval were
calculated. The first law of thermodynamics in the non-extremal BTZ black hole
was recovered by the scattering. The increase of the horizon radius ensures
that the singularity is hidden behind the event horizon of the non-extremal
black hole. For the near-extremal and extremal BTZ black holes, since Eq.(21)
is divergent, we tested the WCCC by evaluating the minimum values of the
function $f$ at the final states. We found that these two black holes maintain
their near-extremity and extremity respectively. This result is full
consistence with that gotten by Wald and Jorse [13, 14].

In the recent work, D$\ddot{u}$ztas directly assumed that the horizons were
destroyed and obtained the relationship between the frequency and azimuthal
wave number of the incident field [49]. When the superradiation occurred, this
frequency range satisfied
$\frac{Jn}{Ml^{2}(1+2\epsilon)}<\omega<\frac{n}{l(1+\epsilon)}$, where $n$ is
the azimuthal wave number. When there was no superradiation, it obeyed
$0<\omega<\frac{n}{l(1+\epsilon)}$. For the extremal BTZ black hole, he found
that it couldn’t overspin if the supperradiation occurred. However, if there
was no superradiation for the field, overspinning would appear. In our
investigation, we did not directly assume that the black hole horizons are
destroyed. We found that the extremal and near-extremal BTZ black holes can
not be overspun in any frequencies range.

Acknowledgments This work is supported by the National Natural Science
Foundation of China (Grant nos. 11205125, 11875095).

## References

  * [1] R. Penrose, _Gravitational collapse: the role of general relativity_ , _Riv. Nuovo Cimento_ 1 (1969) 252.
  * [2] R. Wald, _Gedanken experiments to destroy a black hole_ , _Ann. Phys._ 82 (1974) 548.
  * [3] T. Jacobson and T.P. Sotiriou, _Over-spinning a black hole with a test body_ , _Phys. Rev. Lett._ 103 (2009) 141101.
  * [4] V.E. Hubeny, _Overcharging a black hole and cosmic censorship_ , _Phys. Rev._ D 59 (1999) 064013.
  * [5] G.E.A. Matsas and A.R.R. da Silva, _Overspinning a nearly extreme charged black hole via a quantum tunneling process_ , _Phys. Rev. Lett._ 99 (2007) 181301.
  * [6] S. Hod, _Weak cosmic censorship: as strong as ever_ , _Phys. Rev. Lett._ 100 (2008) 121101.
  * [7] E. Barausse, V. Cardoso and G. Khanna, _Test bodies and naked singularities: Is the self-force the cosmic censor?_ _Phys. Rev. Lett._ 105 (2010) 261102.
  * [8] E. Barausse, V. Cardoso and G. Khanna, _Testing the cosmic censorship conjecture with point particles: The effect of radiation reaction and the self-force_ , _Phys. Rev._ D 84 (2011) 104006.
  * [9] P. Zimmerman, I. Vega, E. Poisson and R. Haas, _Selfforce as a cosmic censor_ , _Phys. Rev._ D 87 (2013) 041501.
  * [10] S. Isoyama, N. Sago and T. Tanaka, _Cosmic censorship in overcharging a Reissner-Nordstrom black hole via charged particle absorption_ , _Phys. Rev._ D 84 (2011) 124024.
  * [11] M. Colleoni and L. Barack, _Overspinning a Kerr black hole: The effect of the self-force_ , _Phys. Rev._ D 91 (2015) 104024.
  * [12] M. Colleoni, L. Barack, Abhay G. Shah and M. van de Meent, _Overspinning a Kerr black hole: The effect of the self-force_ , _Phys. Rev._ D 92 (2015) 084044.
  * [13] R.M. Wald, _Kerr-Newman black holes cannot be over-charged or over-spun,_ _Int. J. Mod. Phys._ D 27 (2018) 1843003.
  * [14] J. Sorce and R.M. Wald, _Gedanken experiments to destroy a black hole. II. Kerr-Newman black holes cannot be overcharged or overspun_ , _Phys. Rev._ D 96 (2017) 104014.
  * [15] T. Crisford and J.E. Santos, _Violating weak cosmic censorship in $AdS_{4}$_, _Phys. Rev. Lett._ 118 (2017) 181101.
  * [16] N. Arkani-Hamed, L. Motl, A. Nicolis and C. Vafa, _The string landscape, black holes and gravity as the weakest force_ , _JHEP_ 0706 (2007) 060.
  * [17] K. D$\ddot{u}$ztas and I. Semiz, _Cosmic censorship, black holes and integer-spin test fields_ , _Phys. Rev._ D 88 (2013) 064043.
  * [18] G.Z. Toth, _Test of the weak cosmic censorship conjecture with a charged scalar field and dyonic Kerr-Newman black holes_ , _Gen. Relat. Grav._ 44 (2012) 2019.
  * [19] I. Semiz, _Dyonic Kerr-Newman black holes, complex scalar field and Cosmic Censorship_ , _Gen. Relat. Grav._ 43 (2011) 833.
  * [20] B. Gwak, _Weak cosmic censorship conjecture in Kerr-(Anti-)de Sitter black hole with scalar field_ , _JHEP_ 1809 (2018) 081.
  * [21] J.M. Martin-Garcia and C. Gundlach, _Global structure of Choptuik’s critical solution in scalar field collapse_ , _Phys. Rev._ D 68 (2003) 024011.
  * [22] M. Reiterer and E. Trubowitz, _Choptuik’s critical spacetime exists_ , [ arXiv:1203.3766[gr-qc]].
  * [23] C. Gundlach, _Critical phenomena in gravitational collapse_ , _Phys. Rept._ 376 (2003) 339.
  * [24] V. Cardoso and O.J.C. Dias, _Rayleigh-Plateau and Gregory-Laflamme instabilities of black strings_ , _Phys. Rev. Lett._ 96 (2006) 181601.
  * [25] P.S. Joshi, N. Dadhich and R. Maartens, _Why do naked singularities form in gravitational collapse?_ _Phys. Rev._ D 65 (2002) 101501.
  * [26] T. Moon and Y.S. Myung, _Gregory-Laflamme instability of BTZ black hole in new massive gravity_ , _Phys. Rev._ D 88 (2013) 124014.
  * [27] Y.S. Myung and T. Moon, _Thermodynamic and classical instability of AdS black holes in fourth-order gravity_ , _JHEP_ 1804 (2014) 058.
  * [28] V. Husain and S. Singh, _On the Penrose inequality in anti-de Sitter space_ , _Phys. Rev._ D 96 (2017) 104055.
  * [29] K.S. Revelar and I. Vega, _Overcharging higher-dimensional black holes with point particles_ , _Phys. Rev._ D 96 (2017) 064010.
  * [30] S. Hod, _Cosmic censorship: formation of a shielding horizon around a fragile horizon_ , _Phys. Rev._ D 87 (2013) 024037.
  * [31] K. D$\ddot{u}$ztas, _Can test fields destroy the event horizon in the Kerr-Taub-NUT spacetime?_ _Class. Quant. Grav._ 35 (2018) 045008.
  * [32] S.J. Gao and Y. Zhang, _Destroying extremal Kerr-Newman black holes with test particles_ , _Phys. Rev._ D 87 (2013) 044028.
  * [33] T. Crisford, G.T. Horowitz and J.E. Santos, _Testing the Weak Gravity Cosmic Censorship Connection_ , _Phys. Rev._ D 97 (2018) 066005.
  * [34] Y. Mino, M. Sasaki and T. Tanaka, _Gravitational radiation reaction to a particle motion_ , _Phys. Rev._ D 55 (1997) 3457.
  * [35] B. Gwak, _Thermodynamics with pressure and volume under charged particle absorption_ , _JHEP_ 1711 (2017) 129.
  * [36] B. Gwak, _Cosmic censorship conjecture in Kerr-Sen black hole_ , _Phys. Rev._ D 95 (2017) 124050 .
  * [37] Y. Gim and B. Gwak, _Charged black hole in gravity’s rainbow: violation of weak cosmic censorship_ , [arXiv:1808.05943[gr-qc]].
  * [38] J. Crisostomo and R. Olea, _Hamiltonian treatment of the gravitational collapse of thin shells_ , _Phys. Rev._ D 69 (2004) 104023.
  * [39] K. D$\ddot{u}$ztas and M. Jamil, _Testing cosmic censorship conjecture for extremal and near-extremal (2+1)-dimensional MTZ black holes_ , [arXiv:1808.04711[gr-qc]].
  * [40] B. Liang, S.W. Wei and Y.X. Liu, _Weak cosmic censorship conjecture in Kerr black holes of modified gravity_ , [arXiv:1804.06966 [gr-qc]].
  * [41] M. Bouhmadi-Lopez, V. Cardoso, A. Nerozzi and J V. Rocha, _Cosmic censorship conjecture in Kerr-Sen black hole_ , _Phys. Rev._ D 81 (2010) 084051.
  * [42] M. Richartz and A. Saa, _Challenging the weak cosmic censorship conjecture with charged quantum particles_ , _Phys. Rev._ D 84 (2011) 104021.
  * [43] B. Ge, Y. Mo, S. Zhao and J. Zheng, _Higher-dimensional charged black holes cannot be over-charged by gedanken experiments_ , _Phys. Lett._ B 783 (2018) 440.
  * [44] J. Natario, L. Queimada and R. Vicente, _Test fields cannot destroy extremal black holes_ , _Class. Quant. Grav._ 33 (2016) 175002.
  * [45] J. An, J. Shan, H. Zhang, S. Zhao, _Five-dimensional Myers-Perry black holes cannot be overspun in gedanken experiments_ , _Phys. Rev._ D 97 (2018) 104007.
  * [46] T.Y. Yu and W.Y. Wen, _Cosmic censorship and weak gravity conjecture in the Einstein-Maxwell-dilaton theory_ , _Phys. Lett._ B 781 (2018) 713.
  * [47] D.Y. Chen, W. Yang and X.X. Zeng, _Thermodynamics and weak cosmic censorship conjecture in Reissner-Nordstr $\ddot{o}$m anti-de Sitter black holes with scalar field_, _Nucl. Phys._ B 946 (2019) 114722.
  * [48] D.Y. Chen, _Thermodynamics and weak cosmic censorship conjecture in extended phase spaces of anti-de Sitter black holes with particles absorption_ , _Eur. Phys. J._ C 79 (2019) 353.
  * [49] K. D$\ddot{u}$ztas, _Overspinning BTZ black holes with test particles and fields_ , _Phys. Rev._ D 94 (2016) 124031.
  * [50] P. Wang, H.W. Wu and H. Yang, _Thermodynamics and weak cosmic censorship conjecture in nonlinear electrodynamics black holes via charged particle absorption_ , [arXiv:1904.12365[gr-qc]].
  * [51] B.R. Mu and J. Tao _Minimal length effect on thermodynamics and weak cosmic censorship conjecture in anti-de Sitter black holes via charged particle absorption_ , [arXiv:1906.10544[gr-qc]].
  * [52] W. Hong, B.R. Mu and J. Tao, _Thermodynamics and weak cosmic censorship conjecture in the charged RN-AdS black hole surrounded by quintessence under the scalar field_ , [arXiv:1905.07747[gr-qc]].
  * [53] S.Q. Hu, Y.C. Ong and D.N. Page, _No violation of the second law in extended black hole thermodynamics_ , [arXiv:1906.05870[gr-qc]].
  * [54] X.X. Zeng and H.Q. Zhang, _Thermodynamics and weak cosmic censorship conjecture in the Kerr-AdS black hole_ , [arXiv:1905.01618[gr-qc]].
  * [55] M. Ba$\tilde{n}$ados, C. Teitelboim and J. Zanelli, _The black hole in three dimensional space time_ , _Phys. Rev. Lett._ 69 (1992) 1849.
  * [56] M. Ba$\tilde{n}$ados, M. Henneaux, C. Teitelboim and J. Zanelli, _Geometry of the 2+1 black hole_ , _Phys. Rev._ D 48 (1993) 1506.
  * [57] J.V. Rocha and V. Cardoso, _Gravitational perturbation of the BTZ black hole induced by test particles and weak cosmic censorship in AdS spacetime_ , _Phys. Rev._ D 83 (2011) 104037.
  * [58] B. Wang, R.K. Su, P.K.N. Yu and E.C.M. Young, _Stability of the event horizon in (2+1)-dimensional black holes_ , _Phys. Rev._ D 54 (1996) 7298.
  * [59] R.B. Mann, J.J. Oh and M.I. Park, _Role of angular momentum and cosmic censorship in $(2+1)$-dimensional rotating shell collapse_, _Phys. Rev._ D 79 (2009) 064005.
  * [60] M. Kenmoku, M. Kuwata and K. Shigemoto, _Normal modes and no zero mode theorem of scalar fields in BTZ black hole spacetime_ , _Class. Quant. Grav._ 25 (2008) 145016.
  * [61] X.K. He and W.B. Liu, _Modified Hawking radiation in a BTZ black hole using Damour-Ruffini method_ , _Phys. Lett._ B 653 (2007) 330.


# Decision-Focused Learning without
Differentiable Optimization:
Learning Locally Optimized Decision Losses

Sanket Shah
Harvard University
<EMAIL_ADDRESS>&Kai Wang
Harvard University
<EMAIL_ADDRESS>&Bryan Wilder
Carnegie Mellon University
<EMAIL_ADDRESS>Andrew Perrault
The Ohio State University
<EMAIL_ADDRESS>&Milind Tambe
Harvard University
<EMAIL_ADDRESS>
###### Abstract

Decision-Focused Learning (DFL) is a paradigm for tailoring a predictive model
to a downstream optimization task that uses its predictions in order to
perform better on that specific task. The main technical challenge associated
with DFL is that it requires being able to differentiate through the
optimization problem, which is difficult due to discontinuous solutions and
other challenges. Past work has largely gotten around this this issue by
handcrafting task-specific surrogates to the original optimization problem
that provide informative gradients when differentiated through. However, the
need to handcraft surrogates for each new task limits the usability of DFL. In
addition, there are often no guarantees about the convexity of the resulting
surrogates and, as a result, training a predictive model using them can lead
to inferior local optima. In this paper, we do away with surrogates altogether
and instead learn loss functions that capture task-specific information. To
the best of our knowledge, ours is the first approach that entirely replaces
the optimization component of decision-focused learning with a loss that is
automatically learned. Our approach (a) only requires access to a black-box
oracle that can solve the optimization problem and is thus generalizable, and
(b) can be convex by construction and so can be easily optimized over. We
evaluate our approach on three resource allocation problems from the
literature and find that our approach outperforms learning without taking into
account task-structure in all three domains, and even hand-crafted surrogates
from the literature.

##  1 Introduction

Predict-then-optimize Donti et al. (2017); Elmachtoub and Grigas (2021) is a
framework for using machine learning to perform decision-making. As the name
suggests, it proceeds in two stages—first, a predictive model takes as input
features and makes some predictions using them, then second, these predictions
are used to parameterize an optimization problem that outputs a decision. A
large number of real-world applications involve both prediction and
optimization components and can be framed as predict-then-optimize
problems—for e.g., recommender systems in which missing user-item ratings need
to be predicted Isinkaye et al. (2015), portfolio optimization in which future
performance needs to be predicted Markowitz and Todd (2000), or strategic
decision-making in which the adversary behavior needs to be predicted Kar et
al. (2017).

In addition to wide applicability, this framework also formalizes the
relationship between prediction and decision-making. This is important because
such predictive models are typically learned independently of the downstream
optimization task in Machine Learning-based decision-making systems, and
recent work in the predict-then-optimize setting Elmachtoub and Grigas (2021);
Mandi et al. (2020); Wilder et al. (2019a); Ferber et al. (2020); Amos et al.
(2019); Wilder et al. (2019a); Xie et al. (2020); Wilder et al. (2019b);
Demirović et al. (2019) has shown that it is possible to achieve better task-
specific performance by tailoring the predictive model to the downstream task.
This is often done by differentiating through the entire prediction and
optimization pipeline end-to-end, leading to a family of approaches that we
will refer to as decision-focused learning (DFL) Wilder et al. (2019a).
Optimizing directly for the quality of decisions induced by the predictive
model in this end-to-end manner yields a loss function we call the decision
loss.

However, training with the decision loss can be challenging because the
solutions to optimization problems are often discontinuous in the predictions
(see Section 2.1). This results in an uninformative loss function with zero or
undefined gradients, neither of which are useful for learning a predictive
model. To address this, DFL approaches often leverage handcrafted surrogate
optimization tasks that provides more useful gradients. These surrogate
problems may be constructed by relaxing the original problem Elmachtoub and
Grigas (2021); Mandi et al. (2020); Wilder et al. (2019a); Ferber et al.
(2020), adding regularization to the objective Amos et al. (2019); Wilder et
al. (2019a); Xie et al. (2020), or even using entirely an different
optimization problem that shares the same decision space Wilder et al.
(2019b).

Designing good surrogates is an art, requiring manual effort, insight into the
optimization problem of interest. In addition, there are no guarantees that
the surrogates induce convex decision losses, leading to local optima that
further complicate training. Instead, we propose a fundamentally different
approach: to learn a decision loss directly for a given task, circumventing
surrogate problem design entirely. Our framework represents the loss as a
function in a particular parametric family and selects parameters which
provide an informative loss for the optimization task. We call the resulting
loss a _locally optimized decision loss (LODL)_.

Our starting point is the observation that a good decision loss should satisfy
3 properties: it should (i) be faithful to the original task, i.e., the
decision quality is consistent with the original problem; (ii) provide
informative gradients everywhere (i.e., defined and non-zero); and (iii) be
convex in prediction space to avoid local minima. These demands are in
tension—the first requirement prevents the loss function from being modified
too much to achieve the other two. It is not obvious apriori that any
tractable parametric family should be able to simultaneously satisfy all three
properties for the complex structure induced by many optimization tasks. We
resolve this tension by separately modeling the loss function locally for the
neighborhood around each individual training example. Faithful representation
of the decision loss is easier to accomplish locally in each individual
neighborhood than globally across instances, allowing us to introduce convex
parametric families of loss functions which capture structural intuitions
about properties important for optimization. To fit the parameters, we sample
points in the neighborhood of the true labels, evaluate the decision loss
associated with these sampled points, and then train a loss function to mimic
the decision loss.

We evaluate LODLs on three resource allocation domains from the literature
Hughes et al. (2018); Wilder et al. (2019a); Wang et al. (2020). Perhaps
surprisingly, we find that LODLs outperform handcrafted surrogates in two out
of the three. In our analysis, we discover a linear correlation between the
agreement of the learned LODL with the decision loss and the decision loss of
a predictive model learned using said LODL. Our approach motivates a new line
of research on decision-focused learning.

##  2 Background

Figure 1: Schematic highlighting how the predictive model $\bm{M_{\theta}}$ is
learned in different approaches. LODL does not require backpropagating through
the optimization problem.

In predict-then-optimize, a predictive model $\bm{M_{\theta}}$ first takes as
input features $\bm{x}$ and produces predictions
$\bm{\hat{y}}=\bm{M_{\theta}}(\bm{x})$. These predictions $\bm{\hat{y}}$ are
then used to parameterize an optimization problem that is solved to yield
decisions $\bm{z}^{*}(\bm{\hat{y}})$:

$\displaystyle\bm{z}^{*}(\bm{\hat{y}})=\operatorname*{arg\,min}_{\bm{z}}\hskip
5.69054pt$ $\displaystyle f(\bm{z};\bm{\hat{y}})$ $\displaystyle s.t.\hskip
5.69054pt$ $\displaystyle g_{i}(\bm{z})\leq 0\textrm{, for
}i\in\\{1,\,\ldots,\,m\\}$ (1)

Note that, unlike typical machine learning problems, the dimensionality of
$\dim(\bm{\hat{y}})=D$ is likely to be large as it consists of all predictions
needed to parameterize the optimization problem. Given the large
dimensionality, and the similarity in the role of all the predictions, the
predictive model typically predicts individual components of $\bm{\hat{y}}$,
i.e.
$\bm{\hat{y}}=[\hat{y}_{1},\ldots,\hat{y}_{D}]=[M_{\bm{\theta}}(x_{1}),\ldots,M_{\bm{\theta}}(x_{D})]$.

Predictions are evaluated with respect to the _decision loss (DL)_ of the
decision that they induce, i.e., the value under the objective function of the
optimization under the ground truth parameters $\bm{y}$:

$DL(\bm{\hat{y}},\bm{y})=f(\bm{z}^{*}(\bm{\hat{y}}),\bm{y})$

Thus, for a dataset
$[(\bm{x}_{1},\bm{y}_{1}),\ldots,(\bm{x}_{N},\bm{y}_{N})]$, we aim to learn a
model $\bm{M_{\theta}}$ that generates predictions
$[\bm{\hat{y}}_{1},\ldots,\bm{\hat{y}}_{N}]$ that minimize the decision loss
$DL$:

$\displaystyle\bm{\theta}^{*}=\operatorname*{arg\,min}_{\bm{\theta}}\frac{1}{N}\sum_{n=1}^{N}DL(\bm{M_{\bm{\theta}}}(\bm{x}_{n}),\bm{y}_{n})$

This is in contrast with standard supervised learning approaches in which the
quality of a prediction is measured by a somewhat arbitrary intermediate loss
(e.g., mean squared error) that does not contain information about the
downstream decision-making task. In this paper, we refer to models that use an
intermediate loss as _2-stage_ and those that directly optimize for $DL$ as
_decision-focused learning (DFL)_. Figure 1 outlines how a predictive model is
learned using these different approaches.

###  2.1 Motivating Example

Consider an $\arg\min$ optimization where the goal is to predict the
disutility $\bm{y}$ of 2 agents (A, B), e.g., $\bm{y}=(0,1)$. Now, if these
parameters are predicted perfectly, the decision is $\bm{z}=$ “Pick A”, and
the decision loss $DL$ is the true disutility of agent A, i.e., $DL=0$.

On the other hand, consider the set of predictions
$\bm{\hat{y}}_{bad}=(1\pm\epsilon_{A},0\pm\epsilon_{B})$ for
$0<\epsilon_{A},\epsilon_{B}<0.5$. Any prediction in this set will yield the
decision ‘Pick B” and a decision loss $DL$ of 1. Given that the decision loss
is constant in this region, the gradients are all zero, i.e.,
$\nabla_{\bm{\hat{y}}}DL(\bm{\hat{y}},\bm{y})\bigr{|}_{\bm{\hat{y}}\in\bm{\hat{y}}_{good}}=0$.
As a result, if a predictive model makes such a prediction, it cannot improve
its predictions by gradient descent. Therefore, although $DL$ is what we want
to minimize, we don’t want to fit it perfectly.

(a) True Decision Loss

(b) Handcrafted Surrogate

(c) LODL

Figure 2: Graphs plotting the values of different loss functions (Blue = 1,
Red = 0) as a function of the predictions of different disutilities for A and
B.

If instead of minimizing $DL$ directly, we minimized a surrogate loss
$SL=\hat{y}_{A}-\hat{y}_{B}$, gradient descent would lead to the model to
predict $\hat{y}=(-\infty,\infty)$ regardless of the initialization (see
Figure 2). While $\hat{y}$ isn’t the true set of disutilities, it does lead to
the optimal decision, i.e., “Pick A” and is thus effective from a predict-
then-optimize perspective.

The challenge is then coming up with such surrogates. Although it is easy for
the problem above, it becomes more complicated as the number and types of
variables and constraints grows. Below, we propose an approach to
automatically learn good surrogates. Figure 2(c) shows what our method looks
like for the example above.

##  3 Related Work

A great deal of recent work on decision-focused learning and related topics
aims to incorporate information about a downstream optimization problem into
the training of a machine learning models. Some optimization problems
(especially strongly convex ones) can be directly differentiated through Donti
et al. (2017); Amos et al. (2018); Agrawal et al. (2019). For others,
particularly discrete optimization problems with ill-defined gradients, a
variety of approaches have been proposed. Most of these construct surrogate
loss functions via smoothing the optimization problem Mensch and Blondel
(2018); Wilder et al. (2019a); Ferber et al. (2020); Wilder et al. (2019b);
Tschiatschek et al. (2018); Mandi and Guns (2020). Alternatively, Elmachtoub
and Grigas (2021) propose a closed-form convex surrogate loss with desirable
theoretical properties; however, this loss applies only when the optimization
problem has a linear objective function. Similarly, Mulamba et al. (2021)
provide a contrastive learning-based surrogate which does not require
differentiation through optimization, but which is also developed specifically
for linear objectives. When the predictive model is itself a linear function,
Guler et al. (2022) propose an approach to search directly for the best model.

Perhaps the most related work to ours is by Berthet et al. (2020). They
differentiate through linear optimization problems during training by adding
randomized perturbations to smooth the induced loss function. Specifically,
they randomly perturb the predictions $\hat{y}$ with random noise $\epsilon$
and solve for $z^{*}(\hat{y}+\epsilon)$, which can be interpreted as replacing
the decision loss with its averaged value in a neighborhood around $\hat{y}$,
where the averaging smooths the function and ensures differentiability. There
are two key differences between our approach and theirs. First, they apply
random perturbations to optimization in the training loop in order to produce
a smoother surrogate loss. By contrast, we use random perturbations to learn a
loss function prior to training; during training optimization is removed
entirely. This allows us to use the same random samples to inform each
training iteration instead of drawing new samples per iteration. Second, their
approach applies only to linear objective functions while ours applies to
arbitrary optimization problems.

##  4 Locally Optimized Decision Losses (LODL)

In this paper, we do away with the need for custom task-specific relaxations
of the optimization problem $\bm{z}^{*}(\bm{\hat{y}})$ by instead translating
task-specific information from the decision loss $DL$ into a loss function
$LODL_{\bm{\phi}}(\bm{\hat{y}},\bm{y})$ that (i) approximates the behavior of
$DL$, and (ii) is convex by construction.

Our broad strategy to do this is to learn the function
$LODL_{\bm{\phi}}\approx DL$ using supervised machine learning. Specifically,
we proceed in 3 steps:

  1. 1.

We simplify the learning problem in two ways (Section 4.1). First, we learn a
separate LODL for every ($(\bm{x},\bm{y})$) pair in the dataset to make our
learning problem easier. Second, we note that there’s a chicken-and-egg
problem associated with learning LODLs—to train the LODL we need inputs of the
form $(\bm{\hat{y}},\bm{y})$, but to produce $\bm{\hat{y}}$ we need a
predictive model trained on said LODL. To resolve this, we make the assumption
that our predictive model $\bm{M_{\theta}}$ will get us sufficiently close to
the true labels $\bm{y}$. This means:

$LODL_{\bm{\phi}}(\bm{\hat{y}},\bm{y})=[LODL_{\bm{\phi}_{1}}(\bm{\hat{y}}_{1}),\ldots,LODL_{\bm{\phi}_{N}}(\bm{\hat{y}}_{N})],\quad\text{and}\quad\bm{\hat{y}}_{i}\approx\bm{y}_{i}\pm\bm{\epsilon}$

  2. 2.

Given these simplifications, we propose convex-by-construction parametric
forms for $\bm{LODL_{\bm{\phi}_{i}}}$ (Section 4.2). We subtract a constant
$DL(\bm{y}_{i},\bm{y}_{i})$ from the target to ensure that the function to be
learned has a minima at $\bm{\hat{y}}_{i}=\bm{y}_{i}$ and that the result can
be modeled well by a convex function:

$\displaystyle LODL_{\bm{\phi}_{i}}(\bm{\hat{y}}_{i})\approx
DL(\bm{\hat{y}}_{i},\bm{y}_{i})-DL(\bm{y}_{i},\bm{y}_{i})\implies
DL(\bm{\hat{y}}_{i},\bm{y}_{i})\approx
LODL_{\bm{\phi}_{i}}(\bm{\hat{y}}_{i})+\overbrace{DL(\bm{y}_{i},\bm{y}_{i})}^{\text{constant}}$

  3. 3.

We propose different strategies for sampling $\bm{\hat{y}}$ (Section 4.3) and
also describe the equation used to learn the optimal LODL parameters
$\phi^{*}$ (Equation 2).

###  4.1 Local Loss Functions

We introduce a separate set of parameters $\bm{\phi}_{n}$ for each
$[(\bm{x}_{1},\bm{y}_{1}),\ldots,(\bm{x}_{n},\bm{y}_{n}),\ldots,(\bm{x}_{N},\bm{y}_{N})]$
in the training set. We take this step because learning a global approximation
to $DL(\bm{\hat{y}},\bm{y})$ (for arbitrary $\bm{\hat{y}}$) is hard; it
requires learning a closed-form approximation to the general optimization
problem $\bm{z}^{*}(\bm{\hat{y}})$ which may not always exist. Introducing
separate parameters per-instance gives two key advantages.

  1. 1.

Learning for a specific $\bm{y_{n}}$: Instead of learning a
$\mathbb{R}^{\dim(\bm{y})+\dim(\bm{\hat{y}})}$ function
$LODL_{\phi}(\bm{\hat{y}},\bm{y})$ to imitate $DL(\bm{\hat{y}},\bm{y})$, we
instead learn $N$ different $\mathbb{R}^{\dim(\bm{\hat{y}})}$ functions
$LODL_{\phi_{n}}(\bm{\hat{y}})$ that imitate $DL(\bm{\hat{y}},\bm{y}_{n})$ for
each $n\in N$. Doing this significantly reduces the dimensionality of the
learning problem—this is especially relevant when $N$ is not very large in
comparison to $\dim(\bm{y})$ (as in our experiments). It also circumvents the
need to enforce invariance properties on the global loss. For example, many
optimization problems are invariant to permutations of the ordering of
dimensions in $\bm{y}$, making it difficult to measure the quality of
$\bm{\hat{y}}$’s across different instances. In a local loss, the ordering of
the dimensions is fixed and so this issue is no longer relevant.

  2. 2.

Learning for only $\bm{\hat{y}}_{n}\approx\bm{y}_{n}$: In addition to the
simplification above, we don’t try to learn a faithful approximation
$\forall\bm{\hat{y}}\in\mathbb{R}^{\dim(\bm{y})}$—we instead limit ourselves
to learning an approximation of $DL(\bm{\hat{y}},\bm{y}_{n})$ only when
$\bm{\hat{y}}$ is in the neighborhood of $\bm{y}_{n}$. We assume that our
predictive model will always get us in the neighborhood of the true labels,
and the utility of LODL is in helping distinguish between these points.

The combination of these two choices makes the learned $LODL_{\phi_{n}}$ a
“local” surrogate for $DL$, rather than a global one.

###  4.2 Representing the $\bm{LODL}$

The key design choice in instantiating our framework is choice of the
parametric family used to represent the LODL. Optimization problems can induce
a complex loss landscape which is not easily summarized in a closed-form
function with concise parameterization. Accordingly, we design a set of
families which capture phenomena particularly important for common families of
predict-then-optimize problems.

#### Parametric families for the local losses

Having made the decision to allow separate parameters for each training
instance, the second design choice is how to represent each local loss, i.e.,
the specific parametric family to use. Our choice must be sufficiently
expressive to capture the local dynamics of the optimization problem while
remaining sufficiently efficient to be replicated across the $N$ training
instances. We propose that the structure of the loss function should capture
the underlying rationale for why decision-focused learning provides an
advantage over 2-stage in the first place; this is the key behavior which will
underpin improved decision quality. We identify three key phenomena which
motivate the design of the family of loss functions:

  1. 1.

Relative importance of different dimensions: Typically, the different
dimensions of a prediction problem are given equal weight, e.g., the MSE
weights errors in each coordinate of $\bm{y}$ equally. However, there may be
some dimensions along which $DL$ is more sensitive to local perturbations. For
example, a knapsack problem may be especially sensitive to errors in the value
of items which are on the cusp of being chosen. In such cases, DFL can capture
the relative importance of accurately predicting different dimensions.

  2. 2.

Cost of correlation: Given the possibly large dimensionality of $\bm{y}$, in
practice, the predictive model $M_{\bm{\theta}}$ does not typically predict
$\bm{y}$ directly. Instead, the the structure of the optimization is exploited
to make multiple predictions $[\hat{y}_{1},\ldots,\hat{y}_{K}]$ that are then
combined to create $\bm{\hat{y}}$. For example, in a knapsack problem, we
might train a model which separately predicts the value of each item (i.e.,
predicts each entry of $\bm{\hat{y}}$ separately) using features specific to
that item, instead of jointly predicting the entire set of values using the
features of all of the items. However, Cameron et al. (2022) show that
ignoring the correlation between different sub-$\bm{y}$ scale predictions (as
in 2-stage) can result in poor optimization performance, and that DFL can
improve by propagating information about the interactions between entries of
$\bm{y}$ to the predictive model.

  3. 3.

Directionality of predictions: In the
$\operatorname*{arg\,min}(\hat{y}_{1},\hat{y}_{2})$ example from the
introduction, the prediction $\hat{y}_{1}=2,\hat{y}_{2}=1$ produces the same
decision as $\hat{y}_{1}=2000,\hat{y}_{2}=1$. On the other hand, the
prediction $\hat{y}_{1}=0.5,\hat{y}_{2}=1$ leads to a different decision. As a
result, over-predicting and under-predicting often have different associated
costs for some optimization problems. Predictive models trained with DFL can
take into account this behavior while those trained by typical symmetric
2-Stage losses like MSE cannot.

Given these insights, we propose three corresponding families of loss
functions for $LODL_{\phi}$, each of which is convex by design and has a
global minima at the true label $\bm{y}_{n}$, a desirable property because
$DL$ also has its minima at $\bm{\hat{y}}=\bm{y}$.

  1. 1.

WeightedMSE: To take into account the relative importance of different
dimensions, we propose a weighted version of MSE:

$\text{WeightedMSE}(\bm{\hat{y}})=\sum_{l=1}^{\dim(\bm{y})}w_{l}\cdot(\hat{y}_{l}-y_{l})^{2},$

where ‘weights’ $w_{l}$ are the parameters of the LODL, i.e.,
$\bm{\phi}=\bm{w}\in\mathbb{R}_{+}^{\dim(\bm{y})}$ (for convexity).

  2. 2.

Quadratic: To take into account the effect of correlation of different
dimensions on each other, we propose learning a quadratic function that has
terms of the form $(\hat{y}_{i}-y_{i})(\hat{y}_{j}-y_{j})$:

$\text{Quadratic}(\bm{\hat{y}})=(\bm{\hat{y}}-\bm{y})^{T}H(\bm{\hat{y}}-\bm{y}),$

where $\bm{\phi}=H$ is a learned low-rank symmetric Positive semidefinite
(PSD) matrix. This family of functions is convex as long as $H$ is PSD, which
we enforce by parameterizing $H=L^{T}L$, where $L$ is a low-rank triangular
matrix $L$ of dimension $\dim(\bm{y})\times k$ and $k$ is the desired rank.

This loss function family has an appealing interpretation because learning
LODL is similar to estimating the partial derivative of $DL$ with respect to
its first input $\bm{\hat{y}}_{n}$. Specifically, consider the first three
terms of the Taylor expansion of $DL$ with respect to $\bm{\hat{y}}_{n}$ at
$(\bm{y}_{n},\bm{y}_{n})$:

$\displaystyle\quad
DL(\overbrace{\bm{y}_{n}+\bm{\epsilon}}^{\bm{\hat{y}}_{n}},\bm{y}_{n})$
$\displaystyle=\overbrace{DL(\bm{y}_{n},\bm{y}_{n})}^{\text{constant}}\;+\;\overbrace{\nabla_{\bm{\hat{y}}_{n}}DL(\bm{y}_{n},\bm{y}_{n})}^{\mathclap{\small\text{$0\leftarrow(\bm{y}_{n},\bm{y}_{n})$
is a
minima}}}\bm{\epsilon}+{\bm{\epsilon}}^{T}\overbrace{\nabla^{2}_{\bm{\hat{y}}_{n}}DL(\bm{y}_{n},\bm{y}_{n})}^{\mathclap{\text{Hessian
$H$}}}{\bm{\epsilon}}+\ldots$ $\displaystyle\approx
DL(\bm{y}_{n},\bm{y}_{n})+(\bm{\hat{y}}_{n}-\bm{y}_{n})^{T}H(\bm{\hat{y}}_{n}-\bm{y}_{n})$

Quadratic $LODL_{\phi}$ can be seen as a $2^{nd}$-order Taylor-series
approximation of $DL$ at $(\bm{y}_{n},\bm{y}_{n})$ where the learned $H$
approximates the Hessian of $DL$. Note that WeightedMSE is a special case of
this Quadratic loss when $H=diag(\bm{w})$.

  3. 3.

DirectedWeightedMSE and DirectedQuadratic: To take into account the fact that
overpredicting and underpredicting can have different consequences, we propose
modifications to the two loss function families above. For WeightedMSE, we
redefine the weight vector $\bm{w}$ as below, and learn both $\bm{w_{+}}$ and
$\bm{w_{-}}$. Similarly for Quadratic, we define 4 copies of the parameter $L$
based on the directionality of the predictions.

$w_{l}=\begin{cases}w_{+},&\text{if}\ \hat{y}_{i}-y_{i}\geq 0\\\
w_{-},&\text{otherwise}\end{cases}$

$L_{ij}=\begin{cases}L_{ij}^{++},&\text{if }\hat{y}_{i}-y_{i}\geq 0\text{ and
}\hat{y}_{j}-y_{j}\geq 0\\\ L_{ij}^{+-},&\text{if }\hat{y}_{i}-y_{i}\geq
0\text{ and }\hat{y}_{j}-y_{j}<0\\\ L_{ij}^{-+},&\text{if
}\hat{y}_{i}-y_{i}<0\text{ and }\hat{y}_{j}-y_{j}\geq 0\\\
L_{ij}^{--},&\text{otherwise}\end{cases}$

###  4.3 Learning $\bm{LODL_{\phi}}$

Given families proposed in Section 4.1, our goal is to learn some
$\bm{\phi^{*}}_{n}$ for every $n\in N$ such that
$LODL_{\bm{\phi_{n}}}(\bm{\hat{y}}_{n})\approx
DL(\bm{\hat{y}}_{n},\bm{y}_{n})$ for $\bm{\hat{y}}_{n}$ “close” to
$\bm{y}_{n}$. We propose a supervised approach to learning $\bm{\phi^{*}}_{n}$
which proceeds in two steps (Figure 1): (1) we build a dataset mapping
$\bm{\hat{y}}_{n}\rightarrow DL(\bm{\hat{y}}_{n},\bm{y}_{n})$ in the region of
$\bm{y}_{n}$, and then (2) we use this dataset to estimate $\bm{\phi^{*}}_{n}$
by minimizing the mean squared error to the true decision loss:

$\bm{\phi}^{*}_{n}=\operatorname*{arg\,min}_{\bm{\phi}_{n}}\frac{1}{K}\sum_{k=1}^{K}(LODL_{\bm{\phi}_{n}}(\bm{y}^{k}_{n})-DL(\bm{y}^{k}_{n},\bm{y}_{n}))^{2}$
(2)

This framework has the key advantage of reducing the design of good surrogate
tasks (a complex problem requiring in-depth knowledge of each optimization
problem) to supervised learning (for which many methods are available).
Indeed, future advances, e.g. in representation learning, can simply be
plugged into our framework.

The major remaining step is to specify the construction of the dataset for
supervised learning of $\bm{\phi^{*}}_{n}$. We propose to construct this
dataset by sampling a set of $K$ points
$[\bm{y}^{1}_{n},\ldots,\bm{y}^{K}_{n}]$ in the vicinity of $\bm{y}$ and
calculate $DL(\bm{y}^{k}_{n},\bm{y}_{n})$ for each. In this paper, we consider
three sampling strategies:

  1. 1.

All-Perturbed: Add zero-mean Gaussian noise to the true label $\bm{y}_{n}$:

$\qquad\bm{y}^{i}_{n}=\bm{y}_{n}+\bm{\epsilon}^{k}=\bm{y}_{n}+\alpha\cdot\mathcal{N}(0,I),$

where $\alpha$ is a normalization factor and $I$ is a $dim(\bm{y})\times
dim(\bm{y})$ identity matrix.

  2. 2.

1-Perturbed or 2-Perturbed: Estimating the behavior of
$DL(\bm{y}_{n}+\epsilon^{i},\bm{y}_{n})$ for small $\epsilon$ can
alternatively be interpreted as estimating
$(\frac{\delta}{\delta\bm{\hat{y}}_{n}})^{dim(\bm{y}_{n})}DL(\bm{\hat{y}}_{n},\bm{y}_{n})$
(i.e., the $dim(\bm{y}_{n})^{th}$ partial derivative of $DL$ w.r.t. its first
input $\bm{\hat{y}}_{n}$) at $(\bm{y}_{n},\bm{y}_{n})$ because all the
dimensions of $\bm{\hat{y}}_{n}$ are being varied simultaneously. While
computing $(\frac{\delta}{\delta\bm{\hat{y}}_{n}})^{dim(\bm{y}_{n})}$ is
computationally challenging, it can be estimated using the simpler 1st or 2nd
partial derivatives. This corresponds to perturbing only one or two dimensions
at a time.

###  4.4 Time Complexity of Learning LODLs

The amount of time taken by each of the methods using gradient descent is:

  * •

2-Stage = $\Theta(T\cdot N\cdot T_{M})$, where $T_{M}$ is the amount of time
taken to run one forward and backwards pass through the model ${M_{\theta}}$
for one optimization instance, $N$ is the number of optimization instances,
and $T$ is the number of time-steps ${M_{\theta}}$ is trained for.

  * •

DFL = $\Theta(T\cdot N\cdot(T_{M}+T_{O}+T^{\prime}_{O}))$, where $T_{O}$ is
the time taken to solve the forward pass of one optimization instance and
$T^{\prime}_{O}$ is the time taken to compute the backward pass.

  * •

LODL = $\Theta(K\cdot N\cdot T_{O}+N\cdot(T\cdot K\cdot T_{LODL})+T\cdot
N\cdot T_{M})$, where $K$ is the number of samples needed to train the LODL,
and $T_{LODL}$ is the amount of time taken to run one forward and backwards
pass through the LODL. The three terms correspond to (i) generating samples,
(ii) training $N$ LODLs, and (iii) training $M_{\theta}$ using the trained
LODLs.

In practice, we find that $(T^{\prime}_{O}>T_{O})>>(T_{M}>T_{LODL})$. As a
result, the difference in complexity of DFL and LODL is roughly $\Theta(T\cdot
N\cdot T_{O})$ vs. $\Theta(K\cdot N\cdot T_{O}+N\cdot T\cdot K\cdot
T_{LODL})$. Further, the calculation above assumes that LODLs are trained in
the same way as $M_{\theta}$. However, in practice, they can often be learned
much faster, sometimes even in closed form (e.g., WeightedMSE and
DirectedWeightedMSE), leading to an effective runtime of $\Theta(K\cdot N\cdot
T_{O}+N\cdot K\cdot T_{LODL})\approx\Theta(K\cdot N\cdot T_{O})$. Then, the
difference between DFL and LODL boils down to $T$ vs. $K$, i.e., the number of
time-steps needed to train $M_{\theta}$ vs. the number of samples needed to
train the LODL.

While our approach can be more computationally expensive, it typically isn’t
for two reasons:

  * •

Amortization: We need only sample candidate predictions once, to then train
any number of LODLs (e.g., WeightedMSE, DirectedQuadratic) without ever having
to call an optimization oracle. Once the LODLs have been learned, you can
train any number of predictive models $M_{\theta}$ based on said LODLs—in
contrast to DFL, which requires calling the oracle to train each model. DFL is
thus more expensive when training a large number of models (e.g., for
hyperparameter/architecture search, trading-off performance vs. inference time
vs. interpretability, etc.). In the future, we imagine that datasets could be
shipped with not only features and labels, but also LODLs associated with
downstream tasks!

  * •

Parallelizability: The sample generation process for LODL is completely
parallelizable, resulting in an $\Omega(T_{O})$ lower-bound wall-clock
complexity for our approach. In contrast, the calls to the optimization oracle
in DFL are interleaved with the training of $M_{\theta}$ and, as a result,
cannot be parallelized with respect to $T$, resulting in an $\Omega(T\cdot
T_{O})$ wall-clock complexity.

We demonstrate this empirically in Section 5.3.

##  5 Experiments

To validate the efficacy of our approach, we run experiments on three resource
allocation tasks from the literature. We use the term _decision quality_ $DQ$
(higher is better) instead of $DL$ because these are all maximization
problems.

Linear Model This domain involves learning a linear model when the underlying
mapping between features and predictions is cubic. Such problems are common in
the explainable AI literature Narayanan et al. (2021); Futoma et al. (2020);
Hughes et al. (2018) where predictive models must be interpretable.

  * •

_Predict:_ Given a feature $x_{n}\sim U[0,1]$, use a linear model to predict
the utility $\hat{y}$ of resource $n$, where the true utility is
$y_{n}=10x_{n}^{3}-6.5x_{n}$. Combining predictions yields
$\bm{\hat{y}}=[\hat{y}_{1},\ldots,\hat{y}_{N}]$.

  * •

_Optimize:_ Choose the $B=1$ out of $N=50$ resources with highest utility:
$\bm{z}^{*}(\bm{\hat{y}})=\operatorname*{arg\,topk}(\bm{\hat{y}})$

  * •

_Surrogate:_ Because the $\operatorname*{arg\,max}$ operation is piecewise
constant, DFL requires a surrogate—we use the soft Top-K proposed by Xie et
al. (2020). Although this surrogate is convex in the decision variables, it is
not convex in the predictions.

Web Advertising This is a submodular optimization task taken from Wilder et
al. (2019a). The aim is to determine on which websites to advertise given
features about different websites.

  * •

_Predict:_ Given features $\bm{x}_{m}$ associated with some website $m$,
predict the click-through rates (CTRs) for a fixed set of $N=10$ users on
$M=5$ websites $\bm{\hat{y}}_{m}=[\hat{y}_{m,1},\ldots,\hat{y}_{m,N}]$. To
obtain the features $\bm{x}_{m}$ for each website $m$, true CTRs $\bm{y}_{m}$
from the Yahoo! Webscope Dataset Yahoo! (2007) are scrambled by multiplying
with a random $N\times N$ matrix $A$, i.e., $\bm{x}_{m}=A\bm{y}_{m}$.

  * •

_Optimize:_ Given the matrix of CTRs, determine on which $B=2$ (budget)
websites to advertise such that the expected number of users that click on the
ad at least once is maximized, i.e.,
$\bm{z}^{*}(\bm{\hat{y}})=\operatorname*{arg\,max}_{\bm{z}}\sum_{j=0}^{N}(1-\prod_{i=0}^{M}(1-z_{i}\cdot\hat{y}_{ij}))$,
where all the $z_{i}\in\\{0,1\\}$.

  * •

_Surrogate:_ Instead of requiring that $\bm{z}_{i}\in\\{0,1\\}$, the multi-
linear relaxation from Wilder et al. (2019a) allows fractional values. The
$DL$ induced by the relaxation is non-convex.

Portfolio Optimization This is a Quadratic Programming domain Donti et al.
(2017); Wang et al. (2020) in which the aim is to choose a distribution over
$N$ stocks that maximizes the expected profit minus a quadratic risk penalty.
We choose this domain as a stress test—it is highly favorable for DFL because
the optimization problem naturally provides informative gradients and thus
requires no surrogate.

  * •

_Predict:_ Given historical data $\bm{x}_{n}$ about stock $n$, predict the
future stock price $y_{n}$. We use historical data from 2004 to 2017 for a set
of $N=50$ stocks from the QuandlWIKI dataset Quandl (2022).

  * •

_Optimize:_ Given a historical correlation matrix $Q$ between pairs of stocks,
choose a distribution $\bm{z}$ over stocks that maximizes
$\bm{z}^{T}\bm{y}-\lambda\cdot\bm{\hat{y}}^{T}Q\bm{\hat{y}}$, where
$\lambda=0.1$ is the risk aversion constant.

More experimental setup details are provided in Appendix A.

###  5.1 Results

Table 1: The decision quality achieved by each approach—higher is better.
DirectedQuadratic consistently performs well.

Loss Function | Normalized $\bm{DQ}$ On Test Data
---|---
Linear Model | Web Advertising | Portfolio Optimization
Random | 0 | 0 | 0
Optimal | 1 | 1 | 1
2-Stage (MSE) | -0.95 ± 0.00 | 0.48 ± 0.15 | 0.32 ± 0.02
DFL | 0.83 ± 0.38 | 0.85 ± 0.10 | 0.35 ± 0.02
NN | 0.96 ± 0.00 | 0.81 ± 0.14 | -0.11 ± 0.08
WeightedMSE | -0.93 ± 0.06 | 0.58 ± 0.15 | 0.31 ± 0.02
DirectedWeightedMSE | 0.96 ± 0.00 | 0.53 ± 0.14 | 0.32 ± 0.02
Quadratic | -0.75 ± 0.38 | 0.93 ± 0.04 | 0.27 ± 0.02
DirectedQuadratic | 0.96 ± 0.00 | 0.91 ± 0.04 | 0.33 ± 0.01

We train either a linear model (for the Linear Model domain) or a 2-layer
fully-connected neural network with 500 hidden units (for the other domains)
using LODLs and compare it to:

  1. 1.

Random: The predictions are sampled uniformly from $[0,1]^{dim(\bm{y})}$.

  2. 2.

Optimal: The predictions are equal to the true labels $\bm{y}$.

  3. 3.

2-Stage: The model is trained on the standard MSE loss
($\frac{1}{N}\sum_{n=1}^{N}||\bm{\hat{y}}_{n}-\bm{y}_{n}||^{2}$).

  4. 4.

DFL: Decision-focused learning using the specified surrogate.

  5. 5.

NN: To determine how important convexity is for LODL we define
$LODL_{\phi}=NN_{\phi}(\bm{\hat{y}})$ in which $NN_{\phi}$ is a 4-layer fully-
connected Neural Network (NN) with 100 hidden units.

Table 1 shows the main results. We find that, in all domains, training
predictive models with LODL outperforms training them with a task-independent
2-stage loss. Surprisingly, it also outperforms DFL, which has the benefit of
handcrafted surrogates, in two of the three. This is strong evidence in favor
of our hypothesis that we can automate away the need for handcrafting
surrogates. We first analyze the results in terms of the domains:

  1. 1.

Linear Model: In this domain, the directionality of predictions is very
important. As we describe in Section 2.1, predicting values higher than the
true utilities for the $B$ resources with highest utility, does not change the
decision. However, if their predicted utility is lower than that of the
$B-1$th best resource, the decision quality is affected. As a result, we see
that the “Directed” methods perform significantly better than their
competition.

  2. 2.

Web Advertising: In this domain, Wilder et al. (2019a) suggest that the
decision quality is linked to being able to predict the quantity
$\sum_{j}\hat{y}_{ij}$ (the sum of CTRs across all users $j$ for a given
website $i$). However, because the input features for every $\hat{y}_{ij}$ are
the same $\bm{x}_{i}$, the errors can be correlated and so the sum can be
biased. As a result, the ability to penalize the correlations between two
predictions $\hat{y}_{ij}$ and $\hat{y}_{jk}$ is important to being able to
perform well on this task—which results in the Quadratic methods outperforming
the others.

  3. 3.

Portfolio Optimization: Given that this stress-test domain was built to be
favorable to $DFL$, it outperforms all other approaches with statistical
significance. While the directed LODL methods do not outperform DFL, they
nonetheless significantly outperform 2-stage at $p<0.05$.

We now analyze the results in terms of the methods:

  1. 1.

Our DirectedQuadratic $\bm{LODL}$ consistently does well: In addition to
consistently high expected values (always better than 2-stage), the associated
variance is lower as well.

  2. 2.

Lack of convexity can cause inconsistent results: While NN does well in the
first two domains, it fails catastrophically in the Portfolio Optimization
domain.

  3. 3.

DFL has a large variance in performance: In both the ”Web Advertising” and
”Linear Model” domain, DFL has higher variation than the best performing
LODLs. We posit that this is also because of the lack of convexity of the
surrogates that DFL uses in these two domains.

###  5.2 Ablations

We study the impact of the sampling strategy and number of samples on the
performance of the LODL methods in the Web Advertising domain in Table 3. We
find:

  1. 1.

Sampling strategy (Table 4(d)): The best sampling strategy is loss family-
specific. Specifically, NN and DirectedWeightedMSE perform best with the
“2-Perturbed” strategy, while the remaining LODLs perform best with the “All-
Perturbed” strategy.

  2. 2.

Number of samples (Table 4(e)): All models perform better with more samples.
In addition, the variance reduces as the number of samples increases
(especially for Quadratic), suggesting that better approximations of $DL$ lead
to more consistent outcomes.

Figure 3: Figure (a) shows that the time taken to train a single model
$\bm{M_{\theta}}$ reduces with the number of cores used. Figure (b) shows that
this time is further reduced when the cost of learning LODLs is amortized
across different predictive models $\bm{M_{\theta}}$.

(a) Parallelizability

(b) Amortization

###  5.3 Computational Cost of Learning with LODLs

We measure the time taken to learn predictive models $\bm{M_{\theta}}$ with
LODLs in the Web Advertisement domain. We train each LODL for 100 gradient
descent steps using 5000 samples and train the predictive model for 500 steps
(the same as the setup as Table 1). We find:

  1. 1.

Learning LODLs is parallelizable: Figure 3(a) shows that the cost of training
a predictive model using LODLs decreases near-linearly in the number of cores
used. With more than 20 cores, training with LODLs can be cheaper than
training with DFL for this domain.

  2. 2.

If LODLs can be reused, their (already low) overhead quickly diminishes: From
Figure 3(b) we see that even for a modest amount of amortization (over 5-10
predictive models), the training time using LODLs converges to that of two-
stage (shown using parallelization with 40 cores).

###  5.4 Correlation between the ‘quality’ of LODL and decision quality

Recall that LODL losses are fit using a Gaussian sampling strategy centered
around the true labels. It is natural to ask how well this proxy loss
correlates with the decision quality on test data. We do this by measuring the
mean absolute error (MAE) of LODL relative to the ground truth decision loss
for points in the _Gaussian neighborhood_ around the true labels.

This Gaussian neighborhood is only an approximation of the true distribution
of interest—the distribution of predictions generated by the predictive model
that is trained using the LODL loss. We can measure the MAE on this
distribution, which we call the _empirical neighborhood_.

Table 2: A table showing the relationship between the quality of the learned
loss for different classes of LODLs, and the performance of a model trained on
said loss. The Empirical Neighborhood MAE is linearly correlated with $DQ$
while the Gaussian Neighborhood MAE is not.

Approach | MAE in Gaussian | MAE in Empirical | Normalized DQ
---|---|---|---
Neighborhood | Neighborhood | on Test Data
(x $10^{-2}$) | (x $10^{-2}$) |
NN | $0.94\pm 0.06$ | $2.22\pm 1.73$ | $0.80\pm 0.16$
WeightedMSE | $1.04\pm 0.00$ | $4.48\pm 1.71$ | $0.58\pm 0.15$
DirectedWeightedMSE | $\mathbf{0.92\pm 0.00}$ | $5.58\pm 1.64$ | $0.50\pm 0.13$
Quadratic | $0.96\pm 0.00$ | $\mathbf{0.86\pm 0.52}$ | $\mathbf{0.92\pm 0.05}$
DirectedQuadratic | $1.06\pm 0.00$ | $1.91\pm 0.79$ | $0.85\pm 0.08$

Table 2 shows the results for the Budget Allocation domain, while the
remaining graphs are in Appendix B.3. All methods are able to approximate the
$DL$ comparably well in the Gaussian neighborhood, but this does not correlate
well with decision quality. In contrast, the error on the empirical
neighborhood is tightly linearly correlated with decision quality.
Furthermore, if we extrapolate the line of best fit to where the MAE is 0,
i.e., when there is no discrepancy LODL and $DL$, we find that the trend
predicts the normalized $DQ$ would be $1$.

##  6 Discussion and Conclusion

Our work proposes a conceptual shift from hand-crafting surrogate losses for
decision problems to automatically learning them, and demonstrates
experimentally that the LODL paradigm enables us to learn high-quality models
without such manual effort. Nevertheless, our current instantiation of this
framework has limitations which are areas for future work.

We considered LODLs that additively decompose across the dimensions of
$\bm{y}$, allowing us to isolate the effects of fit to $DL$ from the
generalization performance across the dimensions of $\bm{y}$. Future work may
learn models that generalize across dimensions, allowing for even greater
scalability.

We demonstrate that the fit of a LODL to the empirical neighborhood around the
ground truth label is highly correlated with the eventual decision quality.
While the Gaussian neighborhood method does yield models that perform well, it
does not correlate well with the decision quality across LODL
parameterizations. It would be valuable to study the empirical neighborhood to
better understand the reasons for this discrepancy and potentially develop
LODLs with even stronger performance.

In summary, LODL provides an alternate framework for machine learning which
informs decision making, opening up new avenues towards models which are both
high-performing and easily trained.

## Acknowledgments and Disclosure of Funding

Research was sponsored by the ARO and was accomplished under Grant Number:
W911NF-18-1-0208. Wilder was supported by the Schmidt Science Fellows program.

## References

  * Agrawal et al. [2019] Akshay Agrawal, Brandon Amos, Shane Barratt, Stephen Boyd, Steven Diamond, and J Zico Kolter.  Differentiable convex optimization layers.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Amos et al. [2018] Brandon Amos, Ivan Jimenez, Jacob Sacks, Byron Boots, and J. Zico Kolter.  Differentiable mpc for end-to-end planning and control.  In _Advances in Neural Information Processing Systems_ , volume 31, 2018.
  * Amos et al. [2019] Brandon Amos, Vladlen Koltun, and J Zico Kolter.  The limited multi-label projection layer.  _arXiv preprint arXiv:1906.08707_ , 2019.
  * Berthet et al. [2020] Quentin Berthet, Mathieu Blondel, Olivier Teboul, Marco Cuturi, Jean-Philippe Vert, and Francis Bach.  Learning with differentiable pertubed optimizers.  _Advances in Neural Information Processing Systems_ , 33:9508–9519, 2020.
  * Cameron et al. [2022] Chris Cameron, Jason Hartford, Taylor Lundy, and Kevin Leyton-Brown.  The perils of learning before optimizing.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 36, 2022.
  * Demirović et al. [2019] Emir Demirović, Peter J Stuckey, James Bailey, Jeffrey Chan, Chris Leckie, Kotagiri Ramamohanarao, and Tias Guns.  An investigation into prediction+ optimisation for the knapsack problem.  In _International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research_ , pages 241–257. Springer, 2019.
  * Donti et al. [2017] Priya Donti, Brandon Amos, and J Zico Kolter.  Task-based end-to-end model learning in stochastic optimization.  _Advances in Neural Information Processing Systems_ , 30, 2017.
  * Elmachtoub and Grigas [2021] Adam N Elmachtoub and Paul Grigas.  Smart “predict, then optimize”.  _Management Science_ , 2021.
  * Ferber et al. [2020] Aaron Ferber, Bryan Wilder, Bistra Dilkina, and Milind Tambe.  MIPaaL: Mixed integer program as a layer.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pages 1504–1511, 2020.
  * Futoma et al. [2020] Joseph Futoma, Michael Hughes, and Finale Doshi-Velez.  POPCORN: Partially observed prediction constrained reinforcement learning.  In _International Conference on Artificial Intelligence and Statistics_ , pages 3578–3588. PMLR, 2020.
  * Guler et al. [2022] Ali Ugur Guler, Emir Demirovic, Jeffrey Chan, James Bailey, Christopher Leckie, and Peter J Stuckey.  Divide and learn: A divide and conquer approach for predict+ optimize.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 36, 2022.
  * Hughes et al. [2018] Michael Hughes, Gabriel Hope, Leah Weiner, Thomas McCoy, Roy Perlis, Erik Sudderth, and Finale Doshi-Velez.  Semi-supervised prediction-constrained topic models.  In _Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics_ , pages 1067–1076, 2018.
  * Isinkaye et al. [2015] Folasade Olubusola Isinkaye, Yetunde O Folajimi, and Bolande Adefowoke Ojokoh.  Recommendation systems: Principles, methods and evaluation.  _Egyptian Informatics Journal_ , 16(3):261–273, 2015.
  * Kar et al. [2017] Debarun Kar, Benjamin Ford, Shahrzad Gholami, Fei Fang, Andrew Plumptre, Milind Tambe, Margaret Driciru, Fred Wanyama, Aggrey Rwetsiba, Mustapha Nsubaga, and Joshua Mabonga.  Cloudy with a chance of poaching: Adversary behavior modeling and forecasting with real-world poaching data.  In _Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems_ , page 159–167, 2017.
  * Mandi and Guns [2020] Jayanta Mandi and Tias Guns.  Interior point solving for LP-based prediction+optimisation.  _Advances in Neural Information Processing Systems_ , 33:7272–7282, 2020.
  * Mandi et al. [2020] Jayanta Mandi, Peter J Stuckey, Tias Guns, et al.  Smart predict-and-optimize for hard combinatorial optimization problems.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pages 1603–1610, 2020.
  * Markowitz and Todd [2000] Harry M Markowitz and G Peter Todd.  _Mean-variance analysis in portfolio choice and capital markets_.  John Wiley & Sons, 2000.
  * Mensch and Blondel [2018] Arthur Mensch and Mathieu Blondel.  Differentiable dynamic programming for structured prediction and attention.  In _International Conference on Machine Learning_ , pages 3462–3471. PMLR, 2018.
  * Michaud [1989] Richard O Michaud.  The Markowitz optimization enigma: Is ‘optimized’ optimal?  _Financial Analysts Journal_ , 45(1):31–42, 1989\.
  * Mulamba et al. [2021] Maxime Mulamba, Jayanta Mandi, Michelangelo Diligenti, Michele Lombardi, Victor Bucarey, and Tias Guns.  Contrastive losses and solution caching for predict-and-optimize.  In _Proceedings of the International Joint Conferences on Artificial Intelligence_ , 2021.
  * Narayanan et al. [2021] Sanjana Narayanan, Abhishek Sharma, Catherine Zeng, and Finale Doshi-Velez.  Prediction-focused mixture models.  _arXiv preprint arXiv:2110.13221_ , 2021.
  * Quandl [2022] Quandl.  WIKI various end-of-day data, 2022.  URL https://www.quandl.com/data/WIKI.
  * Tschiatschek et al. [2018] Sebastian Tschiatschek, Aytunc Sahin, and Andreas Krause.  Differentiable submodular maximization.  In _Proceedings of the 27th International Joint Conference on Artificial Intelligence_ , pages 2731–2738, 2018.
  * Wang et al. [2020] Kai Wang, Bryan Wilder, Andrew Perrault, and Milind Tambe.  Automatically learning compact quality-aware surrogates for optimization problems.  _Advances in Neural Information Processing Systems_ , 33:9586–9596, 2020.
  * Wilder et al. [2019a] Bryan Wilder, Bistra Dilkina, and Milind Tambe.  Melding the data-decisions pipeline: Decision-focused learning for combinatorial optimization.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, pages 1658–1665, 2019a.
  * Wilder et al. [2019b] Bryan Wilder, Eric Ewing, Bistra Dilkina, and Milind Tambe.  End to end learning and optimization on graphs.  _Advances in Neural Information Processing Systems_ , 32:4672–4683, 2019b.
  * Xie et al. [2020] Yujia Xie, Hanjun Dai, Minshuo Chen, Bo Dai, Tuo Zhao, Hongyuan Zha, Wei Wei, and Tomas Pfister.  Differentiable top-k with optimal transport.  _Advances in Neural Information Processing Systems_ , 33:20520–20531, 2020.
  * Yahoo! [2007] Yahoo!  Webscope dataset, 2007.  URL https://webscope.sandbox.yahoo.com/.  ydata-ysm-advertiser-bids-v1.0.

## Checklist

The checklist follows the references. Please read the checklist guidelines
carefully for information on how to answer these questions. For each question,
change the default [TODO] to [Yes] , [No] , or [N/A] . You are strongly
encouraged to include a justification to your answer, either by referencing
the appropriate section of your paper or providing a brief inline description.
For example:

  * •

Did you include the license to the code and datasets? [Yes] See Section
LABEL:gen_inst.

  * •

Did you include the license to the code and datasets? [No] The code and the
data are proprietary.

  * •

Did you include the license to the code and datasets? [N/A]

Please do not modify the questions and only use the provided macros for your
answers. Note that the Checklist section does not count towards the page
limit. In your paper, please delete this instructions block and only keep the
Checklist section heading above along with the questions/answers below.

  1. 1.

For all authors…

    1. (a)

Do the main claims made in the abstract and introduction accurately reflect
the paper’s contributions and scope? [Yes]

    2. (b)

Did you describe the limitations of your work? [Yes] See Section 6

    3. (c)

Did you discuss any potential negative societal impacts of your work? [N/A]

    4. (d)

Have you read the ethics review guidelines and ensured that your paper
conforms to them? [Yes]

  2. 2.

If you are including theoretical results…

    1. (a)

Did you state the full set of assumptions of all theoretical results? [N/A]

    2. (b)

Did you include complete proofs of all theoretical results? [N/A]

  3. 3.

If you ran experiments…

    1. (a)

Did you include the code, data, and instructions needed to reproduce the main
experimental results (either in the supplemental material or as a URL)? [Yes]
As supplemental material.

    2. (b)

Did you specify all the training details (e.g., data splits, hyperparameters,
how they were chosen)? [Yes]  In the appendix

    3. (c)

Did you report error bars (e.g., with respect to the random seed after running
experiments multiple times)? [Yes]  In all tables.

    4. (d)

Did you include the total amount of compute and the type of resources used
(e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]  In the
appendix

  4. 4.

If you are using existing assets (e.g., code, data, models) or
curating/releasing new assets…

    1. (a)

If your work uses existing assets, did you cite the creators? [Yes]

    2. (b)

Did you mention the license of the assets? [No]  It isn’t clear exactly what
the license is, but all the datasets are publicly available.

    3. (c)

Did you include any new assets either in the supplemental material or as a
URL? [No]

    4. (d)

Did you discuss whether and how consent was obtained from people whose data
you’re using/curating? [N/A]

    5. (e)

Did you discuss whether the data you are using/curating contains personally
identifiable information or offensive content? [No]

  5. 5.

If you used crowdsourcing or conducted research with human subjects…

    1. (a)

Did you include the full text of instructions given to participants and
screenshots, if applicable? [N/A]

    2. (b)

Did you describe any potential participant risks, with links to Institutional
Review Board (IRB) approvals, if applicable? [N/A]

    3. (c)

Did you include the estimated hourly wage paid to participants and the total
amount spent on participant compensation? [N/A]

##  Appendix A Extended Experimental Setup

We provide an extended version of the Experimental Setup from Section 5 below.

#### Linear Model

This domain involves learning a linear model when the underlying mapping
between features and predictions is cubic. Concretely, the aim is to choose
the top $B=1$ out of $N=50$ resources using a linear model. The fact that the
features can be seen as 1-dimensional allows us to visualize the learned
models (as seen in Figure 4).

Predict: Given a feature $x_{n}\sim U[0,1]$, use a linear model to predict the
utility $\hat{y}$ of choosing resource $n$, where the true utility is given by
$y_{n}=10x_{n}^{3}-6.5x_{n}$. Combining predictions yields
$\bm{\hat{y}}=[\hat{y}_{1},\ldots,\hat{y}_{N}]$. There are 200
$(\bm{x},\bm{y})$ pairs in each of the training and validation sets, and 400
$(\bm{x},\bm{y})$ pairs in the test set.

Optimize: Given these predictions, choose the $B=1$ (budget) resources with
the highest utility:

$\displaystyle\bm{z}^{*}(\bm{\hat{y}})=\operatorname*{arg\,topk}\hskip
2.84526pt(\bm{\hat{y}}).$

Surrogate: Because the $\operatorname*{arg\,max}$ operation is piecewise
constant, DFL requires a surrogate—we use the soft Top-K proposed by Xie et
al. [2020] that reframes the Top-K problem with entropy regularization as an
optimal transport problem. Note that this surrogate is not convex in the
predictions.

Intuition: With limited model capacity, you cannot model all the data
accurately. Better performance can be achieved by modeling the aspects of the
data that are most relevant to decision-making—in this case, the behavior of
the top $2\%$ of resources. Such problems are common in the explainable AI
literature Narayanan et al. [2021], Futoma et al. [2020], Hughes et al. [2018]
where predictive models must be interpretable and so model capacity is
limited.

#### Web Advertising

This is a submodular optimization task taken from Wilder et al. [2019a]. The
aim is to determine on which $B=2$ websites to advertise given features about
$M=5$ different websites. The predictive model being used is a 2-layer
feedforward neural network with an intermediate dimension of 500 and ReLU
activations.

Predict: Given features $\bm{x}_{m}$ associated with some website $m$, predict
the clickthrough rates (CTRs) for a fixed set of $N=10$ users
$\bm{\hat{y}}_{m}=[\hat{y}_{m,1},\ldots,\hat{y}_{m,N}]$. These CTR predictions
for each of the $M=5$ websites are stitched together to create an $M\times N$
matrix of CTRs $\bm{\hat{y}}$. The task is based on the Yahoo! Webscope
Dataset Yahoo! [2007] which contains multiple CTR matrices. We randomly sample
$M$ rows and $N$ columns from each matrix and then split the dataset such that
the training, validation and test sets have 80, 20 and 500 matrices each. To
generate the features $\bm{x}_{m}$ for some website $m$, the true CTRs
$\bm{y}_{m}$ for the website are scrambled by multiplying with a random
$N\times N$ matrix $A$, i.e., $\bm{x}_{m}=A\bm{y}_{m}$.

Optimize: Given this matrix of CTRs, determine on which $B=2$ (budget)
websites to advertise such that the expected number of users that click on the
advertisement at least once is maximized:

$\displaystyle\bm{z}^{*}(\bm{\hat{y}})=\operatorname*{arg\,max}_{\bm{z}}\hskip
5.69054pt$
$\displaystyle\frac{1}{N}\sum_{j=0}^{N}(1-\prod_{i=0}^{M}(1-z_{i}\cdot\hat{y}_{ij}))$
$\displaystyle s.t.\hskip 5.69054pt$ $\displaystyle\sum_{i=0}^{M}z_{i}\leq
B\quad\text{ and }\quad z_{i}\in\\{0,1\\}\textrm{, for
}i\in\\{1,\,\ldots,\,M\\}$

Surrogate: Instead of requiring that $z_{i}\in\\{0,1\\}$, the multi-linear
relaxation suggested in Wilder et al. [2019a] allows fractional values.
However, while this relaxation may allow for non-zero gradients, the induced
$DL$ is non-convex because the term
$\prod_{i=0}^{M}(1-z_{i}\cdot\hat{y}_{ij})$ in the objective is non-convex in
the predictions.

Intuition: In practice, the CTR values are so small that you can approximate
$\prod_{i=0}^{M}(1-z_{i}\cdot\hat{y}_{ij})\approx
1-z_{i}\cdot\sum_{i=0}^{M}\hat{y}_{ij}$ because the product terms are almost
zero, i.e., $\hat{y}_{ij}*\hat{y}_{i^{\prime}j}\approx 0$. As a result, the
goal is to accurately predict $\sum_{i=0}^{M}y_{ij}$, the sum of CTRs across
all the users for a given website. However, because the input features for
every $y_{ij}$ are the same $\bm{x}_{i}$, the errors are correlated. As a
result, when you add up the values the errors do not cancel out, leading to
biased estimates.

#### Portfolio Optimization

This is a Quadratic Programming domain popular in the literature Donti et al.
[2017], Wang et al. [2020] because it requires no relaxation in order to run
DFL. The aim is to choose a distribution over $N=50$ stocks in a Markowitz
portfolio optimization setup Markowitz and Todd [2000], Michaud [1989] that
maximizes the expected profit minus a quadratic risk penalty. The predictive
model being used is a 2-layer feedforward neural network with a
500-dimensional intermediate layer using ReLU activations, followed by an
output layer with a ‘tanh’ activation.

Predict: Given historical data $\bm{x}_{n}$ about some stock $n$ at time-step
$t$, predict the stock price $y_{n}$ at time-step $t+1$. Combining the
predictions $\hat{y}_{n}$ across a consistent set of $N=50$ stocks together
yields $\bm{\hat{y}}=[\hat{y}_{1},\ldots,\hat{y}_{N}]$. We use historical
price and volume data of S&P500 stocks from 2004 to 2017 downloaded from the
QuandlWIKI dataset Quandl [2022] to generate $\bm{x}$ and $\bm{y}$. There are
200 $(\bm{x},\bm{y})$ pairs in each of the training and validation sets, and
400 $(\bm{x},\bm{y})$ pairs in the test set.

Optimize: Given a historical correlation matrix $Q$ between pairs of stocks,
choose a distribution $\bm{z}$ over stocks such that the future return
$\bm{z}^{T}\bm{y}$ is maximized subject to a quadratic risk penalty
$\bm{\hat{y}}^{T}Q\bm{\hat{y}}$:

$\displaystyle\bm{z}^{*}(\bm{\hat{y}})=\operatorname*{arg\,max}_{\bm{z}}\hskip
5.69054pt$ $\displaystyle\bm{z}^{T}\bm{y}-\lambda\cdot\bm{z}^{T}Q\bm{z}$
$\displaystyle s.t.\hskip 5.69054pt$ $\displaystyle\sum_{i=0}^{N}z_{i}\leq
1\quad\text{ and }\quad 0\leq z_{i}\leq 1\textrm{, for
}i\in\\{1,\,\ldots,\,N\\}$

where $\lambda=0.1$ is the risk aversion constant. The intuition behind the
penalty is that if two stocks have strongly correlated historical prices, the
penalty will be higher, forcing you to hedge your bets.

Intuition Along the lines of Cameron et al. [2022], DFL is able to take into
account the correlations in predictions between the $N$ different stocks,
while 2-stage is not.

### Computation Infrastructure

We ran 100 samples for each $(\text{method},\text{domain})$ pair—we used 10
different random seeds to generate the domain, and for each random seed we
trained the $LODL$s and the predictive model $\bm{M_{\theta}}$ for 10 random
intializations. We ran all the experiments in parallel on an internal cluster.
Each individual experiment was performed on an Intel Xeon CPU with 64 cores
and 128 GB memory.

##  Appendix B Detailed Experimental Results

###  B.1 Visualizing the Linear Model Domain

Figure 4: Graphs showing the true (blue) and 100 learned (orange) mappings
between the features and predictions in the Linear Model domain. 2-stage does
badly, DFL typically learns the correct slope but can sometimes randomly fail,
and DirectedQuadratic does well.

(a) 2-Stage

(b) DFL

(c) DirectedQuadratic

###  B.2 Ablations

Table 3: Ablations across (a) different sampling methods and (b) different
number of samples in the Web Advertising domain. The best sampling strategy is
loss family-specific, while increasing the number of samples uniformly
improves the performance.

(d) Across Sampling Strategies

Approach | Normalized Test $\bm{DQ}$
---|---
1-Perturbed | 2-Perturbed | All-Perturbed
NN | $0.86\pm 0.12$ | $\mathbf{0.89\pm 0.09}$ | $0.80\pm 0.16$
WeightedMSE | $0.50\pm 0.14$ | $0.53\pm 0.14$ | $\mathbf{0.58\pm 0.15}$
DirectedWeightedMSE | $0.47\pm 0.15$ | $\mathbf{0.53\pm 0.16}$ | $0.50\pm 0.13$
Quadratic | $0.77\pm 0.25$ | $0.88\pm 0.10$ | $\mathbf{0.92\pm 0.05}$
DirectedQuadratic | $0.77\pm 0.19$ | $0.84\pm 0.11$ | $\mathbf{0.85\pm 0.08}$

(e) Across Number of Samples

Approach | Normalized Test $\bm{DQ}$
---|---
50 samples | 500 samples | 5000 samples
NN | $0.81\pm 0.13$ | $0.80\pm 0.16$ | $\mathbf{0.81\pm 0.14}$
WeightedMSE | $0.50\pm 0.14$ | $0.50\pm 0.14$ | $\mathbf{0.53\pm 0.14}$
DirectedWeightedMSE | $0.48\pm 0.15$ | $0.53\pm 0.16$ | $\mathbf{0.53\pm 0.150}$
Quadratic | $0.68\pm 0.17$ | $0.92\pm 0.05$ | $\mathbf{0.93\pm 0.04}$
DirectedQuadratic | $0.59\pm 0.13$ | $0.85\pm 0.08$ | $\mathbf{0.91\pm 0.04}$

###  B.3 Extending the Results from Section 5.4 to Different Domains

Figure 5 extends the observation that the LODL’s goodness of fit in the
Empirical Neighborhood linearly correlates to improved ‘Decision Quality’ to
the different domains considered in this paper.

Figure 5: A figure showing the relationship between the quality of the learned
LODL and the performance of a model trained on said loss across different
domains.