# Proper losses regret at least $1/2$-order

Han Bao<EMAIL_ADDRESS>
Kyoto University Asuka Takatsu<EMAIL_ADDRESS>
Tokyo Metropolitan University

###### Abstract

A fundamental challenge in machine learning is the choice of a loss as it
characterizes our learning task, is minimized in the training phase, and
serves as an evaluation criterion for estimators. Proper losses are commonly
chosen, ensuring minimizers of the full risk match the true probability
vector. Estimators induced from a proper loss are widely used to construct
forecasters for downstream tasks such as classification and ranking. In this
procedure, how does the forecaster based on the obtained estimator perform
well under a given downstream task? This question is substantially relevant to
the behavior of the $p$-norm between the estimated and true probability
vectors when the estimator is updated. In the proper loss framework, the
suboptimality of the estimated probability vector from the true probability
vector is measured by a surrogate regret. First, we analyze a surrogate regret
and show that the _strict_ properness of a loss is necessary and sufficient to
establish a non-vacuous surrogate regret bound. Second, we solve an important
open question that the order of convergence in $p$-norm cannot be faster than
the $1/2$-order of surrogate regrets for a broad class of strictly proper
losses. This implies that strongly proper losses entail the optimal
convergence rate.

Keywords: loss functions, proper scoring rules, supervised learning, surrogate
regret bounds, convex analysis

##  1 Introduction

_Proper losses_ , also known as proper scoring rules, are measurements of the
quality of a probabilistic prediction given a true probability vector [BSS05,
GR07, RW10]. Intuitively, we say a loss is proper if the target probability
vector is its minimizer, and strictly proper if the minimizer is unique, which
is a basic property for a reasonable loss. Proper losses are prevailing in
modern machine learning: for example, the cross-entropy loss popular in deep
learning essentially corresponds to the log loss (or logarithmic score), and
the Brier score is used for assessing model uncertainties [OFR+19]. As such,
probabilistic estimators are obtained via proper loss minimization. It is
common to post-process a minimizer of a proper loss for downstream tasks, such
as classification (by choosing the most likely label), ranking (by giving
ranking scores to each label [NA13]), F-measure optimization (by thresholding
the estimated probability [KNRD14]), and probability calibration [KSFF17,
BGHN23]. Here, we are interested in the predictive performance of post-
processed estimators in downstream tasks. Given a true and estimated
probability vectors $\mathbf{q}$ and $\widehat{\mathbf{q}}$, respectively, the
_surrogate regret_ $R(\mathbf{q},\widehat{\mathbf{q}})$ (introduced in Section
3) measures the suboptimality of $\widehat{\mathbf{q}}$ from $\mathbf{q}$ in
terms of a proper loss. Can we relate the suboptimality of a forecaster for a
downstream task to the surrogate regret?

Surrogate regret bounds relate the surrogate regret to the performance for
downstream tasks, and have been derived for binary classification [Zha04,
RW09], bipartite ranking [Aga14], property elicitation [AA15], F-measure
optimization [KD16, ZRA20], and learning with noisy labels [ZLA21],
independently. Recently, a unified surrogate regret bound across different
downstream tasks has been established [Bao23], where surrogate regret bounds
are unified in terms of the $1$-norm. This is based on the observation that
the suboptimality of the aforementioned downstream tasks can be controlled by
the $1$-norm. However, the derived bound has been limited to the binary
classification case, and it remains unclear when the surrogate regret bound is
non-vacuous. A reasonable loss should entail a non-vacuous regret bound, which
is crucial to tackling numerous downstream tasks simultaneously. Moreover, an
important conjecture that the convergence rate of surrogate regret bounds
cannot be faster than the $1/2$-order has yet to be solved. This conjecture
has a significant role in the choice of losses because the lower bound of the
order of convergence contributes to delineating the optimality of a given
proper loss.

In this article, we aim to study when the surrogate regret bounds are non-
vacuous and how fast the order of convergence in the $p$-norm can be. To this
end, we analyze the $p$-norm bounds by the surrogate regret
$R(\mathbf{q},\widehat{\mathbf{q}})$ jointly with a rate function $\psi$ in
the following form by extending from the binary classification case [Bao23] to
the multiclass classification case:

$\|\mathbf{q}-\widehat{\mathbf{q}}\|_{p}\leq\psi(R(\mathbf{q},\widehat{\mathbf{q}})).$
(1)

After formalizing these notions in Section 3, we derive the surrogate regret
bounds in Section 4. To derive bounds of the form (1), we introduce the
_moduli of convexity_ [Fig76], which describe the information of its second
derivative of convex functions, for convex functions defined on the
probability simplex. The rate $\psi$ in (1) can be characterized by the
modulus of a Bregman generator function associated with a proper loss
$\bm{\ell}$ (Theorem 11). To obtain a non-vacuous bound, we first show that
the strict properness of a loss is necessary and sufficient to obtain a non-
vacuous surrogate regret bound, or strictly increasing $\psi$, to put it
differently (Theorem 9). Whereas it has been known that non-strictly proper
losses can achieve non-vacuous bounds for classification [RW11, Corollary 27],
our sufficiency result argues that the strict properness is a minimal
requirement for an estimate to be non-vacuous in terms of the $p$-norm. As our
second main result, we provide an affirmative answer to the above conjecture:
the optimal rate $\psi(\rho)$ as $\rho\downarrow 0$ is $O(\rho^{1/2})$, for a
broad class of proper losses (Theorem 17). This convergence rate has already
been known for a restricted class of proper losses, known as strongly proper
losses [Aga14]. Hence, our result ensures the asymptotic optimality of
strongly proper losses. This gives an answer to the question, “Do we have an
interesting loss that is strictly proper but not strongly proper?” [Bao22,
§6.2.9]: there is no better proper loss outside of strongly proper losses, as
long as we are concerned with the asymptotic rate of $\psi$ in Eq. 1.

###  1.1 Organization and contributions of this article

The organization of this article and our contributions are summarized as
follows.

  * •

Section 2: Notation and necessary backgrounds on convex analysis are
summarized.

  * •

Section 3: Proper losses for multiclass classification are introduced. Lemma 2
characterizes the existence of minimizers for general losses, and Proposition
5 gives a self-contained and rigorous proof of the well-known representation
of proper losses [Sav71].

  * •

Section 4: Theorem 11 extends surrogate regret bounds for binary
classification [Bao23] to multiclass classification. This is achieved by
extending the moduli of convexity to multivariate functions (Definition 8).
Theorem 9 is our first result, proving that the strict properness of a loss is
a necessary and sufficient condition for an associated surrogate regret bound
to be non-vacuous.

Then, the benefits of Theorem 11 are discussed in Section 4.3. In particular,
we can obtain the $p$-norm bound in the form of (1), which can be used to
control the performance of plug-in forecasters for downstream tasks such as
multiclass classification, learning with noisy labels, and bipartite ranking.

  * •

Section 5: We evaluate the rate $\psi(\rho)$ by power functions such as
$\rho^{1/s}\lesssim\psi(\rho)\lesssim\rho^{1/S}$ for some constants
$s,S>0$,111In our notation, $\psi_{1}\lesssim\psi_{2}$ indicates the existence
of an absolute constant $C>0$ such that $C\psi_{1}\leq\psi_{2}$. which is
based on the Simonenko order function previously adopted [Bao23]. Our second
main result roughly shows that $s\geq 2$ (Theorem 17), establishing the
asymptotic optimality $\psi(\rho)\gtrsim\rho^{1/2}$ of strongly proper losses.

  * •

Section 6: Several examples of convex functions to generate proper losses are
discussed.

##  2 Background

In this section, we summarize the notation and basic properties of convex
functions.

###  2.1 Notation

Throughout this article, fix $N\in\mathbb{N}$ and $p\in[1,\infty]$. The
Kronecker delta is denoted by $\delta_{ij}$. For $k\in\mathbb{N}$, we set
$[k]\coloneqq\left\\{{1,2,\dots,k}\right\\}$. A vector is denoted by bold-face
such as $\bm{\xi}\in\mathbb{R}^{N}$, and its $n$-th (scalar) component is
written as non-bold $\xi_{n}$ for each $n\in[N]$. The $p$-norm of
$\bm{\xi}\in\mathbb{R}^{N}$ is denoted by $\|\bm{\xi}\|_{p}$. For a topology
on $\mathbb{R}^{N}$, we refer to one induced from the $2$-norm, but it makes
no difference whichever norm we choose. Similarly, a convexity of a function
on $(\mathbb{R}^{N},\|\cdot\|_{p})$ is determined independently of the choice
of $p$. The standard inner product on $\mathbb{R}^{N}$ is denoted by
$\left\langle{\bm{\xi}},{\bm{\xi}^{\prime}}\right\rangle\coloneqq\sum_{n\in[N]}\xi_{n}\xi_{n}^{\prime}$.
We introduce the notation

$\displaystyle\triangle^{N}\coloneqq\left\\{{\mathbf{q}\in\mathbb{R}^{N}}\mathrel{}\middle|\mathrel{}{q_{n}\geq
0\ (n\in[N]),\
\left\langle{\mathbf{q}},{\mathbf{1}}\right\rangle=1}\right\\},\quad\triangle^{N}_{+}\coloneqq\left\\{{\mathbf{q}\in\triangle^{N}}\mathrel{}\middle|\mathrel{}{q_{n}>0\
(n\in[N])}\right\\},$

where $\mathbf{1}\in\mathbb{R}^{N}$ is the vector with each component being
one. For $\mathbf{q}\in\triangle^{N}$, we denote by
$\operatorname{\mathrm{supp}}(\mathbf{q})$ the _support_ of $\mathbf{q}$, that
is,

$\operatorname{\mathrm{supp}}(\mathbf{q})\coloneqq\left\\{{n\in[N]}\mathrel{}\middle|\mathrel{}{q_{n}>0}\right\\}.$

We adhere to the convention that

$\pm\infty\leq\pm\infty,\quad a\pm\infty=\pm\infty,\quad
b\cdot(\pm\infty)=\pm\infty,\quad-b\cdot(\pm\infty)=\mp\infty,\quad
0\cdot(\pm\infty)=0,$

for $a\in\mathbb{R}$ and $b>0$. We use $O$ and $\Omega$ to always denote the
_infinitesimal_ asymptotic order. To be precise, for two functions $\phi,\psi$
defined around $0$, $\phi(\varepsilon)=\Omega(\psi(\varepsilon))$ as
$\varepsilon\downarrow 0$ should be understood as

$\liminf_{\varepsilon\downarrow
0}\left|\frac{\phi(\varepsilon)}{\psi(\varepsilon)}\right|>0.$

###  2.2 Convex analysis

In this subsection, let $f:\mathbb{R}^{N}\to(-\infty,\infty]$ denote a proper
convex function on $\mathbb{R}^{N}$. Its _effective domain_ is defined by

$\operatorname{\mathrm{dom}}{f}\coloneqq\left\\{{\bm{\xi}\in\mathbb{R}^{N}}\mathrel{}\middle|\mathrel{}{f(\bm{\xi})<\infty}\right\\}.$

A vector $\mathbf{v}\in\mathbb{R}^{N}$ is called a _subgradient_ of $f$ at
$\bm{\xi}^{0}\in\mathbb{R}^{N}$ if

$f(\bm{\xi})\geq
f(\bm{\xi}^{0})+\left\langle{\smash{\mathbf{v}}},{\bm{\xi}-\smash{\bm{\xi}^{0}}}\right\rangle\quad\text{for
all $\bm{\xi}\in\mathbb{R}^{N}$.}$ (2)

We say that $f$ is _subdifferentiable_ at $\bm{\xi}^{0}$ if there exists a
subgradient of $f$ at $\bm{\xi}^{0}$. For
$\bm{\xi}^{0}\in\operatorname{\mathrm{dom}}{f}$,

$f^{\prime}(\bm{\xi}^{0};\bm{\xi})\coloneqq\lim_{\varepsilon\downarrow
0}\frac{f((1-\varepsilon)\bm{\xi}^{0}+\varepsilon\bm{\xi})-f(\bm{\xi}^{0})}{\varepsilon}\quad\text{for
all $\bm{\xi}\in\mathbb{R}^{N}$}$

always exists in $[-\infty,\infty)$ and $\mathbf{v}\in\mathbb{R}^{N}$ is a
subgradient of $f$ at $\bm{\xi}^{0}$ if and only if

$f^{\prime}(\bm{\xi}^{0};\bm{\xi})\geq\left\langle{\mathbf{v}},{\bm{\xi}}\right\rangle\quad\text{for
all $\bm{\xi}\in\mathbb{R}^{N}$}$ (3)

holds [Roc70, Theorem 23.2].

Assume $\triangle^{N}\subseteq\operatorname{\mathrm{dom}}{f}$. Then, $f$ is
subdifferentiable at $\mathbf{q}^{0}\in\triangle^{N}_{+}$ [Roc70, Theorem
23.4]. Moreover, if there is no subgradient of $f$ at
$\mathbf{q}^{0}\in\triangle^{N}\setminus\triangle^{N}_{+}$, then

$f^{\prime}(\mathbf{q}^{0};\mathbf{q})=-\infty\quad\text{for all
$\mathbf{q}\in\triangle^{N}_{+}$}$

holds [Roc70, Theorem 23.3]. From the observation, we define $\partial
f(\mathbf{q}^{0})$ for $\mathbf{q}^{0}\in\triangle^{N}$ as the set consisting
of all subgradients of $f$ at $\mathbf{q}^{0}$ if $f$ is subdifferentiable at
$\mathbf{q}^{0}$, and otherwise

$\displaystyle\partial
f(\mathbf{q}^{0})\coloneqq\left\\{{\mathbf{v}\in[-\infty,\infty)^{N}}\mathrel{}\middle|\mathrel{}{\begin{tabular}[]{l}$\mathbf{v}_{n}\in\mathbb{R}$
for $n\in\operatorname{\mathrm{supp}}(\mathbf{q}^{0})$ and
$\mathbf{v}_{n}=-\infty$ for
$n\notin\operatorname{\mathrm{supp}}(\mathbf{q}^{0})$\\\ such that
$f(\mathbf{q})\geq
f(\mathbf{q}^{0})+\left\langle{\mathbf{v}},{\mathbf{q}-\smash{\mathbf{q}^{0}}}\right\rangle$
holds for all $\mathbf{q}\in\triangle^{N}$\end{tabular}\\!\\!}\right\\}.$

Note that the notion of $\partial f(\mathbf{q}^{0})$ differs from the usual
one. We adopt this definition to accommodate regular losses (Definition 4)
later. We call a map $\partial{f}:\triangle^{N}\to 2^{[-\infty,\infty)^{N}}$
the _subdifferential_ of $f$. Let us denote an arbitrary _selector_ of
$\partial f(\mathbf{q})$ by $\nabla f$, that is, a map assigning to each point
$\mathbf{q}\in\triangle^{N}$ an element in $\partial f(\mathbf{q})$. Since
$\partial{f}(\mathbf{q}^{0})$ consists of the gradient of $f$ at
$\mathbf{q}^{0}$ if $f$ is differentiable at $\mathbf{q}^{0}$, it is
consistent to use the notation $\nabla f$ for a selector. For
$\mathbf{q},\mathbf{q}^{0}\in\triangle^{N}$, the associated _Bregman
divergence_ of $\mathbf{q}$ given $\mathbf{q}^{0}$ is defined by

$B_{(f,\nabla f)}(\mathbf{q}\|\mathbf{q}^{0})\coloneqq
f(\mathbf{q})-f(\mathbf{q}^{0})-\left\langle{\nabla
f(\mathbf{q}^{0})},{\mathbf{q}-\mathbf{q}^{0}}\right\rangle\in[0,\infty].$

We verify that the inequality (3) holds for $\mathbf{q}^{0}\in\triangle^{N}$
and $\mathbf{v}\in\partial f(\mathbf{q}^{0})$.

###### Lemma 1

Let $f:\mathbb{R}^{N}\to(-\infty,\infty]$ be a proper convex function such
that $\triangle^{N}\subseteq\operatorname{\mathrm{dom}}{f}$. For
$\mathbf{q}^{0}\in\triangle^{N}$, the set $\partial f(\mathbf{q}^{0})$ is
nonempty and $\mathbf{v}\in\partial f(\mathbf{q}^{0})$ satisfies
$f^{\prime}(\mathbf{q}^{0};\mathbf{q})\geq\left\langle{\mathbf{v}},{\mathbf{q}}\right\rangle$
for $\mathbf{q}\in\triangle^{N}$.

Proof  Fix $\mathbf{q}^{0}\in\triangle^{N}$. Since the claim trivially holds
true if $f$ is subdifferentiable at $\mathbf{q}^{0}$, we assume that $f$ is
not subdifferentiable at $\mathbf{q}^{0}$. Since $f$ is subdifferentiable at
$\mathbf{q}^{0}\in\triangle^{N}_{+}$ [Roc70, Theorem 23.4],
$I\coloneqq|\operatorname{\mathrm{supp}}(\mathbf{q}^{0})|$ satisfies $1\leq
I\leq N-1$. For $\bm{\eta}\in\mathbb{R}^{I}$, define
$\bm{\xi}^{\bm{\eta}}\in\mathbb{R}^{N}$ by

$\xi^{\bm{\eta}}_{n}\coloneqq\begin{cases}\eta_{n}&\text{if
}n\in\operatorname{\mathrm{supp}}(\mathbf{q}^{0}),\\\ 0&\text{if
}n\notin\operatorname{\mathrm{supp}}(\mathbf{q}^{0}),\end{cases}$

and define a function $f_{I}:\mathbb{R}^{I}\to(-\infty,\infty]^{N}$ by

$f_{I}(\bm{\eta})\coloneqq f(\bm{\xi}^{\bm{\eta}})\quad\text{for
}\bm{\eta}\in\mathbb{R}^{I}.$

Then, $f_{I}$ is a proper convex function on $\mathbb{R}^{I}$ such that
$\triangle^{I}\subseteq\operatorname{\mathrm{dom}}{f}_{I}$, consequently,
$f_{I}$ is subdifferentiable at $\widehat{\bm{\eta}}\in\triangle^{I}_{+}$
[Roc70, Theorem 23.4]. For $\mathbf{q}\in\triangle^{N}$, define
$\bm{\eta}^{\mathbf{q}}\in\mathbb{R}^{I}$ by $\eta^{\mathbf{q}}_{n}=q_{n}$ for
$n\in\operatorname{\mathrm{supp}}(\mathbf{q}^{0})$. Then, for
$\mathbf{q}\in\triangle^{N}$ with
$\operatorname{\mathrm{supp}}(\mathbf{q})\subseteq\operatorname{\mathrm{supp}}(\mathbf{q}^{0})$,
we have $\bm{\eta}^{\mathbf{q}}\in\triangle^{I}$ and
$f_{I}(\bm{\eta}^{\mathbf{q}})=f(\mathbf{q})$. Moreover, if
$\mathbf{q}\in\triangle^{N}$ satisfies
$\operatorname{\mathrm{supp}}(\mathbf{q})=\operatorname{\mathrm{supp}}(\mathbf{q}^{0})$,
then $\bm{\eta}^{\mathbf{q}}\in\triangle_{+}^{I}$ and hence $\partial
f_{I}(\bm{\eta}^{\mathbf{q}})\neq\emptyset$. Choose $\mathbf{w}\in\partial
f_{I}(\bm{\eta}^{\mathbf{q}^{0}})$ and define
$\mathbf{v}\in[-\infty,\infty)^{N}$ by

${v}_{n}\coloneqq\begin{cases}{w}_{n}&\text{if
}n\in\operatorname{\mathrm{supp}}(\mathbf{q}^{0}),\\\ -\infty&\text{if
}n\notin\operatorname{\mathrm{supp}}(\mathbf{q}^{0}).\end{cases}$

From now on, we show that $\mathbf{v}\in\partial f(\mathbf{q}^{0})$. For
$\mathbf{q}\in\triangle^{N}$, if $q_{n}>0$ holds for some
$n\notin\operatorname{\mathrm{supp}}(\mathbf{q}^{0})$, then
$\left\langle{\mathbf{v}},{\mathbf{q}-\mathbf{q}^{0}}\right\rangle=-\infty$
and (2) holds. On the other hand, if $q_{n}=0$ for all
$n\notin\operatorname{\mathrm{supp}}(\mathbf{q}^{0})$, then
$\mathbf{q}\in\triangle^{N}$ with
$\operatorname{\mathrm{supp}}(\mathbf{q})\subseteq\operatorname{\mathrm{supp}}(\mathbf{q}^{0})$
and

$f(\mathbf{q})=f_{I}(\bm{\eta}^{\mathbf{q}})\geq
f_{I}\Big{(}\bm{\eta}^{\mathbf{q}^{0}}\Big{)}+\left\langle{\mathbf{w}},{\bm{\eta}^{\mathbf{q}}-\bm{\eta}^{\mathbf{q}^{0}}}\right\rangle=f(\mathbf{q}^{0})+\left\langle{\mathbf{v}},{\mathbf{q}-\mathbf{q}^{0}}\right\rangle,$

that is, (2) holds for $\mathbf{q}\in\triangle^{N}$. Thus,
$\mathbf{v}\in\partial f(\mathbf{q}^{0})$ follows. Moreover, the above
inequality immediately yields
$f^{\prime}(\mathbf{q}^{0};\mathbf{q})\geq\left\langle{\mathbf{v}},{\mathbf{q}}\right\rangle$.
This completes the proof of the lemma.

##  3 Classification, proper losses, and Savage representation

After introducing the learning problem of multiclass classification, we
discuss losses and their properties. We review the notion of proper losses and
its connection to Bregman divergences. Although this connection is already
known, we formalize it rigorously. In particular, we verify the existence of
minimizers of the conditional risk and its measurable selection (Lemma 2),
which have been implicitly used in previous literature without any proof.

###  3.1 Multiclass classification

We regard a Radon space $\mathcal{X}$ as an input space, that is, the set of
possible observations, and $\mathcal{Y}\coloneqq[N]$ as a set of labels. The
set $\triangle^{N}$ is identified as the set of all probability measures on
$\mathcal{Y}$. We fix a probability measure $\nu$ on
$\mathcal{X}\times\mathcal{Y}$ and denote by $\nu_{\mathcal{X}}$ the marginal
of $\nu$ on $\mathcal{X}$, that is,
$\nu(\mathcal{B}\times\mathcal{Y})=\nu_{\mathcal{X}}(\mathcal{B})$ holds for
any measurable set $\mathcal{B}\subseteq\mathcal{X}$. Then, by the
disintegration theorem [DM78, Chapter III-70 and 72], there exists a Borel map
$\mathbf{q}^{\bullet}:\mathcal{X}\to\triangle^{N}$, uniquely defined
$\nu_{\mathcal{X}}$-a.e., such that

$\nu(\mathcal{B}\times\left\\{{y}\right\\})=\int_{\mathcal{B}}q^{\mathbf{x}}_{y}\mathrm{d}\nu_{\mathcal{X}}(\mathbf{x})\quad\text{for
a measurable set }\mathcal{B}\subseteq\mathcal{X}\text{ and }y\in\mathcal{Y}.$

We deem $\mathbf{q}^{\mathbf{x}}\in\triangle^{N}$ a true probability vector at
the input $\mathbf{x}$ induced from $\nu$. Multiclass classification is a task
to learn a forecaster to predict the most likely label

$y^{\mathbf{x}}\in\operatorname*{arg\,max}_{y\in\mathcal{Y}}q^{\mathbf{x}}_{y}\quad\text{for
each $\mathbf{x}\in\mathcal{X}$.}$

###  3.2 Proper losses

We continue to use the notation in the previous subsection. To elicit
$\mathbf{q}^{\bullet}$, we use a _loss_ $\bm{\ell}$, which is a Borel map from
$\triangle^{N}$ to $\mathbb{R}^{N}$. Define the associated _full risk_ by

$\mathbb{L}[\widehat{\mathbf{q}}^{\bullet}]\coloneqq\int_{\mathcal{X}\times\mathcal{Y}}\ell_{y}(\widehat{\mathbf{q}}^{\mathbf{x}})\mathrm{d}\nu(\mathbf{x},y)\quad\text{for
a Borel map~{}}\widehat{\mathbf{q}}^{\bullet}:\mathcal{X}\to\triangle^{N}.$

A minimizer of $\mathbb{L}$ among Borel maps
$\widehat{\mathbf{q}}^{\bullet}:\mathcal{X}\to\triangle^{N}$ is called an
_estimator_ of $\mathbf{q}^{\bullet}$. The choice of $\bm{\ell}$ directly
affects the quality of an estimator. It is more intuitive to work on the
conditional counterpart of the full risk instead. Let
$\mathbf{q},\widehat{\mathbf{q}}\in\triangle^{N}$. For a loss $\bm{\ell}$, the
associated _conditional risk_ of $\widehat{\mathbf{q}}$ given $\mathbf{q}$ and
_conditional Bayes risk_ of $\mathbf{q}$ are defined by

$L(\mathbf{q},\widehat{\mathbf{q}})\coloneqq\sum_{y\in\mathcal{Y}}q_{y}\ell_{y}(\widehat{\mathbf{q}})\quad\text{and}\quad\underline{L}(\mathbf{q})\coloneqq\inf_{\widehat{\mathbf{q}}\in\triangle^{N}}L(\mathbf{q},\widehat{\mathbf{q}}),$

respectively. Here, we regard $\mathbf{q}$ as a _true_ probability vector and
$\widehat{\mathbf{q}}$ as an _estimate_. The full risk is rewritten as

$\mathbb{L}[\widehat{\mathbf{q}}^{\bullet}]=\int_{\mathcal{X}}L(\mathbf{q}^{\mathbf{x}},\widehat{\mathbf{q}}^{\mathbf{x}})\mathrm{d}\nu_{\mathcal{X}}(\mathbf{x}).$

Since the infimum of a family of linear functions is concave, $\underline{L}$
is concave on $\triangle^{N}$, consequently
$\underline{L}\circ\widehat{\mathbf{q}}^{\bullet}:\mathcal{X}\to[-\infty,\infty)$
is measurable on $\mathcal{X}$, which in turn shows

$\mathbb{L}[\widehat{\mathbf{q}}^{\bullet}]\geq\int_{\mathcal{X}}\underline{L}(\mathbf{q}^{\mathbf{x}})\mathrm{d}\nu_{\mathcal{X}}(\mathbf{x}).$

Thus, the minimization problem of the full risk is reduced to that of the
conditional risk if the map $\mathcal{M}:\triangle^{N}\to 2^{\triangle^{N}}$
defined by

$\mathcal{M}(\mathbf{q})\coloneqq\operatorname*{arg\,min}_{\widehat{\mathbf{q}}\in\triangle^{N}}L(\mathbf{q},\widehat{\mathbf{q}})\quad\text{for
$\mathbf{q}\in\triangle^{N}$.}$

has a Borel selector. Note that $\mathcal{M}(\mathbf{q})=\emptyset$ may
happen.

###### Lemma 2

Suppose $\bm{\ell}:\triangle^{N}\to\mathbb{R}^{N}$ is lower semi-continuous.
Then, we have that $\underline{L}(\mathbf{q})>-\infty$ and
$\mathcal{M}(\mathbf{q})$ is nonempty and closed for
$\mathbf{q}\in\triangle^{N}$. Moreover, if $\bm{\ell}$ is continuous, then
there exists a Borel selector of $\mathcal{M}$.

Proof  Since the first assertion, $\mathcal{M}(\mathbf{q})$ is nonempty and
closed for $\mathbf{q}\in\triangle^{N}$, follows from the standard argument,
we omit its proof.

Assume the continuity of $\bm{\ell}$ and we show the existence of a Borel
selector of $\mathcal{M}$. Note that the continuity of $\ell$ guarantees the
continuity of $L(\mathbf{q},\cdot)$ on $\triangle^{N}$ for each
$\mathbf{q}\in\triangle^{N}$. By the Kuratowski and Ryll-Nardzewski measurable
selection theorem [KRN65, Main Theorem & Corollary 1], it is enough to show
that

$\mathcal{B}_{\mathcal{K}}\coloneqq\left\\{{\mathbf{q}\in\triangle^{N}}\mathrel{}\middle|\mathrel{}{\mathcal{M}(\mathbf{q})\cap\mathcal{K}\neq\emptyset}\right\\}$

is Borel for any compact set $\mathcal{K}$ in $\mathbb{R}^{N}$ with
$\triangle^{N}\cap\mathcal{K}\neq\emptyset$.

Fix a compact set $\mathcal{K}$ in $\mathbb{R}^{N}$ with
$\triangle^{N}\cap\mathcal{K}\neq\emptyset$. Since
$\triangle^{N}\cap\mathcal{K}$ is separable, there exists a dense countable
set $\left\\{{\mathbf{q}^{j}}\right\\}_{j\in\mathbb{N}}$ in
$\triangle^{N}\cap\mathcal{K}$. For each $j\in\mathbb{N}$, define
$d_{j}:\triangle^{N}\to\mathbb{R}$ by

$d_{j}(\mathbf{q})\coloneqq
L(\mathbf{q},\mathbf{q}^{j})-\inf_{\widehat{\mathbf{q}}\in\triangle^{N}}L(\mathbf{q},\widehat{\mathbf{q}})\quad\text{for
}\mathbf{q}\in\triangle^{N},$

which is lower semi-continuous, in particular, Borel on $\triangle^{N}$. Then,

$\mathcal{B}\coloneqq\bigcap_{m\in\mathbb{N}}\bigcup_{j\in\mathbb{N}}d_{j}^{-1}([0,m^{-1}))$

is Borel. We will show $\mathcal{B}=\mathcal{B}_{\mathcal{K}}$. For
$\mathbf{q}\in\mathcal{B}_{\mathcal{K}}$, there exists
$\widehat{\mathbf{q}}\in\mathcal{M}(\mathbf{q})\cap\mathcal{K}$. By the
continuity of $L(\mathbf{q},\cdot)$ on $\triangle^{N}$, for each
$m\in\mathbb{N}$, there exists $\delta_{m}>0$ such that if
$\mathbf{q}^{\prime}\in\triangle^{N}$ satisfies
$\|\mathbf{q}^{\prime}-\widehat{\mathbf{q}}\|_{2}<\delta_{m}$, then $0\leq
L(\mathbf{q},\mathbf{q}^{\prime})-L(\mathbf{q},\widehat{\mathbf{q}})<m^{-1}$.
By the density of $\left\\{{\mathbf{q}^{j}}\right\\}_{j\in\mathbb{N}}$, there
exists $j_{m}\in\mathbb{N}$ such that
$\|\mathbf{q}^{j_{m}}-\widehat{\mathbf{q}}\|_{2}<\delta_{m}$ and hence

$d_{j_{m}}(\mathbf{q})=L(\mathbf{q},\mathbf{q}^{j_{m}})-L(\mathbf{q},\widehat{\mathbf{q}})\in[0,m^{-1}),$

which in turn implies $\mathbf{q}\in\mathcal{B}$. Conversely, for
$\mathbf{q}\in\mathcal{B}$ and $m\in\mathbb{N}$, there exists
$j_{m}\in\mathbb{N}$ such that

$L(\mathbf{q},\mathbf{q}^{j_{m}})<\inf_{\widehat{\mathbf{q}}\in\triangle^{N}}L(\mathbf{q},\widehat{\mathbf{q}})+m^{-1}.$

We extract a convergent subsequence of $(\mathbf{q}^{j_{m}})_{m\in\mathbb{N}}$
(not relabeled) with limit
$\widehat{\mathbf{q}}\in\triangle^{N}\cap\mathcal{K}$. The continuity of
$L(\mathbf{q},\cdot)$ gives

$L(\mathbf{q},\widehat{\mathbf{q}})=\lim_{m\to\infty}L(\mathbf{q},\mathbf{q}^{j_{m}})\leq\inf_{\widehat{\mathbf{q}}^{\prime}\in\triangle^{N}}L(\mathbf{q},\widehat{\mathbf{q}}^{\prime}),$

proving $\widehat{\mathbf{q}}\in\mathcal{M}(\mathbf{q})$ hence
$\mathbf{q}\in\mathcal{B}_{\mathcal{K}}$. This completes the proof of the
lemma.

Although this fact is not directly relevant to our main topic, we complement
it in this article because we are unaware of any previous literature
formalizing it for losses defined on $\triangle^{N}$. For a different type of
(margin-based) losses, the existence of a measurable full risk minimizer has
been studied [Ste07, Theorem 3.2 (ii)].

Since $\mathcal{M}(\mathbf{q})$ is ideally a singleton of $\mathbf{q}$, we
consider such a class of losses.

######  Definition 3 (Proper losses)

A loss $\bm{\ell}:\triangle^{N}\to\mathbb{R}^{N}$ is _proper_ if
$\mathbf{q}\in\mathcal{M}(\mathbf{q})$ holds for each
$\mathbf{q}\in\triangle^{N}$. We say $\bm{\ell}$ is _strictly proper_ if
$\mathcal{M}(\mathbf{q})=\left\\{{\mathbf{q}}\right\\}$ holds for each
$\mathbf{q}\in\triangle^{N}$.

For a proper loss $\bm{\ell}$, the conditional risk is minimized at the true
probability vector, and the identity map on $\triangle^{N}$ becomes a Borel
selector of $\mathcal{M}$. In this case, it follows that
$\underline{L}(\mathbf{q})=L(\mathbf{q},\mathbf{q})$ for
$\mathbf{q}\in\triangle^{N}$.

###  3.3 Savage representation

The range of a loss can be extended from $\mathbb{R}^{N}$ to
$(-\infty,\infty]^{N}$. This extension is necessary to accommodate some
losses, including the log loss $\ell_{y}(\mathbf{q})\coloneqq-\ln q_{y}$ (for
each $y\in\mathcal{Y}$) into proper losses. We will see that a proper loss
induces a Bregman divergence under the regularity.

######  Definition 4 (Regular losses [GR07, Definition 1])

A loss $\bm{\ell}:\triangle^{N}\to(-\infty,\infty]^{N}$ is said to be
_regular_ if $\ell_{y}(\mathbf{q})=\infty$ happens only for
$y\notin\operatorname{\mathrm{supp}}(\mathbf{q})$.

In what follows, we consider a regular loss $\bm{\ell}$, where its range is
$(-\infty,\infty]^{N}$.

Although the following property has been well known in literature [Sav71, §4]
[GR07, Theorem 2] [WVR16, Proposition 7], we provide its rigorous proof to
handle the regularity and subdifferentials carefully.

######  Proposition 5 (Savage representation [§]4)

Savage:1971] Let $\bm{\ell}$ be regular. Then, $\bm{\ell}$ is proper (resp.
strictly proper) if and only if there exists a proper convex (resp. strictly
convex) function $f$ on $\mathbb{R}^{N}$ such that
$\operatorname{\mathrm{dom}}f=\triangle^{N}$ and, for all
$\widehat{\mathbf{q}}\in\triangle^{N}$, there exists a subgradient
$\widehat{\mathbf{v}}\in\partial{f}(\widehat{\mathbf{q}})$ satisfying

$L(\mathbf{q},\widehat{\mathbf{q}})=-f(\widehat{\mathbf{q}})-\left\langle{\widehat{\mathbf{v}}},{\mathbf{q}-\widehat{\mathbf{q}}}\right\rangle\quad\text{for
$\mathbf{q}\in\triangle^{N}$}.$ (4)

Proof  First, assume that $\bm{\ell}$ is proper. Then,
$\underline{L}(\mathbf{q})=L(\mathbf{q},\mathbf{q})\in\mathbb{R}$. Define
$f:\mathbb{R}^{N}\to(-\infty,\infty]$ by

$f(\bm{\xi})\coloneqq\begin{cases}-\underline{L}(\bm{\xi})&\text{if
}\bm{\xi}\in\triangle^{N},\\\ \infty&\text{otherwise},\end{cases}$ (5)

then $f$ is a proper convex function on $\mathbb{R}^{N}$ such that
$\operatorname{\mathrm{dom}}f\subseteq\triangle^{N}$. For
$\mathbf{q},\widehat{\mathbf{q}}\in\triangle^{N}$, we have

$f(\mathbf{q})=-L(\mathbf{q},\mathbf{q})\geq-L(\mathbf{q},\widehat{\mathbf{q}})=-L(\widehat{\mathbf{q}},\widehat{\mathbf{q}})+\left\langle{-\bm{\ell}(\widehat{\mathbf{q}})},{\mathbf{q}-\widehat{\mathbf{q}}}\right\rangle=f(\widehat{\mathbf{q}})+\left\langle{-\bm{\ell}(\widehat{\mathbf{q}})},{\mathbf{q}-\widehat{\mathbf{q}}}\right\rangle.$

In particular, if $f$ is subdifferentiable at $\widehat{\mathbf{q}}$, then
this inequality also holds by replacing $\mathbf{q}\in\triangle^{N}$ with
$\bm{\xi}\in\mathbb{R}^{N}$. Thus,
$-\bm{\ell}(\widehat{\mathbf{q}})\in\partial f(\widehat{\mathbf{q}})$ and Eq.
4 hold for any $\widehat{\mathbf{q}}\in\triangle^{N}$.

Conversely, suppose that there is a proper convex function $f$ on
$\mathbb{R}^{N}$ such that $\operatorname{\mathrm{dom}}f=\triangle^{N}$ and,
for all $\widehat{\mathbf{q}}\in\triangle^{N}$, there exists
$\widehat{\mathbf{v}}\in\partial{f}(\widehat{\mathbf{q}})$ satisfying Eq. 4.
Then, for $\mathbf{q}\in\triangle^{N}$, we have
$L(\mathbf{q},\mathbf{q})=-f(\mathbf{q})$ and

$L(\mathbf{q},\mathbf{q})=-f(\mathbf{q})\leq-f(\widehat{\mathbf{q}})-\left\langle{\widehat{\mathbf{v}}},{\mathbf{q}-\widehat{\mathbf{q}}}\right\rangle=L(\mathbf{q},\widehat{\mathbf{q}})\quad\text{for
}\widehat{\mathbf{q}}\in\triangle^{N},$

in turn, $\bm{\ell}$ is proper.

Next, we show the equivalence of the strict properness of $\bm{\ell}$ and the
strict convexity of $f$ on $\triangle^{N}$. Let $\bm{\ell}$ be a proper loss,
$f$ a convex function on $\triangle^{N}$ such that (4) holds. On the one hand,
if $\bm{\ell}$ is strictly proper, then we have

$\displaystyle f((1-t)\mathbf{q}+t\mathbf{q}^{\prime})$
$\displaystyle=L((1-t)\mathbf{q}+t\mathbf{q}^{\prime},(1-t)\mathbf{q}+t\mathbf{q}^{\prime})$
$\displaystyle=(1-t)L(\mathbf{q},(1-t)\mathbf{q}+t\mathbf{q}^{\prime})+tL(\mathbf{q}^{\prime},(1-t)\mathbf{q}+t\mathbf{q}^{\prime})$
$\displaystyle>(1-t)L(\mathbf{q},\mathbf{q})+tL(\mathbf{q}^{\prime},\mathbf{q}^{\prime})$
$\displaystyle=(1-t)f(\mathbf{q},\mathbf{q})+tf(\mathbf{q}^{\prime},\mathbf{q}^{\prime}),$

for $\mathbf{q},\mathbf{q}^{\prime}\in\triangle^{N}$ and $t\in(0,1)$, proving
the strict convexity of $f$ on $\triangle^{N}$. On the other hand, if
$\bm{\ell}$ is not strict proper, then there exist distinct
$\mathbf{q},\mathbf{q}^{\prime}\in\triangle^{N}$ such that

$f(\mathbf{q})=-L(\mathbf{q},\mathbf{q})=-L(\mathbf{q},\mathbf{q}^{\prime})=f(\mathbf{q}^{\prime})+\left\langle{\mathbf{v}^{\prime}},{\mathbf{q}-\mathbf{q}^{\prime}}\right\rangle,$

where $\mathbf{v}^{\prime}\in\partial f(\mathbf{q}^{\prime})$ satisfies Eq. 4
such that
$L(\mathbf{q},\mathbf{q}^{\prime})=-f(\mathbf{q}^{\prime})-\left\langle{\mathbf{v}^{\prime}},{\mathbf{q}-\mathbf{q}^{\prime}}\right\rangle$.
For any $t\in(0,1)$, we have

$\displaystyle-L((1-t)\mathbf{q}+t\mathbf{q}^{\prime},(1-t)\mathbf{q}+t\mathbf{q}^{\prime})$
$\displaystyle=f((1-t)\mathbf{q}+t\mathbf{q}^{\prime})$
$\displaystyle\leq(1-t)f(\mathbf{q})+tf(\mathbf{q}^{\prime})$
$\displaystyle=f(\mathbf{q}^{\prime})+(1-t)\left\langle{\mathbf{v}^{\prime}},{\mathbf{q}-\mathbf{q}^{\prime}}\right\rangle$
$\displaystyle=f(\mathbf{q}^{\prime})+\left\langle{\mathbf{v}^{\prime}},{(1-t)\mathbf{q}+t\mathbf{q}^{\prime}-\mathbf{q}^{\prime}}\right\rangle$
$\displaystyle=-L((1-t)\mathbf{q}+t\mathbf{q}^{\prime},(1-t)\mathbf{q}+t\mathbf{q}^{\prime}).$

This yields
$f((1-t)\mathbf{q}+t\mathbf{q}^{\prime})=(1-t)f(\mathbf{q})+f(\mathbf{q}^{\prime})$,
that is, $f$ is not strictly convex on $\triangle^{N}$.

This completes the proof of the proposition.

As a by-product of the proof of Proposition 5, we obtain the following
property thanks to the construction (5).

######  Corollary 6 (Subgradient of conditional Bayes risk)

For a regular loss $\bm{\ell}$, define a proper convex function $f$ on
$\mathbb{R}^{N}$ by (5). Then, $f$ is a proper convex function on
$\mathbb{R}^{N}$ such that
$-\bm{\ell}(\widehat{\mathbf{q}})\in\partial{f}(\widehat{\mathbf{q}})$ for
$\widehat{\mathbf{q}}\in\triangle^{N}$.

Equation 5 gives a closed form of a subgradient of $-\underline{L}$ and is of
interest per se.

For a regular loss $\bm{\ell}$, define the _surrogate regret_
$R:\triangle^{N}\times\triangle^{N}\to(-\infty,\infty]$ by

$R(\mathbf{q},\widehat{\mathbf{q}})\coloneqq
L(\mathbf{q},\widehat{\mathbf{q}})-\underline{L}(\mathbf{q})\quad\text{for
$\mathbf{q},\widehat{\mathbf{q}}\in\triangle^{N}$,}$

which measures the suboptimality of an estimate $\widehat{\mathbf{q}}$ given a
true $\mathbf{q}$. If $\bm{\ell}$ is regular and proper, then, by Proposition
5, the Bregman divergence associated with $f$ defined in (5) with the
measurable selector $\nabla f=-\bm{\ell}$ satisfies

$R(\mathbf{q},\widehat{\mathbf{q}})=B_{(f,-\bm{\ell})}(\mathbf{q}\|\widehat{\mathbf{q}})\quad\text{for
$\mathbf{q},\widehat{\mathbf{q}}\in\triangle^{N}$.}$ (6)

###  3.4 Strongly proper losses

For $\kappa>0$, a loss $\bm{\ell}$ is called  _$\kappa$ -strongly proper_ if

$R(\mathbf{q},\widehat{\mathbf{q}})=L(\mathbf{q},\widehat{\mathbf{q}})-\underline{L}(\mathbf{q})\geq\frac{\kappa}{2}\|\mathbf{q}-\widehat{\mathbf{q}}\|_{2}^{2}\quad\text{for
$\mathbf{q},\widehat{\mathbf{q}}\in\triangle^{N}$.}$ (7)

Strongly proper losses have been introduced for $N=2$ [Aga14] and for general
$N\geq 3$ [ZLA21] to derive a surrogate regret bound in the form of (1). For
example, the log loss $\ell_{y}(\mathbf{q})=-\ln q_{y}$ is $1$-strongly proper
[ZLA21, Lemma 3]. Interestingly, for $N=2$, $\bm{\ell}$ is regular and
strongly proper if and only if its conditional Bayes risk $-\underline{L}$ is
strongly convex [Aga14, Theorem 10]. As an immediate consequence of Eq. 7, we
have the $1/2$-order surrogate regret bounds for strongly proper losses:

$\|\mathbf{q}-\widehat{\mathbf{q}}\|_{2}\leq\sqrt{\frac{2}{\kappa}R(\mathbf{q},\widehat{\mathbf{q}})}.$
(8)

Though several binary losses are shown to be strongly proper [Aga14, Table 1],
it remains challenging to determine whether a given multiclass loss is
strongly proper. In the next section, we derive surrogate regret bounds for
general multiclass proper losses.

##  4 Regret bounds: Necessity of strict properness

In this section, we first study the moduli of convexity in Section 4.1.
Therein, the equivalence of the strict convexity of a function and the strict
monotonicity of its modulus (Theorem 9) is the first main result, which
ensures that its surrogate regret bound is non-vacuous. Then, Section 4.2
shows surrogate regret bounds for general multiclass proper losses beyond
strongly proper losses. Finally, Section 4.3 relates surrogate regret bounds
to several downstream tasks.

###  4.1 Moduli of convexity

Before introducing the moduli of convexity, we study the _midpoint Jensen gap_
of a convex function $f:\triangle^{N}\to\mathbb{R}$, which is defined by

$J(\mathbf{q},\widecheck{\mathbf{q}})\coloneqq\frac{f(\mathbf{q})+f(\widecheck{\mathbf{q}})}{2}-f\left(\frac{\mathbf{q}+\widecheck{\mathbf{q}}}{2}\right)\quad\text{for
$\mathbf{q},\widecheck{\mathbf{q}}\in\triangle^{N}$.}$

The midpoint Jensen gap is nonnegative by the convexity of $f$ on
$\triangle^{N}$. The midpoint Jensen gap is invariant under adding an affine
function, and so is the modulus of convexity. That is, the midpoint Jensen
gaps of two convex functions $f:\triangle^{N}\to\mathbb{R}$ and
$f_{\lambda,\mathbf{u}}:\triangle^{N}\to\mathbb{R}$ defined by

$f_{\lambda,\mathbf{u}}(\mathbf{q})\coloneqq
f(\mathbf{q})+\left\langle{\mathbf{u}},{\mathbf{q}}\right\rangle+\lambda\quad\text{for
$\mathbf{q}\in\triangle^{N}$}$

are the same, for any $\mathbf{u}\in\mathbb{R}^{N}$ and
$\lambda\in\mathbb{R}$. Moreover, we will show that for continuous convex
functions $f,g:\triangle^{N}\to\mathbb{R}$, their midpoint Jensen gaps are the
same if and only if $f-g$ is affine. This property is reminiscent of the
condition for the universal equivalence of surrogate losses [NWJ09, Theorem 3]
[DKR18, Theorem 1].

######  Proposition 7 (Uniqueness up to affine functions)

Let $f,g:\triangle^{N}\to\mathbb{R}$ be continuous convex functions. Then,
their midpoint Jensen gaps are the same if and only if $f-g$ is affine.

Proof  We only show that $f-g$ is affine under the assumption that the
midpoint Jensen gaps of $f$ and $g$ are the same since the converse
implication is trivial. Hereafter, let us write the midpoint Jensen gaps of
$f$ and $g$ by $J_{f}$ and $J_{g}$, respectively.

Without loss of generality, we pick $\mathbf{q}^{0}\in\triangle^{N}_{+}$ such
that $f$ and $g$ are differentiable at $\mathbf{q}^{0}$ because a convex
function is differentiable almost everywhere in the interior of its domain.
Define

$\mathbf{v}^{0}\coloneqq\nabla f(\mathbf{q}^{0})-\nabla
g(\mathbf{q}^{0})\quad\text{and}\quad\lambda\coloneqq
f(\mathbf{q}^{0})-g(\mathbf{q}^{0}).$

Fix any $\mathbf{q}\in\triangle^{N}$ and set

$h(t)\coloneqq
f(\mathbf{q}^{0}+t(\mathbf{q}-\mathbf{q}^{0}))-g(\mathbf{q}^{0}+t(\mathbf{q}-\mathbf{q}^{0}))-\left\langle{\mathbf{v}^{0}},{t(\mathbf{q}-\mathbf{q}^{0})}\right\rangle-\lambda\quad\text{for
$t\in[0,1]$.}$

Then, $h:[0,1]\to\mathbb{R}$ is continuous with $h(0)=0$ and
$h^{\prime}(0)=0$. With elementary algebra, we have

$0=J_{f}(\mathbf{q}^{0},\mathbf{q}^{0}+t(\mathbf{q}-\mathbf{q}^{0}))-J_{g}(\mathbf{q}^{0},\mathbf{q}^{0}+t(\mathbf{q}-\mathbf{q}^{0}))=\frac{1}{2}h(t)-h\left(\frac{t}{2}\right)\quad\text{for
all $t\in[0,1]$,}$

which implies

$h\left(\frac{1}{2}t\right)=\frac{1}{2}h(t)\quad\text{for all $t\in[0,1]$.}$

By invoking this relation recursively, we have $h(t)=2^{k}h(2^{-k}t)$ for any
$k\in\mathbb{N}$, which yields

$h(1)=\lim_{k\to\infty}\frac{h(2^{-k})-h(0)}{2^{-k}}=h^{\prime}(0)=0.$

Consequently, we have

$f(\mathbf{q})=g(\mathbf{q})+\left\langle{\mathbf{v}^{0}},{\mathbf{q}-\mathbf{q}^{0}}\right\rangle+\lambda.$

Thus, we have shown that $f-g$ is affine.

We extend the moduli of convexity defined on $(\triangle^{2},\|\cdot\|_{1})$
[Bao23, Definition 4] to $(\triangle^{N},\|\cdot\|_{p})$ for multiclass
classification. Note that the diameter of $(\triangle^{N},\|\cdot\|_{p})$ is
$2^{1/p}$.

######  Definition 8 (Modulus of convexity)

For a convex function $f:\triangle^{N}\to\mathbb{R}$, its _modulus of
convexity_ of $f$ with respect to the $p$-norm is the function
$\omega:[0,2^{1/p}]\to[0,\infty)$ defined by

$\omega(r)\coloneqq\inf\left\\{{J(\mathbf{q},\widecheck{\mathbf{q}})}\mathrel{}\middle|\mathrel{}{\mathbf{q},\widecheck{\mathbf{q}}\in\triangle^{N}\text{
with }\|\mathbf{q}-\widecheck{\mathbf{q}}\|_{p}\geq r}\right\\}\quad\text{for
}r\in[0,2^{1/p}].$

The modulus of convexity quantifies the convexity of a function. We will show
that the convexity and strict convexity of a function are translated to the
monotonicity and strict monotonicity of its modulus, respectively. This is an
important result throughout this article because the moduli of convexity
characterize surrogate regret bounds, as we will see in Section 4.2 soon.

######  Theorem 9 (Monotonicity of modulus)

For a convex function $f:\triangle^{N}\to\mathbb{R}$, the modulus $\omega$ is
non-decreasing on $[0,2^{1/p}]$ and $\omega(0)=0$. Moreover, the strict
convexity of $f$ on $\triangle^{N}$ is equivalent to the strict monotonicity
of $\omega$ on $[0,2^{1/p}]$.

Before proving Theorem 9, we show a lemma used repeatedly.

###### Lemma 10

Let $f:\triangle^{N}\to\mathbb{R}$ be a convex function. For
$r\in[0,2^{1/p}]$, there exist
$\mathbf{q}^{r},\widecheck{\mathbf{q}}^{r}\in\triangle^{N}$ such that
$\omega(r)=J(\mathbf{q}^{r},\widecheck{\mathbf{q}}^{r})$ and
$\|\mathbf{q}^{r}-\widecheck{\mathbf{q}}^{r}\|_{p}=r$.

Proof  Let $r\in[0,2^{1/p}]$. Define

$\mathcal{D}^{N}(r)\coloneqq\left\\{{(\mathbf{q},\widecheck{\mathbf{q}})\in\triangle^{N}\times\triangle^{N}}\mathrel{}\middle|\mathrel{}{\|\mathbf{q}-\widehat{\mathbf{q}}\|_{p}\geq
r}\right\\}.$

Since $\mathcal{D}^{N}(r)$ is compact and $J$ is continuous on
$\mathcal{D}^{N}(r)$, there is
$(\mathbf{q},\widecheck{\mathbf{q}})\in\mathcal{D}^{N}(r)$ such that
$\omega(r)=J(\mathbf{q},\widecheck{\mathbf{q}})$. Define
$c:[0,1]\to\triangle^{N}$ by

$c(t)\coloneqq(1-t)\mathbf{q}+t\widecheck{\mathbf{q}}\quad\text{for
$t\in[0,1]$.}$

In the case of $\|\mathbf{q}-\widecheck{\mathbf{q}}\|_{p}=r$, we can take
$(\mathbf{q}^{r},\widecheck{\mathbf{q}}^{r})=(\mathbf{q},\widecheck{\mathbf{q}})$,
and the assertion follows. Assume
$\|\mathbf{q}-\widecheck{\mathbf{q}}\|_{p}>r$. Then, there exists
$\tau\in(0,1/2]$ such that

$\|c(\tau)-c(1-\tau)\|_{p}=(1-2\tau)r=r.$

Since $f\circ c:[0,1]\to\mathbb{R}$ is convex, we have

$\displaystyle\frac{f(c(\tau))-f(c(0))}{\tau}\leq\frac{f(c(1))-f(c(1-\tau))}{\tau},$
(9)

which is equivalent to

$\displaystyle J(c(\tau),c(1-\tau))$
$\displaystyle=\frac{f(c(\tau))+f(c(1-\tau)}{2}-f(c(1/2))$
$\displaystyle\leq\frac{f(c(0))+f(c(1)}{2}-f(c(1/2))=J(\mathbf{q},\widecheck{\mathbf{q}}).$

This yields $J(c(\tau),c(1-\tau))=\omega(r)$, and hence, we can take
$(\mathbf{q}^{r},\widecheck{\mathbf{q}}^{r})=(c(\tau),c(1-\tau))$. Thus, we
have confirmed the statement.

Proof of Theorem 9 Define

$\mathcal{D}^{N}(r)\coloneqq\left\\{{(\mathbf{q},\widehat{\mathbf{q}})\in\triangle^{N}\times\triangle^{N}}\mathrel{}\middle|\mathrel{}{\|\mathbf{q}-\widehat{\mathbf{q}}\|_{p}\geq
r}\right\\}.$

For $r^{\prime},r\in[0,2^{1/p}]$ with $r^{\prime}\leq r$, we observe from the
monotonicity $\mathcal{D}^{N}(r)\subseteq\mathcal{D}^{N}(r^{\prime})$ that
$\omega(r^{\prime})\leq\omega(r)$. It is easily seen that
$J(\mathbf{q},\mathbf{q})=0$ holds for any $\mathbf{q}\in\triangle^{N}$ hence
$\omega(0)=0$. Thus, the first assertion follows.

Assume that the strict convexity of $f$ on $\triangle^{N}$. Let
$r\in(0,2^{1/p}]$. By Lemma 10, there exist
$\mathbf{q},\widecheck{\mathbf{q}}\in\triangle^{N}$ such that
$\omega(r)=J(\mathbf{q},\widecheck{\mathbf{q}})$ and
$\|\mathbf{q}-\widecheck{\mathbf{q}}\|_{p}=r$. Define
$c:[0,1]\to\triangle^{N}$ by

$c(t)\coloneqq(1-t)\mathbf{q}+t\widecheck{\mathbf{q}}\quad\text{for
$t\in[0,1]$.}$

Since $f\circ c$ is strictly convex on $[0,1]$, we have the strict inequality

$\frac{f(c(\tau))-f(c(0))}{\tau}<\frac{f(c(1))-f(c(1-\tau))}{\tau}\quad\text{for
$\tau\in(0,1/2]$.}$

Consequently, we conclude

$\omega((1-2\tau)r)\leq
J(c(\tau),c(1-\tau))<J(c(0),c(1))=\omega(r)\quad\text{for $\tau\in(0,1/2]$,}$

that is, the strict monotonicity of $\omega$ on $[0,2^{1/p}]$.

Conversely, if $f$ is not strictly convex on $\triangle^{N}$, there exist
distinct $\mathbf{q},\widecheck{\mathbf{q}}\in\triangle^{N}$ such that

$f((1-t)\mathbf{q}+t\widecheck{\mathbf{q}})=(1-t)f(\mathbf{q})+tf(\widecheck{\mathbf{q}})\quad\text{for
}t\in[0,1].$

This leads to $J(\mathbf{q},\widecheck{\mathbf{q}})=0$. Consequently, $\omega$
is not strictly increasing on $[0,\|\mathbf{q}-\widecheck{\mathbf{q}}\|_{p}]$.

Thus, the proof of the theorem is achieved.

Despite the simple proof, this will lead to the necessity and sufficiency for
a surrogate regret bound being non-vacuous in Section 4.2, together with
Theorem 11.

###  4.2 Surrogate regret bounds

Now, we give surrogate regret bounds with respect to the $p$-norm. The order
of a surrogate regret bound for a proper loss $\bm{\ell}$ is essentially
governed by the modulus of convexity of (the negative of) its conditional
Bayes risk $-\underline{L}$. This is an extension of surrogate regret bounds
for binary classification [Bao23, Theorem 6] to multiclass classification.

######  Theorem 11 (Surrogate regret bounds)

Let $\bm{\ell}:\triangle^{N}\to(-\infty,\infty]^{N}$ be a regular proper loss
and $f:\mathbb{R}^{N}\to(-\infty,\infty]$ a proper convex function defined by
(5). For $\mathbf{q},\widehat{\mathbf{q}}\in\triangle^{N}$, it holds

$\omega(\|\mathbf{q}-\widehat{\mathbf{q}}\|_{p})\leq\frac{1}{2}R(\mathbf{q},\widehat{\mathbf{q}})$
(10)

with equality if $\mathbf{q}=\widehat{\mathbf{q}}$.

Proof  By the definition of $\omega$ together with (6), it is sufficient to
show

$J(\mathbf{q},\widehat{\mathbf{q}})\leq\frac{1}{2}B_{(f,-\bm{\ell})}(\mathbf{q}\|\widehat{\mathbf{q}})\quad\text{for
$\mathbf{q},\widehat{\mathbf{q}}\in\triangle^{N}$.}$

By Corollary 6, we have

$f\left(\frac{\mathbf{q}+\widehat{\mathbf{q}}}{2}\right)\geq
f(\widehat{\mathbf{q}})+\left\langle{-\bm{\ell}(\widehat{\mathbf{q}})},{\frac{\mathbf{q}+\widehat{\mathbf{q}}}{2}-\widehat{\mathbf{q}}}\right\rangle=f(\widehat{\mathbf{q}})+\frac{1}{2}\left\langle{-\bm{\ell}(\widehat{\mathbf{q}})},{\mathbf{q}-\widehat{\mathbf{q}}}\right\rangle,$

which implies

$\displaystyle
J(\mathbf{q},\widehat{\mathbf{q}})\leq\frac{1}{2}\left[f(\mathbf{q})-f(\widehat{\mathbf{q}})-\left\langle{-\bm{\ell}(\widehat{\mathbf{q}})},{\mathbf{q}-\widehat{\mathbf{q}}}\right\rangle\right]=\frac{1}{2}B_{(f,-\bm{\ell})}(\mathbf{q}\|\widehat{\mathbf{q}}).$

The equality can be seen immediately by choosing
$\widehat{\mathbf{q}}=\mathbf{q}$.

Let us discuss when a proper loss entails a non-vacuous bound. If $\bm{\ell}$
is strictly proper, then $\omega$ is strictly increasing, which in turn has an
inverse function $\omega^{-1}$ and leads (10) to

$\|\mathbf{q}-\widehat{\mathbf{q}}\|_{p}\leq\begin{dcases}{\omega}^{-1}\left(\frac{1}{2}R(\mathbf{q},\widehat{\mathbf{q}})\right)&\text{if~{}~{}$\frac{1}{2}R(\mathbf{q},\widehat{\mathbf{q}})\leq\omega\Big{(}2^{\frac{1}{p}}\Big{)}$,}\\\
2^{\frac{1}{p}}&\text{otherwise.}\end{dcases}$ (11)

The strict monotonicity of $\omega^{-1}$ is essential because otherwise we
cannot always expect that the estimate $\widehat{\mathbf{q}}$ approaches
$\mathbf{q}$ even if the suboptimality $R(\mathbf{q},\widehat{\mathbf{q}})$ is
minimized. By Propositions 5 and 9, the _strict_ properness of $\bm{\ell}$ is
necessary and sufficient for the surrogate regret bound (10) being non-
vacuous. This is why strict properness matters.

Let us leave a remark on the existing surrogate regret bounds for proper
_composite_ losses [ML21, Corollary 3]. They derived a surrogate regret bound
similar to (11), with the moduli of _continuity_ of the conditional risk
$L(\mathbf{q},\cdot)$. While the relationship between the moduli of convexity
of $-\underline{L}$ and the moduli of continuity of $L(\mathbf{q},\cdot)$ has
not been clear, $-\underline{L}$ suffices because a surrogate regret is solely
determined by $\underline{L}$ due to (6) and Corollary 6. Moreover, the
existing surrogate regret bounds [ML21, Corollary 3] has been limited to the
binary case $N=2$. Our Theorem 11 is more general therein.

###  4.3 Relating surrogate regret to downstream tasks

The upper bound for the $p$-norm (11) is useful for many scenarios to assess
the predictive performance of plug-in forecasters, i.e., post-processed
forecasters based on the estimator $\widehat{\mathbf{q}}^{\bullet}$. Thus, we
can regard the $p$-norm bound as a _versatile_ surrogate regret bound across
different downstream tasks. Subsequently, we provide several examples of
downstream tasks to support this idea.

#### Task 1: multiclass classification.

Let us consider multiclass classification based on the post-process approach.
Given true and estimated probability vectors
$\mathbf{q},\widehat{\mathbf{q}}\in\triangle^{N}$, respectively, the plug-in
forecaster based on the estimate $\widehat{\mathbf{q}}$ is given by
$\widehat{y}\in\operatorname*{arg\,max}_{y\in\mathcal{Y}}\widehat{q}_{y}$,
where the tie is broken arbitrarily. Here, the forecaster’s suboptimality in
multiclass classification is measured by the (conditional) _0-1 regret_

$\mathrm{Reg}_{01}(\mathbf{q},\widehat{\mathbf{q}})\coloneqq\sum_{n\in\mathcal{Y}}q_{n}(1-\delta_{n\widehat{y}})-\min_{y\in\mathcal{Y}}\sum_{n\in\mathcal{Y}}q_{n}(1-\delta_{ny})=\max_{y\in\mathcal{Y}}\left\langle{\mathbf{q}},{\mathbf{L}_{\widehat{y}}-\mathbf{L}_{y}}\right\rangle,$

where $\mathbf{L}\in\mathbb{R}^{N\times N}$ is the 0-1 loss matrix with each
component being $L_{ij}\coloneqq 1-\delta_{ij}$, and $\mathbf{L}_{y}$ denotes
the $y$-th column vector of $\mathbf{L}$. Let $p^{\ast}$ denote the Hölder
conjugate of $p$. The 0-1 regret can be bounded as

$\mathrm{Reg}_{01}(\mathbf{q},\widehat{\mathbf{q}})\leq\max_{y\in\mathcal{Y}}\left\langle{\mathbf{q}-\widehat{\mathbf{q}}},{\mathbf{L}_{\widehat{y}}-\mathbf{L}_{y}}\right\rangle\leq\|\mathbf{q}-\widehat{\mathbf{q}}\|_{p}\max_{y\in\mathcal{Y}}\|\mathbf{L}_{\widehat{y}}-\mathbf{L}_{y}\|_{p^{\ast}}\leq
2^{1-\frac{1}{p}}\|\mathbf{q}-\widehat{\mathbf{q}}\|_{p},$

where the first inequality holds because
$\left\langle{\widehat{\mathbf{q}}},{\mathbf{L}_{\widehat{y}}-\mathbf{L}_{y}}\right\rangle\leq
0$ for any $y\in\mathcal{Y}$ attributed to the construction of $\widehat{y}$,
and the second inequality owes to Hölder’s inequality. Eventually, the 0-1
regret is controlled by the surrogate regret
$R(\mathbf{q},\widehat{\mathbf{q}})$ via (11) if $\bm{\ell}$ is strictly
proper, which relates the estimation quality of $\widehat{\mathbf{q}}$ to the
predictive performance of the post-processed forecaster via the $p$-norm.

#### Task 2: learning with noisy labels.

Let us consider multiclass classification with class-conditional label noises:
a true label $y$ is observed as $\widetilde{y}$ with probability
$C_{y,\widetilde{y}}$ with a row-stochastic noise matrix
$\mathbf{C}\in[0,1]^{N\times N}$. In this scenario, our access is limited to
the noisy target probability vector
$\widetilde{\mathbf{q}}=\mathbf{C}^{\top}\mathbf{q}$, through which a noisy
estimate $\widehat{\mathbf{q}}$ is obtained. By following the noise-correction
strategy [ZLA21], the plug-in forecaster based on the noisy estimate
$\widehat{\mathbf{q}}$ is given by
$\widecheck{y}\in\operatorname*{arg\,max}_{y\in\mathcal{Y}}\widecheck{q}_{y}$,
where
$\widecheck{\mathbf{q}}\coloneqq(\mathbf{C}^{\top})^{-1}\widehat{\mathbf{q}}$
(provided that $\mathbf{C}$ is invertible). Under this setup, the 0-1 regret
of $\widecheck{\mathbf{q}}$ given $\mathbf{q}$ is bounded as follows:

$\displaystyle\mathrm{Reg}_{01}(\mathbf{q},\widecheck{\mathbf{q}})$
$\displaystyle=\max_{y\in\mathcal{Y}}\left\langle{\mathbf{q}},{\mathbf{L}_{\widecheck{y}}-\mathbf{L}_{y}}\right\rangle$
$\displaystyle\leq\max_{y\in\mathcal{Y}}\left\langle{\mathbf{q}-\widecheck{\mathbf{q}}},{\mathbf{L}_{\widecheck{y}}-\mathbf{L}_{y}}\right\rangle=\max_{y\in\mathcal{Y}}\left\langle{\widetilde{\mathbf{q}}-\widehat{\mathbf{q}}},{\mathbf{C}^{-1}(\mathbf{L}_{\widecheck{y}}-\mathbf{L}_{y})}\right\rangle$
$\displaystyle\leq\|\widetilde{\mathbf{q}}-\widehat{\mathbf{q}}\|_{p}\max_{y\in\mathcal{Y}}\|\mathbf{C}^{-1}(\mathbf{L}_{\widecheck{y}}-\mathbf{L}_{y})\|_{p^{\ast}}$

where the first inequality holds because
$\left\langle{\widecheck{\mathbf{q}}},{\mathbf{L}_{\widecheck{y}}-\mathbf{L}_{y}}\right\rangle\leq
0$ for any $y\in\mathcal{Y}$ attributed to the construction of
$\widecheck{y}$, and the second inequality owes to Hölder’s inequality. The
$p$-norm $\|\widetilde{\mathbf{q}}-\widehat{\mathbf{q}}\|_{p}$ can be
minimized even with access to the noisy observations only, and the $p$-norm
bound (11) controls this by the surrogate regret of a strictly proper loss.
This is also an extension of the previous surrogate regret transfer bounds
[ZLA21, Theorem 4] beyond strongly proper losses.

#### Task 3: bipartite ranking.

Consider $N=2$ and identify $\mathbf{q}=[q_{1}\;q_{2}]^{\top}\in\triangle^{2}$
with the instance $q_{1}\in[0,1]$. Given two instances $q,q^{\prime}\in[0,1]$,
we are interested in giving estimates
$\widehat{q},\widehat{q}^{\prime}\in[0,1]$ that yield a consistent ranking
with $(q,q^{\prime})$. In bipartite ranking, we use the estimates
$(\widehat{q},\widehat{q}^{\prime})$ directly without any post process. The
(conditional) _ranking regret_ [CLV08] is measured by

$\mathrm{Reg}_{\text{rank}}(q,q^{\prime},\widehat{q},\widehat{q}^{\prime})\coloneqq|q-q^{\prime}|\left[\mathds{1}_{\\{(\widehat{q}-\widehat{q}^{\prime})(q-q^{\prime})<0\\}}+\frac{1}{2}\mathds{1}_{\\{\widehat{q}=\widehat{q}^{\prime}\\}}\right],$

where $\mathds{1}_{\\{A\\}}=1$ when the predicate $A$ holds and $0$ otherwise,
and the first and second terms penalize an inconsistent ranking and tie,
respectively. This can be immediately related to the $1$-norm [Aga14]:

$\mathrm{Reg}_{\text{rank}}(q,q^{\prime},\widehat{q},\widehat{q}^{\prime})\leq|q-\widehat{q}|+|q^{\prime}-\widehat{q}^{\prime}|,$

where the bound (11) can be further applied. Thus, the ranking regret is
controlled by the surrogate regret.

#### Other benefits.

In addition to the above examples, one can easily relate the $p$-norm and
downstream tasks such as binary classification with generalized performance
criteria [KD16, Eq. (9)], which we omit here. Another benefit of the $p$-norm
bound (11) is that it relates a possibly non-metric
$R(\mathbf{q},\widehat{\mathbf{q}})$ to the metric
$\|\mathbf{q}-\widehat{\mathbf{q}}\|_{p}$.

To conclude this section, we raise attention to the kinship between moduli of
convexity and the known devices such as calibration functions [BJM06] [Ste07]
[OBLJ17] [BSS20] [BSX+22], comparison inequalities [MPRS12] [CRR20], and
Fisher consistency bounds [AMMZ22a] [AMMZ22b] [MMZ23]. In spite of the
relevance, moduli of convexity are different in that these devices have been
tailored for a specific target loss of each downstream task, whereas moduli
are concerned with the $p$-norm.

##  5 Lower bounds of surrogate regret order

We move on to the next main result: the surrogate regret order cannot go
beyond the square root. To this end, we first review the Simonenko order
function and the strong convexity used to establish the main result, and then
show the main result. In this section, let $f:\triangle^{N}\to\mathbb{R}$ be a
convex function unless otherwise stated.

###  5.1 Power evaluation of moduli

To interpret the surrogate regret bound (10), we evaluate the order of the
modulus $\omega$ by power functions. To this end, we introduce the order of
$\omega$, which is well-defined since $\omega(r)>0$ for $r\in(0,2^{1/p}]$ from
Theorem 9.

######  Definition 12 (Simonenko order function [Sim64])

Let $f:\triangle^{N}\to\mathbb{R}$ be a strictly convex function. The
_Simonenko order function_ $\sigma:(0,2^{1/p}]\to[0,\infty]$ is defined by

$\sigma(r)\coloneqq\frac{rD^{-}\omega(r)}{\omega(r)}\quad\text{for
}r\in\big{(}0,2^{\frac{1}{p}}\big{]},\text{~{}~{}where~{}~{}}D^{-}\omega(r)\coloneqq\limsup_{\varepsilon\downarrow
0}\frac{\omega(r)-\omega(r-\varepsilon)}{\varepsilon}.$

The quantity $D^{-}\omega$ is called the _upper left Dini derivative_ of
$\omega$ at $r$. If $\omega$ is differentiable at $r$, then
$D^{-}\omega(r)=\omega^{\prime}(r)$ holds. The Simonenko order function
$\sigma$ evaluates the order of $\omega$.

######  Proposition 13 (Power evaluations of moduli)

Let $f:\triangle^{N}\to\mathbb{R}$ be a strictly convex function. For a fixed
$r_{0}\in(0,2^{1/p}]$, we define $s,S\in[0,\infty]$ by

$s\coloneqq\inf_{r\in(0,r_{0}]}\sigma(r),\quad
S\coloneqq\sup_{r\in(0,r_{0}]}\sigma(r),$

and assume $S<\infty$. Then, the function $r\mapsto\omega(r)r^{-s}$ is non-
decreasing on $(0,r_{0})$ and the function $r\mapsto\omega(r)r^{-S}$ is non-
increasing on $(0,r_{0})$. Consequently, the following inequalities hold for
any $r\in[0,r_{0}]$:

$\left[\frac{\omega(r_{0})}{r_{0}^{S}}\right]r^{S}\leq\omega(r)\leq\left[\frac{\omega(r_{0})}{r_{0}^{s}}\right]r^{s}.$

Here, we show the proof by assuming the differentiability of $\omega$ because
the resulting proof is instructive. The complete proof without the
differentiability is slightly convoluted and deferred to Appendix A.

Proof  By the definition of $S$, for any $t\in(0,r_{0}]$,

$\frac{S}{t}=\frac{1}{t}\sup_{r\in(0,r_{0}]}\sigma(r)\geq\frac{\omega^{\prime}(t)}{\omega(t)}.$

By integrating both sides, for any $r^{\prime}\in[r,r_{0}]$,

$S\ln\frac{r^{\prime}}{r}=S\int_{r}^{r^{\prime}}\frac{\mathrm{d}{t}}{t}\geq\int_{r}^{r^{\prime}}\frac{\omega^{\prime}(t)}{\omega(t)}\mathrm{d}{t}=\ln\frac{\omega(r^{\prime})}{\omega(r)},$

which gives the one side of the desiderata. The other side can be proven
similarly.

Thus, the $p$-norm upper bound (11) is controlled by the rate
$\omega^{-1}(\rho)=O(\rho^{1/S})$. Since we are interested in the behavior of
$\|\mathbf{q}-\widehat{\mathbf{q}}\|_{p}$ when $\widehat{\mathbf{q}}$ is close
to the minimizer of $R(\mathbf{q},\cdot)$, we focus on the asymptotic behavior
of the Simonenko order function as $r\downarrow 0$.

###  5.2 Strong convexity and its relation to moduli

For the asymptotic analysis of $\sigma$, we leverage _strong_ convexity.
Herein, we define the strong convexity parameter for a convex function
$f:\triangle^{N}\to\mathbb{R}$ and $t\in(0,1)$ by

$\displaystyle\kappa^{f,t}_{p}$ $\displaystyle\coloneqq\
\inf\left\\{{\frac{2\left[(1-t)f(\mathbf{q})+tf(\widecheck{\mathbf{q}})-f((1-t)\mathbf{q}+t\widecheck{\mathbf{q}})\right]}{t(1-t)\|\mathbf{q}-\widecheck{\mathbf{q}}\|_{p}^{2}}}\mathrel{}\middle|\mathrel{}{\text{distinct
}\mathbf{q},\widecheck{\mathbf{q}}\in\triangle^{N}}\right\\},$
$\displaystyle\kappa^{f}_{p}$
$\displaystyle\coloneqq\inf_{t\in(0,1)}\kappa^{f,t}_{p}.$

We observe from the convexity of $f$ that $\kappa^{f}_{p}\in[0,\infty)$ and

$f((1-t)\mathbf{q}+t\widecheck{\mathbf{q}})\leq(1-t)f(\mathbf{q})+tf(\widecheck{\mathbf{q}})-\frac{\kappa^{f}_{p}}{2}t(1-t)\|\mathbf{q}-\widecheck{\mathbf{q}}\|_{p}^{2}\quad\text{for
$\mathbf{q},\widecheck{\mathbf{q}}\in\triangle^{N}$ and $t\in(0,1)$.}$

Remark that the strong convexity parameter depends on the underlying set where
we take the infimum. Let us define the strong convexity parameter on
$\mathbb{R}^{N}$ by replacing $\triangle^{N}$ with $\mathbb{R}^{N}$ and write
$\bar{\kappa}^{f,t}_{p}$ instead of $\kappa^{f,t}_{p}$ for each $t\in(0,1)$.
By $\triangle^{N}\subseteq\mathbb{R}^{N}$, we observe that

$\bar{\kappa}^{f,t}_{p}\leq\kappa^{f,t}_{p}\text{~{}~{}for a function
$f:\mathbb{R}^{N}\to(-\infty,\infty]$,}$

where the equality does not necessarily hold.

To calculate $\kappa^{f}_{p}$, we only need to know $\kappa^{f,1/2}_{p}$.

######  Proposition 14 (Strong convexity parameter at midpoint)

For a continuous convex function $f:\triangle^{N}\to\mathbb{R}$, we have
$\kappa^{f}_{p}=\kappa^{f,1/2}_{p}$.

The proof is deferred to Appendix B. By Proposition 14, the strong convexity
parameter and the modulus of convexity are connected.

Since we have

$\kappa^{f,\frac{1}{2}}_{p}=\inf\left\\{{\frac{8J(\mathbf{q},\widecheck{\mathbf{q}})}{\|\mathbf{q}-\widecheck{\mathbf{q}}\|_{p}^{2}}}\mathrel{}\middle|\mathrel{}{\text{distinct
$\mathbf{q},\widecheck{\mathbf{q}}\in\triangle^{N}$}}\right\\},$

the following bound holds:

$\displaystyle\inf\left\\{{\frac{\|\mathbf{q}\|_{p}^{2}}{\|\mathbf{q}\|_{2}^{2}}}\mathrel{}\middle|\mathrel{}{\mathbf{q}\in\triangle^{N}}\right\\}\leq\frac{\kappa^{f,\frac{1}{2}}_{2}}{\kappa^{f,\frac{1}{2}}_{p}}\leq\sup\left\\{{\frac{\|\mathbf{q}\|_{p}^{2}}{\|\mathbf{q}\|_{2}^{2}}}\mathrel{}\middle|\mathrel{}{\mathbf{q}\in\triangle^{N}}\right\\}.$

In particular, if $N=2$, we have

$\|\mathbf{q}-\widecheck{\mathbf{q}}\|_{p}=\left((q_{1}-\widecheck{q}_{1})^{p}+(q_{2}-\widecheck{q}_{2})^{p}\right)^{\frac{1}{p}}=\left((q_{1}-\widecheck{q}_{1})^{p}+(q_{1}-\widecheck{q}_{1})^{p}\right)^{\frac{1}{p}}=2^{\frac{1}{p}}|q_{1}-\widecheck{q}_{1}|$

for $\mathbf{q},\widecheck{\mathbf{q}}\in\triangle^{2}$, and hence,
$2\kappa^{f,1/2}_{2}=2^{2/p}\kappa^{f,1/2}_{p}$. Therefore, $\kappa_{p}^{f}$
remains the same up to constant regardless of the choice of $p\geq 1$.

We will use another representation of $\kappa_{p}^{f,1/2}=\kappa_{p}^{f}$
later:

$\kappa^{f}_{p}=\inf\left\\{{\frac{8\omega(r)}{r^{2}}}\mathrel{}\middle|\mathrel{}{r\in(0,2^{\frac{1}{p}}]}\right\\}.$
(12)

###  5.3 Asymptotic lower bound

The asymptotic behavior of the Simonenko order $\sigma(r)$ as $r\downarrow 0$
is controlled by the strong convexity parameter $\kappa^{f}_{p}$. We introduce
a “local” version of the strong convexity parameter.

######  Definition 15 (Local strong convexity modulus)

For a convex function $f:\triangle^{N}\to\mathbb{R}$, define
$K_{p}^{f}:(0,2^{1/p}]\to\mathbb{R}$ by

$K^{f}_{p}(r)\coloneqq\frac{8\omega(r)}{r^{2}}.$

This quantity is defined based on the alternative expression of the strong
convexity parameter $\kappa^{f}_{p}$ in (12). From the relationship (12),
$K^{f}_{p}(r)\geq\kappa^{f}_{p}$ always holds on $r\in(0,2^{1/p}]$. In the
following lemma, we verify the continuity properties that $K^{f}_{p}$
naturally entails.

###### Lemma 16

If $f:\triangle^{N}\to\mathbb{R}$ is continuous convex, then
$K^{f}_{p}:(0,2^{1/p}]\to\mathbb{R}$ is lower semi-continuous and left-
continuous.

Proof  Fix $r\in(0,2^{1/p}]$. Let
$(r_{j})_{j\in\mathbb{N}}\subseteq(0,2^{1/p}]$ be a sequence converging to
$r$. For each $j\in\mathbb{N}$, there exist
$\mathbf{q}^{j},\widecheck{\mathbf{q}}^{j}\in\triangle^{N}$ satisfying

$\|\mathbf{q}^{j}-\widecheck{\mathbf{q}}^{j}\|_{p}=r_{j}\quad\text{and}\quad\omega(r_{j})=J(\mathbf{q}^{j},\widecheck{\mathbf{q}}^{j})$

from Lemma 10. Define $c_{j}:[0,1]\to\triangle^{N}$ by

$c_{j}(t)\coloneqq(1-t)\mathbf{q}^{j}+t\widecheck{\mathbf{q}}^{j}\quad\text{for
$t\in[0,1]$.}$

By the Arzelá–Ascoli theorem, we can extract a subsequence
$(c_{j_{m}})_{m\in\mathbb{N}}$ converging uniformly to some
$c:[0,1]\to\triangle^{N}$ uniformly, where

$c(t)=(1-t)c(0)+tc(1)\quad\text{for
$t\in[0,1]$~{}~{}and}\quad\|c(0)-c(1)\|_{p}=r$

hold. Since $f$ is continuous, we have

$\displaystyle K^{f}_{p}(r)=\frac{8}{r^{2}}\omega(r)$
$\displaystyle\leq\frac{8}{r^{2}}J(c(0),c(1))$
$\displaystyle=\lim_{m\to\infty}\frac{8}{r_{j_{m}}^{2}}J(c_{j_{m}}(0),c_{j_{m}}(1))=\lim_{m\to\infty}\frac{8}{r_{j_{m}}^{2}}\omega(r_{j_{m}})=\lim_{m\to\infty}K^{f}_{p}(r_{j_{m}}).$

Thus, $K^{f}_{p}:(0,2^{1/p}]\to\mathbb{R}$ is lower semi-continuous.

Next, we choose distinct $\mathbf{q},\widecheck{\mathbf{q}}\in\triangle^{N}$
satisfying

$\|\mathbf{q}-\widecheck{\mathbf{q}}\|_{p}=r\quad\text{and}\quad\omega(r)=J(\mathbf{q},\widecheck{\mathbf{q}}),$

which exist thanks to Lemma 10. For these $\mathbf{q},\widecheck{\mathbf{q}}$,
define

$c(t)\coloneqq(1-t)\mathbf{q}+t\widecheck{\mathbf{q}}\quad\text{for
$t\in[0,1]$.}$

For $\tau\in(0,1/2)$, we have

$\displaystyle\frac{K^{f}_{p}((1-2\tau)r)}{8}[(1-2\tau)r]^{2}$
$\displaystyle=\omega((1-2\tau)r)$ (13) $\displaystyle\leq
J(c(\tau),c(1-\tau))$ $\displaystyle\leq
J(c(0),c(1))-\frac{\kappa^{f}_{p}}{2}\tau(1-\tau)r^{2}$
$\displaystyle=\omega(r)-\frac{\kappa^{f}_{p}}{2}\tau(1-\tau)r^{2}$
$\displaystyle\leq\frac{K^{f}_{p}(r)}{8}r^{2}-\frac{\kappa^{f}_{p}}{2}\tau(1-\tau)r^{2}.$

Dividing by $[(1-2\tau)r]^{2}/8\neq 0$ and then taking the limit yields

$\limsup_{\tau\downarrow 0}K^{f}_{p}((1-2\tau)r)\leq K^{f}_{p}(r).$

Together with the lower semi-continuity $K_{p}^{f}$, the left-continuity
$K_{p}^{f}$ is ensured.

This completes the proof of the lemma.

Now, we analyze the asymptotic behavior of $\sigma(r)$ at $r\downarrow 0$ when
$f$ is continuous on $\triangle^{N}$, which is our second main result. We need
a slightly stronger continuity of $K^{f}_{p}$ than what Lemma 16 provides.
Moreover, we assume the continuity of $f$ to prevent $f$ from being
discontinuous on the $\triangle^{N}\setminus\triangle^{N}_{+}$.

######  Theorem 17 (Lower bound of order)

Let $f:\triangle^{N}\to\mathbb{R}$ be a continuous strictly convex function.
Assume one of the following two conditions.

  1. (C1)

$\kappa^{f}_{p}>0$.

  2. (C2)

$K^{f}_{p}$ is continuous on $(0,r_{0}]$ for some $r_{0}\in(0,2^{1/p}]$ and
$K^{f}_{p}$ converges as $r\downarrow 0$.

Then,

$\limsup_{r\downarrow 0}\sigma(r)\geq 2.$ (14)

Moreover, if we assume both conditions, then

$\liminf_{r\downarrow 0}\sigma(r)\geq 2.$ (15)

To prove Theorem 17, we leverage the following lemma to locally control
$\sigma(r)$, which is proven in Appendix B.

###### Lemma 18

Let $f:\triangle^{N}\to\mathbb{R}$ be a continuous convex function. Then, for
any $\mathbf{q},\widecheck{\mathbf{q}}\in\triangle^{N}$ and $r\in(0,2^{1/p}]$,

$\displaystyle\liminf_{r\downarrow 0}K^{f}_{p}(r)=\kappa^{f}_{p},\quad
J(\mathbf{q},\widecheck{\mathbf{q}})\geq\frac{\kappa^{f}_{p}}{8}\|\mathbf{q}-\widecheck{\mathbf{q}}\|_{p}^{2},\quad\text{and}\quad
D^{-}\omega(r)\geq\frac{\kappa^{f}_{p}}{4}r.$

Proof of Theorem 17 We observe from the strict convexity of $f$ and Theorem 9
that $K^{f}_{p}>0$ on $r\in(0,2^{1/p}]$. By assuming (C1) only, it follows
from Lemma 18 that

$\displaystyle\limsup_{r\downarrow 0}\sigma(r)=\limsup_{r\downarrow
0}\frac{rD^{-}\omega(r)}{\omega(r)}\geq\limsup_{r\downarrow
0}\frac{r\cdot\dfrac{\kappa^{f}_{p}}{4}r}{\dfrac{K^{f}_{p}(r)}{8}r^{2}}=\limsup_{r\downarrow
0}\frac{2\kappa^{f}_{p}}{K^{f}_{p}(r)}=2.$

In addition, assume (C2) together. Then, the above inequality provides

$\displaystyle\liminf_{r\downarrow 0}\sigma(r)\geq\liminf_{r\downarrow
0}\frac{2\kappa^{f}_{p}}{K^{f}_{p}(r)}=\lim_{r\downarrow
0}\frac{2\kappa^{f}_{p}}{K^{f}_{p}(r)}=2.$

Next, assume (C2) only, and $\kappa^{f}_{p}>0$ does not hold. In this case,
Lemma 18 indicates that $K^{f}_{p}(r)\downarrow 0$ as $r\downarrow 0$, from
which we can inductively define $(r_{j})_{j\in\mathbb{N}}\subseteq(0,r_{0}]$
by

$r_{j}\coloneqq\inf\left\\{{r\in(0,2^{1/p}]}\mathrel{}\middle|\mathrel{}{K^{f}_{p}(r)\geq\frac{1}{2}K^{f}_{p}(r_{j-1})}\right\\}.$

Then, $(r_{j})_{j\in\mathbb{N}}$ converges to $0$ because $K^{f}_{p}>0$ always
holds on $r\in(0,2^{1/p}]$ and hence $K^{f}_{p}(r)=0$ if and only if $r=0$. We
observe that

$K^{f}_{p}(r)<\frac{1}{2}K^{f}_{p}(r_{j-1})=K^{f}_{p}(r_{j})\quad\text{for
$r\in(0,r_{j}]$.}$

This yields

$\displaystyle D^{-}\omega(r_{j})=\limsup_{\varepsilon\downarrow
0}\frac{\omega(r_{j})-\omega(r_{j}-\varepsilon)}{\varepsilon}$
$\displaystyle=\limsup_{\varepsilon\downarrow
0}\frac{\dfrac{K^{f}_{p}(r_{j})}{8}r_{j}^{2}-\dfrac{K^{f}_{p}(r_{j}-\varepsilon)}{8}(r_{j}-\varepsilon)^{2}}{\varepsilon}$
$\displaystyle\geq\limsup_{\varepsilon\downarrow
0}\frac{\dfrac{K^{f}_{p}(r_{j})}{8}r_{j}^{2}-\dfrac{K^{f}_{p}(r_{j})}{8}(r_{j}-\varepsilon)^{2}}{\varepsilon}=\frac{K^{f}_{p}(r_{j})}{4}r_{j},$

which implies

$\displaystyle\limsup_{r\downarrow
0}\sigma(r)\geq\limsup_{j\to\infty}\sigma(r_{j})=\limsup_{j\to\infty}\frac{r_{j}D^{-}\omega(r_{j})}{\omega(r_{j})}\geq\limsup_{j\to\infty}\frac{r_{j}\cdot\dfrac{K^{f}_{p}(r_{j})}{4}r_{j}}{\dfrac{K^{f}_{p}(r_{j})}{8}r_{j}^{2}}=2.$

This completes the proof of Theorem 17.

It follows from Proposition 13 and Theorem 17 that the $p$-norm bound (11) is
controlled by the rate of $\omega^{-1}(\rho)$ cannot be faster than
$O(\rho^{1/2})$ for a very large class of strictly proper $\bm{\ell}$. To see
this, we invoke Proposition 13 to observe that for some $r_{0}\in(0,2^{1/p}]$,

$\omega^{-1}(\rho)\leq[r_{0}\omega(r_{0})^{-\frac{1}{S}}]\cdot\rho^{\frac{1}{S}}\quad\text{for
$r\in[0,r_{0}]$ such that $\rho=\omega(r)$.}$

If the bound (14) holds, then we have

$2\leq\limsup_{r\downarrow 0}\sigma(r)\leq\sup_{r\in(0,r_{0}]}\sigma(r)=S,$

which implies $\rho^{1/S}\geq\rho^{1/2}$ (for $\rho<1$). Thus, we discern the
optimal rate $\omega^{-1}(\rho)=O(\rho^{1/2})$ for $\rho\in[0,1]$. This
assures that strongly proper losses asymptotically achieve the optimal rate
$O(\rho^{1/2})$ as seen in (8). Indeed, the condition (C1) is tightly
connected to the strong properness.

#### Lower bound of $\omega^{-1}(\rho)$.

Proposition 13 also implies that for some $r_{0}\in(0,2^{1/p}]$,

$\omega^{-1}(\rho)\geq[r_{0}\omega(r_{0})^{-\frac{1}{s}}]\cdot\rho^{\frac{1}{s}}\quad\text{for
$r\in[0,r_{0}]$ such that $\rho=\omega(r)$.}$

If the bound (15) holds with the _strict_ inequality, then we can choose
$r_{0}$ to satisfy

$\frac{2+\varsigma}{2}\leq\inf_{r\in(0,r_{0}]}\sigma(r)=s\quad\text{for~{}~{}$\varsigma\coloneqq\liminf_{r\downarrow
0}\sigma(r)>2$,}$

which implies $\rho^{1/s}\geq\rho^{2/(2+\varsigma)}>\rho^{1/2}$ (for
$\rho<1$). Thus, $\omega^{-1}$ admits the lower bound $\Omega(\rho^{1/2})$ for
$\rho\in[0,1]$.

#### Comparison with the known lower bound.

A relevant lower bound $\omega^{-1}(\rho)=\Omega(\rho^{1/2})$ has been shown
previously for a slightly different type of losses [FW21, Theorem 4]. To
derive the lower bound, they assume that a loss is strongly convex and has a
locally Lipschitz gradient [FW21, Assumption 1]. The latter condition is
assumed under the loss differentiability, whereas both our (C1) and (C2) do
not need the differentiability of $\bm{\ell}$. Ergo, the differentiability
assumption is lifted to show the optimality of
$\omega^{-1}(\rho)=O(\rho^{1/2})$. In Section 6, we will see a non-
differentiable example, the max-power function. To show
$\omega^{-1}(\rho)=\Omega(\rho^{1/2})$ in our case, (C1) and (C2) coupled with
the existence of the limit of $K^{f}_{p}(r)$ as $r\downarrow 0$ suffice.

Figure 1: Illustration of
$\omega(r)=r\sin\left(\frac{1}{r}\right)-\mathrm{Ci}\left(\frac{1}{r}\right)+r$.

###### Remark 1

Our analysis with the Simonenko order evaluates the order of $\omega$ by a
power function in the form of $r^{S}\lesssim\omega(r)\lesssim r^{s}$ for
$r\in[0,r_{0}]$. This is an evaluation for a _finite_ range, which is more
than an _asymptotic_ evaluation. Despite its subtlety, it often matters, as
seen in the following example:

$\omega(r)=r\sin\left(\frac{1}{r}\right)-\mathrm{Ci}\left(\frac{1}{r}\right)+r\quad\text{for
$r>0$},\quad\text{where}\quad\mathrm{Ci}(z)\coloneqq-\int_{z}^{\infty}t^{-1}\cos(t)\mathrm{d}{t}.$

This $\omega$ is monotonically increasing and satisfies $\omega(r)=O(r)$ in
the asymptotic evaluation. However, when it comes to the finite evaluation, we
cannot go faster than $\omega(r)\gtrsim r^{2}$ just because this $\omega$
satisfies (C2) and Theorem 17 implies $\limsup_{r\downarrow 0}\sigma(r)\geq
2$. Thus, the finite evaluation gives a better characterization when we assess
the convergence rate of finitely large surrogate regret. See Fig. 1 to better
understand the above example.

##  6 Examples

We overview a couple of proper losses. Since there is the one-to-one
correspondence between a regular proper loss $\bm{\ell}$ and a convex function
$f=-\underline{L}$ on $\triangle^{N}$ (see Eq. 5), we show examples in terms
of the corresponding convex functions. To facilitate closed-form solutions of
$\omega$, we restrict ourselves to $N=2$ and $p=1$. In this case, we overload
$f(q_{1},q_{2})=f(q,1-q)$ for $q\in[0,1]$.

Table 1:  Examples of a convex function $f$. For $\omega$, we show the expressions with $(N,p)=(2,1)$.  | $f(\mathbf{q})$ |  Range of $\alpha$ |  Modulus $\omega(r)$ |  Loss $\bm{\ell}$
---|---|---|---|---
Shannon ent. | $\left\langle{\mathbf{q}},{\ln\mathbf{q}}\right\rangle$ | — | $\frac{1+r}{2}\ln\frac{1+r}{2}+\frac{1-r}{2}\ln\frac{1-r}{2}+\ln 2$ | Log
Sq. $\alpha$-norms | $\|\mathbf{q}\|_{\alpha}^{2}$ | $1<\alpha<2$ | $\frac{1}{4}\left\|{\begin{bmatrix}{1+r}\\\ {1-r}\end{bmatrix}}\right\|_{\alpha}^{2}-4^{1/\alpha-1}$ |  Brier ($\alpha=2$)
$2\leq\alpha$ | $\frac{1}{2}\left\|{\begin{bmatrix}{r}\\\ {1-r}\end{bmatrix}}\right\|_{\alpha}^{2}-\frac{1}{4}\left\|{\begin{bmatrix}{r}\\\ {2-r}\end{bmatrix}}\right\|_{\alpha}^{2}+\frac{1}{2}$
$\alpha$-norms | $\|\mathbf{q}\|_{\alpha}$ | $1<\alpha<2$ | (No closed-form in general) |  Pseudo- spherical
$2\leq\alpha$ | $\frac{1}{2}\left\|{\begin{bmatrix}{r}\\\ {1-r}\end{bmatrix}}\right\|_{\alpha}-\frac{1}{2}\left\|{\begin{bmatrix}{r}\\\ {2-r}\end{bmatrix}}\right\|_{\alpha}+\frac{1}{2}$
Tsallis ent. | $\|\mathbf{q}\|_{\alpha}^{\alpha}$ | $\alpha\in(1,2)\cup(3,\infty)$ | $\frac{1}{2^{\alpha}}\left\|{\begin{bmatrix}{1+r}\\\ {1-r}\end{bmatrix}}\right\|_{\alpha}^{\alpha}-2^{1-\alpha}$ | $\alpha$-log
$2\leq\alpha\leq 3$ | $\frac{1}{2}\left\|{\begin{bmatrix}{r}\\\ {1-r}\end{bmatrix}}\right\|_{\alpha}^{\alpha}-\frac{1}{2^{\alpha}}\left\|{\begin{bmatrix}{r}\\\ {2-r}\end{bmatrix}}\right\|_{\alpha}^{\alpha}+\frac{1}{2}$
Max-power | $\displaystyle\max\limits_{n\in[N]}\\!\Big{[}\\!\left|q_{n}\\!-\\!\tfrac{1}{N}\right|^{\alpha}\\!\Big{]}$ | $1<\alpha<2$ | $\frac{1}{2}\left|r-\frac{1}{2}\right|^{\alpha}\\!-\\!\frac{1}{2^{\alpha}}|r-1|^{\alpha}\\!+\\!\frac{1}{2^{1+\alpha}}$ | —
$2\leq\alpha$ | $(\frac{r}{2})^{\alpha}$

$\displaystyle{0.0}$$\displaystyle{0.2}$$\displaystyle{0.4}$$\displaystyle{0.6}$$\displaystyle{0.8}$$\displaystyle{1.0}$$\displaystyle{0}$$\displaystyle{1}$$\displaystyle{2}$$\displaystyle{3}$$\displaystyle{4}$$\displaystyle{5}$$\displaystyle{6}$$\displaystyle
K^{f}_{p}(r)$ShannonTsallis ($\alpha=2.00$)Tsallis ($\alpha=1.50$)Tsallis
($\alpha=2.25$)Tsallis ($\alpha=1.75$)Tsallis ($\alpha=2.50$)

$\displaystyle{0.0}$$\displaystyle{0.2}$$\displaystyle{0.4}$$\displaystyle{0.6}$$\displaystyle{0.8}$$\displaystyle{1.0}$$\displaystyle{0}$$\displaystyle{1}$$\displaystyle{2}$$\displaystyle{3}$$\displaystyle{4}$$\displaystyle{5}$$\displaystyle{6}$Sq.
norm ($\alpha=1.5$)Norm ($\alpha=2.0$)Sq. norm ($\alpha=2.0$)Norm
($\alpha=2.5$)Sq. norm ($\alpha=2.5$)

$\displaystyle{0.0}$$\displaystyle{0.2}$$\displaystyle{0.4}$$\displaystyle{0.6}$$\displaystyle{0.8}$$\displaystyle{1.0}$$\displaystyle{0}$$\displaystyle{1}$$\displaystyle{2}$$\displaystyle{3}$$\displaystyle{4}$$\displaystyle{5}$$\displaystyle{6}$Max-
pow. ($\alpha=1.25$)Max-pow. ($\alpha=2.00$)Max-pow. ($\alpha=1.50$)Max-pow.
($\alpha=2.25$)Max-pow. ($\alpha=1.75$)Max-pow. ($\alpha=2.50$)

Figure 2: Numerical plots of $K^{f}_{p}(r)=8\omega(r)/r^{2}$ for each $f$ in
Table 1.

Table 1 lists several convex functions with their moduli, whose derivations
are given previously [Bao23]. All examples satisfy at least (C2) of Theorem
17. Indeed, there exists the limit of $K^{f}_{p}(r)$ as $r\downarrow 0$, as
seen in Fig. 2. Thus, we have ensured that the optimal order of the inverse
modulus $\omega^{-1}(\rho)$ for many common losses is $O(\rho^{1/2})$. Note
that the Shannon entropy, squared $\alpha$-norms (for $\alpha>1$), and Tsallis
entropies (for $\alpha>1$) satisfy (C1), but the $\alpha$-norms satisfy (C1)
only for $\alpha\in(1,2]$ but violate for $\alpha>2$.

In these examples, $f$ is differentiable entirely on $\triangle^{N}_{+}$
except for the max-power function. For $N=2$, the max-power function is
$f(q)\coloneqq\left|q-\frac{1}{2}\right|^{\alpha}$, which is not
differentiable at $q=1/2$. Theorem 17 is applicable even for such non-
differentiable functions.

#### Example for $N\geq 3$.

Though deriving a closed form of $\omega$ for general $N>2$ is challenging, we
can delineate $\omega$ for the Shannon entropy with $p=2$: for
$r\in(0,2^{1/2})$, define $\mathbf{q},\widecheck{\mathbf{q}}\in\triangle^{N}$
by

$\mathbf{q}=\begin{bmatrix}\dfrac{1+2^{-1/2}r}{2}&\dfrac{1-2^{-1/2}r}{2}&0&\\!\\!\dots\\!\\!&0\end{bmatrix}\text{~{}~{}and~{}~{}}\widecheck{\mathbf{q}}=\begin{bmatrix}\dfrac{1-2^{-1/2}r}{2}&\dfrac{1+2^{-1/2}r}{2}&0&\\!\\!\dots\\!\\!&0\end{bmatrix}.$

Then, $\|\mathbf{q}-\widecheck{\mathbf{q}}\|_{2}=r$ and
$\omega(r)=J(\mathbf{q},\widecheck{\mathbf{q}})$. At this minimizer, $\omega$
can be written as

$\omega(r)=\frac{1+2^{-1/2}r}{2}\ln\frac{1+2^{-1/2}r}{2}+\frac{1-2^{-1/2}r}{2}\ln\frac{1-2^{-1/2}r}{2}+\ln
2.$

This $\omega$ (for $p=2$) is akin to the form of $\omega$ shown in Table 1,
which is for $(N,p)=(2,1)$, with a slight difference in the scale. Its
derivation is based on the method of Lagrange multipliers and deferred to
Proposition 24.

## Acknowledgments

HB and AT are supported by JSPS Grant-in-Aid for Transformative Research
Areas(A) (22A201). AT is supported by JSPS Grant-in-Aid for Scientific
Research(C) (19K03494).

## References

  * [AA15] Arpit Agarwal and Shivani Agarwal.  On consistent surrogate risk minimization and property elicitation.  In Proceedings of the 28th Conference on Learning Theory, pages 4–22, 2015.
  * [Aga14] Shivani Agarwal.  Surrogate regret bounds for bipartite ranking via strongly proper losses.  Journal of Machine Learning Research, 15(1):1653–1674, 2014.
  * [AMMZ22a] Pranjal Awasthi, Anqi Mao, Mehryar Mohri, and Yutao Zhong.  $\mathcal{H}$-consistency bounds for surrogate loss minimizers.  In Proceedings of the 39th International Conference on Machine Learning, pages 1117–1174, 2022.
  * [AMMZ22b] Pranjal Awasthi, Anqi Mao, Mehryar Mohri, and Yutao Zhong.  Multi-class $\mathcal{H}$-consistency bounds.  Advances in Neural Information Processing Systems, 35:782–795, 2022\.
  * [Bao22] Han Bao.  Excess Risk Transfer and Learning Problem Reduction towards Reliable Machine Learning.  PhD thesis, University of Tokyo, 2022.
  * [Bao23] Han Bao.  Proper losses, moduli of convexity, and surrogate regret bounds.  In Proceedings of the 36th Conference on Learning Theory, pages 525–547, 2023.
  * [BGHN23] Jarosław Błasiok, Parikshit Gopalan, Lunjia Hu, and Preetum Nakkiran.  When does optimizing a proper loss yield calibration?  Advances in Neural Information Processing Systems, 36:72071–72095, 2023.
  * [BJM06] Peter L Bartlett, Michael I Jordan, and Jon D McAuliffe.  Convexity, classification, and risk bounds.  Journal of the American Statistical Association, 101(473):138–156, 2006.
  * [BSS05] Andreas Buja, Werner Stuetzle, and Yi Shen.  Loss functions for binary class probability estimation and classification: Structure and applications.  Technical Report, 2005.
  * [BSS20] Han Bao, Clay Scott, and Masashi Sugiyama.  Calibrated surrogate losses for adversarially robust classification.  In Proceedings of the 30th Conference on Learning Theory, pages 408–451, 2020.
  * [BSX+22] Han Bao, Takuya Shimada, Liyuan Xu, Issei Sato, and Masashi Sugiyama.  Pairwise supervision can provably elicit a decision boundary.  In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics, pages 2618–2640, 2022.
  * [CLV08] Stéphan Clémençon, Gábor Lugosi, and Nicolas Vayatis.  Ranking and empirical minimization of U-statistics.  The Annals of Statistics, 36(2):844–874, 2008.
  * [CRR20] Carlo Ciliberto, Lorenzo Rosasco, and Alessandro Rudi.  A general framework for consistent structured prediction with implicit loss embeddings.  Journal of Machine Learning Research, 21(1):3852–3918, 2020.
  * [DKR18] John Duchi, Khashayar Khosravi, and Feng Ruan.  Multiclass classification, information, divergence and surrogate risk.  The Annals of Statistics, 46(6B):3246–3275, 2018.
  * [DM78] Claude Dellacherie and Paul-André Meyer.  Probabilities and Potential, volume 29 of North-Holland Mathematics Studies.  North-Holland Publishing Co., Amsterdam-New York, 1978.
  * [Fig76] Tadeusz Figiel.  On the moduli of convexity and smoothness.  Studia Mathematica, 56(2):121–155, 1976.
  * [FW21] Rafael Frongillo and Bo Waggoner.  Surrogate regret bounds for polyhedral losses.  Advances in Neural Information Processing Systems, 34:21569–21580, 2021.
  * [GR07] Tilmann Gneiting and Adrian E Raftery.  Strictly proper scoring rules, prediction, and estimation.  Journal of the American statistical Association, 102(477):359–378, 2007.
  * [KD16] Wojciech Kotłowski and Krzysztof Dembczyński.  Surrogate regret bounds for generalized classification performance metrics.  In Proceedings of the 8th Asian Conference on Machine Learning, pages 301–316, 2016.
  * [KK96] R. Kannan and Carole King Krueger.  Advanced Analysis on the Real Line.  Universitext. Springer-Verlag, New York, 1996.
  * [KNRD14] Oluwasanmi O Koyejo, Nagarajan Natarajan, Pradeep K Ravikumar, and Inderjit S Dhillon.  Consistent binary classification with generalized performance metrics.  Advances in Neural Information Processing Systems, 27:2744–2752, 2014.
  * [KRN65] K. Kuratowski and C. Ryll-Nardzewski.  A general theorem on selectors.  Bulletin de l’Académie Polonaise des Sciences. Série des Sciences Mathématiques, Astronomiques et Physiques, 13:397–403, 1965.
  * [KSFF17] Meelis Kull, Telmo Silva Filho, and Peter Flach.  Beta calibration: a well-founded and easily implemented improvement on logistic calibration for binary classifiers.  In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, pages 623–631, 2017.
  * [ML21] Alexander Mey and Marco Loog.  Consistency and finite sample behavior of binary class probability estimation.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 8967–8974, 2021.
  * [MMZ23] Anqi Mao, Mehryar Mohri, and Yutao Zhong.  Structured prediction with stronger consistency guarantees.  Advances in Neural Information Processing Systems, 36:46903–46937, 2023.
  * [MPRS12] Youssef Mroueh, Tomaso Poggio, Lorenzo Rosasco, and Jean-Jeacques Slotine.  Multiclass learning with simplex coding.  Advances in Neural Information Processing Systems, 25:2789–2797, 2012.
  * [NA13] Harikrishna Narasimhan and Shivani Agarwal.  On the relationship between binary classification, bipartite ranking, and binary class probability estimation.  Advances in Neural Information Processing Systems, 26:2913–2921, 2013.
  * [NWJ09] XuanLong Nguyen, Martin J Wainwright, and Michael I Jordan.  On surrogate loss functions and $f$-divergences.  The Annals of Statistics, 37(2):876–904, 2009.
  * [OBLJ17] Anton Osokin, Francis Bach, and Simon Lacoste-Julien.  On structured prediction theory with calibrated convex surrogate losses.  Advances in Neural Information Processing Systems, 31:302–313, 2017\.
  * [OFR+19] Yaniv Ovadia, Emily Fertig, Jie Ren, Zachary Nado, David Sculley, Sebastian Nowozin, Joshua Dillon, Balaji Lakshminarayanan, and Jasper Snoek.  Can you trust your model’s uncertainty? evaluating predictive uncertainty under dataset shift.  Advances in Neural Information Processing Systems, 32:13991–14002, 2019.
  * [OT13] Shin-Ichi Ohta and Asuka Takatsu.  Displacement convexity of generalized relative entropies. II.  Communications in Analysis and Geometry, 21(4):687–785, 2013.
  * [Roc70] R Tyrrell Rockafellar.  Convex Analysis, volume 28.  Princeton University Press, 1970.
  * [RW09] Mark D Reid and Robert C Williamson.  Surrogate regret bounds for proper losses.  In Proceedings of the 26th International Conference on Machine Learning, pages 897–904, 2009.
  * [RW10] Mark D Reid and Robert C Williamson.  Composite binary losses.  Journal of Machine Learning Research, 11:2387–2422, 2010.
  * [RW11] Mark D Reid and Robert C Williamson.  Information, divergence and risk for binary experiments.  Journal of Machine Learning Research, 12(22):731–817, 2011.
  * [Sav71] Leonard J Savage.  Elicitation of personal probabilities and expectations.  Journal of the American Statistical Association, 66(336):783–801, 1971.
  * [Sim64] Igor Borisovich Simonenko.  Interpolation and extrapolation of linear operators in Orlicz spaces.  Matematicheskii Sbornik, 105(4):536–553, 1964.
  * [Ste07] Ingo Steinwart.  How to compare different loss functions and their risks.  Constructive Approximation, 26(2):225–287, 2007.
  * [WVR16] Robert C Williamson, Elodie Vernet, and Mark D Reid.  Composite multiclass losses.  Journal of Machine Learning Research, 17:1–52, 2016.
  * [Zha04] Tong Zhang.  Statistical behavior and consistency of classification methods based on convex risk minimization.  The Annals of Statistics, 32(1):56–85, 2004.
  * [ZLA21] Mingyuan Zhang, Jane Lee, and Shivani Agarwal.  Learning from noisy labels with no change to the training process.  In Proceedings of the 38th International Conference on Machine Learning, pages 12468–12478. PMLR, 2021.
  * [ZRA20] Mingyuan Zhang, Harish Guruprasad Ramaswamy, and Shivani Agarwal.  Convex calibrated surrogates for the multi-label F-measure.  In Proceedings of the 37th International Conference on Machine Learning, pages 11246–11255. PMLR, 2020.

##  Appendix A Proof of power evaluations without differentiability

In Section 5, we show power evaluations of the moduli with the
differentiability of $\omega$.

See 13

Proof  We first show that $r\mapsto\omega(r)r^{-S}$ is non-increasing on
$(0,r_{0})$ in a similar way to the existing argument [OT13, Lemma 2.9]. For
$r\in(0,r_{0}]$ and $\delta>0$, there exists $\varepsilon_{r,\delta}>0$ such
that

$\frac{r}{\omega(r)}\cdot\sup_{\varepsilon\in(0,\varepsilon_{r,\delta})}\frac{\omega(r)-\omega(r-\varepsilon)}{\varepsilon}\leq\sigma(r)+\frac{1}{2}\delta$
(16)

by the definition of $D^{-}\omega$. Define

$g(t)\coloneqq
S+\frac{1}{2}\delta+\frac{1}{t}[(1-t)^{S+\delta}-1]\quad\text{for
$t\in(0,1)$.}$

Then, $g$ is continuous on $(0,1)$ and

$\lim_{t\downarrow
0}g(t)=S+\frac{1}{2}\delta-(S+\delta)=-\frac{1}{2}\delta<0,$

which implies the existence of $\tau\in(0,1)$ such that $g(t)<0$ for
$t\in(0,\tau)$. Then, for any $u\in(0,\varepsilon_{r,\delta})\cap(0,r\tau)$,

$\displaystyle-\frac{r^{S+\delta}}{\omega(r)}+\frac{(r-u)^{S+\delta}}{\omega(r-u)}$
$\displaystyle=\frac{ur^{S+\delta-1}}{\omega(r-u)}\left[\frac{r}{\omega(r)}\frac{\omega(r)-\omega(r-u)}{u}\right]-\frac{r^{S+\delta}}{\omega(r-u)}+\frac{r^{S+\delta}(1-\frac{u}{r})^{S+\delta}}{\omega(r-u)}$
$\displaystyle\leq\frac{ur^{S+\delta-1}}{\omega(r-u)}\left[\sigma(r)+\frac{1}{2}\delta\right]+\frac{ur^{S+\delta-1}}{\omega(r-u)}\cdot\frac{1}{\frac{u}{r}}\left[\left(1-\frac{u}{r}\right)^{S+\delta}-1\right]$
$\displaystyle\leq\frac{ur^{S+\delta-1}}{\omega(r-u)}\left[S+\frac{1}{2}\delta+g\left(\frac{u}{r}\right)-\left(S+\frac{1}{2}\delta\right)\right]$
$\displaystyle=\frac{ur^{S+\delta-1}}{\omega(r-u)}\cdot
g\left(\frac{u}{r}\right)$ $\displaystyle<0,$

where the inequality (16) is used at the second line and the third line
follows from the definition of $S$. Hence, we have

$\frac{(r-u)^{S+\delta}}{\omega(r-u)}<\frac{r^{S+\delta}}{\omega(r)}\quad\text{for
$r\in(0,r_{0})$ and $u\in(0,\varepsilon_{r,\delta})\cap(0,r\tau)$.}$

Letting $\delta\downarrow 0$, we conclude that $r\mapsto r^{S}/\omega(r)$ is
non-decreasing on $(0,r_{0})$. This is equivalent to that
$r\mapsto\omega(r)r^{-S}$ is non-increasing on $(0,r_{0})$.

Next, we show that $r\mapsto\omega(r)r^{-s}$ is non-decreasing on $(0,r_{0})$.
For $r\in(0,r_{0}]$, let $u\in(0,r)$. Since $\ln\omega$ is non-decreasing on
$[r-u,r]$, it follows from the fundamental theorem of calculus [KK96, Theorem
1.3.1] that

$\int_{r-u}^{r}D^{-}\ln\omega(r^{\prime})\mathrm{d}{r^{\prime}}\leq\ln\frac{\omega(r)}{\omega(r-u)}.$

By $D^{-}\omega(r^{\prime})\leq S<\infty$, we have

$\lim_{\varepsilon\downarrow
0}\omega(r^{\prime}-\varepsilon)=\omega(r^{\prime})\quad\text{for
$r^{\prime}\in(0,r_{0})$,}$

which yields

$\lim_{\varepsilon\downarrow
0}\frac{\ln\omega(r^{\prime})-\ln\omega(r^{\prime}-\varepsilon)}{\omega(r^{\prime})-\omega(r^{\prime}-\varepsilon)}=\frac{1}{\omega(r^{\prime})}$

and

$D^{-}\ln\omega(r^{\prime})=\limsup_{\varepsilon\downarrow
0}\left[\frac{\ln\omega(r^{\prime})-\ln\omega(r^{\prime}-\varepsilon)}{\omega(r^{\prime})-\omega(r^{\prime}-\varepsilon)}\cdot\frac{\omega(r^{\prime})-\omega(r^{\prime}-\varepsilon)}{\varepsilon}\right]=\frac{1}{\omega(r^{\prime})}D^{-}\omega(r^{\prime})\geq\frac{s}{r^{\prime}}.$

Thus, we have

$\int_{r-u}^{r}D^{-}\ln\omega(r^{\prime})\mathrm{d}{r^{\prime}}\geq\int_{r-u}^{r}\frac{s}{r^{\prime}}\mathrm{d}{r^{\prime}}=s\ln\frac{r}{r-u}.$

These imply

$\omega(r-u)\cdot(r-u)^{-s}\leq\omega(r)\cdot r^{-s},$

that is, $r\mapsto\omega(r)r^{-s}$ is non-decreasing on $(0,r_{0})$.

##  Appendix B Proofs

See 14

Proof  By definition, $\kappa^{f}_{p}\leq\kappa^{f,1/2}_{p}$ trivially holds.
We shall prove the converse inequality. Observe from the definition that

$f\left(\frac{\mathbf{q}+\widecheck{\mathbf{q}}}{2}\right)\leq\frac{1}{2}f(\mathbf{q})+\frac{1}{2}f(\widecheck{\mathbf{q}})-\frac{\kappa^{f,\frac{1}{2}}_{p}}{8}\|\mathbf{q}-\widecheck{\mathbf{q}}\|_{p}^{2}\quad\text{for
all $\mathbf{q},\widecheck{\mathbf{q}}\in\triangle^{N}$.}$

For $i,j\in\mathbb{N}$, set

$t_{i,j}\coloneqq 2^{-i}j.$

Fix distinct $\mathbf{q},\widecheck{\mathbf{q}}\in\triangle^{N}$ and define
$c:[0,1]\to\triangle^{N}$ by

$c(t)\coloneqq(1-t)\mathbf{q}+t\widecheck{\mathbf{q}}\quad\text{for
$t\in[0,1]$.}$

We will show that

$f(c(t_{i,j}))\leq(1-t_{i,j})f(c(0))+t_{i,j}f(c(1))-\frac{\kappa^{f,\frac{1}{2}}_{p}}{2}t_{i,j}(1-t_{i,j})\|\mathbf{q}-\widecheck{\mathbf{q}}\|_{p}^{2}$
(17)

for $(i,j)\in\mathbb{N}\times\mathbb{Z}_{\geq 0}$ with $t_{i,j}\in[0,1]$
(namely, for $i\in\mathbb{N}$ and $0\leq j\leq 2^{i}$) by induction on $i$. We
immediately observe that (17) always holds for $t_{i,0}=0$ and $t_{i,2^{i}}=1$
regardless of $i$. Note that $t_{i,j}\in(0,1)$ leads to $t_{i,j\pm
1}\in[0,1]$.

The inequality (17) trivially holds for $i=1$. Assume that (17) holds for some
$i\in\mathbb{N}$ and all $j$ with $0\leq j\leq 2^{i}$. Then, (17) also holds
for $t_{i+1,2j}=t_{i,j}$ with $0\leq j\leq 2^{i}$. For $0\leq j\leq 2^{i}-1$,
we have

$t_{i+1,2j+1}=\frac{t_{i+1,2j}+t_{i+1,2j+2}}{2}=\frac{t_{i,j}+t_{i,j+1}}{2}.$

Define $c_{i,j}:[0,1]\to\triangle^{N}$ by

$c_{i,j}(t)\coloneqq c((1-t)\cdot t_{i,j}+t\cdot t_{i,j+1})\quad\text{for
$t\in[0,1]$.}$

This implies

$\displaystyle f$ $\displaystyle(c(t_{i+1,2j+1}))$
$\displaystyle\leq\frac{1}{2}f(c_{i,j}(0))+\frac{1}{2}f(c_{i,j}(1))-\frac{\kappa^{f,\frac{1}{2}}}{8}\|c_{i,j}(0)-c_{i,j}(1)\|_{p}^{2}$
$\displaystyle=\frac{1}{2}f(c_{i,j}(0))+\frac{1}{2}f(c_{i,j}(1))-\frac{\kappa^{f,\frac{1}{2}}_{p}}{8}\cdot
2^{-2i}\cdot\|\mathbf{q}-\widecheck{\mathbf{q}}\|_{p}^{2}$
$\displaystyle=\frac{1}{2}f(c(t_{i,j}))+\frac{1}{2}f(c(t_{i,j+1}))-\frac{\kappa^{f,\frac{1}{2}}_{p}}{8}\cdot
2^{-2i}\cdot\|\mathbf{q}-\widecheck{\mathbf{q}}\|_{p}^{2}$
$\displaystyle\leq\frac{1}{2}\bigg{[}(1-t_{i,j})f(c(0))+t_{i,j}f(c(1))-\frac{\kappa^{f,\frac{1}{2}}_{p}}{2}t_{i,j}(1-t_{i,j})\|\mathbf{q}-\widecheck{\mathbf{q}}\|_{p}^{2}\bigg{]}$
$\displaystyle\phantom{\leq}+\frac{1}{2}\bigg{[}(1-t_{i,j+1})f(c(0))+t_{i,j+1}f(c(1))-\frac{\kappa^{f,\frac{1}{2}}_{p}}{2}t_{i,j+1}(1-t_{i,j+1})\|\mathbf{q}-\widecheck{\mathbf{q}}\|_{p}^{2}\bigg{]}$
$\displaystyle\phantom{\leq}-\frac{\kappa^{f,\frac{1}{2}}_{p}}{8}\cdot
2^{-2i}\cdot\|\mathbf{q}-\widecheck{\mathbf{q}}\|_{p}^{2}$
$\displaystyle=(1-t_{i+1,2j+1})f(c(0))+t_{i+1,2j+1}f(c(1))-\frac{\kappa^{f,\frac{1}{2}}_{p}}{2}t_{i+1,2j+1}(1-t_{i+1,2j+1})\|\mathbf{q}-\widecheck{\mathbf{q}}\|_{p}^{2}$

as desired. Noting again that the inequality (17) holds for $t_{i+1,2j+1}$
with $j=2^{i}$, we have shown the induction case for $0\leq j\leq 2^{i+1}$.

Because $f$ is continuous on $\triangle^{N}$ and
$\left\\{{t_{i,j}\in[0,1]}\mathrel{}\middle|\mathrel{}{(i,j)\in\mathbb{N}\times\mathbb{Z}_{\geq
0}}\right\\}$ is dense in $[0,1]$, we find

$f((1-t)\mathbf{q}+t\widecheck{\mathbf{q}})\leq(1-t)f(\mathbf{q})+tf(\widecheck{\mathbf{q}})-\frac{\kappa^{f,\frac{1}{2}}_{p}}{2}t(1-t)\|\mathbf{q}-\widecheck{\mathbf{q}}\|_{p}^{2}\quad\text{for
$t\in(0,1)$,}$

which leads to

$\kappa^{f,\frac{1}{2}}_{p}\leq\frac{2[(1-t)f(\mathbf{q})+tf(\widecheck{\mathbf{q}})-f((1-t)\mathbf{q}+t\widecheck{\mathbf{q}})]}{t(1-t)\|\mathbf{q}-\widecheck{\mathbf{q}}\|_{p}^{2}}\quad\text{for
$t\in(0,1)$.}$

Since $\mathbf{q},\widecheck{\mathbf{q}}\in\triangle^{N}$ are arbitrary, this
ensures that $\kappa^{f,t}_{p}\geq\kappa^{f,1/2}_{p}$ for $t\in(0,1)$ and
completes the proof of the proposition.

See 18

Proof  Assume that there exists $r_{\ast}\in(0,2^{1/p}]$ such that
$K_{p}^{f}(r_{\ast})=\kappa_{p}^{f}$. We can see from the bound (13) that

$\displaystyle\frac{K^{f}_{p}((1-2\tau)r_{\ast})}{8}[(1-2\tau)r_{\ast}]^{2}$
$\displaystyle\leq\frac{K^{f}_{p}(r_{\ast})}{8}r^{2}-\frac{\kappa^{f}_{p}}{2}\tau(1-\tau)r_{\ast}^{2}=\frac{K^{f}_{p}(r_{\ast})}{8}[(1-2\tau)r_{\ast}]^{2}$

for $\tau\in(0,1/2)$. Since $K_{p}^{f}(r)\geq\kappa_{p}^{f}$ for
$r\in(0,2^{1/p}]$, this implies $K_{p}^{f}(r)=\kappa_{p}^{f}$ for
$r\in(0,r_{\ast}]$ hence

$\liminf_{r\downarrow 0}K^{f}_{p}(r)=\kappa_{p}^{f}.$

Assume that there is no $r\in(0,2^{1/p}]$ so that
$K_{p}^{f}(r)=\kappa_{p}^{f}$. Then, there exists
$(r_{j})_{j\in\mathbb{N}}\subseteq(0,2^{1/p}]$ converging to $0$ such that

$\lim_{j\to\infty}K^{f}_{p}(r_{j})=\inf\left\\{{K^{f}_{p}(r)}\mathrel{}\middle|\mathrel{}{r\in(0,2^{\frac{1}{p}}]}\right\\}=\kappa^{f,\frac{1}{2}}_{p}\leq\liminf_{r\downarrow
0}K^{f}_{p}(r)\leq\lim_{j\to\infty}K^{f}_{p}(r_{j}),$

where the second equality follows from (12). This with Proposition 14 proves
the first assertion.

For $\mathbf{q},\widecheck{\mathbf{q}}\in\triangle$, we calculate

$J(\mathbf{q},\widecheck{\mathbf{q}})\geq\omega(\|\mathbf{q}-\widecheck{\mathbf{q}}\|_{p})=\frac{K^{f}_{p}(\|\mathbf{q}-\widecheck{\mathbf{q}}\|_{p})}{8}\|\mathbf{q}-\widecheck{\mathbf{q}}\|_{p}^{2}\geq\frac{\kappa^{f}_{p}}{8}\|\mathbf{q}-\widecheck{\mathbf{q}}\|_{p}^{2}.$

This is the second assertion.

For $r\in(0,2^{1/p}]$, we can pick
$\mathbf{q},\widecheck{\mathbf{q}}\in\triangle^{N}$ such that
$\omega(r)=J(\mathbf{q},\widecheck{\mathbf{q}})$ and
$\|\mathbf{q}-\widecheck{\mathbf{q}}\|_{p}=r$ from Lemma 10. For
$\tau\in(0,1/2)$, we have

$\omega((1-2\tau)r)\leq\omega(r)-\frac{\kappa^{f}_{p}}{2}\tau(1-\tau)r^{2}$

from (13), which yields

$D^{-}\omega(r)=\limsup_{\tau\downarrow
0}\frac{\omega(r)-\omega((1-2\tau)r)}{r-(1-2\tau)r}\geq\limsup_{\tau\downarrow
0}\frac{\dfrac{\kappa^{f}_{p}}{2}\tau(1-\tau)r^{2}}{2\tau
r}=\frac{\kappa^{f}_{p}}{4}r.$

This completes the proof of the lemma.

##  Appendix C Derivation of modulus for general $N$

In Section 6, we mainly consider examples of $\omega$ only for $(N,p)=(2,1)$.
Since we have extended the moduli on general $(\triangle^{N},\|\cdot\|_{p})$
in Definition 8, it is nice to have an example beyond the binary case. To this
end, we calculate $\omega$ for the Shannon entropy
$f(\mathbf{q})=\left\langle{\mathbf{q}},{\ln\mathbf{q}}\right\rangle$ with
general $N\geq 2$ and $p=2$. In what follows, we focus on
$f(\mathbf{q})=\left\langle{\mathbf{q}},{\ln\mathbf{q}}\right\rangle$ with
$p=2$, and the modulus $\omega$ and midpoint Jensen gap $J$ is defined based
on this particular $f$ throughout this section.

Let

$\mathcal{U}^{N-1}\coloneqq\left\\{{\mathbf{u}\in(0,1)^{N-1}}\mathrel{}\middle|\mathrel{}{\sum_{n\in[N-1]}u_{n}<1}\right\\}$

and define $\psi:\mathcal{U}^{N-1}\times\mathcal{U}^{N-1}\to\mathbb{R}$ and
$\phi:\mathcal{U}^{N-1}\to\mathbb{R}$ by

$\displaystyle\psi(\mathbf{u},\mathbf{w})$
$\displaystyle\coloneqq\frac{1}{2}\Bigg{\\{}\sum_{n\in[N-1]}(u_{n}-w_{n})^{2}+\bigg{[}\sum_{n\in[N-1]}(u_{n}-w_{n})\bigg{]}^{2}\Bigg{\\}}$
for $\mathbf{u},\mathbf{w}\in\mathcal{U}^{N-1}$,
$\displaystyle\phi(\mathbf{u})$
$\displaystyle\coloneqq\sum_{n\in[N-1]}u_{n}\ln
u_{n}+\Bigg{(}1-\sum_{n\in[N-1]}u_{n}\Bigg{)}\ln\Bigg{(}1-\sum_{n\in[N-1]}u_{n}\Bigg{)}$
for $\mathbf{u}\in\mathcal{U}^{N-1}$,

respectively. Here, $\phi$ is the Shannon entropy but defined on the
constrained set $\mathcal{U}^{N-1}$, where we drop the marginal constraint in
the original $\triangle^{N}$. Indeed, we have

$\begin{bmatrix}u_{1}\\\ \vdots\\\ u_{N-1}\\\
1-\left\langle{\mathbf{u}},{\mathbf{1}}\right\rangle\end{bmatrix}\in\triangle^{N}_{+}\quad\text{and}\quad\psi(\mathbf{u},\mathbf{w})=\frac{1}{2}\left\|\begin{bmatrix}u_{1}\\\
\vdots\\\ u_{N-1}\\\
1-\left\langle{\mathbf{u}},{\mathbf{1}}\right\rangle\end{bmatrix}-\begin{bmatrix}w_{1}\\\
\vdots\\\ w_{N-1}\\\
1-\left\langle{\mathbf{w}},{\mathbf{1}}\right\rangle\end{bmatrix}\right\|_{2}^{2},$

which yields $\psi(\mathbf{u},\mathbf{w})\in[0,1]$. First, we present a couple
of necessary lemmas.

###### Lemma 19

For $r\in(0,2^{1/2})$, there exist
$\mathbf{q},\widecheck{\mathbf{q}}\in\triangle^{N}$ such that

$\|\mathbf{q}-\widecheck{\mathbf{q}}\|_{2}=r,\quad\operatorname{\mathrm{supp}}(\mathbf{q})\cap\operatorname{\mathrm{supp}}(\widecheck{\mathbf{q}})\neq\emptyset,\quad
J(\mathbf{q},\widecheck{\mathbf{q}})<\ln 2.$

Proof  Fix $r\in(0,2^{1/2})$ and set $a\coloneqq 2^{-1/2}r\in(0,1)$. Define
$\mathbf{q},\widecheck{\mathbf{q}}\in\triangle^{N}$ by

$q_{n}\coloneqq\delta_{1n},\quad\widecheck{q}_{n}\coloneqq(1-a)\delta_{1n}+a\delta_{2n}\quad\text{for
$n\in[N]$.}$

Then, we have $\|\mathbf{q}-\widecheck{\mathbf{q}}\|_{2}=r$,
$\operatorname{\mathrm{supp}}(\mathbf{q})\cap\operatorname{\mathrm{supp}}(\widecheck{\mathbf{q}})\neq\emptyset$,
and

$\displaystyle\overline{J}(a)\coloneqq
J(\mathbf{q},\widecheck{\mathbf{q}})=\frac{1-a}{2}\ln(1-a)-\left(1-\frac{a}{2}\right)\ln\left(1-\frac{a}{2}\right)+\frac{a}{2}\ln
2.$

Since we have

$\overline{J}(1)=\ln
2,\quad\overline{J}^{\prime}(a)=\frac{1}{2}\ln\frac{2-a}{1-a}>0,$

we conclude $J(\mathbf{q},\widecheck{\mathbf{q}})<\ln 2$ as desired.

###### Lemma 20

For $\mathbf{q},\widecheck{\mathbf{q}}\in\triangle^{N}$, if

$\operatorname{\mathrm{supp}}(\mathbf{q})\cap\operatorname{\mathrm{supp}}(\widecheck{\mathbf{q}})\neq\emptyset,\quad\operatorname{\mathrm{supp}}(\mathbf{q})\neq\operatorname{\mathrm{supp}}(\widecheck{\mathbf{q}}),$

then there exist
$\mathbf{q}^{\prime},\widecheck{\mathbf{q}}^{\prime}\in\triangle^{N}$ such
that

$\|\mathbf{q}-\mathbf{q}\|_{2}=\|\mathbf{q}^{\prime}-\widecheck{\mathbf{q}}^{\prime}\|_{2},\quad\operatorname{\mathrm{supp}}(\mathbf{q}^{\prime})=\operatorname{\mathrm{supp}}(\widecheck{\mathbf{q}}^{\prime}),\quad
J(\mathbf{q}^{\prime},\widecheck{\mathbf{q}}^{\prime})<J(\mathbf{q},\widecheck{\mathbf{q}}).$

Proof  Take
$i\in\operatorname{\mathrm{supp}}(\mathbf{q})\cap\operatorname{\mathrm{supp}}(\widecheck{\mathbf{q}})$
and write

$S_{1}\coloneqq[\operatorname{\mathrm{supp}}(\mathbf{q})\cap\operatorname{\mathrm{supp}}(\widecheck{\mathbf{q}})]\setminus\left\\{{i}\right\\},\quad
S_{2}\coloneqq\operatorname{\mathrm{supp}}(\mathbf{q})\setminus\operatorname{\mathrm{supp}}(\widecheck{\mathbf{q}}),\quad
S_{3}\coloneqq\operatorname{\mathrm{supp}}(\widecheck{\mathbf{q}})\setminus\operatorname{\mathrm{supp}}(\mathbf{q}),$

and $m\coloneqq|S_{2}\cup S_{3}|$. For sufficiently small $\varepsilon>0$,
define
$\mathbf{q}^{\varepsilon},\widecheck{\mathbf{q}}^{\varepsilon}\in\triangle^{N}$
by

$q_{n}^{\varepsilon}\coloneqq\begin{cases}q_{i}-m\varepsilon&\text{for
$n=i$,}\\\ q_{n}&\text{for $n\in S_{1}$,}\\\ q_{n}+\varepsilon&\text{for $n\in
S_{2}\cup S_{3}$,}\\\
0&\text{otherwise,}\end{cases}\quad\widecheck{q}_{n}^{\varepsilon}\coloneqq\begin{cases}\widecheck{q}_{i}-m\varepsilon&\text{for
$n=i$,}\\\ \widecheck{q}_{n}&\text{for $n\in S_{1}$,}\\\
\widecheck{q}_{n}+\varepsilon&\text{for $n\in S_{2}\cup S_{3}$,}\\\
0&\text{otherwise.}\end{cases}$

We find that
$\|\mathbf{q}^{\varepsilon}-\widecheck{\mathbf{q}}^{\varepsilon}\|_{2}=\|\mathbf{q}-\widecheck{\mathbf{q}}\|_{2}$,
$\operatorname{\mathrm{supp}}(\mathbf{q}^{\varepsilon})=\operatorname{\mathrm{supp}}(\widecheck{\mathbf{q}}^{\varepsilon})$,
and

$\lim_{\varepsilon\downarrow
0}J(\mathbf{q}^{\varepsilon},\widecheck{\mathbf{q}}^{\varepsilon})=J(\mathbf{q},\widecheck{\mathbf{q}}),$

thanks to the continuity of $J$. Since we have

$\frac{\partial{}}{\partial{\varepsilon}}J(\mathbf{q}^{\varepsilon},\widecheck{\mathbf{q}}^{\varepsilon})=-\frac{m}{2}\ln\frac{(q_{i}-m\varepsilon)(\widecheck{q}_{i}-m\varepsilon)}{\left(\frac{q_{i}+\widecheck{q}_{i}}{2}-m\varepsilon\right)^{2}}+\frac{1}{2}\sum_{n\in
S_{2}}\ln\frac{(q_{n}+\varepsilon)\varepsilon}{\left(\frac{q_{n}}{2}+\varepsilon\right)^{2}}+\frac{1}{2}\sum_{n\in
S_{3}}\ln\frac{(\widecheck{q}_{n}+\varepsilon)\varepsilon}{\left(\frac{\widecheck{q}_{n}}{2}+\varepsilon\right)^{2}},$

which diverges to $-\infty$ as $\varepsilon\downarrow 0$, we have
$J(\mathbf{q}^{\varepsilon},\widecheck{\mathbf{q}}^{\varepsilon})<J(\mathbf{q},\widecheck{\mathbf{q}})$
for sufficiently small $\varepsilon>0$. This completes the proof of the lemma.

###### Corollary 21

For $\mathbf{q},\widecheck{\mathbf{q}}\in\triangle^{N}$ with
$\|\mathbf{q}-\widecheck{\mathbf{q}}\|_{2}<2^{1/2}$,
$\omega(\|\mathbf{q}-\widecheck{\mathbf{q}}\|_{2})=J(\mathbf{q},\widecheck{\mathbf{q}})$
holds if and only if
$\operatorname{\mathrm{supp}}(\mathbf{q})=\operatorname{\mathrm{supp}}(\widecheck{\mathbf{q}})$.

Proof  Let $\mathbf{q},\widecheck{\mathbf{q}}\in\triangle^{N}$ satisfy
$\|\mathbf{q}-\widecheck{\mathbf{q}}\|_{2}<2^{1/2}$. We observe from Lemma 19
that $J(\mathbf{q},\widecheck{\mathbf{q}})<\ln 2$. On the other hand,
$J(\mathbf{q}^{\prime},\widecheck{\mathbf{q}}^{\prime})=\ln 2$ follows for
$\mathbf{q}^{\prime},\widecheck{\mathbf{q}}^{\prime}\in\triangle^{N}$ with
$\operatorname{\mathrm{supp}}(\mathbf{q}^{\prime})\cap\operatorname{\mathrm{supp}}(\widecheck{\mathbf{q}}^{\prime})=\emptyset$.
Thus,
$\omega(\|\mathbf{q}-\widecheck{\mathbf{q}}\|_{2})=J(\mathbf{q},\widecheck{\mathbf{q}})$
implies
$\operatorname{\mathrm{supp}}(\mathbf{q})=\operatorname{\mathrm{supp}}(\widecheck{\mathbf{q}})$.
The converse implication immediately follows from Lemma 20.

Thus, the proof of the corollary is complete.

Subsequently, we show Lemmas 22 and 23, which are needed to invoke the method
of Lagrangian multipliers later.

###### Lemma 22

For $\mathbf{u},\mathbf{w}\in\mathcal{U}^{N-1}$, the rank of the Jacobian of
$\psi$ at $(\mathbf{u},\mathbf{w})$ is zero if and only if $\mathbf{u}$ and
$\mathbf{w}$ are linearly dependent.

Proof Since we have

$\frac{\partial{\psi}}{\partial{u_{i}}}(\mathbf{u},\mathbf{w})=u_{i}-w_{i}+\sum_{n\in[N-1]}(u_{n}-w_{n})=-\frac{\partial{\psi}}{\partial{w_{i}}}\quad\text{for
$i\in[N-1]$,}$

the rank of the Jacobian of $\psi$ at $(\mathbf{u},\mathbf{w})$ is zero if and
only if

$u_{i}-w_{i}+\sum_{n\in[N-1]}(u_{n}-w_{n})=0\quad\text{for $i\in[N-1]$.}$

Summing the above equation up gives

$N\sum_{n\in[N-1]}(u_{n}-w_{n})=0,$

and hence $u_{i}-w_{i}=0$ for all $i\in[N-1]$, which shows the linear
dependence of $\mathbf{u}$ and $\mathbf{w}$. The converse implication is
trivial.

###### Lemma 23

For $r\in(0,2^{1/2})$, let $\mathbf{u},\mathbf{w}\in\mathcal{U}^{N-1}$ satisfy
$\psi(\mathbf{u},\mathbf{w})=r^{2}/2$. If there exists $\lambda\in\mathbb{R}$
such that

$\displaystyle\frac{1}{2}\frac{\partial{\phi}}{\partial{u_{n}}}(\mathbf{u})-\frac{\partial{\phi}}{\partial{u_{n}}}\left(\frac{\mathbf{u}+\mathbf{w}}{2}\right)+\lambda\frac{\partial{\psi}}{\partial{u_{n}}}(\mathbf{u},\mathbf{w})$
$\displaystyle=0\quad\text{and}$ (18)
$\displaystyle\frac{1}{2}\frac{\partial{\phi}}{\partial{u_{n}}}(\mathbf{u})-\frac{\partial{\phi}}{\partial{u_{n}}}\left(\frac{\mathbf{u}+\mathbf{w}}{2}\right)+\lambda\frac{\partial{\psi}}{\partial{w_{n}}}(\mathbf{u},\mathbf{w})$
$\displaystyle=0$

for $n\in[N-1]$. Then,

$u_{n}=\frac{1}{(N-1)(1+\mu)},\qquad
w_{n}=\frac{\mu}{(N-1)(1+\mu)}\qquad\text{for $n\in[N-1]$,}$

where $\mu\in(0,1)$ satisfies

$\frac{N(1-\mu)^{2}}{(N-1)(1+\mu)^{2}}=r^{2}.$

Proof For simplicity, set

$\mathbf{v}\coloneqq\frac{\mathbf{u}+\mathbf{w}}{2},\quad u_{N}\coloneqq
1-\\!\\!\sum_{n\in[N-1]}u_{n},\quad w_{N}\coloneqq
1-\\!\\!\sum_{n\in[N-1]}w_{n},\quad\text{and}\quad v_{N}\coloneqq
1-\\!\\!\sum_{n\in[N-1]}v_{n}.$

Assuming Eq. 18, we calculate

$\displaystyle 0$
$\displaystyle=\frac{1}{2}\frac{\partial{\phi}}{\partial{u_{i}}}(\mathbf{u})-\frac{\partial{\phi}}{\partial{u_{i}}}(\mathbf{v})+\lambda\frac{\partial{\psi}}{\partial{u_{i}}}(\mathbf{u},\mathbf{w})=\frac{1}{2}\left(\ln\frac{u_{i}}{u_{N}}-\ln\frac{v_{i}}{v_{N}}\right)+\lambda[u_{i}-w_{i}-(u_{N}-w_{N})],$
$\displaystyle 0$
$\displaystyle=\frac{1}{2}\frac{\partial{\phi}}{\partial{w_{i}}}(\mathbf{w})-\frac{\partial{\phi}}{\partial{w_{i}}}(\mathbf{v})+\lambda\frac{\partial{\psi}}{\partial{w_{i}}}(\mathbf{u},\mathbf{w})=\frac{1}{2}\left(\ln\frac{w_{i}}{w_{N}}-\ln\frac{v_{i}}{v_{N}}\right)-\lambda[u_{i}-w_{i}-(u_{N}-w_{N})],$

for $i\in[N-1]$, which yields

$\displaystyle\ln\frac{u_{i}}{u_{N}}-\ln\frac{v_{i}}{v_{N}}$
$\displaystyle=-2\lambda[u_{i}-w_{i}-(u_{N}-w_{N})]=\ln\frac{u_{j}}{u_{N}}-\ln\frac{v_{j}}{v_{N}}$
$\displaystyle=-\ln\frac{w_{i}}{w_{N}}+\ln\frac{v_{i}}{v_{N}}$

for $i,j\in[N-1]$. Thus, we have

$\frac{u_{i}}{u_{j}}=\frac{v_{i}}{v_{j}}=\frac{w_{i}}{w_{j}},\quad\frac{u_{i}}{u_{N}}\cdot\frac{w_{i}}{w_{N}}=\frac{v_{i}^{2}}{v_{N}^{2}}\quad\text{for
$i,j\in[N-1]$.}$

Then, there exists $\mu>0$ such that

$w_{i}=\mu u_{i}\quad\text{for $i\in[N-1]$.}$

It follows from $\psi(\mathbf{u},\mathbf{w})\neq 0$ that $\mu\neq 1$. This
gives the relation

$v_{i}=\frac{1+\mu}{2}u_{i}\text{~{}~{}for $i\in[N-1]$,~{}~{}}\qquad
v_{N}=\frac{(1+\mu)u_{N}+1-\mu}{2},\qquad w_{N}=\mu u_{N}+1-\mu,$

and we have

$\frac{\mu u_{i}^{2}}{u_{N}(\mu
u_{N}+1-\mu)}=\frac{u_{i}}{u_{N}}\cdot\frac{w_{i}}{w_{N}}=\frac{v_{i}^{2}}{v_{N}^{2}}=\frac{(1+\mu)^{2}u_{i}^{2}}{[(1+\mu)u_{N}+1-\mu]^{2}},$

which is equivalent to

$u_{N}=\frac{\mu}{1+\mu}.$

these imply

$0=\ln\frac{u_{i}}{u_{N}}-\ln\frac{v_{i}}{v_{N}}+2\lambda[u_{i}-w_{i}-(u_{N}-w_{N})]=\ln\frac{1}{\mu}+2\lambda(1-\mu)\left(u_{i}+\frac{1}{1+\mu}\right),$

and hence

$u_{i}=\frac{1}{2\lambda(1-\mu)}\ln\mu-\frac{1}{1+\mu}\quad\text{for
$i\in[N-1]$.}$

This with the relation

$1=\sum_{n\in[N]}u_{n}=\frac{N-1}{2\lambda(1-\mu)}\ln\mu-\frac{N-1}{1+\mu}+\frac{\mu}{1+\mu}$

provides

$\lambda=\frac{(N-1)(1+\mu)}{2N(1-\mu)}\ln\mu\quad\text{and}\quad
u_{i}=\frac{1}{(N-1)(1+\mu)}\quad\text{for $i\in[N-1]$}.$

Thus, we have

$r^{2}=2\psi(\mathbf{u},\mathbf{w})=(1-\mu)^{2}\sum_{n\in[N-1]}u_{n}^{2}+(1-\mu)^{2}\frac{1}{(1+\mu)^{2}}=\frac{N(1-\mu)^{2}}{(N-1)(1+\mu)^{2}},$

as desired.

By combining these lemmas, we have the following claim, which is the
minimizers $(\mathbf{q},\widecheck{\mathbf{q}})$ of the Shannon entropy we
show in Section 6.

###### Proposition 24

For $r\in(0,2^{1/2})$, $\mathbf{q},\widecheck{\mathbf{q}}\in\triangle^{N}$
satisfy $\|\mathbf{q}-\widecheck{\mathbf{q}}\|_{2}=r$ and
$\omega(r)=J(\mathbf{q},\widecheck{\mathbf{q}})$ if and only if there exist
distinct $i,j\in[N]$ such that

$q_{n}\coloneqq\frac{1+2^{-1/2}r}{2}\delta_{ni}+\frac{1-2^{-1/2}r}{2}\delta_{nj},\quad\widecheck{q}_{n}\coloneqq\frac{1-2^{-1/2}r}{2}\delta_{ni}+\frac{1+2^{-1/2}r}{2}\delta_{nj}.$

Proof  There exist
$\mathbf{q}^{\prime},\widecheck{\mathbf{q}}^{\prime}\in\triangle^{N}$ such
that

$\|\mathbf{q}^{\prime}-\widecheck{\mathbf{q}}^{\prime}\|_{2}=r,\quad\omega(r)=J(\mathbf{q},\widecheck{\mathbf{q}}),\quad\text{and}\quad\operatorname{\mathrm{supp}}(\mathbf{q}^{\prime})=\operatorname{\mathrm{supp}}(\widecheck{\mathbf{q}}^{\prime})$

from Lemma 10 and Corollary 21. By relabeling the indices $n\in[N]$ and
switching $\mathbf{q}^{\prime}$ and $\widecheck{\mathbf{q}}^{\prime}$ if
necessary, we may assume that $q_{1}^{\prime}>\widecheck{q}_{1}^{\prime}$ and
there exists $N^{\prime}\in[N]$ such that $N^{\prime}\geq 2$ and

$\operatorname{\mathrm{supp}}(\mathbf{q}^{\prime})=\operatorname{\mathrm{supp}}(\widecheck{\mathbf{q}}^{\prime})=[N^{\prime}].$

Define $\mathbf{u}^{\prime},\mathbf{w}^{\prime}\in\mathcal{U}^{N-1}$ by

$u_{n}^{\prime}=q_{n}^{\prime},\quad
w_{n}^{\prime}=\widecheck{q}_{n}^{\prime}\quad\text{for
$n\in[N^{\prime}-1]$.}$

Then, the pair $(\mathbf{u}^{\prime},\mathbf{w}^{\prime})$ minimizes $\phi$
subject to $\phi(\mathbf{u},\mathbf{w})=r^{2}/2$ on
$\mathcal{U}^{N-1}\times\mathcal{U}^{N-1}$. We observe from the method of
Lagrangian multipliers together with Lemmas 22 and 23 that

$u_{n}^{\prime}=\frac{1}{(N^{\prime}-1)(1+\mu_{N^{\prime}})},\quad
w_{n}^{\prime}=\frac{\mu_{N^{\prime}}}{(N^{\prime}-1)(1+\mu_{N^{\prime}})}\quad\text{for
$n\in[N^{\prime}-1]$,}$

where $\mu_{N^{\prime}}\in(0,1)$ satisfies

$\frac{N^{\prime}(1-\mu_{N^{\prime}})^{2}}{(N^{\prime}-1)(1+\mu_{N^{\prime}})^{2}}=r^{2}.$

This implies

$q_{N^{\prime}}=\frac{\mu_{N^{\prime}}}{1+\mu_{N^{\prime}}},\quad\widecheck{q}_{N^{\prime}}=\frac{1}{1+\mu_{N^{\prime}}},\text{~{}~{}and~{}~{}}J(\mathbf{q}^{\prime},\widecheck{\mathbf{q}}^{\prime})=-\ln(1+\mu_{N^{\prime}})+\frac{\mu_{N^{\prime}}}{1+\mu_{N^{\prime}}}\ln\mu_{N^{\prime}}+\ln
2.$

By setting

$\bar{J}(\mu)\coloneqq-\ln(1+\mu)+\frac{\mu}{1+\mu}\ln{\mu}+\ln
2\quad\text{for $\mu\in(0,1)$,}$

we see that

$\bar{J}^{\prime}(\mu)=\frac{1}{(1+\mu)^{2}}\ln{\mu}<0$

and $\mu_{N^{\prime}}\leq\mu_{n^{\prime}}$ holds for $N^{\prime}\leq
n^{\prime}$. Thus, we conclude that $N^{\prime}=2$. Since we have

$\mu_{2}=\frac{1-2^{-1/2}r}{1+2^{-1/2}r},$

this in turn shows

$q_{n}^{\prime}=\frac{1+2^{-1/2}r}{2}\delta_{n1}+\frac{1-2^{-1/2}r}{2}\delta_{n2},\qquad\widecheck{q}_{n}^{\prime}=\frac{1-2^{-1/2}r}{2}\delta_{n1}+\frac{1+2^{-1/2}r}{2}\delta_{n2}.$

By the invariance of $J$ under relabeling the indices $n\in[N]$, the proof of
the proposition is completed.