# Maximal Operators on BMO and Slices

Shahaboddin Shaabani  Department of Mathematics and Statistics
Concordia University<EMAIL_ADDRESS>
###### Abstract.

We prove that the Hardy-Littlewood maximal operator is discontinuous on
${BMO}(\mathbb{R}^{n})$ and maps ${VMO}(\mathbb{R}^{n})$ to itself. A
counterexample to boundedness of the strong and directional maximal operators
on ${BMO}(\mathbb{R}^{n})$ is given, and properties of slices of
${BMO}(\mathbb{R}^{n})$ functions are discussed.

##  1\. Introduction

Let $A\subset\mathbb{R}^{n}$ be a measurable set with positive finite measure
and $f\in{L}_{loc}^{1}(\mathbb{R}^{n})$. By the mean oscillation of $f$ on $A$
we mean the quantity

$O(f,A):=\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{A}{|f-f_{A}|},$

where
$\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{A}{f}$
and $f_{A}$ mean the average of $f$ over $A$ i.e. $\frac{1}{|A|}\int_{A}f$.
Then it is said that $f$ is of bounded mean oscillation if $O(f,Q)$ is
uniformly bounded on all cubes $Q$ (by a cube we mean one with sides parallel
to the axes). The space of such functions is denoted by
${BMO}(\mathbb{R}^{n})$, and modulo constants the following quantity defines a
norm on this space.

$\|f\|_{{BMO}(\mathbb{R}^{n})}=\sup_{Q}O(f,Q).$

(Sometimes we use $\|f\|_{BMO(Q_{0})}$ which means that we take the above
supremum over all cubes contained in $Q_{0}$.) ${BMO}(\mathbb{R}^{n})$ is a
Banach space, and since its introduction has played an important role in
harmonic analysis. It appears in many problems and somehow serves as a
substitute for ${L}^{\infty}(\mathbb{R}^{n})$. For instance, it’s the dual of
the Hardy space ${H}^{1}(\mathbb{R}^{n})$, and singular integral operators map
${L}^{\infty}(\mathbb{R}^{n})$ to ${BMO}(\mathbb{R}^{n})$ and not to itself
[12],[6].

In [2] the authors proved that the uncentered Hardy-Littlewood maximal
operator, defined by

$Mf(x)=\sup_{x\in
Q}\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{Q}{|f|},\quad
f\in{L}_{loc}^{1}(\mathbb{R}^{n}),$

is bounded on ${BMO}(\mathbb{R}^{n})$. (The above supremum is taken over all
cubes containing $x$.) Another proof of this was given in [1], and a third one
in [10], where the author proved that $M$ preserves Poincare inequalities. In
this paper we want to give an answer to the following related questions:

Q1. Is the Hardy-Littlewood maximal operator $M$ continuous on
${BMO}(\mathbb{R}^{n})$?

The operator $M$ is nonlinear and for such operators continuity doesn’t follow
from boundedness. However, it is sublinear and this makes it continuous on
${L}^{p}(\mathbb{R}^{n})$ for $1<p\leq\infty$. In [9], a similar question has
been studied for Sobolev spaces, where the author proved that $M$ is
continuous on $W^{1,p}(\mathbb{R}^{n})$ for $1<p<\infty$. However, in Section
2 we give a negative answer to question Q1.

${BMO}(\mathbb{R}^{n})$ has an important subspace, namely
${VMO}(\mathbb{R}^{n})$ or functions of vanishing mean oscillation.
${VMO}(\mathbb{R}^{n})$ is the closure of the uniformly continuous functions
in ${BMO}(\mathbb{R}^{n})$ [11],[butaev]. Another characterization of
${VMO}(\mathbb{R}^{n})$ is given in terms of the moduli of mean oscillation
which is defined by

(1) $\omega(f,\delta):=\sup_{l(Q)\leq\delta}O(f,Q),$

and $f\in{VMO}(\mathbb{R}^{n})$ exactly when $\lim\limits_{\delta\to
0}\omega(f,\delta)=0$. (In the above by $l(Q)$ we mean the side length of
$Q$). Regarding this subspace we ask:

Q2. Dose $M$ map ${VMO}(\mathbb{R}^{n})$ to itself?

In Section 3 we provide a positive answer to this question.

In the last section, we consider the action of other maximal operators on
${BMO}(\mathbb{R}^{n})$. More specifically, the directional maximal operator
$M_{e_{1}}$, and the strong maximal operator $M_{s}$ which are defined as the
following:

$M_{e_{1}}f(x_{1},x^{\prime}):=\sup_{x_{1}\in
I}\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{I}{|f_{x^{\prime}}|},\quad\quad
M_{s}f(x):=\sup_{x\in
R}\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{R}{|f|}.$

In the above, $f_{x^{\prime}}(t)=f(t,x^{\prime})$ and the left supremum is
taken over all intervals containing $x_{1}$. The right one is taken over all
rectangles (here and afterwards by a rectangle we mean one with sides parallel
to the axes) containing $x$. These are the most important maximal operators in
multi-parameter harmonic analysis and are bounded and continuous on
${L}^{p}(\mathbb{R}^{n})$ for $1<p<\infty$[4]. Regarding this we ask:

Q3. Do $M_{e_{1}}$ and $M_{s}$ map ${BMO}(\mathbb{R}^{n})$ to itself
boundedly?

We answer this question negatively in Section 4, where some properties of
slices of functions in ${BMO}(\mathbb{R}^{n})$ are also investigated.

##  2\. Discontinuity of $M$ on ${BMO}(\mathbb{R}^{n})$

Our theorem in this section is the following:

######  Theorem 2.1.

Let $f$ be a nonnegative function supported in $[0,1]$,
$\|f\|_{{L}^{\infty}}\leq 1$ and $\|f\|_{{L}^{1}}>\log 2$. Then the Hardy-
Littlewood maximal operator $M:{BMO}(\mathbb{R})\rightarrow{BMO}(\mathbb{R})$
is discontinuous at $f$.

To prove this we need a couple of simple lemmas which we give below.

######  Lemma 2.2.

Let $T>0$ and $h\in BMO[0,\frac{T}{2}]$. Then the even periodic extension of
$h$, which is defined by

$H(-x)=H(x),\quad\quad H(x+T)=H(x),\quad x\in\mathbb{R},$

is in ${BMO}(\mathbb{R})$ and $\|H\|_{{{BMO}(\mathbb{R})}}\leq
10\|h\|_{BMO[0,\frac{T}{2}]}$.

###### Proof.

For an arbitrary interval $I$, there are two possibilities:

  * •

$|I|\leq\frac{T}{2}$.

In this case by a translation with an integer multiple of $T$ and using
periodicity of $H$, we may assume either $I\subset[-\frac{T}{2},\frac{T}{2}]$
or $I\subset[0,T]$. Suppose $I\subset[-\frac{T}{2},\frac{T}{2}]$ and note that
if $0\notin I$, we have either $I\subset[0,\frac{T}{2}]$ or
$I\subset[-\frac{T}{2},0]$ and from the symmetry
$O(H,I)\leq\|h\|_{BMO[0,\frac{T}{2}]}$. If $0\in I$, then take the interval
$J$ centered at zero with the right half $J^{+}$, which contains $I$ and
$|J|\leq 2|I|.$ Again from symmetry we get

$O(H,I)\leq 2\frac{|J|}{|I|}O(H,J)\leq 4O(H,J^{+})\leq
4\|h\|_{BMO[0,\frac{T}{2}]}.$

The same argument works for $I\subset[0,T]$. This time we use the symmetry of
$H$ around $\frac{T}{2}$.

  * •

$|I|\geq\frac{T}{2}$.

This time take $J=[nT,mT]$ with $n,m\in\mathbb{Z}$ which contains $I$ and
$|J|\leq|I|+2T\leq 5|I|$. And again like the previous cases, from the symmetry
and periodicity of $H$, we get

$O(H,I)\leq 2\frac{|J|}{|I|}O(H,J)\leq 10O(h,[0,\frac{T}{2}])\leq
10\|h\|_{BMO[0,\frac{T}{2}]}.$

The proof is now complete.

∎

######  Remark 2.3.

There are much more general ways to extend $BMO$ functions to the outside of
domains, but for the purpose of our paper the above simple lemma is enough.
See [7] for more on extensions.

Before we proceed further, let us fix some notations. By $A\lesssim B$,
$A\gtrsim B$ and $A\approx B$, we mean $A\leq CB$, $A\geq CB$ and $C^{-1}B\leq
A\leq CB$ respectively, where $C$ is a constant independent of the important
parameters.

######  Lemma 2.4.

For $c<-1$, there exists a sequence of functions $g_{n}$ with the following
properties:

  1. (1)

$g_{n}\geq 0$

  2. (2)

$g_{n}=0$ on $[c,1]$

  3. (3)

$\|g_{n}\|_{{L}^{\infty}}\leq 1$

  4. (4)

$\lim\limits_{n\to\infty}\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{[0,n]}{g_{n}}=1$

  5. (5)

$\lim\limits_{n\to\infty}\|g_{n}\|_{{{BMO}(\mathbb{R})}}=0$.

###### Proof.

Let $\log^{+}|x|=\max\\{0,\log|x|\\}$ be the positive part of the logarithm,
and consider the function $h_{n}(x)=\log^{+}x$ on the interval $[0,n]$, which
belongs to $BMO[0,n]$ with
$\|h_{n}\|_{BMO[0,n]}\leq\|\log^{+}|\cdot|\|_{{{BMO}(\mathbb{R})}}$. Then an
application of lemma 2.2 with $T=2n$ gives us a sequence of nonnegative
functions $H_{n}$ with $\|H_{n}\|_{{{BMO}(\mathbb{R})}}\lesssim 1$. Now let
$g_{n}=\frac{1}{\log n}H_{n}(x)(1-\chi_{[c,0]}(x))$. The first three
properties are immediate from the definition, the forth one follows from
integration, and the last one from

$\|g_{n}\|_{{{BMO}(\mathbb{R})}}\leq\frac{1}{\log
n}(\|H_{n}\|_{{{BMO}(\mathbb{R})}}+\|H_{n}\chi_{[c,0]}\|_{{L}^{\infty}})\lesssim\frac{\log|c|}{\log
n}.$

This finishes the proof. ∎

Now we turn to the proof of the above theorem.

###### Proof of Theorem 2.1.

Let $f$ be as in the theorem, $a=\int_{0}^{1}f$, $c<0$ a constant with large
magnitude to be determined later, and let $g_{n}$ be the sequence constructed
in lemma 2.4.

We will show that

(2)
$\varliminf\limits_{n\to\infty}\|M(f+\frac{a}{1-c}g_{n})-Mf\|_{{{BMO}(\mathbb{R})}}>0.$

This, together with
$\lim\limits_{n\to\infty}\|g_{n}\|_{{{BMO}(\mathbb{R})}}=0$, proves the
theorem.

To begin with, we claim that $M(f+\frac{a}{1-c}g_{n})=Mf$ on $[c,0]$. To see
this, note that from the positivity of $f$ and $g_{n}$,
$M(f+\frac{a}{1-c}g_{n})(x)\geq Mf(x)$ for all values of $x$, and it remains
to show that the reverse inequality holds also. For $x\in[c,0]$,
$Mf(x)\geq\frac{\int_{c}^{1}f}{1-c}=\frac{a}{1-c}$, and for any interval $I$
which contains $x$, we have two possibilities:

  * •

either $I\subset(-\infty,0)$, in which case from the third property of $g_{n}$
we have

$\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{I}{(f+\frac{a}{1-c}g_{n})}=\frac{a}{1-c}\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{I}{g_{n}}\leq\frac{a}{1-c}\|g_{n}\|_{{L}^{\infty}}\leq\frac{a}{1-c}\leq
Mf(x),$

  * •

or $I\cap[0,1]\neq\emptyset$, in which case the second and the third property
of $g_{n}$ gives us

$\displaystyle\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{I}{(f+\frac{a}{1-c}g_{n})}=\frac{|I\cap[x,1]|}{|I|}\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{I\cap[x,1]}{f}+\frac{|I\backslash[x,1]|}{|I|}\frac{a}{1-c}\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{I\backslash[x,1]}{g_{n}}$
$\displaystyle\leq\frac{|I\cap[x,1]|}{|I|}Mf(x)+\frac{|I\backslash[x,1]|}{|I|}\frac{a}{1-c}\leq
Mf(x).$

This proves our claim.

Next we look at the mean oscillation of $M(f+\frac{a}{1-c}g_{n})-Mf$ on
$[2c,0]$. Because this function vanishes on $[c,0]$, we have

(3)
$O(M(f+\frac{a}{1-c}g_{n})-Mf,[2c,0])\geq\frac{1}{4}\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{[2c,c]}{(M(f+\frac{a}{1-c}g_{n})-Mf)}.$

To bound the right hand side of the above inequality from below, we note that
$f\leq\chi_{[0,1]}$ so $Mf(x)\leq M(\chi_{[0,1]})(x)=\frac{1}{1-x}$ for $x\leq
0$. Also for $x\leq 0$, we have

$M(f+\frac{a}{1-c}g_{n})(x)\geq\frac{a}{1-c}\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{[x,n]}{g_{n}}\geq\frac{a}{1-c}.\frac{n}{n-x}\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{[0,n]}{g_{n}}.$

So we get the following estimate for the right hand side in (3):

(4)
$\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{[2c,c]}{(M(f+\frac{a}{1-c}g_{n})-Mf)}\geq\frac{a}{1-c}\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{[0,n]}{g_{n}}\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{[2c,c]}{\frac{n}{n-x}dx}-\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{[2c,c]}{\frac{1}{1-x}dx}.$

Combining (3) and (4), gives us

$\|M(f+\frac{a}{1-c}g_{n})-Mf\|_{{{BMO}(\mathbb{R})}}\geq\frac{1}{4}(\frac{a}{1-c}\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{[0,n]}{g_{n}}\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{[2c,c]}{\frac{n}{n-x}dx}+\frac{1}{c}\log(1+\frac{c}{c-1})).$

Now by taking the $\varliminf$ and using the forth property of $g_{n}$ we get

$\varliminf\limits_{n\to\infty}\|M(f+\frac{a}{1-c}g_{n})-Mf\|_{{{BMO}(\mathbb{R})}}\geq\frac{1}{4}(\frac{a}{1-c}+\frac{1}{c}\log(1+\frac{c}{c-1})).$

This shows that if we have

(5) $a>\frac{c-1}{c}\log(1+\frac{c}{c-1})$

then (2) holds. Here we note that the function on the right hand side of (5),
attains its minimum, which is $\log 2$, at infinity. So if we choose $|c|$
sufficiently large (5) holds, and this completes the proof. ∎

By lifting the above functions to higher dimensions with

(6) $f(x_{1},..,x_{n})=f(x_{1}),\quad g_{m}(x_{1},..,x_{n})=g_{m}(x_{1}),$

we obtain a counterexample for continuity of the $n$-dimensional Hardy-
Littlewood maximal operator on ${BMO}(\mathbb{R}^{n})$, simply because the
${BMO}(\mathbb{R}^{n})$ norms and the maximal operator become one dimensional.

######  Corollary 2.5.

The Hardy-Littlewood maximal operator is discontinuous on
${BMO}(\mathbb{R}^{n})$ for $n\geq 1$.

##  3\. Maximal function on ${VMO}(\mathbb{R}^{n})$

As it is mentioned before, ${VMO}(\mathbb{R}^{n})$ is the
${BMO}(\mathbb{R}^{n})$-closure of uniformly continuous functions which belong
to ${BMO}(\mathbb{R}^{n})$. The operator $M$ reduces moduli of continuity,
because it’s sublinear, so it preserves uniformly continuous functions. But
from our previous result, one cannot deduce boundedness of $M$ on
${VMO}(\mathbb{R}^{n})$ by a limiting argument. Nevertheless, we have the
following theorem:

######  Theorem 3.1.

The operator $M$ maps ${VMO}(\mathbb{R}^{n})$ to itself for $n\geq 1$.

Before we prove this, we bring the following lemma which is needed later.

######  Lemma 3.2.

Let $A$ be a measurable subset of a cube $Q$ and $f\in{BMO}(\mathbb{R}^{n})$
with $\|f\|_{{BMO}(\mathbb{R}^{n})}=1$; then we have

(7)
$\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{A}{|f-f_{Q}|}\lesssim
1+\log\frac{|Q|}{|A|}.$

###### Proof.

From the John-Nirenberg inequality, there’s a dimensional constant $c>0$ such
that

$\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{A}{e^{c|f-f_{Q}|}}\leq\frac{|Q|}{|A|}\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{Q}{e^{c|f-f_{Q}|}}\lesssim\frac{|Q|}{|A|}.$

Now Jensen’s inequality gives us 7, as follows:

$\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{A}{|f-f_{Q}|}=\frac{1}{c}\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{A}{\log
e^{c|f-f_{Q}|}}\leq\frac{1}{c}\log\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{A}{e^{c|f-f_{Q}|}}\lesssim
1+\log\frac{|Q|}{|A|}.$

∎

######  Remark 3.3.

In the above lemma, let $A$ be a rectangle and take $Q$ to be the smallest
cube which contains it. Then

$O(f,A)\lesssim 1+\log e(A),$

where $e(A)$ is the eccentricity of $A$, or the ratio of the largest side to
the smallest one.

We now turn to the proof of Theorem 3.1, which is a simpler variant of the
local-nonlocal argument in [10].

###### Proof of Theorm 3.1.

We have to show that $\varlimsup\limits_{\delta\to 0}\omega(Mf,\delta)=0$ when
$f\in{VMO}(\mathbb{R}^{n})$. Now for every cube Q, we have $O(|f|,Q)\leq
2O(f,Q)$, which means that $|f|\in{VMO}(\mathbb{R}^{n})$ too. From this
together with $M(|f|)=M(f)$, it’s enough to prove the theorem for nonnegative
functions. Also from the homogeneity of $M$ we may assume
$\|f\|_{{BMO}(\mathbb{R}^{n})}=1$.

Let $Q_{0}$ be a cube and $c$ a constant with $c>e$. We decompose $M$ into the
local part $M_{1}$, and the nonlocal part $M_{2}$ as follows:

$M_{1}f(x)=\underset{l(Q)\leq cl(Q_{0})}{\underset{x\in
Q}{\sup}f_{Q}},\quad\quad M_{2}f(x)=\underset{l(Q)\geq
cl(Q_{0})}{\underset{x\in Q}{\sup}f_{Q}}.$

We have $Mf(x)=\max\\{M_{1}f(x),M_{2}f(x)\\}$ and so

(8) $O(Mf,Q_{0})\lesssim O(M_{1}f,Q_{0})+O(M_{2}f,Q_{0}).$

To estimate the first term in the right hand side of (8), let $Q_{0}^{*}$ be
the concentric dilation of $Q_{0}$ with $l(Q_{0}^{*})=2cl(Q_{0})$. Then for
the local part we have

$\displaystyle O(M_{1}f,Q_{0})\leq
2\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{Q_{0}}{|M_{1}f-f_{Q_{0}^{*}}|}\leq
2\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{Q_{0}}{M_{1}|f-f_{Q_{0}^{*}}|}$
$\displaystyle\leq
2(\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{Q_{0}}{(M_{1}|f-f_{Q_{0}^{*}}|)^{2}})^{\frac{1}{2}}\leq
2(\frac{1}{|Q_{0}|}\int(M|f-f_{Q_{0}^{*}}|\chi_{Q_{0}^{*}})^{2})^{\frac{1}{2}}.$

By using the boundedness of $M$ on $L^{2}(\mathbb{R}^{n})$ we get

$\displaystyle O(M_{1}f,Q_{0})\lesssim
c^{\frac{n}{2}}(\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{Q_{0}^{*}}{|f-f_{Q_{0}^{*}}|^{2}})^{\frac{1}{2}},$

and an application of the John-Nirenberg inequality gives us

(9) $O(M_{1}f,Q_{0})\lesssim c^{\frac{n}{2}}\|f\|_{BMO(Q_{0}^{*})}.$

To estimate the mean oscillation of the nonlocal part, suppose $x,y\in Q_{0}$,
$M_{2}f(x)>M_{2}f(y)$ and let $Q$ be a cube with $l(Q)\geq cl(Q_{0})$, which
contains $x$ and such that $M_{2}f(y)<f_{Q}$. Now let $Q^{\prime}$ be a cube
such that $Q_{0}\cup Q\subset Q^{\prime}$, $l(Q^{\prime})=l(Q)+l(Q_{0})$, and
let $A=Q^{\prime}\backslash Q$. Then $M_{2}f(y)\geq f_{Q^{\prime}}$ and we
have

$\displaystyle f_{Q}-M_{2}f(y)\leq
f_{Q}-f_{Q^{\prime}}=f_{Q}-(\frac{|A|}{|Q^{\prime}|}f_{A}+\frac{|Q|}{|Q^{\prime}|}f_{Q})=\frac{|A|}{|Q^{\prime}|}(f_{Q}-f_{A})$
$\displaystyle\leq\frac{|A|}{|Q^{\prime}|}(|f_{Q}-f_{Q^{\prime}}|+|f_{Q^{\prime}}-f_{A}|)\lesssim\frac{|A|}{|Q|}O(f,Q^{\prime})+\frac{|A|}{|Q^{\prime}|}\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{A}{|f-f_{Q^{\prime}}|}.$

Here we note that $|A|=|Q^{\prime}|-|Q|\approx l(Q_{0})l(Q)^{n-1}$, and
$l(Q^{\prime})\approx l(Q)$. So from the above inequality and lemma 3.2 we get

$f_{Q}-M_{2}f(y)\lesssim\frac{l(Q_{0})}{l(Q)}(1+\log\frac{l(Q)}{l(Q_{0})})\lesssim
c^{-1}\log c.$

The reason for the last inequality is that $\frac{l(Q_{0})}{l(Q)}\leq c^{-1}$
and the function $-t\log t$ is increasing when $t<e^{-1}$. Finally, by taking
the supremum over all such cubes $Q$, we obtain

$|M_{2}f(x)-M_{2}f(y)|\lesssim c^{-1}\log c,\quad x,y\in Q_{0}.$

So for the nonlocal part we have

(10)
$O(M_{2}f,Q_{0})\leq\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int\limits_{Q_{0}}\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int\limits_{Q_{0}}|M_{2}f(x)-M_{2}f(y)|dxdy\lesssim
c^{-1}\log c.$

By putting (8), (9) and (10) together we get

$O(Mf,Q_{0})\lesssim c^{\frac{n}{2}}\|f\|_{BMO(Q_{0}^{*})}+c^{-1}\log c,$

and taking the supremum over all cubes $Q_{0}$ with $l(Q_{0})=\delta$ gives us

$\omega(Mf,\delta)\lesssim c^{\frac{n}{2}}\omega(f,2c\delta)+c^{-1}\log c.$

To finish the proof, it’s enough to take the $\varlimsup\limits_{\delta\to 0}$
first and then let $c\to\infty$. ∎

######  Remark 3.4.

The above argument shows that for all functions in ${BMO}(\mathbb{R}^{n})$, if
one chooses a sufficiently large localization of $M$, (10) holds, meaning that
the mean oscillation of the nonlocal part is small. This also shows itself in
the dyadic setting: if one considers the dyadic maximal operator $M^{d}$ and
dyadic $BMO$, denoted by ${BMO_{d}}(\mathbb{R}^{n})$, then for a dyadic cube
$Q_{0}$

$M^{d}_{2}f(x)=\underset{l(Q)\geq l(Q_{0})}{\underset{x\in
Q}{\sup}f_{Q}}=\sup_{Q_{0}\subset Q}f_{Q},\quad x\in Q_{0}.$

Hence $O(M_{2}f,Q_{0})=0$ and therefore no dilation is needed $(c=1)$.

##  4\. Slices of BMO functions and unboundedness of directional and strong
maximal operators

In this final section we discuss properties of slices of functions in
${BMO}(\mathbb{R}^{n})$, and for simplicity we restrict ourselves to
${BMO}(\mathbb{R}^{2})$. We begin by asking:

Q4. Suppose $\varphi,\psi$ are two functions of one variable, when does
$f(x,y)=\varphi(x)\psi(y)$ belong to ${BMO}(\mathbb{R}^{2})$?

To answer this, we need the following lemma which is an application of
Fubini’s theorem and its proof is found in [5].

######  Lemma 4.1.

Let $A,B\subset\mathbb{R}$ be two measurable sets with finite positive
measure, and $f$ be a measurable function on $\mathbb{R}^{2}$. Then

$O(f,A\times
B)\approx\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{B}{O(f_{y},A)}dy+\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{A}{O(f_{x},B)}dx.$

Now take two intervals $I,J$ with $l(I)=l(J)$. Then an application of the
above lemma to $f(x,y)=\varphi(x)\psi(y)$ gives us

$O(f,I\times J)\approx
O(\psi,J)\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{I}{|\varphi|}+O(\varphi,I)\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{J}{|\psi|}.$

Taking the supremum over all such $I,J$ we obtain

(11)
$\|f\|_{{{BMO}(\mathbb{R}^{2})}}\approx\sup\limits_{\delta>0}\left(\sup_{l(I)=\delta}\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{I}{|\varphi|}.\sup_{l(J)=\delta}O(\psi,J)+\sup_{l(I)=\delta}O(\varphi,I).\sup_{l(J)=\delta}\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{J}{|\psi|}\right).$

When $f\in{BMO}(\mathbb{R}^{2})$ is not identically zero, the above condition
implies that $\varphi,\psi\in{BMO}(\mathbb{R})$. To see this, note that if
$\varphi$ is not identically zero, for some Lebesgue point of $\varphi$ like
$x$, $\varphi(x)\neq 0$. Then from the Lebesgue differentiation theorem, for
sufficiently small $\delta$ we must have
$\sup_{l(I)=\delta}\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{I}{\varphi}\gtrsim|\varphi(x)|>0$.
So $\psi$ has bounded mean oscillation on intervals with length less than
$\delta$. For intervals $J$ with $l(J)\geq\delta$, $|\psi|$ has bounded
averages because otherwise there is a sequence of intervals $J_{n}$ with
$l(J_{n})\geq\delta$ and
$\lim\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{J_{n}}{|\psi|}=\infty$.
Then by dividing each of these intervals into sufficiently small pieces of
length between $\frac{\delta}{2}$ and $\delta$, we conclude that $|\psi|$ has
large averages over such intervals so
$\sup_{l(J)=\delta}\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{J}{|\psi|}=\infty$.
But then $\sup_{l(I)=\delta}O(\varphi,I)=0$, which means that $\varphi$ is
constant. We summarize the above discussion in the following proposition.

######  Proposition 4.2.

Let $f(x,y)=\varphi(x)\psi(y)$, $f\in{BMO}(\mathbb{R}^{2})$ if and only if
(11) holds and if $f\neq 0$, then $\varphi,\psi\in{BMO}(\mathbb{R})$.

######  Remark 4.3.

When $\varphi$ and $\psi$ are not constants, the above argument shows that
they belong to $bmo(\mathbb{R})$, the nonhomogeneous $BMO$, which is a proper
subspace of ${BMO}(\mathbb{R})$. See [3] for more on $bmo(\mathbb{R})$.

######  Corollary 4.4.

Let $\log^{-}|x|=\max\\{0,-\log|x|\\}$ be the negative part of the logarithm
and $p,q>0$ with $p+q\leq 1$. Then the function
$f(x,y)=(\log^{-}|x|)^{p}(\log^{-}|y|)^{q}$ is in ${BMO}(\mathbb{R}^{2})$.

###### Proof.

A direct calculation shows that

$\displaystyle\sup_{l(I)=\delta}\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{I}{(\log^{-}|x|)^{p}}\approx\begin{cases}\delta^{-1}&\delta\geq\frac{1}{2}\\\
(-\log\delta)^{p}&\delta<\frac{1}{2}\end{cases},$
$\displaystyle\sup_{l(J)=\delta}O(\log^{-}|\cdot|,J)^{q}\approx\begin{cases}\delta^{-1}&\delta\geq\frac{1}{2}\\\
(-\log\delta)^{q-1}&\delta<\frac{1}{2}\end{cases},$

and the claim follows from proposition 4.2. ∎

######  Remark 4.5.

The above function $f$ doesn’t have bounded mean oscillation on rectangles,
simply because the $BMO$-norm of the slices becomes larger and larger as we
get close to the origin. See [8] (Example 2.32) for another example.

Now we answer the third question of this paper.

######  Theorem 4.6.

The operators $M_{e_{1}}$ and $M_{s}$ are unbounded on
${BMO}(\mathbb{R}^{n})$.

To prove this we need the following simple lemma.

######  Lemma 4.7.

Let $Q_{0}=[-1,1]^{n}$, $f\in{BMO}(\mathbb{R}^{n})$ with support in $Q_{0}$,
and $x_{k}$ be a sequence in $\mathbb{R}^{n}$ with $|x_{k}-x_{m}|\geq
3\sqrt{n}$ for $k\neq m$. Then $g(x)=\sum f(x-x_{k})$ is in
${BMO}(\mathbb{R}^{n})$ and
$\|g\|_{{BMO}(\mathbb{R}^{n})}\lesssim\|f\|_{{BMO}(\mathbb{R}^{n})}$.

###### Proof.

First, by comparing the average of $|f|$ on $Q_{0}$ with $Q_{0}+2e_{1}$ we
have $\int_{Q_{0}}|f|\lesssim\|f\|_{{BMO}(\mathbb{R}^{n})}$. Next, take a cube
$Q$ and suppose for some $k$, $Q\cap x_{k}+Q_{0}\neq\emptyset$. We note that
the distance of the support of functions $f(\cdot-x_{k})$ from each other is
at least $\sqrt{n}$ so if $l(Q)\leq 1$ then $O(g,Q)=O(f(\cdot-
x_{k}),Q)\leq\|f\|_{{BMO}(\mathbb{R}^{n})}$. Otherwise we have

$\displaystyle O(g,Q)\leq$ $\displaystyle
2\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{Q}{|g|}\leq\frac{2}{|Q|}\sum_{Q\cap
x_{k}+Q_{0}\neq\emptyset}\int_{x_{k}+Q_{0}}|f(y-x_{k})|dy$
$\displaystyle\lesssim\frac{\\#\\{k|Q\cap
x_{k}+Q_{0}\neq\emptyset\\}}{|Q|}\|f\|_{{BMO}(\mathbb{R}^{n})}.$

Now to finish the proof, note that $\\#\\{k|Q\cap
x_{k}+Q_{0}\neq\emptyset\\}\lesssim|Q|$ which implies
$O(g,Q)\lesssim\|f\|_{{BMO}(\mathbb{R}^{n})}$. ∎

###### Proof of Theorem 4.6.

We may assume $n=2$, since by a lifting argument similar to (6), we can
conclude the theorem for higher dimensions. Let $f$ be as in Corollary 4.4,
$N$ a positive integer, and consider the following function:

$g_{N}(x,y)=\sum_{k=0}^{N}\sum_{m=2^{k}}^{2^{k+1}-1}f(x-3\sqrt{2}m,y-\frac{k}{N}).$

$g_{N}$ has the following properties:

  1. (i)

$\|g_{N}\|_{{BMO}(\mathbb{R}^{n})}\lesssim 1$. (Here our bounds only depend on
$p,q$ but not $N$.)
This follows from Corollary 4.4 and Lemma 4.7 applied to $f$ with
$x_{m,k}=(3\sqrt{2}m,\frac{k}{N})$.

  2. (ii)

$M_{s}g_{N}\geq M_{e_{1}}g_{N}(x,y)\gtrsim(\log N)^{q}$ for $0\leq x,y\leq 1$.

To see this, let $0\leq x\leq 1$ and $\frac{l}{N}\leq y<\frac{l+1}{N}$ for
some $l<N$. Then consider the average of $(g_{N})_{y}$ on $I=[0,3\cdot
2^{l+1}\sqrt{2}]$, which is bounded from below by

$\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{I}{(g_{N})_{y}}\geq\frac{1}{3\cdot
2^{l+1}\sqrt{2}}\sum_{m=2^{l}}^{2^{l+1}-1}\int_{I}f(t-3\sqrt{2}m,y-\frac{l}{N})dt\\\
.$

Now note that for $2^{l}\leq m\leq 2^{l+1}-1$, $I$ contains the support of
$f(\cdot-3\sqrt{2}m,y-\frac{l}{N})$ and since $0\leq
y-\frac{l}{N}\leq\frac{1}{N}$ we have

$\displaystyle f(t-3\sqrt{2}m,y-\frac{l}{N})\geq(\log
N)^{q}(\log^{-}(t-3\sqrt{2}m))^{p}.$

From this we get

$\displaystyle
M_{e_{1}}g_{N}(x,y)\geq\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{I}{(g_{N})_{y}}$
$\displaystyle\geq\frac{1}{3\cdot
2^{l+1}\sqrt{2}}\sum_{m=2^{l}}^{2^{l+1}-1}\int_{I}f(t-3\sqrt{2}m,y-\frac{l}{N})dt$
$\displaystyle\geq\frac{1}{6\sqrt{2}}(\log N)^{q}\int(\log^{-}|t|)^{p}dt.$

  3. (iii)

$M_{e_{1}}g_{N}(x,y)=0$ for $y<-1$.

This holds simply because $g_{N}$ is supported on
$[3\sqrt{2}-1,\infty)\times[-1,2]$.

  4. (iv)

$M_{s}g_{N}(x,y)\lesssim 1$ for $0\leq x\leq 1,y\leq-2$.

To prove this final property of $g_{N}$, suppose $R=I\times J$ is a rectangle
with $(x,y)\in R$. Then if $R\cap supp(g_{N})\neq\emptyset$ we have
$l(I),l(J)\geq 1$, and we note that $\\#\\{(m,k)|R\cap
supp(f(\cdot-3\sqrt{2}m,\cdot-\frac{k}{N}))\neq\emptyset\\}\lesssim l(I)$
which implies

$\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{R}{g_{N}}\leq
l(I)^{-1}\\#\\{(m,k)|R\cap
supp(f(\cdot-3\sqrt{2}m,\cdot-\frac{k}{N}))\neq\emptyset\\}\int f\lesssim 1.$

Taking the supremum over all rectangles $R$ proves the last property of
$g_{N}$.

To complete the proof, let us measure the mean oscillation of $M_{e_{1}}g_{N}$
on the square $[-3,3]^{2}$ by

$O(M_{e_{1}}g_{N},[-3,3]^{2})\gtrsim|\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{[0,1]^{2}}{M_{e_{1}}g_{N}}-\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{[0,1]\times[-3,-2]}{M_{e_{1}}g_{N}}|.$

Then from the second and the third property of $g_{N}$ we obtain

(12) $O(M_{e_{1}}g_{N},[-3,3]^{2})\gtrsim(\log N)^{q},$

and the same is true for $M_{s}$. So by putting the first property of $g_{N}$
with (12) together, we conclude that neither $M_{s}$ nor $M_{e_{1}}$ is
bounded on ${BMO}(\mathbb{R}^{2})$. ∎

By modifying the above function, one can construct a function in
${BMO}(\mathbb{R}^{2})$ such that none of its horizontal slices are in
${BMO}(\mathbb{R})$. To do this, let $r_{n}$ be an enumeration of rational
numbers and consider the following function:

$h(x,y)=\sum_{m\geq 1}f(x-3\sqrt{2}m,y-r_{m}).$

Then we have

$O(h_{y},[3\sqrt{2}m-1,3\sqrt{2}m+1])=O((\log^{-}(\cdot))^{p},[-1,1])(\log^{-}(y-r_{m}))^{q}.$

So for all values of $y$, we get $\sup_{l(I)=2}O(h_{y},I)=\infty$, even though
$h\in{BMO}(\mathbb{R}^{2})$.
This example shows that one can not control the maximum mean oscillation of
the slices, when we look at intervals with a fixed length. However, in the
following theorem, we show that there is a loose control when the length of
intervals increases.

######  Theorem 4.8.

Let $f\in{BMO}(\mathbb{R}^{2})$ with $\|f\|_{{{BMO}(\mathbb{R}^{2})}}=1$. Then
there exist constants $\lambda,c>0$, independent of $f$, such that for any
sequence of intervals $I_{k}$ $(k\geq 1$) with $l(I_{k})=2^{k}$, and any
interval $J$ with $l(J)=1$, we have

$\int_{J}e^{\lambda\sup_{k\geq 1}\frac{O(f_{y},I_{k})}{k}}dy\leq c.$

###### Proof.

Let $E_{t}=\\{y\in J|\sup\limits_{k\geq 1}\frac{O(f_{y},I_{k})}{k}>t\\}$; then

(13) $E_{t}=\cup_{k=1}^{\infty}E_{t,k},\quad\quad E_{t,k}=\\{y\in
J|\frac{O(f_{y},I_{k})}{k}>t\\}.$

Now by taking the average over $E_{t,k}$ and applying Lemma 4.1 we get

$t<\frac{1}{k}\,\ThisStyle{\ensurestackMath{\stackinset{c}{.2\LMpt}{c}{.5\LMpt}{\SavedStyle-}{\SavedStyle\phantom{\int}}}\kern-16.56937pt}\int_{E_{t,k}}{O(f_{y},I_{k})}dy\lesssim\frac{1}{k}O(f,I_{k}\times
E_{t,k}).$

Next, let $J_{k}$ be the interval with the same center as J and with
$l(J_{k})=2^{k}$, and note that $E_{t,k}\subset J\subset J_{k}$, so
$I_{k}\times E_{t,k}\subset I_{k}\times J_{k}$. Then an application of Lemma
3.2 shows that

$t\lesssim\frac{1}{k}O(f,I_{k}\times
E_{t,k})\lesssim\frac{1}{k}(1+\log\frac{|I_{k}\times J_{k}|}{|I_{k}\times
E_{t,k}|})\lesssim 1-\frac{1}{k}\log|E_{t,k}|.$

So for an appropriate constants $a>0$, which is independent of $f$, we have
$|E_{t,k}|\lesssim e^{-atk}$ for $t>0$. From this and (13) we get the estimate

$|E_{t}|\leq\sum|E_{t,k}|\lesssim e^{-at},\quad t>0.$

Now an application of Cavalieri formula gives us

$\int_{J}e^{\frac{a}{2}\sup_{k\geq
1}\frac{O(f_{y},I_{k})}{k}}dy=\frac{a}{2}\int_{0}^{\infty}e^{\frac{a}{2}t}|E_{t}|dt\lesssim
1.$

Hence (4.8) holds with $\lambda=\frac{a}{2}$, and this finishes the proof. ∎

## Acknowledgements

I would like to thank G. Dafni and R. Gibara for suggesting these problems and
valuable discussions and comments.

## References

  * [1] Bennett, Colin. ”Another characterization of BLO.” Proceedings of the American Mathematical Society 85.4 (1982): 552-556.
  * [2] Bennett, Colin, and Ronald A. DeVore. ”Weak-Ly and BMO.” Annals of Mathematics 113 (1981): 601-611.
  * [3] Butaev, Almaz, and Galia Dafni. ”Locally uniform domains and extension of bmo functions.” arXiv preprint arXiv:2101.04587 (2021).
  * [4] Chang, Sun-Yung A., and Robert Fefferman. ”Some recent developments in Fourier analysis and $H^{p}$-theory on product domains.” Bulletin of the American Mathematical Society 12, no. 1 (1985): 1-43.
  * [5] Dafni, Galia, Ryan Gibara, and Hong Yue. ”Geometric Maximal Operators and BMO on Product Bases.” The Journal of Geometric Analysis 31.6 (2021): 5740-5765.
  * [6] Grafakos, Loukas. Modern fourier analysis. Vol. 250. New York: Springer, 2009.
  * [7] Jones, Peter W. ”Extension theorems for BMO.” Indiana University Mathematics Journal 29.1 (1980): 41-66.
  * [8] Korenovskii, Anatolii. Mean oscillations and equimeasurable rearrangements of functions. Berlin: Springer, 2007.
  * [9] Luiro, Hannes. ”Continuity of the maximal operator in Sobolev spaces.” Proceedings of the American Mathematical Society 135.1 (2007): 243-251.
  * [10] Saari, Olli. ”Poincaré inequalities for the maximal function, to appear in Ann.” Sc. Norm. Super. Pisa Cl. Sci.(5) 3. preprint arXiv:1605.05176 (2016).
  * [11] Sarason, Donald. ”Functions of vanishing mean oscillation.” Transactions of the American Mathematical Society 207 (1975): 391-405.
  * [12] Stein, Elias M., and Timothy S. Murphy. Harmonic analysis: real-variable methods, orthogonality, and oscillatory integrals. Vol. 3. Princeton University Press, 1993.


# Decision-Focused Learning: Through the Lens of Learning to Rank

Jayanta Mandi  Víctor Bucarey  Maxime Mulamba  Tias Guns

###### Abstract

In the last years, decision-focused learning, also known as predict-and-
optimize, has received increasing attention. In this setting, the predictions
of a machine learning model are used as estimated cost coefficients in the
objective function of a discrete combinatorial optimization problem for
decision making. Decision-focused learning proposes to train the ML models,
often neural network models, by directly optimizing the quality of decisions
made by the optimization solvers. Based on a recent work that proposed a
_noise contrastive estimation loss over_ a subset of the solution space, we
observe that decision-focused learning can more generally be seen as a
learning-to-rank problem, where the goal is to learn an objective function
that ranks the feasible points correctly. This observation is independent of
the optimization method used and of the form of the objective function. We
develop pointwise, pairwise and listwise ranking loss functions, which can be
differentiated in closed form given a subset of solutions. We empirically
investigate the quality of our generic methods compared to existing decision-
focused learning approaches with competitive results. Furthermore, controlling
the subset of solutions allows controlling the runtime considerably, with
limited effect on regret.

Learning to rank, Predict and Optimize

##  1 Introduction

Many real-world decision making problems rely on the combination of machine
learning (ML) and combinatorial optimization (CO). In those applications, CO
problems are solved to arrive at a decision by maximizing or minimizing an
objective function. However, often some parameters of the optimization
problem, such as costs, prices and profits, are not known but can be estimated
from other feature attributes based on historical data.

A two-stage predict-_then_ -optimize approach is widely used by practitioners
in both the industry and the public sector, where first an ML model is trained
to make point estimates of the uncertain parameters and then the optimization
problem is solved using the predictions. However, this treats the parameter
errors as independent and does not take the _interplay of the parameter errors
and their effect_ on the combinatorial optimisation problem into account.

Recently _decision-focused learning_ (Wilder et al., 2019; Pogancic et al.,
2020) (also known as predict-and-optimize (Elmachtoub & Grigas, 2021; Mandi et
al., 2020)) has received increasing attention. In this setting, during
training, the ML model is trained with a loss function that first solves the
downstream CO problem to observe the joint error. On the technical level, the
challenge of integrating combinatorial optimization into the training loop of
ML is the non-differentiability of combinatorial problems. To address this,
Mulamba et al. (2021) recently proposed an approach motivated by noise-
contrastive estimation (Gutmann & Hyvärinen, 2010), where they introduce a new
family of surrogate loss functions considering non-optimal feasible solutions
as _negative examples_. In their work, they propose a surrogate loss function,
which maximizes the divergence between the objective values of the true
optimal and the negative examples.

We argue that decision-focused learning can be more generally viewed through
the lens of learning to rank (LTR) approach (Burges et al., 2005). In a LTR
problem, for each query there is a list of items and their feature variables
given. The training objective is to learn a ranking function, which will rank
the (top) items correctly for each query.

In the context of CO problems, a partial ordering of the feasible solutions is
induced by the objective function. Learning the orders of the feasible
solution with respect to the objective function hence achieves the goal of
decision-focused learning. When compared to the LTR literature, there are two
important differences: 1) part of the structure of the objective function is
already given, only some of its parameters must be estimated; and 2) the set
of ‘items’ are all feasible solutions, which are the same for all CO problem
instances (queries), but it is intractable to enumerate all. While
backpropagating, 1) needs not be an issue under the assumption that just the
objective function itself is differentiable, which is the case for standard
continuous functions including linear functions. With respect to 2), we can
subsample the feasible solutions as is done by Mulamba et al. (2021).

The main contributions of this work are the following: First, we formulate the
decision-focused learning as a ranking problem. Secondly, we introduce and
study several well-known learning to rank loss functions. In particular, we
formulate pointwise, pairwise and listwise ranking loss functions for
decision-focused learning problems. Thirdly, we show that the pairwise ranking
loss is a generalization of the loss functions proposed by Mulamba et al.
(2021). Lastly, we show that in case of a linear objective function, the
pointwise and pairwise-difference loss functions can be interpreted as trading
off the mean square error (MSE) and regret of predictions.

##  2 Related Literature

#### Decision-focused learning.

Decision-focused learning involves optimization problems, where the
optimization parameters are defined partially. One of the major developments
in this topic is the _differentiable optimization layer_ (Amos & Kolter,
2017), which analytically computes the gradients by differentiating the KKT
optimality conditions of a quadratic program. The gradient calculation of Amos
& Kolter (2017) does not translate to linear programming (LP) problems due to
singularities of the objective function in this case. Wilder et al. (2019)
address this by introducing a small quadratic regularizer in the objective
function while Mandi & Guns (2020) introduce a log-barrier regularization term
and compute the gradients from the homogeneous self dual embedding of the LP.
Ferber et al. (2020) studies mixed integer LPs and reduce it to LP by adding
cutting plane to the root LP node, applying the framework of Wilder et al.
(2019) afterwards. All these methods are specific to the structure of the CO
problem used.

Other approaches are independent of the CO problem and solver used. The _smart
predict-and-optimize_ approach of Elmachtoub & Grigas (2021) studies
optimization problems with linear objectives and where the cost vector has to
be predicted. They introduce a convex surrogate upper bound of the loss and
propose an easy to use subgradient. Pogancic et al. (2020) also studies
problems with linear objectives. They compute the gradient by perturbing the
predicted cost vector. Niepert et al. (2021) extend this work by adding noise-
perturbations for perturbation-based implicit differentiation. For an overview
of decision-focused learning, we refer the readers to Kotary et al. (2021).

All these approaches involve solving the optimization problem for every
instance during training, which comes at a very high computational cost. To
address this problem, Mulamba et al. (2021) propose contrastive loss functions
with respect to a pool of feasible solutions of the optimization problem. It
cleanly separates the solving (adding solutions to the pool), from the loss
function. This allows the loss function to be differentiated directly. We
build on this idea but through the lens of learning to rank.

#### Learning to rank.

Learning to rank problems have been studied thoroughly over the years,
especially within the context of information retrieval. Readers can refer to
Liu (2011) for a detailed analysis. Most of the LTR approaches assign real-
valued scores to the items, then define surrogate loss functions on the
scores. In pointwise LTR models (Li et al., 2007), the labels are the rank (or
true score, if known) of the items. These models fail to consider any inter
dependencies across the item rankings. Pairwise ranking approaches (Burges et
al., 2005) aim to learn the relative ordering of pairs of items. Finally,
listwise approaches (Cao et al., 2007) define loss functions with respect to
the scores of the whole ranked lists. The LTR framework has been applied to
various contexts such as recommender systems (Karatzoglou et al., 2013) and
software debugging (Xuan & Monperrus, 2014), among others.

Demirović et al. (2019) have used LTR in decision-focused learning framework,
but by considering the parameters of a linear objective function as the items
to rank, e.g. the value of items of a knapsack problem, instead of the
feasible solutions as we do. Kotary et al. (2021) propose a fair LTR
methodology, which impose fairness constraints using constraints in the
combinatorial optimization problem and they use decision-focused learning to
integrate the optimization program with an ML model. In contrast, we use LTR
models and losses for decision-focused learning.

##  3 Problem Statement and Motivation

In this section, we introduce the decision-focused learning setup. We consider
a discrete combinatorial optimization problem

$v^{\star}(c)\in\operatorname*{argmin}_{v\in V}f(v,c)$ (1)

where $V\subseteq\mathbb{Z}^{K}$ is the set of feasible integer solutions,
typically specified implicitly through constraints, and
$f:V\times\mathcal{C}\rightarrow\mathbb{R}$ is the real valued objective
function, where $\mathcal{C}\subset\mathbb{R}^{K}$ is the domain of the vector
of parameters $c$. We denote an optimal solution of (1) by $v^{\star}(c)$. The
value of $c$ is unknown but we have access to correlated features $x$ and a
historic dataset $D=\\{(x_{i},c_{i})\\}_{i=1}^{N}$. The goal is to predict the
apriori unknown coefficient vector $c_{i}$ in a supervised machine learning
setup. To do so, we train a model noted by $m(\omega,x_{i})$ to make a
prediction of vector $c_{i}$, where $\omega$ are the model parameters. Let us
denote the predicted value as $\hat{c}_{i}=m(\omega,x_{i})$.

In a traditional supervised machine learning setup, we train by minimizing the
difference between $c$ and $\hat{c}$. For instance, in a regression problem,
we minimize the multi-output mean square error,

$\mathbf{mse}(c,\hat{c})=\sum_{k=1}^{K}(c_{k}-\hat{c}_{k})^{2}=\sum_{k=1}^{K}\epsilon_{k}^{2}$
(2)

where $\epsilon_{k}=(c_{k}-\hat{c}_{k})$, over a set of $N$ instances
$\\{(c,\hat{c})\\}$.

In contrast, in decision-focused learning $\hat{c}$ is an intermediate result.
The final output is $v^{\star}(\hat{c})$, the solution of the discrete
combinatorial optimization problem. The final goal is to minimize the impact
of the solution $v^{\star}(\hat{c})$ in the downstream optimization problem
whenever the real cost vector $c$ is realized. In order to measure how good
$\hat{c}$ is, we compute the _regret_ of the combinatorial optimisation. The
_regret_ is defined as the difference between the value of the optimal
objective value $f(v^{\star}(c),c)$ and the value of the objective function
with ground truth $c$ and predicted solution $v^{\star}(\hat{c})$. Formally,
we define regret, without any assumptions on the structure of $f$, as

$\mbox{Regret}(\hat{c},c)=f(v^{\star}(\hat{c}),c)-f(v^{\star}(c),c).$ (3)

Ideally, we aim to learn parameters $\omega$ that determine
$\hat{c}=m(\omega,x)$ such that it minimizes the _regret_. To do so in a
neural network setup, the gradient of the regret has to be backpropagated,
which requires computing the exact derivative of the regret (3). This task is
problematic as $V$ is discrete and the regret function is non-continuous and
involves differentiating over the argmin in $v^{\star}(\hat{c})$.

As mentioned in section 2, several recent works have studied this problem.
However, in all those cases, in order to compute the gradient, the
optimization problem (1) must be solved repeatedly for each instance during
training. Hence, scalability is a major challenge in these approaches.

###  3.1 Contrastive Surrogate Loss

To improve the scalability of decision-focused learning Mulamba et al. (2021)
proposed an alternative class of loss functions. They first define the
following probability distribution of $v\in V$ being the optimal one.

$p(v|c)=\begin{cases}\frac{\exp\left(-f\left(v,c\right)\right)}{\sum_{v^{\prime}\in
V}\exp\left(-f\left(v^{\prime},c\right)\right)}&\text{if}\ v\in V\\\
0,&\text{if}\ v\notin V\end{cases}$ (4)

It is easy to verify that, if $v$ is one minimizer of Eq. 1, then it will
maximize Eq. 4. To define the loss functions they consider to have access to
$S$, a _subset_ of $V$ and treat $\left(S\setminus\\{v^{\star}(c)\\}\right)$
as negative examples. With this setup, they define the following noise
contrastive estimation (NCE) loss

$\displaystyle L_{\operatorname*{NCE}}(\hat{c},c)=\frac{1}{|S|}\sum_{v^{s}\in
S}\Big{(}f\big{(}v^{\star}(c),\hat{c}\big{)}-f\big{(}v^{s},\hat{c}\big{)}\Big{)}.$
(5)

The novelty of this approach is that Eq. (5) is differentiable and that the
differentiation does not involve solving the optimization problem in (1).
Further, if the solutions in $S$ are optimal solutions of arbitrary cost
vectors, this approach is equivalent to training in a region of the convex-
hull of $V$.

##  4 Rank Based Loss Functions

In this section we develop and motivate a family of surrogate loss functions
for decision-focused learning problems. We remark that, for a given $c$, we
can create a partial ordering of all $v\in V$ by ordering them with respect to
the objective value. Let us denote by $p_{1},\ldots,p_{|V|}$ the indices of
$V$ so that $f(v^{p_{1}},c)\leq f(v^{p_{2}},c)\leq\ldots\leq
f(v^{p_{|V|}},c)$. The key idea of our approach is to generate prediction
$\hat{c}$ so that $f(v^{p_{1}},\hat{c})\leq f(v^{p_{2}},\hat{c})\leq\ldots\leq
f(v^{p_{|V|}},\hat{c})$. Notice that, if the ranks of $v\in V$ with respect to
$\hat{c}$ are identical to that of $c$, the regret is zero. Furthermore, it is
sufficient that $\forall p_{s}:f(v^{p_{1}},\hat{c})\leq f(v^{p_{s}},\hat{c})$
for the regret to be zero. In general, our surrogate task is to learn the
ranking of each $v\in V$ with respect to $c$. This motivates us to use the LTR
framework to develop a new class of surrogate loss functions for decision-
focused learning problems.

Drawing a parallel to the LTR literature, we consider each $x$ a query, and
the feasible solutions $v\in V$ as the set of items to be ordered. Our
formulation differs from traditional LTR framework because in LTR problems
each item has its own set of feature variables, whereas in our formulation
each $v$ does not have feature variables. We hence only have query-features
($x$ itself) to predict $c$. In the LTR framework, a ranking function is used
to assign scores to each item. In decision-focused learningsetup, we will
consider the objective function $f(v,c)$ as the scoringh function.

To rank all $v\in V$ is an intractable task for most combinatorial problems.
To overcome this in practice, we will consider a set of feasible solution
$S\subset V$. The proposed implementation is described in pseudocode form in
Algorithm 1. For each $c$, we compute a loss function $L(\hat{c},c)$
considering the surrogate ranking task. The implementation details are
described later. Next, we will introduce the family of rank based loss
functions.

Algorithm 1 Gradient-descent implementation of decision-focused learning
problems with Ranking Loss

Input: D$\equiv\\{(x_{i},c_{i})\\}_{i=1}^{n}$

1: Initialize $\omega$

2: Initialize $S=\\{v^{\star}(c_{i})|(x_{i},c_{i})\in D\\}$ Training

3: for each epochs do

4: for each $(x_{i},c_{i})$ do

5: $\hat{c}_{i}=m(\omega,x_{i})$

6: if random$()<p_{solve}$ then

7: $v^{\star}(\hat{c}_{i})\leftarrow$call solver to solve Eq. (1),

8: $S\leftarrow S\cup\\{v^{\star}(\hat{c}_{i})\\}$

9: end if

10: $\mathcal{L}+=L(\hat{c}_{i},c_{i};S)$

11: end for

12: $\omega\leftarrow\omega-\alpha\frac{\partial\mathcal{L}}{\partial\omega}$
# backward pass

13: end for

###  4.1 Pointwise Ranking

In pointwise ranking loss formulation, the loss function is defined for each
item (feasible solution) independently. In our pointwise rank loss
formulation, we propose to regress the predicted objective function value on
the actual objective function value. Thus, we propose the pointwise loss
function

$\displaystyle L_{P}(\hat{c},c;S)=\frac{1}{|S|}\sum_{v\in
S}\left(f(v,\hat{c})-f(v,c)\right)^{2}$ (6)

that measures the errors in the evaluation of the predicted cost function at
each point in $S$.

#### Intuitive idea of the pointwise loss function.

When the objective function is linear i.e. $f(v,c)=c^{\intercal}v$, the
pointwise loss (6) becomes

$\displaystyle L^{p}(\hat{c},c;S)=\frac{1}{|S|}\sum_{v\in
S}\left(c^{\intercal}v-\hat{c}^{\intercal}v\right)^{2}$ (7)

The derivative of this loss is

$\displaystyle\frac{\partial
L^{p}(\hat{c},c;S)}{\partial\hat{c}}=-\frac{2}{|S|}\sum_{v\in
S}\left(c^{\intercal}v-\hat{c}^{\intercal}v\right)v$ (8)

When considering a combinatorial problem where $v$ is a binary vector, we can
see from Eq. (8) that coordinates where $v$ has zeros, will not contribute to
the gradient. Moreover, the first component
$\left(c^{\intercal}v-\hat{c}^{\intercal}v\right)$ is the difference between
the actual and the predicted objective value on $v$. The gradient contribution
of $v$ is weighed by this difference.

#### Pointwise loss as a regularizer.

For the special case of a linear objective function $f(v,c)=$
$\sum_{j=1}^{K}c_{j}v_{j}$, the pointwise task loss can be rewritten as:

$\displaystyle L_{P}(\hat{c},c;S)=$
$\displaystyle\sum_{i=1}^{K}(\hat{c}_{i}-c_{i})^{2}\gamma_{i}+\sum_{i\neq
j}(\hat{c}_{i}-c_{i})(\hat{c}_{j}-c_{j})\gamma_{ij}$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{K}\epsilon_{i}^{2}\gamma_{i}+\sum_{i\neq
j}\epsilon_{i}\epsilon_{j}\gamma_{ij}$ (9)

where $\gamma_{i}=\frac{1}{|S|}\sum_{v\in S}v_{i}^{2}$ and
$\gamma_{ij}=\frac{1}{|S|}\sum_{v\in S}v_{i}v_{j}$ and $\epsilon_{i}$ defined
as in (2). In this case, it is a weighted version of the $\mathbf{mse}$
function plus a term that measures the pairwise relationship of errors of the
coordinates.

Moreover, when $V\subseteq\\{0,1\\}^{K}$, the weight $\gamma_{i}$ is the
frequency of how many times coordinate $v_{i}$ takes value 1 (since
$v_{i}^{2}=v_{i}$). Coefficients $\gamma_{ij}$ measure the frequency where
$v_{i}$ and $v_{j}$ take value 1 at the same time. In particular, if $S=V$

$\displaystyle
L^{p}(\hat{c},c;V)=\frac{1}{2}\Big{(}\mathbf{mse}(\hat{c},c)+\sum_{i=1}^{K}\sum_{j=1:j<i}^{K}\epsilon_{i}\epsilon_{j}\Big{)}$

Hence, the pointwise loss function can be seen as the $\mathbf{mse}$ plus a
regularizer which penalizes the crossed-errors between coordinates of the
vector $c$.

###  4.2 Pairwise Ranking

Example. To demonstrate the shortcoming of the pointwise loss and the
motivation behind the pairwise loss formulation, we construct a simple
example. Let us consider the feasible space is the 2 dimensional 0-1 space,
containing the four feasible points $[0,0],[0,1],[1,0],[1,1]$. Now, let $c$ be
$[2,-5]$. The objective values at these four points are $0,-5,2$ and $-3$,
hence $v^{\star}(c)=[0,1]$. Now let $\hat{c}_{1}$ be $[-1,1]$ and
$\hat{c}_{2}$ be $[5,-11]$. For $\hat{c}_{1}$ and $\hat{c}_{2}$, the objective
values of these four points are $0,1,-1,0$ and $0,-11,5,-6$ respectively. The
square error of both $\hat{c}_{1}$ and $\hat{c}_{2}$ is $45=(3^{2}+6^{2})$.
The pointwise loss between $c$ and $\hat{c}_{1}$ is
$54=(0+(-5-1)^{2}+(2+1)^{2}+(-3-0)^{2})$ and $c$ and $\hat{c}_{2}$ is
$54=(0+(-5+11)^{2}+(2-5)^{2}+(-3+6)^{2})$. But $v^{\star}(\hat{c}_{1})=[1,0]$
and $v^{\star}(\hat{c}_{2})=[0,1]=v^{\star}(c)$. Even though the regret of
$\hat{c}_{2}$ is $0$, its pointwise loss is the same as $\hat{c}_{1}$, whose
regret is positive. With this motivation behind, we will construct the
pairwise ranking loss function.

Let $(p,q)$ be an ordered pair in $S$ with respect to $c$. We define
$\mbox{OP}_{c}^{S}$ as the set of all the ordered pairs such that the first
coordinate dominates the second one in the order induced by $c$, or
equivalently:

$(p,q)\in\mbox{OP}_{c}^{S}\implies f(v^{p},c)<f(v^{q},c)$ (10)

For an ordered pair $(p,q)$, we expect the predicted $\hat{c}$ would also
respect the ordering i.e. $f(v^{p},\hat{c})<f(v^{q},\hat{c})$. In other words,
$f(v^{p},\hat{c})-f(v^{q},\hat{c})$ is the quantity we aim to minimize. In the
standard pairwise _margin_ ranking loss formulation (Joachims, 2002), the loss
is zero, if $f(v^{p},\hat{c})$ is smaller than $f(v^{q},\hat{c})$ by at least
a margin of $\nu>0$. With this notion of margin, we introduce the following
generic pairwise loss

$\displaystyle\operatorname*{L_{\mbox{OP}^{S}_{c}}}(\hat{c},c)=$
$\displaystyle\frac{1}{|\mbox{OP}_{c}^{S}|}\sum_{(p,q)\in\mbox{O.P.}_{c}^{S}}\max\left(0,\nu+f(v^{p},\hat{c})-f(v^{q},\hat{c})\right)$
(11)

#### Ordered pairs generation.

Eq. (11) is built upon the concept of a pairwise ranking loss (Burges et al.,
2005). Note that, to implement this approach we have to identify ordered pairs
from the negative examples. Clearly generating all possible pairs comes with a
complexity of $\mathcal{O}(|S|^{2})$. To overcome this implementation
challenge, we consider _best-versus-rest_ scheme, i.e.
$\mbox{OP}_{c}^{S}=\\{(v^{p_{1}},v^{p_{2}}),(v^{p_{1}},v^{p3}),\ldots,(v^{p_{1}},v^{p_{S}})\\}$,
where $v^{p_{1}}=v^{\star}(c)$. With this _best-versus-rest_ pair generation
scheme and $\gamma$ being $0$, Eq. (11) becomes

$\frac{1}{|S|}\sum_{v^{q}\in
S}\max\left(0,(f(v^{\star}(c),\hat{c})-f(v^{q},\hat{c}))\right)$ (12)

We point out that (12) takes the form of (5), without the _relu_ operator.
This shows that the NCE approach of Mulamba et al. (2021), although derived
differently, can be seen as a special case of our _best-versus-rest_ pairwise
approach.

Example continued. For computing the pairwise loss, first, we have to generate
the ordered pairs. The ordering of the feasible points with respect to $c$ is
$[0,1],[1,1],[0,0],[1,0]$. Following the best-vs-rest scheme, the pairs are
$\\{([0,1],[1,1]),([0,1],[0,0]),([0,1],[1,0])\\}$. For $\hat{c}_{1}$ the value
of the pairwise loss is $1+1+2=4$. For $\hat{c}_{2}$ the value of pairwise
loss is $0+0+0=0$, which is reasonable as its regret is $0$.

###  4.3 Regress on Pairwise Difference

Another way to generate a ranking of solutions in $S$ is to generate predicted
cost vectors, that produce the same difference in objective value. To do so,
we propose a loss function over the difference over pairs of solutions their
cost vectors $\hat{c}_{i}$ and $c_{i}$. This pairwise difference loss function
can be formulated as:

$\displaystyle L_{pd}(\hat{c},c;S)=\frac{1}{|S|}$
$\displaystyle\sum_{(p,q)\in\mbox{OP}_{c}^{S}}\bigg{(}\left(f(v^{p},\hat{c})-f(v^{q},\hat{c})\right)-$
$\displaystyle\left(f(v^{p},c)-f(v^{q},c)\right)\bigg{)}^{2}$ (13)

For the sake of clarity, we ommitted $\mbox{O.P.}_{c}^{S}$ from the definition
of $L_{p}d$.

It is easy to check that in the case of a linear objective:

$\displaystyle L_{pd}(\hat{c},c;S)=$
$\displaystyle\sum_{i=1}^{K}\epsilon_{i}^{2}\overline{\gamma}_{i}+\sum_{i\neq
j}\epsilon_{i}\epsilon_{j}\overline{\gamma}_{ij}$ (14)

where
$\overline{\gamma}_{i}=\frac{1}{|S|}\sum_{(p,q)}(v^{p}_{i}-v^{q}_{i})^{2}$,
which is proportional to how many times $v^{p}_{i}$ and $v^{q}_{i}$ are
different, and
$\overline{\gamma}_{ij}=\frac{1}{|S|}\sum_{(p,q)}(v^{p}_{i}-v^{q}_{i})(v^{p}_{j}-v^{q}_{j})$.
As in the pointwise loss, the pairwise difference loss can be seen as a
weighted $\mathbf{mse}$ loss function with a regularizer term; this time
involving the difference between solutions rather then individual
coefficients.

Example continued. As before, the set of pairs is
$\\{([0,1],[1,1]),([0,1],[0,0]),([0,1],[1,0])\\}$. The difference between
these three sets of pairs for $c$ are $2,5,7$. The corresponding differences
for $\hat{c}_{1}$ and $\hat{c}_{2}$ are $-1,-1,-2$ and $5,11,16$. So, the
corresponding losses for $\hat{c}_{1}$ and $\hat{c}_{2}$ are
$(2+1)^{2}+(5+1)^{2}+(7+2)^{2}=94$ and $(2-5)^{2}+(5-11)^{2}+(7-16)^{2}=94$.

###  4.4 Listwise Ranking

Instead of considering instance pairs, the listnet loss (Cao et al., 2007)
considers the entire ordered list. It is obvious that, if the list contains
only two instances, then there are no differences between the two approaches.
The listnet loss computes the probabilities of each item being the top one and
then defines a cross entropy loss of these probabilities. Instead of using Eq.
(4) directly, we further introduce a temperature parameter $\tau$ (Niepert et
al., 2021) to define

$\displaystyle
p_{\tau}(v|c)=\frac{\exp\left(-\frac{f\left(v,c\right)}{\tau}\right)}{\sum_{v^{\prime}\in
V}\exp\left(\frac{-f\left(v^{\prime},c\right)}{\tau}\right)}$ $\displaystyle\
\forall v\in V$ (15)

In this formulation, $\tau$ controls the smoothness of the distribution. As
$\tau\to 0$, $p_{\tau}(v|c)$ takes the form of a categorical distribution with
_only_ $v^{\star}(c)$ having positive probability mass. As $\tau$ increases
$p_{\tau}(v|c)$ converges to a uniform distribution in $V$.

In order to avoid the computation of the partition function (denominator), we
will approximate it as in the ranking functions proposed above, namely to
replace $V$ by a subset $S\subseteq V$.

Given a probability distribution, listnet loss is the cross entropy loss
between the predicted and the target distribution. Following this idea, we
define listwise loss as the cross entropy loss between $p_{\tau}(v|c)$ and
$p_{\tau}(v|\hat{c})$ for all $v\in S$:

$\displaystyle L^{l}_{S}(\hat{c},c)=-\frac{1}{|S|}\sum_{v\in
S}p_{\tau}(v|c)\log p_{\tau}(v|\hat{c})$ (16)

We remark that we could also consider the KL divergence loss instead of cross
entropy loss and define listwise loss as

$\displaystyle\frac{1}{|S|}\sum_{v\in S}p_{\tau}(v|c)\bigg{(}\log
p_{\tau}(v|c)-\log p_{\tau}(v|\hat{c})\bigg{)}$

Using this loss formulation, we obtained similar results to Eq.(16) and do not
further discuss it.

(a) Shortest path (Deg= 2)

(b) Shortest path (Deg= 4)

(c) Shortest path (Deg= 6)

(d) Shortest path (Deg= 8)

(e) Energy-1

(f) Energy-2

(g) Matching-1

(h) Matching-2

Figure 1: Learning Curve. We show how the average regrets on validation
dataset progress as the models learn.

###  4.5 Implementation

So far we define pointwise (6) pairwise (11), pairwise-difference (13) and
listwise (16) ranking losses. As mentioned, the fundamentals of the LTR loss
functions is to learn the partial ordering of $v\in S$. To construct and
expand $S$, we use the strategy of Mulamba et al. (2021). The generic
structure of the proposed algorithm is shown in Algorithm 1, which is a
modified version of standard gradient descent algorithms for decision-focused
learning problems. They proposed to initialise $S$ with all true optimal
solutions. In Algorithm 1 $S$ is initialized by caching all the optimal
solutions of the training instances in line 2. To expand $S$, they defined a
hyperparameter $p_{solve}$, which is the probability of calling a optimization
oracle to solve an instance during training. If an instance is solved, its
solution is added to $S$. This is demonstrated in line 8 in Algorithm 1.
Obviously with $p_{solve}=100\%$, Eq. (1) is solved for every $\hat{c}_{i}$
during training.

Table 1: Comparison of regret on three problem sets. We present average percentage regret of 10 runs. | Pointwise | Pairwise | Pairwise-diff | Listwise | NCE | MAP | SPO | Blackbox | Twostage
---|---|---|---|---|---|---|---|---|---
Shortest Path Problem
Deg-1 | 15.45% | 16.37% | 16.00% | 15.56% | 23.63% | 19.68% | 15.51% | 18.62% | 15.45%
Deg-2 | 10.07% | 10.74% | 11.60% | 10.41% | 30.84% | 14.15% | 10.06% | 13.26% | 10.07%
Deg-4 | 19.27% | 8.06% | 17.89% | 7.71% | 65.10% | 9.44% | 7.98% | 9.39% | 10.44%
Deg-6 | 72.18% | 9.27% | 32.63% | 8.29% | 129.42% | 9.45% | 16.19% | 9.69% | 15.96%
Deg-8 | 178.16% | 12.75% | 61.80% | 12.38% | 242.30% | 13.68% | 33.75% | 14.14% | 28.50%
Energy Scheduling Problem
Energy-1 | 2.51% | 1.65% | 1.63% | 1.67% | 1.69% | 1.59% | 1.56% | 1.54% | 1.91%
Energy-2 | 2.83% | 2.08% | 2.04% | 1.96% | 2.23% | 2.01% | 1.93% | 1.93% | 2.46%
Bipartite Matching Problem
Matching-1 | 90.17% | 88.80% | 88.23% | 88.49% | 89.39% | 89.13% | 88.70% | 90.09% | 90.12%
Matching-2 | 89.86% | 87.24% | 85.87% | 86.40% | 85.31% | 84.80% | 85.79% | 90.31% | 89.42%

The distinctive feature of this proposed approach is that the loss function
$L(\hat{c}_{i},c_{i})$ does not involve any argmin differentiation. So we can
use standard automatic differentiation libraries and it can be run on GPU.
Yet, it still considers the task loss of the downstream optimization problem.
The part that can not be run on GPU is calling an optimization oracle to
expand $S$.

##  5 Experiments

We analyze our approaches on a series of experiments. We consider three
discrete combinatorial optimization problems. First, we briefly describe the
experimental setups.

#### Shortest Path Problems.

We adopt this synthetic experiment from Elmachtoub & Grigas (2021). It is a
shortest path problem in a $5\times 5$ grid, with the objective of going from
the southwest corner of the grid to the northeast corner where the edges can
go either north or east. The feature vectors are sampled from a multivariate
Gaussian distribution. They generate the cost vector as per the following
model

$c_{ij}=\bigg{(}\frac{1}{\sqrt{p}}\big{(}Bx_{i}\big{)}+3\bigg{)}^{\text{Deg}}\epsilon_{i}^{j}$
(17)

where $c_{ij}$ is the $j$-th component of cost vector $c_{i}$ and $B$ is the
latent data generation matrix. Deg specifies the extent of model
specification, the higher the value of Deg, the more it deviates from a linear
model and the more errors there will be. We experiment with degree of
$1,2,4,6\text{ and }8$. $\epsilon_{i}^{j}$ is a multiplicative noise that is
sampled from $\text{U}(0.5,1.5)$. For each degree, we have 1000, 250 and
10,000 training, validation and test instances111The dataset is generated as
described in https://github.com/paulgrigas/SmartPredictThenOptimize. The
underlying model is a neural network without any hidden layer i.e. a
regression model.

#### Energy-cost Aware Scheduling.

Next we consider the problem of energy-cost aware scheduling, adapted from
_CSPLib_ (Gent & Walsh, 1999), a library of constraint optimization problems.
In energy-cost aware scheduling (Simonis et al., 1999), a given number of
tasks, to be scheduled on a certain number of machines without violating the
resource capacities of each machine. The goal of the optimization problem is
to find the scheduling which would minimize the total energy consumption
subject to the energy prices, which would be realized in the future. The
prediction task is to predict the future energy prices using feature variables
such as calendar attributes; day-ahead estimates of weather characteristics,
forecasted energy-load, wind-energy production and prices. We take the energy
price data from Ifrim et al. (2012). We study two instances named Energy-1 and
Energy-2. The first one involves scheduling 3 tasks on 10 machines, whereas
the other instance has 3 tasks and 15 machines.

(a) Energy-1

(b) Energy-2

(c) Matching-1

(d) Matching-2

Figure 2: MSE vs Regret trade-off

(a) Energy-1

(b) Matching-1

Figure 3: Change of MSE and Regret with $\alpha$ as a tuning parameter. The
green and blue bar present the MSE loss and percentage regret respectively.

#### Diverse Bipartite Matching.

We adopt this from Ferber et al. (2020) and Mulamba et al. (2021). The
topologies are taken from the CORA citation network (Sen et al., 2008). We
have 27 disjoint topologies and each of them is considered as an instance. The
prediction task is to predict which edges are present. Each node has 1433 bag-
of-words features. The feature of and edge is formed by concatenating features
of the two corresponding nodes. The optimization task is to find the maximum
matching after prediction. In the optimization task, diversity constraints
ensures that there are some edges between papers of the same field as well as
edges between papers of different fields. We study two instantiations with
different degrees of diversity constraints (see Appendix for detail).

###  5.1 Experimental Results

#### Performance of surrogate loss functions.

In this section, we compare the quality of the rank based loss functions. As
described in section 4, we train the neural network with respect to these loss
functions222The code is available at https://github.com/JayMan91/ltr-predopt..
As our objective is to have lower regret, we consider the percentage regret
($\frac{f(v^{\star}(\hat{c}),c)-f(v^{\star}(c),c)}{f(v^{\star}(c),c)}$) as the
evaluation metric. One way to know whether model training decreases the regret
is to monitor the regret on the validation dataset. Figure 1 validates that by
minimizing the surrogate losses, the neural network models learn to lower the
regret. In the shortest path problem, overall, the listwise and pairwise loss
functions perform better than the other two. The difference is more pronounced
in higher degrees, where the linear model makes larger error. In the
scheduling and matching experiments, the pairwise difference loss generalizes
the best. The lowest regret of listwise loss is similar to pairwise
difference, but its learning curve is less stable.

Next we compare the rank based loss functions with the SPO+ loss (Elmachtoub &
Grigas, 2021), Blackbox backpropagation approach (Pogancic et al., 2020) and
the NCE and MAP approach of Mulamba et al. (2021). We also include a two-stage
baseline approach which is trained purely on MSE loss. We present average
regret on test data of 10 independent trials in Table 1. We refer the readers
to C to view the distribution of the regrets. For the shortest path problem,
we again see the regret goes up with the degree parameter. This is expected as
the degree parameter controls the magnitude of the errors of the linear model.
For degree 4, 6 and 8, the listwise loss function produces the lowest regret.
For lower two degrees, the pointwise and pairwise difference loss function
produces low regret, but their regret jumps up at higher degrees. This is
reasonable as their los functions include the absolute difference between the
predicted and true solutions. Listwise loss comes second among all in Energy-2
and Matching-1. The pairwise difference loss has lowest regret in Matching-1
and its regret is competitive with the best loss function in these two
problems. In all cases the pointwise loss function performs poorly, even worse
than pure MSE (two-stage). The possible explanation is that its added penalty
term is not always aligned with regret as discussed in section 4.2. Overall,
Table 1 and Figure 1 indicate the performance of the parirwise difference loss
is steady when the underlying predictive model is consistent with the data
generation process, whereas the listwise loss is robust and reliable across
all problem instances.

Table 2: Impact of $p_{solve}$ on per epoch training time and regret in Energy scheduling instances |  | Pointwise | Pairwise | Pairwise-diff | Listwise
---|---|---|---|---|---
| $p_{solve}$ | Regret | Time (s) | Regret | Time (s) | Regret | Time (s) | Regret | Time (s)
Energy-1 | 100% | 2.12% | 110 | 1.64% | 110 | 1.63% | 110 | 1.72% | 100
10% | 2.51% | 30 | 1.65% | 30 | 1.61% | 30 | 1.67% | 25
Energy-2 | 100% | 2.70% | 130 | 2.05% | 140 | 2.07% | 140 | 1.99% | 120
10% | 2.83% | 40 | 2.08% | 45 | 2.04% | 45 | 1.96% | 40

#### MSE vs Regret tradeoff.

The three problems we consider happen all to be integer linear programming
(ILP) problems. As ILP problems are scale-invariant, the regret can be
minimized even if the predictions are multiples of the actual values. In
Figure 2, we show both MSE and regret of the predictions. In all cases we
observe that the MSE loss of the pointwise loss is very low, comparable to
minimizing MSE. But its regret is even higher than MSE, as seen before. The
pairwise difference loss function has marginally better MSE than listwise and
pairwise losses, showing little added gain from its more MSE-related
formulation.

#### Combined Regression and Ranking Experiment.

The previous experiment reveals that although the performances of the ranking
loss functions are comparable with the state of the art in terms of regret,
their MSE loss remains high. In this experiment we will consider a convex
combination of MSE loss and listwise ranking loss, inspired by (Sculley, 2010)
but formulated as a multi-task problem instead of sampling between the two
losses:

$\alpha L^{l}_{S}(\hat{c},c)+(1-\alpha)\mathbf{mse}(\hat{c},c)$ (18)

The motivation behind this loss function is that we can control $\alpha$ as a
tuning parameter. Clearly, $\alpha=0$ results in MSE loss whereas $\alpha=1$
results in listwise ranking loss. Figure 3 displays the impact $\alpha$ on the
two scheduling instances. As hypothesised, we see MSE goes up and regret goes
down as we increase $\alpha$. This experiment suggests it is possible to
choose a value of $\alpha$ so that we sacrifice regret (problem-specific) to
attain predictions with lower MSE (close to the true values).

#### Impact of $p_{solve}$.

The motivation behind ours (and Mulamba et al. (2021)) approach is reducing
the number of times of the optimization problem is solved during training. In
the next experiment, we show how $p_{solve}$ impacts the model training time.
Lower values of $p_{solve}$ would make the training faster because of two
reasons. Firstly, we have to call the optimization oracle few number of times.
Secondly, the smaller cardinality means ranking loss would be computed on
fewer datapoints.In Table 2 we report percentage regret and per epoch runtime
of the four ranking loss functions for $p_{solve}=10\%\text{ and }100\%$ for
the scheduling instances. We choose this problem because this is most
difficult optimization problem among the three. Table 2 shows that in all
cases, reducing $p_{solve}$ to 10% barely impacts regret for all except
pointwise (which already performs worse). On the other hand, the efficiency
gain in terms of runtime is significant.

##  6 Conclusion

We extend the approach of Mulamba et al. (2021), which introduces surrogate
loss functions for decision-focused learning problems by caching a subset of
feasible solutions. Motivated by their work, we frame the decision-focused
learning problem as a learning to rank problem, where we train models to learn
the partial ordering of the pool of feasible solutions. This generalizes their
approach and inherits its nice properties of separating the solving from the
loss computation. We also attempt to draw connections between the two-stage
MSE loss and regret minimizing ranking losses. This stimulates a further cross
fertilisation of the rich and more mature field of learning to rank with the
relatively recent topic of decision-focused learning.

## Acknowledgements

This research was partially funded by the FWO Flanders project Data-driven
logistics (FWO-S007318N), the ANID-Fondecyt Iniciacion grant no 11220864, the
European Research Council (ERC) under the European Union’s Horizon 2020
research and innovation programme (Grant No. 101002802, CHAT-Opt) and the
Flemish Government under the “Onderzoeksprogramma Artificiele Intelligentie
(AI) Vlaanderen” programme. We are also thankful to the reviewers for their
insightful comments.

## References

  * Amos & Kolter (2017) Amos, B. and Kolter, J. Z.  Optnet: Differentiable optimization as a layer in neural networks.  In _International Conference on Machine Learning_ , pp. 136–145. PMLR, 2017.
  * Burges et al. (2005) Burges, C., Shaked, T., Renshaw, E., Lazier, A., Deeds, M., Hamilton, N., and Hullender, G.  Learning to rank using gradient descent.  In _Proceedings of the 22nd international conference on Machine learning_ , pp. 89–96, 2005.
  * Cao et al. (2007) Cao, Z., Qin, T., Liu, T.-Y., Tsai, M.-F., and Li, H.  Learning to rank: from pairwise approach to listwise approach.  In _Proceedings of the 24th international conference on Machine learning_ , pp. 129–136, 2007.
  * Demirović et al. (2019) Demirović, E., Stuckey, P. J., Bailey, J., Chan, J., Leckie, C., Ramamohanarao, K., and Guns, T.  An investigation into prediction + optimisation for the knapsack problem.  In Rousseau, L.-M. and Stergiou, K. (eds.), _Integration of Constraint Programming, Artificial Intelligence, and Operations Research_ , pp. 241–257, Cham, 2019. Springer International Publishing.  ISBN 978-3-030-19212-9.
  * Elmachtoub & Grigas (2021) Elmachtoub, A. N. and Grigas, P.  Smart “predict, then optimize”.  _Management Science_ , 2021.
  * Ferber et al. (2020) Ferber, A. M., Wilder, B., Dilkina, B., and Tambe, M.  Mipaal: Mixed integer program as a layer.  In _The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020_ , pp. 1504–1511. AAAI Press, 2020.
  * Gent & Walsh (1999) Gent, I. P. and Walsh, T.  Csplib: a benchmark library for constraints.  In _International Conference on Principles and Practice of Constraint Programming_ , pp. 480–481. Springer, 1999.
  * Gutmann & Hyvärinen (2010) Gutmann, M. and Hyvärinen, A.  Noise-contrastive estimation: A new estimation principle for unnormalized statistical models.  In _Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics_ , pp. 297–304, 2010.
  * Ifrim et al. (2012) Ifrim, G., O’Sullivan, B., and Simonis, H.  Properties of energy-price forecasts for scheduling.  In _International Conference on Principles and Practice of Constraint Programming_ , pp. 957–972. Springer, 2012.
  * Joachims (2002) Joachims, T.  Optimizing search engines using clickthrough data.  In _Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, July 23-26, 2002, Edmonton, Alberta, Canada_ , pp. 133–142. ACM, 2002.
  * Karatzoglou et al. (2013) Karatzoglou, A., Baltrunas, L., and Shi, Y.  Learning to rank for recommender systems.  In _Proceedings of the 7th ACM Conference on Recommender Systems_ , pp. 493–494, 2013.
  * Kotary et al. (2021) Kotary, J., Fioretto, F., Hentenryck, P. V., and Wilder, B.  End-to-end constrained optimization learning: A survey.  In _Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence_ , volume 5, pp. 4475–4482, 2021.
  * Kotary et al. (2021) Kotary, J., Fioretto, F., Van Hentenryck, P., and Zhu, Z.  End-to-end learning for fair ranking systems.  _arXiv preprint arXiv:2111.10723_ , 2021.
  * Li et al. (2007) Li, P., Wu, Q., and Burges, C.  Mcrank: Learning to rank using multiple classification and gradient boosting.  _Advances in neural information processing systems_ , 20:897–904, 2007.
  * Liu (2011) Liu, T.-Y.  Learning to rank for information retrieval.  2011\.
  * Mandi & Guns (2020) Mandi, J. and Guns, T.  Interior point solving for lp-based prediction+optimisation.  In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M. F., and Lin, H. (eds.), _Advances in Neural Information Processing Systems_ , volume 33, pp. 7272–7282. Curran Associates, Inc., 2020.
  * Mandi et al. (2020) Mandi, J., Demirović, E., Stuckey, P. J., and Guns, T.  Smart predict-and-optimize for hard combinatorial optimization problems.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 34(02):1603–1610, Apr. 2020.
  * Mulamba et al. (2021) Mulamba, M., Mandi, J., Diligenti, M., Lombardi, M., Bucarey, V., and Guns, T.  Contrastive losses and solution caching for predict-and-optimize.  In Zhou, Z.-H. (ed.), _Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21_ , pp. 2833–2840. International Joint Conferences on Artificial Intelligence Organization, 8 2021.
  * Niepert et al. (2021) Niepert, M., Minervini, P., and Franceschi, L.  Implicit mle: Backpropagating through discrete exponential family distributions.  In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), _Advances in Neural Information Processing Systems_ , volume 34, pp. 14567–14579. Curran Associates, Inc., 2021.
  * Pogancic et al. (2020) Pogancic, M. V., Paulus, A., Musil, V., Martius, G., and Rolinek, M.  Differentiation of blackbox combinatorial solvers.  In _8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020_ , 2020.
  * Sculley (2010) Sculley, D.  Combined regression and ranking.  In _Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , KDD ’10, pp. 979–988. Association for Computing Machinery, 2010.  ISBN 9781450300551.
  * Sen et al. (2008) Sen, P., Namata, G., Bilgic, M., Getoor, L., Galligher, B., and Eliassi-Rad, T.  Collective classification in network data.  _AI Magazine_ , 29(3):93, Sep. 2008.
  * Simonis et al. (1999) Simonis, H., O’Sullivan, B., Mehta, D., Hurley, B., and Cauwer, M. D.  CSPLib problem 059: Energy-cost aware scheduling.  http://www.csplib.org/Problems/prob059, 1999.
  * Wilder et al. (2019) Wilder, B., Dilkina, B., and Tambe, M.  Melding the data-decisions pipeline: Decision-focused learning for combinatorial optimization.  In _The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1, 2019_ , pp. 1658–1665. AAAI Press, 2019\.
  * Xuan & Monperrus (2014) Xuan, J. and Monperrus, M.  Learning to combine multiple ranking metrics for fault localization.  In _2014 IEEE International Conference on Software Maintenance and Evolution_ , pp. 191–200. IEEE, 2014.

##  Appendix A Problem Specification

###  A.1 Shortest Path Problem

In this problem, we consider shortest path problem on $5\times 5$ a grid. The
goal is to go from the southwest corner to the northeast corner, where we can
go towards east or north. We model it as an LP problem.

$\displaystyle\min_{x\geq 0}c^{\top}x$ $\displaystyle Ax=b$

Where $A$ is the incidence matrix. The decision variable $x$ is binary vector
whose entries would be 1 only if corresponding edge is selected for traversal.
$b$ is 25 dimensional vector whose first entry is 1 and last entry is -1 and
rest are 0. The constraint must be satisfied to go from the southwest corner
to the northeast corner. With respect to the (predicted) cost vector
$c\in\mathbb{R}^{|E|}$, the objective is to minimize the cost.

###  A.2 Energy-cost Aware Scheduling

In this problem $J$ is the set of tasks to be scheduled on $M$ number of
machines maintaining resource requirement of $R$ resources. The tasks must be
scheduled over $T$(= 48) set of equal length time periods. Each task $j$ is
specified by its duration $d_{j}$, earliest start time $e_{j}$, latest end
time $l_{j}$, power usage $p_{j}$.$u_{jr}$ is the resource usage of task $j$
for resource $r$ and $c_{mr}$ is the capacity of machine $m$ for resource $r$.
Let $x_{jmt}$ be a binary variable which is 1 only if task $j$ starts at time
$t$ on machine $m$. If $c_{t}$ is the (predicted) energy price at timeslot
$t$, the objective is to minimize the following formulation of total energy
cost. Then the problem can be formulated as the following MILP:

$\displaystyle\min_{x_{jmt}}$ $\displaystyle\sum_{j\in J}\sum_{m\in
M}\sum_{t\in T}x_{jmt}\Big{(}\sum_{t\leq
t^{\prime}<t+d_{j}}p_{j}c_{t^{\prime}}\Big{)}$ subject to
$\displaystyle\sum_{m\in M}\sum_{t\in T}x_{jmt}=1\ ,\forall_{j\in J}$
$\displaystyle x_{jmt}=0\ \ \forall_{j\in J}\forall_{m\in M}\forall_{t<e_{j}}$
$\displaystyle x_{jmt}=0\ \ \forall_{j\in J}\forall_{m\in
M}\forall_{t+d_{j}>l_{j}}$ $\displaystyle\sum_{j\in
J}\sum_{t-d_{j}<t^{\prime}\leq t}x_{jmt^{\prime}}u_{jr}\leq
c_{mr},\forall_{m\in M}\forall_{r\in R}\forall_{t\in T}$

The first constraint ensures each task is scheduled only once. The next
constraints ensure the task scheduling abides by earliest start time and
latest end time constraints. The final constraint is to respect the resource
requirement of the machines.

###  A.3 Diverse Bipartite Matching

We adapt this from Ferber et al. (2020). in this problem 100 nodes
representing scientific publications are split into two sets of 50 nodes
$N_{1}$ and $N_{2}$. A (predicted) reward matrix $c$ indicates the likelihood
that a link between each pair of nodes from $N_{1}$ to $N_{2}$ exists. Finally
a indicator $m_{i,j}$ is $0$ if article $i$ and $j$ share the same subject
field, and $0$ otherwise $\forall i\in N_{1},j\in N_{2}$. Let $p\in[0,1]$ be
the rate of pair sharing their field in a solution and $q\in[0,1]$ the rate of
unrelated pairs, the goal is to match as much nodes in $N_{1}$ with at most
one node in $N_{2}$ by selecting edges which maximizes the sum of rewards
under similarity and diversity constraints. Formally:

$\begin{array}[]{lll}\max_{x}&\sum_{i,j}c_{i,j}x_{i,j}&\\\ \text{ subject to
}&\sum_{j}x_{i,j}\leq 1&\forall i\in N_{1}\\\ &\sum_{i}x_{i,j}\leq 1&\forall
j\in N_{2}\\\ &\sum_{i.j}m_{i,j}x_{i,j}\geq p\sum_{i,j}x_{i,j}&\\\
&\sum_{i.j}(1-m_{i,j})x_{i,j}\geq q\sum_{i,j}x_{i,j}\\\
&x_{i,j}\in\\{0,1\\}&\forall i\in N_{1},j\in N_{2}\\\ \end{array}$

In our experiments, we considered two variations of this problem with $p=q=$
being $25\%$ and $5\%$, respectively named Matching-1 and Matching-2.

(a) Shortest path (Deg= 1)

(b) Shortest path (Deg= 2)

(c) Shortest path (Deg= 4)

(d) Shortest path (Deg= 6)

(e) Shortest path (Deg= 8)

(f) Energy-1

(g) Energy-2

(h) Matching-1

(i) Matching-2

Figure 4: Boxplot

##  Appendix B Hyperparameter Configuration

To reproduce the result reported in this paper use the hyperparameter settings
as described in Table 3.

Table 3: Details of hyperparameters for reproducing the result |  | Shortest Path Problem
---|---|---
|  | Deg-1 | Deg-2 | Deg-4 | Deg-6 | Deg-8
Pointwise | learning rate | 0.8 | 0.8 | 0.8 | 0.8 | 0.8
Pairwise | learning rate | 0.1 | 0.1 | 0.1 | 0.1 | 0.1
margin | 1.0 | 0.1 | 0.1 | 0.1 | 0.1
Listwise | learning rate | 0.1 | 0.1 | 0.1 | 0.1 | 0.1
temperature | 1.0 | 0.1 | 0.05 | 0.05 | 0.05
Pairwise-difference | learning rate | 0.1 | 0.1 | 0.1 | 0.5 | 0.5
NCE | learning rate | 0.5 | 0.5 | 0.5 | 0.5 | 0.5
MAP | learning rate | 0.05 | 0.05 | 0.05 | 0.7 | 0.7
SPO | learning rate | 0.1 | 0.5 | 0.5 | 0.5 | 0.1
Blackbox | learning rate | 0.5 | 0.5 | 0.5 | 0.5 | 0.5
displace parameter | 1. | 1. | 1. | 1. | 1.
Twostage | learning rate | 0.5 | 0.5 | 0.1 | 0.5 | 0.5
|  | Energy Scheduling |  | Bipartite Matching
|  | Energy-1 | Energy-2 |  | Matching-1 | Matching-2
Pointwise | learning rate | 0.9 | 0.5 |  | 0.01 | 0.01
Pairwise | learning rate | 0.1 | 0.1 |  | 0.001 | 0.01
margin | 100 | 100 |  | 0.2 | 1.0
Listwise | learning rate | 0.1 | 0.1 |  | 0.005 | 0.01
temperature | 1.0 | 1.0 |  | 0.01 | 1.0
Pairwise-difference | learning rate | 0.5 | 0.5 |  | 0.01 | 0.01
NCE | learning rate | 0.5 | 0.5 |  | 0.001 | 0.01
MAP | learning rate | 0.5 | 0.5 |  | 0.001 | 0.01
SPO | learning rate | 0.9 | 0.9 |  | 0.01 | 0.01
Blackbox | learning rate | 0.1 | 0.1 |  | 0.01 | 0.01
displace parameter | 0.001 | 0.1 |  | $10^{-5}$ | 0.001
Twostage | learning rate | 0.7 | 0.7 |  | 0.01 | 0.01

##  Appendix C Distribution of the regret of the predictions

In Table 1, we report only the average regret of all the instances over 10
independent trails. In Figure fig:boxplot, we show the distributions of the
regret across all the test instances with box-plots for the three problems.