The Geometry of Mixability
Authors: Armando J Cabrera Pacheco
Robert Williamson
Venue: Accepted by TMLR ()

Abstract: Mixable loss functions are of fundamental importance in the context of prediction with expert advice in the online setting since they characterize fast learning rates. By re-interpreting properness from the point of view of differential geometry, we provide a simple geometric characterization of mixability for the binary and multi-class cases: a proper loss function $\ell$ is $\eta$-mixable if and only if the superprediction set $\textrm{spr}(\eta \ell)$ of the scaled loss function $\eta \ell$ slides freely inside the superprediction set $\textrm{spr}(\ell_{\log})$ of the log loss $\ell_{\log}$, under fairly general assumptions on the differentiability of $\ell$. Our approach provides a way to treat some concepts concerning loss functions (like properness) in a ''coordinate-free'' manner and reconciles previous results obtained for mixable loss functions for the binary and the multi-class cases.

The Geometry of Mixability
Armando J. Cabrera Pacheco
a.cbbeema@unn-tueebnne..ccc
University of Tübingen and Tübingen Al Center, Germany
Robert C. Williamson
bob. bob.uullaammonndeudtt-ttennnneee
University of Tübingen and Tübingen AI Center, Germany
Reviewed on OpenReview: https: // oppenevveew. net/ pormfo VruGHDSaZ7
Abstract
Mixable loss functions are of fundamental importance in the context of prediction with expert advice in the online setting since they characterize fast learning rates. By re-interpreting properness from the point of view differential geometry, we provide a simple geometric characterization of mixability for the binary and multi-class cases: a proper loss function i is mixixable if and only if the superprediction set spr(n)) of the scaled loss function r/l slides freely inside the superprediction set spr(Aiog) of the log loss loog, under fairly general assumptions on the differentiability of l. Our approach provides way to treat some concepts concerning loss functions (like properness) in a "coordinate-free free" manner and reconciles previous results obtained for mixable loss functions for the binary and the multi-class cases.
1 Introduction
In the context of prediction with expert advice described by Vovk (1998; 2001), information game is considered between three players: the learner, N N experts and nature?. At each step t E Z4,
each expert makes prediction of eT, i= 1,..., N, (here the prediction space) which the learner allowed see,
the learner makes prediction 7² TT,
nature chooses outcome w' Ω (here Q is the set of outcomes),
for fixed loss function L: Ω x r [0, oo], the cumulative loss is calculated for the learner and each of the experts:
L (learner) = Σ e(wi,
i=1
(e(eprtt))) = Σ e(wi, ;1):
1=1
where expert, denotes the k-th expert (k: = 1,....N) N).
The goal is to bound the difference between the learner's loss and the experts' loss, which is often called the regret. That is, we want to bound the quantity
R = (learner) L (experttz)
for all
We refer the reader (Vovk, 1998; 2001) for discussions about the desired (or required) assumptions T, Ω and

---

Published in Transactions on Machine Learning Research (09/2023)
1.1 Mixable games and characterizations of mixable and fundamental loss functions
For a wide class of games, called 17-inable games for v > 0, the Aggregating algorithm (see for example (Vovk, 2001)) ensures an optimal bound for the regret (Rf S 1 In N, for all k = N)) independent of the trial t. Since the mixability of a game depends on the loss function E, a loss function is n-mizable if the corresponding game is mixable. Since arguably the aggregating algorithm is one the most well founded and studied prediction algorithms, there a natural interest in understanding properties and characterizations of mixable loss functions.
Examples of mixable loss functions include the log loss, relative entropy for binary outcomes (Haussler et al., 1998) and the Brier score (Vovk& & Zhdanov, 2009; van Erven et al., 2012). Mixability of a loss function l is characterized by a "stronger convexity" of the superprediction set of e, which can be described as the convexity of the superprediction set of l after an "exponential projection" (see (1.3) below and Vovk (2015) and van Erven et al. (2012)). Unfortunately, this characterization of mixability lacks a transparent geometric interpretation.
The main goal of this work is to provide such geometric interpretation. The motivation stems from an observation made by Vovk (2015): a r-mixable loss can be characterized as the positiveness of the infimum of the quotient of the curvatures of the strictly proper loss function & and the log loss log for binary outcomes. Here as usual, loss functions are defined on the 2-simplex A (see (1.1).. Moreover, he then proves that fundamentality (see Vovk (Vovk, 2015)) of a loss can be characterized as the finiteness of the supremum of the same quotient of curvatures. These two results suggest that these properties are geometric, meaning that they can be studied using differential geometry tools, and in this regard, mixability and fundamentality should not depend on the coordinates chosen to express them.
Loosely speaking, in convex geometry a convex set L is said to slide freely inside a convex set K, if for any point in the boundary of K, there is a translation vector y such that the translation of L by y (i.e., the Minkowski sum L + y, see (4.2)), intersects K at and L C K. We provide the following geometric characterization of mixability and fundamentality, as a geometric comparison to the log loss (sec Figure 1). Let spr(E) denote the superprediction set of a loss function (see (1.4)..
Theorem 1.1 (Informal statement). A continuously twice differentiable proper loss function is n-mirable if and only there is nj > 0 such that spr(ne) slides freely inside spr spr((1og). In addition, the same & is fundamental if and only if there evists 7 > 0 such that spr(f1oR) slides freely inside spr(y?).
This new characterization of mixability appeals because it is stated directly in terms of the superprediction sets of the loss functions, rather than the exponentiated super-prediction set. In order to obtain this theorem it is necessary to re-interpret properness from a differential geometry point of view, which constitutes a big part of this work. However, this technical effort pays off. van Erven et al. (2012) characterized mi-ixable (differentiable) loss functions for multi-class loss functions and moreover, related 17 to the Hessian of the Bayes risk of é and the log loss (see Definition 1.3), which is interpreted as its curvature. By generalizing the tools developed here for the binary case, we were able to obtain a multi-class analog result to Theorem 1.1 and to build a bridge to the results in (van Erven et al., 2012)
Finally we note that the large field of information geometry (Amari, 2016) strives to understand the basic problems of statistical inference from a geometric perspective, with strong focus on the geometry of statistical manifolds. Likewise, there are strongly geometric theories which describe the effect of hypothesis classes in machine learning (Mendelson & Williamson, 2002; Van Erven et al., 2015). Our hope is that by geometrizing the theory of loss functions we may be able to bridge these diverse perspectives.
1.2 Description of results and structure of the article
Using the same setting as (van Erven et al., 2012), we obtain a geometric characterization of m-mixable loss functions in the sense of differential geometry. Loss functions are considered to be maps l: A - Rn which under the conditions assumed in this work, give rise to submanifolds ((relint ()")) of I whose geometric
IIn fact, the present paper can seen as the successful realization of the attempt of (van Erven al., 2012), where we felt. that the whole argument should doable coordinate-fres free manner, but did not then have the skills achieve that.
2

---

Published in Transactions on Machine Learning Research (09/2023)
spr(ne + +3)
B
Figure 1: We abuse notation and denote the image a loss function l by simply L. The figure shows how the superprediction set of a translation of the scaling of l slides freely inside the spr spr(Aiog). The bullet points are located the image of p E 2
properties are determined by l (see the relevant precise definitions below). We first discuss the case n 2 (binary classification loss functions) since it is more intuitively understandable, and then the case 2. We summarize the main results as follows.
We recast the notion of a (strictly) proper loss as a geometric property of the loss itself rather than its superprediction set. That is, properness no longer considered parametrization dependent property, is a statement about the geometric properties of the "loss surface" ((relin((A)) (the boundary of the superprediction set). See lemmas 2.7 and 3.2.
2. geometric comparison is performed. For n = 2 in terms of the curvature of the "loss curves" (see Section 1.5 below), and for n 2 2 in terms the scalar second fundamental form of the "loss surfaces" (see Section and Appendix A), which measure how they curve inside R=, The precise statements are given in Lemma 2.13 and Lemma 3.6. Intuitively, these results tell how the superprediction set of l sits inside the superprediction set of the log loss. We remark fundamental difference between the cases 2 and 2 2: for 2, Vovk (2015) observes, mixability can be related to the quotient of the curvature of l and the curvature of liog. In this case the image of & is a curve in IR2 whose curvature can be easily computed. In higher dimensions the notion of curvature is far more complicated and different notions of curvature exist (see for example (Lee, 2018)). For n 2 2, our geometric comparison relies on a comparison of the second fundamental forms of the "loss surfaces" defined by l and bog the second fundamental form measures how a surfaces curved inside an ambient space, which is RR" in our case (see Appendix A). In this regard, part of our work can be interpreted as coordinate independent version of the main computations carried out in (van Erven et al., 2012).
Finally, we interpret our result from the point of view convex analysis to give a new characterization of mixability. More precisely, we show that a (strictly) proper loss function & 1-mixable if and only the superprediction set of & slides freely (see Definition 4.11) inside the superprediction set of the log loss.
3

---

Published in Transactions on Machine Learning Research (09/2023)
As byproducts, obtain general way to define mixability with respect to fixed (strictly) proper loss function, further properties and consequences for binary classification loss functions, particularly for composite losses and canonical links, and a bridge to the results obtained in (van Erven et al., 2012).
Since we treat loss functions from the point of view of differential geometry and convex geometry, a considerable background in these topics needed. We present this work as self-contained as possible and spend some time providing the intuition and motivation for the results (and sometimes the background) which naturally results in longer exposition. In Section 2 we treat the binary case, in Section 3 the multi-class case to obtain the geometric interpretation of properness and mixability and perform the geometric comparison (in terms of curvature). In Section 4 we make the connections to convex geometry and obtain the geometric characterization of mixability in terms of the sliding freely conditions of superprediction sets. In Section 5, we provide some additional comments and remarks, and provide a bridge between our results and those in van Erven al. (2012).
1.3 Setup
Here we summarize our setup, for more details see van Erven et al. (2012). Denote by [n] the set of natural numbers (I,...,n} The set of probability distributions on a finite set y with [ E N is given by
A (mI.....P)) Pm)
p: = 1, 2 0, for = 1, 1,..., E T Σ t=1
(1.1)
We note that A a manifold with (non-smooth) boundary of dimension n n-1. Moreover, A is a hypersurface in IR;; we denote the interior (as a manifold) of A as int(A") which is the same set as the relative interior relint () of A We define the standard parametrization of A as the map Dsdd Sa-1 =-=11 A given by
n
(1.2)
where Sn-1 {t), ( tn-) E 1- Σ 4 1,4 0, for i == I,.... n n -1].
In particular, when n = the standard parametrization of 2 is the map Derd: [0, - A given by (L) = -1.
Definition 1.2. A loss function is map l: x - R2zo such that for each k y, the map El.,k) A R is continuous.
Given a loss function f, p E A and & E V, the value ((p, k) represents the penalty of predicting p upon observing k. We define the partial losses of a loss function l as the maps 4, A - R20 given by (p) = E(p, i). A loss function can be described in terms its partial losses as
n
e(p,k)
Σ bk = (e)(p)
Thus, we can identify a loss function é with the map e: A R2 determined by its partial losses
{(p) = (o,
In this work we follow this convention unless stated otherwise. Note that this way we can see a loss function as an embedding of int (A") into Ry (assuming enough properties on E). We will see later that properness ensures the image of this embedding to be nice hypersurface of R. with appealing geometric properties. Under the assumption that the outcomes are distributed with probability p A", we make the below definitions following (van Erven et al., 2012; Reid & Williamson, 2010).
4

---

Published in Transactions on Machine Learning Research (09/2023)
Definition 1.3. Given loss function e, we define the conditional risk the map L: A A
R as
Lp,.g) = (E(4),
and the associated conditional Bayes risk as the map L: A - given by
L(p) inf QEA"
Lpp Q)
inf (l(g),
qEa"
Definition 1.4. A loss function e: A
20 is said to be proper if for any E A
p inf Lpp q)
9Ear
for all E A", In other words, L(p,)) has minimum at p. When is the only mänimam of L(p,-) we say that l is strictly proper.
Proper losses are the natural losses to use when predicting class probabilities they are such that perfect prediction is not penalized; for further discussion of why they are important, and additional references to the literature, see (Buja et al., 2005; Williamson & Cranko, 2022; Williamson et al., 2016).
For our geometric considerations it will be useful denote the image of A under by Me, and impose enough differentiability conditions l so that Mt is (at least) -2-manifold. See Definitions 2.1 and 3.1 below.
We now recall the definition of mixability (see for example, (Vovk, 2015; van Erven et al., 2012)). For > 0, let E,; E. - R= be the e-eroonential projection defined as
Ey (e 1 e 18m).
(1.3)
A loss function l is called mimizable if the image of its superprediction set, spr(e), given by
there is E A such that ((g) S x for i E [n]] spr( = { E [0, "
(1.4)
is convex under the eeexonentiall projection, that is (spr(()) C [0, 1]" is convex. We say that mixable if is 1-mixable for some 1) >
Definition 1.5. Let l be mizable loss function. The mixability constant of e, ne is defined as
Te sup {n > 0 is m-mixable). 7>0
1.4 Motivation
In this part we mainly discuss the case n = since it more intuitively accessible. It has been made evident that there is a strong relation between properness and mixability. Here we make this relation more explicit and transparent from geometric point of view. The basic motivation is as follows. that properness is a property that depends on the parametrization of the boundary of the superprediction set of l (Vovk, 2015). It has been also shown that it is related to the "curvature" of the Bayes risk, since it requires that the superprediction set remains convex under the reexponential projection given by (1.3) (with the standard parametrization of the simplex A (Buja et al., 2005; Reid & Williamson, 2010; van Erven et al., 2012). Mixability is considered to be stronger notion of convexity (Vovk, 2015), for some > 0. The basic observation in this work is that it is possible recast properness from a geometric point of view, i.e,, independent of the parametrization of A More precisely, we define properness in terms of the loss function viewed as a map l: A -> TR rather than in terms of the superprediction set spr(4) (as is usually defined). More precisely, to determine whether a given é is proper or not, is not enough look at image ((A") (as the boundary of spr(f)) but rather how A is mapped into B% by & - since we will be using tools of differential geometry, we will assume C differentiability (see Section 2). More precisely, restricting first to n (see Lemma 2.7 below), given loss function e: A - -RR will be (strictly) proper if and only if
commonly understood
5

---

Published in Transactions on Machine Learning Research (09/2023)
A 2
l2
Figure 2: Consider the two loss functions given by (P1, = (-log(p1) log(pz)) and (2), (=1og(p2), log(p))), for p = (21,P2) E A Although spr(f1) spr(E2), la is not proper since the normal vector at (p) not #p/lpl for any p E A
1. the normal vector to ((A)) at {(p) is equal to +p/lpl for all E int(A?), and
2. the curvature (see Section 1.5 below) at any point {(p) with respect to the unit normal vector = p/ppp is strictly positive for all E int(
As observed in Figure 2, spr({1) spr(E2), which implies that their boundaries coincide (as a set). In particular, this implies that it is possible to "parametrize" the boundary of lg (Aa)), (((2(A))), in the same way (A)) in order to have proper loss. However, note that this changes the map & and hence from the point of view of this work, this is different loss function. In practice, one is given loss function l rather than a superprediction set spr(2), therefore we look at losses as individual maps from A to I22 instead of looking at their superpredictions sets and obtaining a proper loss by choosing a convenient paramctrization of ((spr(e)).
Remark 1.6. Our strength by characterizing proper loss functions in this way is that we will be able to apply techniques from differential geometry, however, these considerations only work for loss functions which are sufficiently differentiable. For a general set up, it is possible to characterize properness of a loss function in a fairly simple way via the converity of its superprediction set. More precisely, the "loss surface" " the subgradient of the support function of the superprediction set. This was thoroughly studied by Williamson & Cranko (2022). We briefly explore some connections to our work in Section Alternative approaches to exlending and better underslanding mizability include (Reid et al., 2015) and (Mhammedi & Williamson, 2018).
1.5 Comments about the curvature of planar curves
The second condition for l to be proper mentioned above involves a condition on the curvature of ((in((A)) We now make this notion precise. Recall that (tt) = (a, =2())))))) C² curve with a' = (af af(()))))) (t)) # (0,0) for all in its domain, then its curvature be seen a measurement. of the variation of its unit normal

---

Published in Transactions on Machine Learning Research (09/202))
nc
n
Ilc
I1c
a'
Figure For a regular curve a, at each point we have two normal unit vectors.
vector at each point. We define the canonical normal vector at a(t), (t), as the unit normal vector in the direction obtained by rotating a' 90º counterclockwise. Then, the signed curvature of a at t is defined
Ka (a(t) -
(1.5)
(1) 22))))22(1))))))
The interpretation of this number is as follows: (t) is positive if a "curves" in the direction of (t). However, note that each point we have two normal vectors: (t) Thus, nt and Ka depend on the direction of (i.e., a'), and their values differ by negative sign. Thus, we can talk about the curvature of a with respect to chosen unit vector (either choosing n -n for all points, assuming this is possible, which is the case for the curves we will consider here, see Figure 3) and denote it by Ke. In the case when n = n², then not = Ka, and when (up to a sign), we can simply talk at the curvature of a at a given point in the image of a. In Section we make precise our choice in (2) above. For a summary of geometry of curves see Appendix A.
-n', then N = -Na- Since Ka is invariant under reparametrizations
Going back to loss functions, suppose L: A - R2. parametrization around a point (of its interior) can be assumed to be of the form Φ: (a, b) C - - A for some < b. Thus, the local expression of l under this parametrization ~ = & is a curve in R2. By changing T around the same point, we are reparametrizingg t. Since curvature is independent of coordinates (i.e., of the T used) up to a sign, we can define the curvature of the loss curve (iit(A²)) with respect to a chosen unit normal vector (which will depend only on e). To compute it from its definition in (1.5), we need to choose a parametrization T and as we will see, many times it convenient to take Pstd-
a loss function. Since A is a 1-manifold, any
Remark 1.7. One could avoid part of the technical complications above by choosing beforehand $ Lstd, it is usually implicitly done, and then requiring & and lg to be monotone (ef. Buja et al. (2005); Reid & Williamson (2010); Shuford et al. (1966); Vouk (2015)) essentially, this amounts to choosing "direction" for the admissible loss curues. Although this approach is appealing since the curve parameter (t in our case) can be directly interpreted as a probability, and moreover it simplifies calculations since in this case the convention can be chosen so that the signed curvature coincide with x+ (see for example Vook (2015)), when considering the multi- class case, the notion of "direction" breaks down and is not clear which properties of M, = {(A") one should consider. The approach we consider here gives a concrete logical path to generalization the multi-class case (see Section 9).
1.6 Reconciling this point of view with previous works
In this part we explain how to "translate" the results we obtain here to previous results regarding proper losses and mixability. We do this in particular with (Reid & Williamson, 2010) and (Vovk, 2015).
7

---

Published in Transactions on Machine Learning Research (09/2023)
(Reid & Williamson, 2010) Let + Dstd- The parameter f in (Reid & Williamson, 2010) corresponds to the parameter t here, & (77) and (-) correspond to (t) and (2))), respectively. Although the regularity assumption in (Reid & Williamson, 2010) is initially only differentiability of the partial losses, when discussing the weight of loss function they impose C² regularity. From (Reid & Williamson, 2010, Theorem 1), we see that a loss l is proper if (in particular) {-1 > 0 and lg < 0. We can heuristically say that l goes from "right" to "left". This means that in this case, ki ( -x) The log loss in this case is llog
(n)) - In(1 ()).
(Vovk, 2015) In (Vovk, 2015) the loss functions are defined as maps (Ao(p), A1 (p)), with A increasing and A decreasing (infinite differentiable). In this case, heuristically, losses go from "left" to "right" that <x (p) (p). To relate this convention to ours, we set (t)) (1 t, t). Then the parameter p in (Vovk, 2015) corresponds to and X and A correspond to & and Ez. The log loss is then given by A(p) = (- - p), - In()))
Therefore, from our point of view, in previous works there an implicit choice of a parametrization of A?, particularly motivated to interpret the parameter as a probability. However, sometimes this might not be the case and a link function is needed (Reid & Williamson, 2010) this fits well with our approach as a link function for us is a different choice of parametrization; this will carefully explained in Section 2.7. In favor of the study of loss functions using tools from differential geometry we are then motivated to eliminate this choice of parametrization and consider l as a map between manifolds (namely, (A? and (int( as a submanifold of IR?). Although picking a general parametrization of A complicates the interpretation of the parameter, it makes other properties of loss functions transparent. This approach has, to the knowledge of the authors, never been explored. We remark that, however, one can always set $ = Berd and reinterpret the results of this work the parameter being a probability. With this geometric characterization of loss functions and properness at hand we continue to study mixability.
2 Properness and Mixability for Binary Classification
We first restrict our discussion to binary classification, i.e., setting = 2. Thus, we consider maps f: 2 - 12200 where A = {(11, E RR P1 + P2 = 1}, with partial losses (p) and (z(p). In this case the standard parametrization of A is given by (t)a(t) (t, t) for t [0, 1]. When parametrization of A say Φ is chosen, then the local expression of with respect to + (E = b) is a map from some interval I C IR to R², that is, a curve in the plane I.2.
Dating back to (Haussler et al., 1995; Vovk, 1998) it has been established that properness of loss function imposes strong conditions the first and second derivatives of their partial losses. In (Vovk, 2015) these relations were expressed by means of the curvature of the loss curve. Moreover, in (Buja et al., 2005; Reid & Williamson, 2010) properness is related to the second derivative of its Bayes risk, which in a way can be interpreted as its curvature. However, in these works there is always an implicit choice of parametrization of 2 which turn imposes certain restrictions on the "admissible" loss functions, particularly making the results parametrization dependent. In this section, we first recast properness as a geometric property which allows us to obtain results in parametrization (or coordinate) independent way. Definition 2.1. An admissible loss function is map & A R23 such that
R22 is a 1-manifold of class C? (1) (int C 20
(i) there exists O map n: ((in((A2)) + Ne(int(A3),, n(((p)) Ib(()), where Ne(intA?) is the normal space of E(int22), and
(mi) n((())) or -n((p)) belongs to R2, for all p E int(
We denote the set of admissible loss functions as L.
Remark 2.2. We give the following interpretation of the previous definition. (i) simply says that the loss curve (once parometrized) is twice differentiable with continuous second partial derivatives. (ii) prevents some
8

---

Published in Transactions on Machine Learning Research (09/2023)
"anomalies" on for erample, can not be constant neighborhood of point. (tit) defines subfamily of loss curves which are not allowed to vary "too much".. This definition should be compared to the definition of loss functions in (Vouk, 2015, Section 2).
Definition 2.3. Let E L. Let n: ((int(A3)) (e(int(A2)) be the map that assigns to each E(p) the normal vector to Mj at E(p) that lies in RR20 We denote by NT (.) the signed curvature of with respect to the unit normal belonging to 20 We refer to (-) as the curvature with respect to the unit normal vector pointing towards R22 20'
2.1 Proper losses
Lemma 2.4. Suppose that i in L is strictly proper, then the signed curvature of the loss curve {(A>) has sign. Moreover, its curvature, Ke, is positive with respect to unit normal vector (field) pointing towards IR2
Proof. Let po in) and let 4: I CCR-> A be parametrization of A around Po (to), for some to I, which we use to obtain parametrization of A x A around Po), We consider the local expression of L given by
E(t, (e o (())-
Using strict properness we know that fixing t, the function [(t,-) achieves a minimum at (and it the only one), that is
0 = (t 0=0 = ())
(2.1)
0 < 0.0 ()) = =
-((0)(())))))))))))))))
(2.2)
compute the sign the signed curvature {(A?) it is enough to determine the sign of (1)
Without loss of generality, assuming Φ + on this coordinate neighborhood we can write
7 (t)
(1(())
22(()
(t) [t))) (2)))
22(()
(t)
(t) (())), .(t)) > 0,
where we have used (2.1) and (2.2). Notice that if 2 (t) = 0 for some t then necessarily ()()) = 0 by (2.1), which is impossible in L. Therefore e has sign and this sign determines the sign of the signed curvature of ((A)).
For the second statement, notice that again using (2.1) we know that and &g have different signs (and they do not change). If & > 0, then that means that the first coordinate increases and the second decreases, hence n(t) points towards R2 and <=> 0. If E < 0, then are in the opposite and in this case n(t) points 0, thus the signed curvature with respect to -n(t) (the unit normal pointing towards R2,)
to RR3 and <, is positive.
From the proof of the previous theorem we obtain the following corollary.
Corollary 2.5. Let E L. If l is proper, then p int(A?) is normal to the loss curve ((A2) at l(p).
Proof. It follows directly from (2.1), since for fixed E int(A?), (e(g), p) attains a minimum at
Notice that this particular choice coordinates around (po, Po) suffices since want conclude something about the curvature of the curve loss

---

Published in Transactions on Machine Learning Research (09/2023)
Lemma 2.6. In L, proper implies strictly proper.
Proof. Let p E int( and suppose that there is p" # p E int(A?), such that
(e(p"), inf (f(g). p)- gea?
Using (2.1), we see that p" is normal to at E(p), and hence and p are parallel. Since both belong to A?, it follows that p" p, which a contradiction.
Therefore, in what follows (as long we stay within L) we will use proper and strictly proper interchangeably.
Note that the converse of Lemma 2.4 does not hold. That is, there are E & which have positive signed curvature (with respect to the unit normal pointing towards 180)), but are not proper. Indeed let be defined as
{pp) (- In(2)), In(1)).
Taking the (standard) parametrization Est (t) = (t, 1 - () we see that the loss curve ? goes from left to right so ((t) points towards IR? 22 Moreover, we can readily see that the (signed) curvature Ky is positive. However,
sta (t) is not normal to l at É(t), thus by Corollary 2.5, l can not be proper.
Therefore, we obtain the following characterization of proper losses in L.
Lemma 2.7. Let E L. Then & is striclly proper if and only if p is normal to the loss curve E(A2) at l(p) for all E in) and the signed curvature of E(A²) with respect to the normal vector pointing towards IR2 is positive at all points t(p) for p E int(
20
Proof. The "if" part Lemma 2.4. For the "only if" part, let E L be such that
Dp + P lpl
(2.3)
K 0,
(2.4)
where o is the signed curvature of & with respect to the unit normal pointing towards R22 Let E int(A?) and let & be a parametrization around p. We readily see that (2.3) implies that
a,ī(t, s)
while (2.4) implies (t, s)la=t > O by the proof of Lemma 2.4. This implies that fixing t, L achieves its minimum at s = t. Then is proper and by Lemma 2.6, we conclude it is strictly proper.
Remark 2.8. Notice that to check whether a given loss function E E L is proper or not, it suffices to do it in any coordinate system. That is, given Φ, we check conditions (2.3) and (2.4) for i -o $.
2.2 Mixable loss functions
We say that loss function is fair if (p) -p) as p-> (0,1) and (2(p) as p - (1, (this is motivated by the interpretation when using the standard parametrization, Reid & Williamson (2010)). In addition, recall that a loss function e E L is proper if and only if
(i) Dt(p)) [e can be chosen, and
(ii K (p) > 0
for all p E int
Thus, prototype of fair proper loss function shown in Figure 4.
10

---

Published in Transactions on Machine Learning Research (09/2023)
A 2 l
S
l = lo
(a, C
Figure 4: Prototype of a mixable fair proper loss function.
Recall from Section that mixability is defined in terms of the superprediction set spr(() of t. More precisely, for > 0, consider the map
(11 1/2 (e (mn
7711 -e ,--)))
where E,, IR220 - [0, 1]2 the exponential projection (1.3). Then, e is r-mixable and only (spr(()) is convex.
Remark 2.9. We stress the fact that this definition depends on the superprediction set of l rather than on itself two different loss functions with the same superprediction set will be equally mizable. From our perspective, when tolking about mizability of the map (i.e., without making reference to the superprediction set), we see that we define it follows. A loss l is mixable if the 1-dimensional manifold E, (i)) has signed curvature E S O. We will adopt the latter version here. Although clearly these definitions are equivalent, it useful to have this at hand to relate mizability with properness. For now on, when we say E is mizable mean in the latter way. See Figure 5.
We close this part by describing the log loss, which will play an important role. Let biog: A2 R.2 given by
(p) = (- 1-(np))), - In(p2))
(2.5)
Let Φ- Fstd- Then
Aog = (-In - In(1 1))
Since (t) = (---1,(1-0) its canonical normal vector is
(t))(t) Vta + (1 - t)2 ((1-t)-1,t-))
The curvature with respect to -
(t) the normal vector pointing towards R2 is then given by
1(1 > 0. 1)2)3/2 (1-
x²t flog
Kew Esox
(2.6)
+ (
When there is risk of confusion we denote nat Eiog
simply as n
11

---

Published in Transactions on Machine Learning Research (09/2023)
Se
A 2
l
Em
(a, C R
(0, 1)
(S,)
(0,0)
(1,0)
Figure 5: Diagram depicting how convexity of (spr(()) is characterized by the principal curvatures of E, ((in((A3))
2.3 Mixability and curvature
Haussler al. (1995) gave characterization of the mixability constant of mixable proper binary loss function & in terms of the first and second derivatives of its partial losses. We reprove this characterization from a geometric point of view, that is, independent of the parametrization chosen for A
Let E C be proper and & a 1-chart parametrization' of 2 then E, (spr(()) will be convex if and only if the curve (t)) = Et)()(t)) has negative curvature with respect to the unit normal pointing towards R20- assume without loss of generality that ke(p) x (p) 0. We then interested in computing the signed curvature of
Since l is proper
g(t) = (en (1), = (B((())) (e (e- (1)( ( nFa(t))
and showing that Kg 2 0. We have
o (t) (t)e (1)
(t) = (t) (T)( + (t)² (0)
ne 17i(1) [t)] -t)
and
82(t) -t
4This means that the map D - 2 such that ((D) 2
12

---

Published in Transactions on Machine Learning Research (09/2023)
g²(1) = n2' 12(11) (12
ne 1l2(1)
and thus we have
(di(1)² + 5/)())))))) kc(() = (1)(()) (1)e -2,(1) (6((1) (122(1)² - {(0]
n/e (1)
ne (1) -2((0] (-n6((0)e -B((t))
= 22 (t) -pa(0)
(((())(()) - (1)))(())) -((0)(())++((0) (1))0-((0)))))
=n n (1) -x2(() (0)(1)))()
- (0()) -
Note that the sign of & 22) is the sign of Kz. If Ny positive, then check that (t) 0 and (4) O, thus the first term in brackets is necessarily negative. Thus by making n large (tg(t) will become negative. Then we want
ZOG ((() +
- ()0) ((0)) 20,
that is,
- n (-)00(())00)- (t))
When considering the case when the signed curvature is negative, we have:
Lemma 2.10. Suppose that & E L is proper loss function. Then, if l is minable, for any 1-chart parametrization t of A the mizabilily constant is given by
-000020000
inf LE LE (In)
(2.7)
102000 (())
Conversely, (2.7) holds, then & is mixable with mizability constant n7.
By the local nature of curvature, it would be possible to consider a "local version" of Lemma 2.10, which would characterize a "local" notion of mixability. This alternative will not be pursued here.
Vovk (2015) observed that mixability for proper losses is equivalent to a quotient of curvatures being bounded away from zero. For the reader's convenience we prove this statement. To recover Vovk's statement observe that the properties he imposes the loss functions imply that x is the signed curvature (see Section 1.6).
Lemma 2.11. A proper loss function l E L is micable if and only if
Kr (p)
inf
0,
1og (p)
where migg denotes the curvature of blog- Moreover, when this holds,
mi inf
log (p) 0,
Proof. By Lemma 2.10, l is proper with mixability constant ni > 0 if and only if
-
inf (E0-1())(A2))
((((()))) (,(1))
13

---

Published in Transactions on Machine Learning Research (09/2023)
for any given 1-chart parametrization Φ. Setting 4 Pstd and using (2.6), we have the following. For any E $ (int(in)))))
2 -0000000000000
((())((()(((()))))))))))))))))))
(111)) + (1)3 3/2
3/2
(t)) (t)
(1-1}²
1
+ 82
t) 82 N/2 (t)
(G00+22(1)) +002)) 3/2
3/2
1
(1- + #1)
1
(1-t)2
82
8 (t)
(2(1)) + (1))
3/2
(1-1)a
(1)
(1-1)= +
(2))) (c) (t) - (()1
3/2
RI (t)
(t)) 1 + 12
1-102 vz
1
(1-1)²
8
kJ (1)
(+(1-))²
(1) +5)
FLOK
([1-t)=
k.t (L)
(t)
Blog
where we used that by properness (t())= = - (see (2.1)).
Since xt is independent of the parametrization, we obtain the result.
Remark 2.12. Lemma 2.11 ezemplifies the usefulness of Pard. The curvature of loog easily computed with respect to the slandard porametrization, by ftaing $ Laud we can easily recognize when the curvature of l appears in our computation. However, since curvature is a geometric quantity know this relation between curvatures will hold for any other parametrization well.
Using this point of view, the following observations enlighten why the weight function in (Buja et al., 2005) and in (Reid& & Williamson, 2010) basically encodes all the relevant information in the binary case. Recall that given proper loss function f, the weight of & (with respect to a local parametrization & of A?) is defined as
we (t) = (t)
= (t)
(2.8)
(1)
1 (
We stress that the weight depends on the coordinates & of that we use, and hence we use the notation lg. As observed in Remark 2.12, we sometimes set o Pad (as is done in (Buja et al., 2005; Reid & Williamson, 2010)) to be able to recognize some terms.
Lemma 2.13. Let l E L be proper loss and & a local perametrization of 2 denote by Eo its local expression and by We, be its weight. Then we have for any t E $ (int(((A))))
3/2
kt kt())
(L)
{{((1)
wed (t)
(t)2 (t)
and moreover, if X is another proper loss,
(t)
Wha (t)
Eo
(2.9)
(t)
(t)
In particular, when + &htdd
3/2
1
kt (t)
Eard
wena (t)
t + (1 -)²
14

---

Published in Transactions on Machine Learning Research (09/2023)
and if in addition, X flog (with +- Pstd),
k- (t)
Extd
1
1
WEsok (4)
(2.10)
k (t)
Weesd
(1) ((1 t)
Weadd
flog
Proof. Let L: A 22 be a proper loss and let be any parametrization of A around p. Let us compute et (assuming w.l.o.g. that nt t which means & 0 and & <0). to
kot (t) (1))(()) (1))) (1)
3/2
11(t)
(1(tt)
-3/2
(1)) 211())
(t(
GO) 1 ((0))(()++++))))))))
(1))))
-3/2
22(()² +1
22(1) (1)
(1)) 1
(t)2
3322
(0000()++(0)))))))
+1
(2(+) e (t)3
@2(2)2
(1) 1
(1(()(()) (0))) 2 (t) (t)
(t)2
(
-3/2
+1
22(1) & (1)3
22(1)
21)
1
(1)()) (((()) 2
2 (t)² + (2)
-3/2
(t)))
& (t)
(t
(t
1
(1)(())) 9 (1)
(t)
3/2
(2)))
(1)
(1)
$ (t)² + (
22(1)
3/2
(1(())2211) (1)))((1)
(t)
(1)2 + 22)2
3/2
1
+
wes (t)
Φ (t)2 + 22())
3/2
1 we, (t)
1
(-)((1)) (12 + (1)
(+2(())
(1)2 + & (t)2
where we have used that by properness know that (L),,, ((1) ((21)), which implies (1), (())
(t), & (t)) by differentiating with respect to from the third the fourth equality, and that y since (1) A from the third to last to the second to last equality.
Notice that in the last equation of the previous string of equalities, the only term involving & is 2 (or more precisely We (t)) and the remaining terms depend only on the parametrization $. Then we obtain
Whx (t) Wed (t)
(t)
The remaining statements follow from setting + Pstd and (2.6).
Remark 2.14. Combining Lemma 2.11 and (2.10), we recover the characterization of the mizability constant in terms of the quotient of weights obtained by van Erven et al. (2012, Section 4.1). However for the corresponding statement involving the quotient of second derivatives of the Bayes risks, the fact that A has
15

---

Published in Transactions on Machine Learning Research (09/2023)
offine parametrization is important. Indeed, this relies Corollary 3 in (Reid & Williamson, 2010) that states that w(t) = -L (t). In general, it can be checked that
(t) I"(1= $
l2())² ['()) =10===0(0((() (1+
3/2
k7((),
@ (1)2
which reduces to w(t) -I when = From the point of view of the present work, L (or a quotient of them) is not good quantity to consider since it strongly depends on coordinates. However, notice that if one restricts to affine parametrizations of A then L' (t) depends on & (1)² and ke(l) and hence in view of Lemma 2.13 restricting to fized affine parametrization of A will make quotients of the second derivative of the Bayes risk well behaved.
Let us remark some points about Lemma 2.13.
Let f: A - R be a given strictly proper, fair, loss function. Given a parametrization, we obtain a weight Wen given by (2.8), that is, the weight depends on the parametrization.
The curvature of is independent of & up to sign. However, when defining K we made the choice of the sign in uniform way, thus the curvature is independent of the parametrization for the family of losses considered here. Then it follows that the quotient of curvatures is independent of the parametrization and by (2.9), it also follows that the quotient of weights is also independent of the coordinates (despite the weights being coordinate dependent themselves).
A corresponding notion of weight in higher dimensions (for the multi-class case) is way more complicated and is unclear whether using them would lead to successful results. One higher dimensional analog of curvatures is readily seen to be the so called "principal curvatures" of a hypersurface in Euclidean space (see Appendix A). This will be the main motivation when dealing with the multi-class case (Section 3) Alternative ways to characterize proper higher dimensional loss functions have been studied in (Williamson et al., 2016).
2.4 Geometric comparison of loss functions
Fix a proper, fair loss function X: 2 - R?. Given another proper, fair loss function E + X, how might we compare them? From the point of view of differential geometry, since given p the normal vectors Xpp) and {(p) coincide, it is natural to look at their curvatures. Motivated by Lemma 2.11, we impose (for the moment) the condition
K (p) x (p)
inf PEA2
=1
Note that this implies that (p) 2 xx (p) for all E A We divide the comparison in steps for clarity.
(1) Expressing X(A2) as a function. Note that since is proper and fair, the normal vector a point X(p) can only be (1, when p = (1, (i.e., when evaluating at the boundary of A?). Thus, the set X(int( A A)) can be expressed
graph over the a-axis. To obtain an explicit expression let $ Pstd- We use the fact that d1 (0, 1) (0,4) (where I could infinity) invertible. Then, we have that
X(int(A3)) = {(x, f())) (0,4))
where f(x) =
(2) Translating and parametrizing ((A2). Let po E int int(A?) with x (po) > x (Po), such Po does not exist then L X. We define e0 2 - 2² by ((p) = {(p) [A(po) E(po)), i.e., we translate that it coincides with À at A(po)- (fo not fair anymore, however, the curvature is invariant under translations.)
16

---

Published in Transactions on Machine Learning Research (09/2023)
We now parametrize 2( the graph of function 9 defined on an interval To around zo (the x-coordinate of X( "aligning" it with À (we can assume this interval to be maximal). We let g(x) (()())) the northeast of f.
(()))((()) Since xj (po) > xx (po), we know that around zo the graph of g is to
(3) Comparison.
If the graph of g is to the northeast of f on the whole fo, then superprediction set of e is contained in that of X. If this does not hold, it means that there is E To such that ((11) = g(æ1), and w.l.o.g. we can assume > Zg. Thus we know that g(z) f(x) 2 0 on (co, 21] and g(x) f() = 0 on (z0,,1); i.e., the boundary of [i). Define the second order operator which computes the curvature of the graph (z, h(x)) (see (A.1)):
that the
L(h)(z) N (x)
(1 + 1'(x)233/12 h"
Since K (po) > xxx (po), we see that L(g - 2 0 on (ro, 01). The maximum principle now implies that the supremum of g - f is attained at the boundary on [ı0, and hence we know that f(x) g(x) on [xo, xiI, which contradiction. Thus the superprediction set is contained in the superprediction set of À (see Section 4).
More generally, if we assume instead that
ki (p)
inf
= 1),
PEA
xx (p)
for some 77 > 0, we see that (see Appendix A) that (p) = np(p)) satisfies
+ (p)
ki
inf PEAa Kx (p)
=.
That is, we can reproduce the previous analysis with ey instead of t.
The previous discussion motivates right away comparison between proper, fair loss functions.
Definition 2.15. Let A: A - IR20 be proper, fair loss in L, which we call base loss. We say that proper, fair loss L: 2 R² is mizable with respect to x if
7 inf
> 0. PEAR X (p)
2.5 Mixability and fundamentality comparison the log loss
Now, suppose l E C is proper and fair. Thus, in particular x (p) for all p e int(A2). We want to think of mixability as geometric comparison to the log loss as suggested by Vovk (2015) and give detailed interpretation of this comparison. We fix the standard parametrization of A2, & o aad: [0, 1] A given by
(t) (t, t).
The log loss in these coordinates is thus given by
(ox(t) = (- In((n, In(1 -t)),
and by (2.6), its curvature with respect to the unit normal pointing towards R,,, is given by
t(1 d(1-t)
nt (1)
Blo
(12 + 8/2
17

---

Published in Transactions on Machine Learning Research (09/2023)
Notice that not (t) 0 for all t E (0, 1) and n (t) 0 as t - 0 or t + 1. Thus, clearly by Lemma 2.7, for boo any proper subinterval C' [0, 1] (cf. (Vovk, 2015, Corollary 2)), we have
doog
x (1)
inf EEO
>0
not (L)
bsok
Thus, whether proper, fair loss function é mixable not will depend of the behavior of the quotient Net (p)/ at (p) p approaches (0,1) and (1,0). More precisely, we have obtained the following.
Lemma 2.16. Let E L be proper loss. Then l is mirable if and only if
Nig (p)
lim (0,(0,)
0, and
log (p)
Kit (p)
lim
> 0.
(1,01
Kiog (p)
Motivated by this we make the following definition.
Definition 2.17. Let l be proper, fair loss function in L, and + Bstd be the standard parometrization of 2 We say that is l (B1, -logarihhmee at the boundary if
kテ kt(()
lim
1
B > 0, and
(t)
Blo
B > 0. kt
lim
Let us analyze what this means. Suppose that proper and (B1, Bog-logrrithmic. Then for any t E (0, 1), using (2.10) in Lemma 2.13 and (2.8), we have
x (t)
1
kt (1)
(t) - (t)
Notice that as + 0+,
(BoR))(()
B lim
lim
+
(t)
t-
?7 (t)
and similarly,
(t)
B lim +-1- 1- 1-t (()
lim t+1
())
that is, only comparing the rate at which 4, i= 1,2, go to (since they do by fairness) with the rate at which the log loss does.
In (Vovk, 2015), Vovk defines a loss function X to be fundamental if given a (computable, proper, mixable) loss function À and a data sequence in Ç E 0 that is random under X with respect to a prediction algorithm F, then it is random under À with respect to F. He shows that fair, mixable & E L is fundamental if and only if (using the notation in (Vovk, 2015))
sup Ke(p)
00.
pE|O.1] Klog (p)
18

---

Published in Transactions on Machine Learning Research (09/2023)
Since we have seen that mixability can be regarded comparison of curvatures of the loss curve of l and that of blog and we have reinterpreted fundamentabilly as comparison of & and blog near the boundary building on Definition 2.15, we can easily come up with a notion of J-fundamentalitty
Definition 2.18. Let x be proper, fair loss function in L. We say that a proper, fair loss function & E L is A-fundamental if
l is mirable with respect to X, and
when 4 std, we have
ket (1)
lim
nCt(t) < 00
++0+
kt(
lim
< 00.
t11
x (t)
Suppose now that mixable loss function l E L is fundamental. Then there exist 7 such that
Kep (p)
S y
Mog (p)
for all p E int(A?). This implies that
n n (p) 2 N (p) and m (p) 2 ~ xp)( (p),
for all p E int(A²), which readily implies (Appendix A) that
nhe (p) 2 n (p) and nst (p) 2 (p))
for all p E int(
Rephrasing the previous discussion we have obtained the following characterization of fundamentality.
Theorem 2.19. A loss function l is fundamental if and only if there exist numbers 7) > 0, such that for any p int(A?), there translation vectors Tp and Up in R2 such that
spr(nk + xp) C spr(410g) C spr(yl Up).
2.6 Constructing new mixable losses from previous
We now observe how mixability helps us to construct new proper, fair and mixable functions from previous proper, fair and mixable losses. We first define a family of losses that will serve to illustrate the idea. We set +- std and loog- Let and define the loss function Xa: A RR2
20
X (p) a>(p).
It can be readily checked that K5. (t) = a 1xx (t), thus since
Kr. (t) T()) a
it follows that Aa is 1-mixable for < and it is not if a > 1. Note that lo is still proper and fair. Take then < 1, we can readily see that there exists a proper, fair an mixable loss function X such that
A= -
19

---

Published in Transactions on Machine Learning Research (09/2023)
Indeed, X X Xa Xl which is fair, proper and 1-mixable.
This process works in more general setting than scalings of X. Consider for example the spherical loss o defined in coordinates by
a(1) ( (1=(1-
V
It can be easily checked that this bounded, proper and fair and that (=((1= Thus
R (t) (t² + (1- 1,
xx (t)
1(1-t)
thus o is 1-mixable. Thus, as before, there is a loss function such that X o + Moreover, the loss function given (in coordinates) by
-(t)=(((n()))))) (In(t) - -1+ VF+(1-1)2" In(1 t) - Ve+(1-03
e" (t) X(t) -
which can be seen to be unbounded, proper, fair and mixable.
We close this subsection with the following observation. Suppose that is a proper, fair, mixable loss function with mixability constant 17 > 0. Then the loss function ( = ne is 1-mixable. Thus, there exists a proper, fair, mixable loss &e such that
Blg 0d +
As we will in Section 4, the previous observation can be interpreted from the point of view of the superprediction sets of the involved loss functions and convex geometry: spr(ne) slides freely inside spr(X) (see Theorem 4.23).
2.7 Composite losses and the canonical link
In this part discuss composite losses following (Reid & Williamson, 2010). Let recall their setting. Let V C IR be a set of prediction values. A link function is continuous map th [0, 1 V. Given a loss function ã: {0,1) x [0, 1] - R and assuming V = I, if vp is invertible, we define the composite loss d as
(3 v) = ē(v, (w)).
Definition 2.20. A composite loss σy is a proper composite loss if Ø is proper loss in the sense of Reid & Williamson (2010).
Recall that in (Reid & Williamson, 2010), + = atd is implicitly assumed. Then, given a loss function /
(in the (Reid & Williamson, 2010) sense), we can construct a loss function e: A - RR by e = ~ $ std Then, the composite loss dd can be expressed
et (ēo 1b (b)
(e o Detd o o (p)
= (e ( o t - (p)
In other words, the composite loss d is the local expression of with respect to the parametrization
Φ = o of 2 We denote the local expression of with respect to +b by Ø that is Ø = go P V1 =
ão -1
To show how this reconciliation terms work, we obtain result similar to Corollary 12 in (Reid & Williamson, 2010). Suppose that composite loss ~h is given and has differentiable partial losses (i.e., the corresponding
20

---

Published in Transactions on Machine Learning Research (09/2023)
loss o is in C), furthermore, assume that v is diffeomorphism which in one dimension means it is strictly monotonic. Then we know that @º is strictly proper if and only if is strictly proper (by definition). This implies that is normal to e( at e(p) for all E int(A²) and its curvature is positive (with respect to the unit normal pointing towards 20) This means for all v E V,
0 (ū'(v), (()))
(1)
+
(v)),
where we have used that & is a diffeomorphism and that 인 + 22 for all parametrizations & of A Therefore, we have
2 (2) (v)))))) = 2
that is
( (v) (v) (2 2 (1-11(1) (v-)
for all v E V.
Since we are working with valid reparametrizations the choice of will not affect the curvature of p. Hence we obtain
Corollary 2.21. composite loss Φ is strictly proper if and only if e E is strictly proper and xb satisfies
(xb (w) (2)(v~(()) - (
for all IR.
Remark 2.22. We have seen that whether a loss function é C is strictly proper or not, depends on whether conditions (2.3) and (2.4) hold not. Notice that under (admissible) change of coordinates, for ezample given by link v (2.4) will not be modified. However, (2.3) might change (since in way, we are changing the "velocity" at which we move on {(A2)). Hence, Corollary 2.21 is giving us a way to define the set of admissible links (or reparametrizations of A?) given a loss function and the standard parametrization of A this case, the new parametrization is given by +b Pstd ob
For applications, it is desired to be able to work with a given composite loss Th and moreover, to have convexity of the partial losses o. and oy From our point of view, we see Φh as the local expression of some e: 2 R. that @ o o (uand o 1)- (e Lsta) - To -1
Let us work with the partial losses separately:
du @v)) = =
_ @d()) = ( du
Proceeding in the proof of Lemma 2.4, properness implies
0 a,ī(u, v)lo=u
- (o))((
21

---

Published in Transactions on Machine Learning Research (09/2023)
or, equivalently,
0 ( (v)) (v) + 22 (v))
Therefore, we can define w as
0 (
(1
w(v) == w-
(2.11)
1
22(1)
where wy is the weight of ē we can rewrite the derivatives of the partial losses of
dē1 (v)= = -+)=)
dv
dØ du
(0) = (+)
Taking second derivatives we have
d2 01 (v) = - (w(()) 22()) - [w(v) Ø'((),
dv
d2 02
2 1) [w(v)( (1)) + (o(v)()))(w))) (y
A way to guarantee both expressions are positive as follows. Assume w.l.o.g. that (b- > 0. Since we are assuming w 0, Le increasing and @1 decreasing (also we have + is increasing and $ decreasing). We readily see that imposing
w(v)((->)(v)=
for all V E R, is enough to guarantee both second derivatives to be strictly positive.
Definition 2.23. Given L strictly proper, we define the canonical link vp as the link defined by
$ (w) 1 (w-
(2.12)
(v) w(v)'
for u E V, where w is defined in (2.11).
The differential equation (2.12) can be seen as separable ordinary differential equation, which is solvable for loss functions in L.
To give geometric meaning, we look at the norm of the velocity of the loss curve a(v) @(v).
la (2( (w)))( (v) + (2))]
By assuming (ss)(s))(()) and +- = V we have
Ja' (s) = @ ( +
Thus the canonical link gives a parametrization of 2 such that @ is a curve such that its velocity vector at v coincides with the length of the vector 2 (v)). In other words, it a parametrization the loss curve e(int(A²)) such that for e(p) = (()) E (i)))) the tangent vector at the point has length lp]. We close this discussion with charcterization of the canonical link.
Theorem 2.24. Let e be strictly proper loss function and db its canonical link. The reparametrization of e determined by its cononical link is parametrization of e(int(A2)) with weight equal to 1.
22

---

Published in Transactions on Machine Learning Research (09/2023)
Proof. Let @= 2o (Datd - ēo 1- be the reparametrization of e(inn(A3)) determined by the canonical link. Since
25(v) -
for all V E V, and from Definition 2.23
2 (26 3 (v)
(2.13)
()b)
for all v E V, we have
( = + (u)-
(v) 1.
Thus wv)
9 (v)
3 Mixability for Multi-Class Classification
Now we focus our attention on multi-class classification loss functions, that is, maps e: A Ra given by the partial losses
{(p) (4,
Our main goal is to interpret mixability a geometric comparison of given loss function l to the log loss, we did for the binary case. As suggested by the comments after Remark 2.11, the extra work of characterizing properness and mixability in geometric way (coordinate independent) will pay off since to carry out the comparison we will look at the scalar second fundamental forms of (()t(Aa)) and loog (on(ii(AA")) The scalar second fundamental form measures how a Riemannian manifold curves inside an "ambient space", in this case how ((int(A)) curves inside TR. (see Appendix for details).
The definition of (Definition 2.1) can be extended to higher dimensions.
Definition 3.1. An admissible loss function a map t: A + 1 such that
(1) (A") c Ro is a (n - -)-mniffold of class C²,
(ii there erists a C map n (int((A)) + Ne(int(A")), n(f(p)) = ne(p)) where Ne(int((A")) is the normal space of ((int((A))), and
(ii) n((())) or (e(p)) belongs to R for all p E int(A*).
We denole the set of admissible loss functions Ln, or simply L when the dimension is clear from contert.
We fix the log loss and denote it for convenience by = biog: A Th 20: as the map
(p)) (- -nnp:))).,,-((paa))
for = (pı,..., Pro) E n
Let L fn and consider a parametrization Φ: D C R0-1 a of A around p int(A"). The local
expression of the conditional risk (using the parametrization & of A A around (p,p)) is given by
ī(t,s) = (((s), Σ (t))
where (f1,--4n-1), 8 (81, (81, 8n-1) D and = lo +
23

---

Published in Transactions on Machine Learning Research (09/2023)
Imposing to be proper implies that when fixing t, is critical point of E(t,) -), that is,
0 -= 0=
[tt :e== (0., (tt, ((t))
for all i E i1,..., 1}. Note that since the tangent space of Me at E(t), (R)) is generated by (8o, ((t), ..., - {(t),, we conclude that (t) a normal vector. other words, as before, we have
n(((p) + ppl
for all p E int(A").
The fact that -tt,-) achieves minimum at (at interior points) is equivalent requiring that the Hessian, D2L, is positive definite at 8 = t. The Hessian of [(t,,) at = t is given by
[1 0,,, [tt, )1a (0 1 (())
The next step is to relate [D [ty((t to the scalar second fundamental form h of M, = ((A") (see Appendix A for its definition). More precisely, compute the h with respect to local parametrization & of A", iee, we obtain the matrix [hiy] representing h. To do this we need to compute the second derivatives of its parametrization i fo (Appendix A). Since,
0,.2(s) (0,,
we have
00 {(s) 00 (s), ..... 00 (n
The scalar second fundamental form (with respect the normal vector pointing towards R8x) is then given by
(s)(s) = h(0,, 8,,
0, ((s) (0²,, ((s). ({(()))
(0? (ss, (s)
1
(02 sjs, [(s){ ((s))
[((s) 1 [ ())
(3.1)
for i,j = =1,.., 1, thus if [D² is positive definite, then the matrix [hay]s) ) is positive definite. In this case its eigenvalues are strictly positive and hence, the principal curvatures of Mr at ((s) (see Appendix A), *it (s) (with respect to the unit normal pointing towards IRT))) are all positive. Therefore, using a similar reasoning as we did the case n = 2, we have obtained the following geometric characterization of properness (by following the same arguments in Section 2).
Lemma 3.2. Let E Ln. l is strictly proper and only if (e(p)) +p//pl and the principal curvatures of Me at {(p), K (p) (i=11 1,,,,,, 1), are strictly positive for all int(An).
We briefly explain how the comparison of scalar second fundamental forms will be performed. We follow a similar procedure as the one described in Section 2.4 for the case n = 2.
We establish that given a proper loss function & Lns around every p' E int(A"), ((int(A)) can be parametrized as graph of a function defined on neighborhood around some x* e F such that (x",((*))) E(p"). We do this explicitly for the log loss X.
24

---

Published in Transactions on Machine Learning Research (09/202))
n((int(A"))
n
A(int(A)))
H
Figure 6: Geometric interpretation of n-mixability.
Since and are proper, the normal vector to X(int(A")) and ((int(A")) at X(p*) and E(p"), respectively, p" /lp"). Hence we can identify their tangent spaces at these points. We do so and fix the parametrizations given in step (1).
By assuming r-mixability l, we look at the principal curvatures of E, (e(int(AA)) and prove an equivalent condition for them to be non-negative with respect normal vector field pointing towards E, (spr(()) (i.e., convexity). The condition to be satisfied is seen to be comparison of the scalar second fundamental forms of À and l that
recognize by step (1).
We interpret this comparison as follows. Since the tangent spaces to l(p") (and ne(p")) and X(p*) coincide for the chosen point p", if translate l to coincide to À p², call this tangent space H (and note it can be indetified with the supporting plane of the loss functions at the given point). Then if we express (locally) ne(int (A") and A(int(A")) over H, the graph of (e(in((())) lies above the graph of X(int(A")). See Figure 6.
3.1 Representing proper loss functions as graphs over Euclidean spaces
When restricting to the set of admissible loss functions Ln (n 2 2), we can represent losses as functions over R=-1 (a similar approach was taken in (van Erven et al., 2012); the difference relies on the fact that here we are after the comparison of second fundamental forms), which allows us to represent geometric quantities in a simple way. This will be useful recognize these quantities when comparing proper loss function l to the log loss X, did for the binary case in Section 2. Let E: A Rno be proper loss in L,, given by
{pp) (ca (p))
Let Φ: nn C 1R--1 - A be the standard parametrization of A given by
n
((s) ss)
81 ..., Sn
81
where 8 = -s1, 8n) E n-1 The local expression of ? in these coordinates is then given by ?(s) = (l (s), so that (s) (l: + (s). Also, we define the projection II: R - RR--1 I[yy,, Vn) = (4I, .... Un 1).
Recall that properness implies that the normal vector of Mt {(A") at E(p) can be chosen to be |p| p, for p E int(A"). As consequence, the normal vector never parallel to the hyperplane (I,))., E
25

---

Published in Transactions on Machine Learning Research (09/2023)
R" |² = 0}, that around any point {(p) with p int(A"), My can be written graph over 22 {0} (as regular Mt is). In general, the existence of this function is guaranteed by the implicit function theorem, however, in our case we can give an explicit description of it as follows. The function [I|M, is a map with injective derivative, say around E(g) for a fixed E int( therefore, the inverse function theorem ensures the existence (and differentiability) of a local inverse, which we can denote by M. This inverse map can seen as a local parametrization of My. Thus, the local expression of & (viewed as a map from A " Me), 8: D2 R=-1 - Ul(g) [R=11 (where the latter are small neighborhoods around o (-) and II(E(g)) respectively) is given by
{() = (II () = (s) (n-)))
This map is diffeomorphism and its inverse _ Ue(() - Du, will be denoted by
T (x) (t),
We warn the reader about this abuse notation, (x) is not the inverse of (s), it is a map satisfying
2; {s(s)
8, = 1, (x), (eo E (xx I,
( ())
We want to define f: Uz, - R such that graph(f) C MM. We see that setting Ul(2) C II(M)), so that it contains I({())), we arrive to
f(x) = (L, o ooo (x) (x)
(z)).
We have obtained the following result.
Lemma 3.3. Let l E Ln be strictly proper loss. Let q int(A"). Then there exists open set U c R x {0} and a function f: - Rzo such that Mt admits the parametrization
s (x) (z, f(x)),
around E(q).
Let l and f be as in Lemma 3.3. The unit normal vector field (pointing towards 1gy) is then given by
1
n n((x)
VIDf (-DS(x),
(3.2)
We proceed to calculate the scalar second fundamental form. The first and second derivatives of & are given by
O @ (x) = (ex, (x)())), 2mm 1 (x) (0, f (x)),
for k m = 1,.,, n-
where denotes the canonical basis of B and 0 is the 0 vector of Ra-11, Denote by he the scalar second fundamental form of Mr. Thus with respect to this coordinates we have
1
h (z) = (8rm T (x),, n' (x))
Fkm f(x),
(3.3)
2DD +1
for k 1,.., n 1.
26

---

Published in Transactions on Machine Learning Research (09/2023)
3.1.1 M, graph
Fix an arbitrary point q² E in)t(A"). The local expression of (with respect to the standard parametrization + 2td around q"' and II around {(q*)) is given by
X(s) = (- In(31)),.., In(8n-1)),
thus, we have
X (x) = =(e 31 ,..., e #n-1.
Fix 8" == =q- Thus, around x" = (T(AQq)) )), using Lemma 3.3, M, around {(g) can be described as $ x = (zx).
Moreover, in this case we have the explicit expression g(x) In(1 Eiel e...). Notice that X (x*) 5² We now compute the scalar second fundamental form h of at x².
03 1 (x)
Ck
f== E-
8kmE
e Thee
3mm $ (x)
0, 1
Einl
E xI
Σi= e
for k, m = 1,..., n 1 (here ppm denotes the Kronecker delta). In particular,
0x²)(=²)
ck:
=i
8
5km k
$ sm
2km (x²")
0,
+
Σi 8
(1 11
n-1
1==1
$7
for k, m 1,..., n 1, and since n(x*", ,((")))
(8", Σ 87) we have
V E "9y
97)2
h (x*) = (0km Φ (x()))x))))))))))("))) n((x", n((x",,(<=)))
(3.4)
1
81 mm
Jam * +
(3.5)
1- Σ iim 8
1 + (1 - 87)2
for k, m = 12...,1
Remark 3.4. Note that if instead of we would have used a translation of it, that ús, for c 12" define loss function sp: n R by
(pp) A(p) +
can repeat the previous compulation. The only difference is that we would have different point af instead
of z..
3.2 Geometric interpretation of mixability
Mixability is defined as property of the superprediction set of a proper loss E L. More preciscly, é is mixable and only if (spr(()) is convex for some > 0. As before, we can determine whether E,, (spr(f)) is convex by looking at its boundary (spr((())) = E, (f(Ar)). (spr(()) convex if the principal curvatures of (!(AA)) are non-negative (when defined with respect to the inner pointing normal vector) at all points. Since convexity is global property that can be tested "locally everywhere", it makes sense to make the following definition.
27

---

Published in Transactions on Machine Learning Research (09/2023)
Definition 3.5 (1-Mixability at p E A*). We say that l E Cn is 7-mixable at p int(A") if (Mee has non-negative principal curvatures with respect to the unit normal vector pointing towards (spr((()) at (e(p)).
Clearly, L E L, is n-mixable at all E iA" if and only if it is 7-mixable.
Let e E C. be strictly proper. First, we note that properness implies that the second fundamental forms of and @ can be compared the following sense. Given q"' A", note that the normal vector to M, and Mg can be chosen to be q" /l A translation does not affect the geometric properties of Me (since it an isometry of RT), thus we consider the translated loss el(a") A + R" given by
ola' =()))=)))>>>>))) [e(a") e(a")),
i.c., we translate e by the vector c" = >(q)) - E(q") so that both 8² and coincide when evaluated at q²: Doing so allows us to identify the tangent spaces to Marcor) and Me at ell9") = l(g"). We will call e the translation of e l(g").
Lemma 3.6. Let E fn strictly proper. Let he and hd denote the scalar second fundamental form of M; and Mx (the log loss), respectively. Then, E is m-minable p int(Ar) if and only if
((((()) ()p))
(3.6)
is posilive semi-deftrile, where he and h denole the second fundamental forms of l and X in the graphical coordintes described in Lemma 3.3. And therefore, e is n-mizable if and only if (3.6) holds for all p E int(A*).
Proof. Let l: A R be admissible proper loss
{(p) = (li(p), en (p)).
The 7eexponential projection map E IRn
R8th given by
Ey( = (e (e-
m8h ,..., e -V=)
Let q" E in" and write Me around E(g*) as the graph of a function f over _0-1 defined on an open set U.J containing x², such that f(x') = E(q"). We can directly give a parametrization of (Mr) around ((((")))) ((x fxx))) by
(x) (e - mp--1 -e--)_e--(((e)
We proceed to compute the second fundamental form of (Me) around (e(g")) (with respect to the inward pointing unit normal vector). The first and second derivatives of W are given by
a (x: = (-ne hek ek, - -n0
2mm (x)) (n² d2me 7F ek: - nf(=) + (=) -nf())
and noting that the (inward pointing) unit vector field is given by
((E)) Enn (z + e2nlle)) 1/2
(drf(z)e ,.., On (n -e7)(z)
Therefore, letting Ed = (U) ,U,)), the second fundamental form of E" at E, ,(()))))))) given by
h (x*) = -0km V (xx) ((("(()))))
28

---

Published in Transactions on Machine Learning Research (09/2023)
(n² km 1s Pick Σ (e es)xn- (e)
Σ n-1 0if(x*) ) + eanf(or)) 1/2
+n0km - - f (0m)) fmm
(Een (x c2n 1/2 @k + 8km 0kmf(x") - noxs (x') pm f(x=)(())))))))))())
Thus, since the convexity of E, (spr(e)) equivalent to the principal curvatures of E (Mr) being non-negative at q" for all qº int(A") (with respect to the inner pointing normal vector), this will be the case if and only if the matrix
Akm Ix= 11-ōkm Ox J (mm))m[(x")))
is positive semi-definite for all x* corresponding to q" E int.
Note that since have graphical parametrization Φ of M, around x² E U, have
Ox²1(x²) (ek, Ox Oxf("*))
and by (3.2).
a(x,ff"""
VDDf +1 (-Df(x"),1)
On the other hand, since the normal vector Φ (U) (a*, f(x*)) is 1 we have
<(<=,f(()))))
1
8 si...., s 1
Σ s
E (1 Em= 87)2
for s* E R such that (s*)) = q"
By properness we know that
0 10,00(20))) nn(x",((,, f()))))
n-1
8 + 0x)(x²)
[1 8,
1
Σニ (s;) (1 Ex= s?'2
thus
Oxf(x*)
k
1 - Σm
==
and also
nー Σ (07)2+ + (1 -n- o6
1 1= =1 Σラ (87)2
(3.7)
n- (1~
(1- 11ーEー1 n- 8
$
Using (3.3) and the previous observations, can rewrite the terms of Akm as
Ox=) DDD 1
(Dff(*))3= 12+ 2km f(x)
29

---

Published in Transactions on Machine Learning Research (09/2023)
1 E (03) (0g) (1 (1- Ei= )))n()))) h (2*
(1-> Di=1 81)
and
kkm $
$ sm
1- Oxf(x") + (0ff(")0mffaa
(1 2'
i== of
Now, consider the log loss and its translation to Elq*) which we denote by X to simplify the notation. That is, we have
X- =xp)) [e(a") -
As discussed in Remark 3.4, we can write Mx- a graph around x" (since X² E(g*)). The scalar second fundamental form of Mx- at (q") is then given by
h (x*)
6km
8m sm
(3.8)
V 2i=(()7)2 + (1 - En 87)2
1- E 8
This readily implies that
(-ommO + (xf((=()))))) (mm("")0mm(=²)] 1 Ei=1 8
1
(07)2
(1-Ei s:)
h (x*).
Therefore, l is m-mixable at q² if and only if we have that
["gl(=)) - nhh I(x))
is semi- definite. Since 4º was arbitrary the result follows.
Remark 3.7. The previous comparison of second fundamental forms is possible because properness forces the induced metrics by l and À to coincide al E(q") X (q"), that is, [ofy](=*) = L ((x*) (see Appendio A and Remark A.3). The conclusion of Theorem 3.6 does not necessarily hold if one takes different coordinate system.
In order to get geometric interpretation (i.e,, independent of coordinates) we note the following:
0 < [k(r((**) - n|4("" ((x))
= (115((=")99()) 1o - n 1(== (z"')
= (10 (x)) ( 1(2 1ot
[of)
The matrices [h]](( (x=) (1-")(<x*)) and [ [0=))a- are the local expression of the Weingarten map (see (Lee, 2018) for its definition and properties) of l and À respectively. The eigenvalues of these matrices are the principal curvatures of Me and MA (and they are independent of coordinates), and the determinants are their Gaussian curvatures. From here it also follows that
B M1 )ob ' (x*) [n (0 (2x
[()))) 1 1= (at) (=()
?
[1]] 19 |n 1 1x))
30

---

Published in Transactions on Machine Learning Research (09/2023)
that is,
[WT]] [ 2 0,
(3.9)
where W denotes the Weingarten map of the loss function t. Then once a system of coordinates around p E A " is chosen the relation (3.9) holds. A priori, the relation obtained between the Weingarten maps of and À does not provide much information, but it does points to look at the loss function n/e With this mind Lemma 3.6 does give a direct geometric interpretation as follows. Let L: A + 123 in L be a proper loss. Given point q E A" we know that around E(q), My can be parametrized with & (I) = (α, f for some function f around the point (({()))- Let x= = (((())) Consider now the proper loss Q = ne, for some 1) > O. We readily see that & can parametrized as (y) = (y, (v)) with
g(y) = nf (1 y), with g defined around y4 = nz. Now we compute the second fundamental form of e at vq. Notice that Agg())l=ma = f 1> = 0x*),
digg(v)lu=ne = (n x)) 17- 10: fz²
and hence,
hig (1z²) = hig (1z²²) = =n n 1z'x)'
Then assuming the hypothesis of Lemma 3.6, we obtain
(m=*") - h (xx) = 1 (zt*) - hxy" = =n n (h'(x*) - nh (x*)) 20 0.
(3.10)
The supporting planes at np(p)) and X(p) of Mnt (or more precisely, of its translation to X(p)) and My respectively, coincide (since the normal vectors are the same), we denote it by Hp. By looking at Mne and M2 locally as graphs over Hp, Lemma 3.6 gives the following comparison of graphs, which in turn can be regarded as local embeddability in the sense of convex geometry (see Definition 4.16 below).
Theorem 3.8. E f. proper is n-miixable if and only if for all p E in" the local graph of the translation of Tp to X(p) over the supporting plane to both Mt, and M2 at X(p), Hp, lies above the graph of X over Hp. Remark 3.9. Observe the resemblance of Lemma 3.6 to Theorem 10 in (van Erven et al., 2012). To recover the latter from our point of view we will first reinterpret Lemma 3.6 and Theorem 3.8 from a convez geometry point of view which will lead to nice bridge between Lemma 3.6 and (van Erven et al., 2012, Theorem 10).
4 Connections to convex geometry
In this section we reinterpret our results from the point of view of convex geometry. With this interpretation we can relate Theorem 3.8 results in (van Erven al., 2012) and (Williamson & Cranko, 2022). We first provide some background and state relevant results from convex geometry which are well-known and can be found in (Schneider, 2014) and can be adapted to our setting.
Let K C R be a convex set, that is
Ao + (1 (1 2) KK
for all r, E K and E [].
We define the recession cone of K as the set
rec(K)= = fx E R. : K + C K).
The boundary of K is denoted by aK, as since we will assume that 0K is a differentiable manifold we denote the interior (as a manifold) of 0K by iaK( As usual the scaling of K by n > 0 and the Minkowski sum of K and L are defined as
πk= {nk RD k]
(4.1)
K L (k +lER & ke L).
(4.2)
31

---

Published in Transactions on Machine Learning Research (09/2023)
Definition 4.1. Let K be closed convex set in R The support function of K, oKK, u): R - R, is defined as
o(K,u) = sup (z, u).
=Ek
We sometimes denote it as xx(u) = o (K,,)) From the definition we know that
NEK (y, S ox((u) for all E R".
From (Schneider, 2014, Section 1.7) we have the following.
Lemma 4.2 (Properties of o). Let K,K C In be closed conver sets.
σr. ok if and only C K.
oK +t, u) = oK,, u) + (t, u) for all E R..
3. o(K L, u) o(K, u) + o (L,u))
Definition 4.3. A function f: C R - RR is convex if its eatension to R2" given by
F(x) f(x), D 00, &
is convex.
The following lemma is well-known result (see (Schneider, 2014, Theorem 1.7.1) for example).
Lemma 4.4. Let f: R + R conver, closed and positively homogeneous, then f is the support function of the conver, closed set
K$ = (= (x, u) S (u) for all E ]
Definition 4.5. Let L, K C R and closed and conver. We say that L is summand of K if there exists convez, closed set M C RD such that K M + L.
We will be mainly interested in sets K whose recession cone is R hence we denote by K. the set of closed, convex sets whose recession cone is R220 In the following we extend some common results in convex geometry which are usually stated for closed, compact convex sets in Th" (Schneider, 2014), however, some of them are easily extended to 1CT (Shveidel, 2001).
Lemma 4.6 (Basic properties of sets in KCT). Let K, L E K. and n > 0. Then, the following holds:
(1) n E JC,,
(2) rec(K + L) 1200
(8) K + L is closed, and
(4) K LE
Proof. In order to show (1), we need to show that nKK closed, convex and rec(nK) R5 Let x, E nK
and > E [0, then have
Ax + (1- A)y 77>k + (1 (1-A)ky)
where x nk2 and y = nkk for some kz, ky K. Since K convex, then Ak + (1- A)kk K and hence n is convex. Let 2n K be convergent sequence that converges Then, there exists kiz, K such
32

---

++ C. Published in Transactions on Machine Learning Research (09/2023)
that 2n n/,..- Since is constant, {ka,} } converges to fe K (since K is closed). By the uniqueness of the limit, x = 1/20o0 nk. Now, let x E R want to show that r + C yk. Take any k K,
1 nk + k = nk
1)
since x E R Conversely, if ree(nK), then for any h1 E K, we have
m/1 + nk
then there exists 22 E K, such that n/1 + x = n/22 Hence
k + x k2
"
thus 1,2 E rec(K) 2o thus 22
To show (2), let æ E 2 We want to show that K + + L. Let K and & E L, then
++I+xERa ++
since / + x E L. Thus 3o C rec(K K + L). Now, suppose that there is a E rec(K + L) such that æ & R2 Since rec(K + L) is a cone, for all À > O, we have d E rec(K (K + L). Let &o E K and E L. Then
Thus ++ λ E ree(K)= R for all À > 0, but notice that this is contradiction since by picking À sufficiently large, 1+ λo & 1220 Thus rec(K K + L) = '2'0
For (3), see (Rockafellar, 1970, Theorem 8.2) and (Shveidel, 2001, Theorem 3.1). Finally, (4) is simply the combination of (2) and (3) (and the fact that K + L is convex).
We now specialize the discussion to a particular type of sets E K.. First, suppose that the boundary 0K is of class C², then each point z E i@KK there an outward pointing normal vector ux(x). Thus, clearly, gn-1 assigning ux(x) to int(@K). We define
can define map uk: iōK(
Rn = {at E R. I (2I, Fn), with x; S 0 for i = I,...,n..
so that
int R2 5 = fxr TR. x (I,,,..,I,,) In), with as < 0 for i = 1,..,, n2 Run =0-
Definition 4.7. Define C (KTT) as the collection of sets K E K with boundary θK of class C², and such that the map uk is C -iffeommorphism from iāK( to s g--1 n R
We now specialize some properties of the support function to (KC)) Lemma 4.8. If K E C2 (ICT), then dom(ax) ( (0}
Proof. Take u + 0 in dom(ax) then it must be an outward normal vector to int(aK), hence is in Sn-1 Then dom(ox) (R U (0). Now, for E R normalize to make unitary by letting v = u/lul, then S--1 and thus it must be normal vector form some E int(aK), hence the support function evaluated at v is finite, and in consequence αx(u) is finite too.
Remark 4.9. Following Schneider (2014, Section 2.5) the condition K E C2 (CC)) is equivalent to assuming the principal curvatures of θK to be non-zero. It also follows that
σ (w) 1 (u (u), u)
and moreover, σк of class C²
33

---

Published in Transactions on Machine Learning Research (09/2023)
Remark 4.10. Let l Ln be proper loss function. By definition that Remark 4.9 implies spr(f) E (KC) (since Mj = (sspr())))
Definition 4.11. Let K, E C (IC)). We say that slides freely inside K if to each boundary point x of K, there erists a translation vector t TR.", such that x E + C K.
Theorem 4.12. Let K ( L is summand of K, then L slides freely inside K.
Proof. Suppose that there exists M E (KT) such that K = L + M. Let E 0K. Then there are I E L and E M such that
I x= z=1+ m.
Thus, I E E + mm -
Remark 4.13. For a general conver set L, if L is a summand of K E C+.(C.) we see that the previous proof holds an we conclude that L slides freely inside K; nole however that this imposes restrictions on possible sels L. One of this consequences is that the principal curvatures of aL must be positive as can be seen from a second fundamental form comparison and Theorem 3.8.
Lemma 4.14. Let K, L E C2 (KT) and suppose that f()) xxx()) oL(-) is conver. Then the set
M = = ER" (z,, u) S f() for all u E R"),
is in (KT), and it is such that K = M + L, that is, L and M are summands of K.
Proof. From Lemma 4.8, the domain of f is R ( i.., f: R U { + R is convex. Thus it is the support function of M (by Lemma 4.4). That is, f(-) = a
Therefore have оM ок- o,, and hence K M L. Note that M is a summand of K, then using Theorem 4.12 we know that M slides freely inside K, and since θK has positive principal curvatures then 0M does too (Remark 4.13). Since σM is of class C², then M has to be in C² (KC))
Theorem 4.15. [(Schneider, 2014, Theorem 1.5.2)] Let D C Rh convex and let f: D - R be continuous function. Suppose that for each point E D there are an affine function on Rº and neighborhood U of To such that fxx) = g(zo) and f 2 g in D. Then f is conver.
Definition 4.16. We say that L is locally embeddable in K if for all æ 0K, there a ay E and neighborhood U of y, such that (LNU)
y K.
Theorem 4.17. Let K, LL (KTT) and L strictly convex. If L is locally embeddable in K, then L is summand of K.
Proof. Let uh E S and Zo E ÖK be a point such that u(zo) = un- Since is locally embeddable in K there are yo E L and neighborhood Uo of such that (LNU)) +oo- Do C K. Since u²²: g - OL is continuous, yo, un) -oo-oo-yo o o(K, uo)
there exists a neighborhood Vo of uo such that u (V)) Ug. Then follows that a aL++oo--00 and (L To yo, u) (K, u) for all Vo by Lemma 4.2.
Let f(-) o o(K, - (L, :) (this is defined on R7 U {0} and is positively homogeneous), and g(-) (x -. Then, clearly, we have
(i) f(uo) g(u)), since
f(wo) o oKK, un) o oLL, un) OK, un) aLL + g (4o).
yo, uo) + (x0 - yo, uo)
(ii) f on Vo,
f(u) = o(K, u) - σ (L, u)
oK,, u) (L + zo yo. u) + (ro No. 4)
2 g(u).
34

---

Published in Transactions on Machine Learning Research (09/2023)
It follows by Theorem 4.15 that f is convex, and by Lemma 4.14 we conclude that L is summand of K. ]
The following lemma is direct consequence of the characterization of mixability in Theorem 3.8 and Definition 4.16.
Lemma 4.18. Let l Cn be a proper loss. For 17 > O, if l is n-miiabbl then spr(ne) is locally embeddable in spr(A).
Lemma 4.19. If l is m-miaable then spr(nE) slides freely inside spr(A).
Proof. Let & be n-mixable, then Lemma 4.18 implics spr(ne) it is locally embeddable in spr(A). Then Theorem 4.17 implies it is a summand and Theorem 4.12 implies it slides freely inside spr(A).
Corollary 4.20. Let i be n-mizable proper loss. Then spr(né) E C (KCT) and it slides freely inside spr(A) (A is the log loss). Additionally, there ezists M E C2 (KC)) such that
spr(A) = spr(ne) + M.
Moreover, QM can be regarded as e(Ar) for 1-mixable proper loss g.
Proof. Since l is n-mixable proper loss function, rpl is also a proper loss function and hence spr(ne) C (KC)) (Remark 4.10). Theorem 3.8 implies that spr(nE) is locally embeddable in spr(X). From Theorem 4.17 we know that spr(ne) is a summand of spr(A), which proves the existence of M. As consequence, M is a convex set with recession cone R2 (Lemma 4.14). By applying (Williamson & Cranko, 2022, Proposition 21) we can regard 0M as the image of a proper loss function 2, which since spr(e) is a summand of spr(A) it is 1-mixable (Lemma 4.14).
We now state (Schneider, 2014, Theorem 2.5.4) adapted to our setting which will be helpful to relate our work to (van Erven et al., 2012). Theorem 4.21. Let K, (KT). Let hM (z) denote the second fundamental form of M at x with respect to u (see (A.2)). The following are equivalent:
(1) (x) h (y) for all pairs of points and y at which u(x) u(y).
(ii) ок oL is support function.
Since A an affine manifold, the geodesics A are simply straight lines. This allows to define convexity of functions defined on A in the usual way we do for functions on R". The following theorem connects and reconciles our results to those in (van Erven et al., 2012). More precisely, create bridge between results and (van Erven et al., 2012, Theorem 10).
Theorem 4.22. Let E Ln be proper loss. Let 17 > O, then n-mizable if and only if n-)(+) L²(() is convex on int(A"), where L!(.) denotes the Bayes risk of the loss function e (Definition 1.3) and denotes the log loss.
Proof. Suppose that é is a proper loss in Ln which is mixable. By Lemma 4.19 spr(ne) slides freely inside spr(X) and in particular hnd (2(p)) h^()))). By Theorem 4.21 it follows that spr((A) spr((ne) is support function with domain Rn U (0), in particular it is convex on its interior. Let u E Ien such that the outward normal vector of ((Ar) and A(An) at E(p) and A(p), respectively, is u. Then we have for x - E A",
spr((A) (z) - o (pe (x) = |=1(Gspo(s)(( - (xpr(ne)<//<x1)) |=]((A(p), x/|=|) - =r((p),=/1x1))
1p(((A()),-//1)
-p/p))))
(A(p), (ne(p), -P)
=-(X(p),p) + (nd(p),
-p)((p) + mL'(D)
which proves the claim.
35

---

Published in Transactions on Machine Learning Research (09/2023)
Suppose now that for given l E Ln proper, there exists 17 > 0 such that spr(ne) slides freely inside (A). Note that in particular this implies that spr(ne) is locally embeddable in spr(A), and hence for each p E int (A we have
h hhd - ( 20,
which by (3.10) and Lemma 3.6 implies that is n-mixable. Thus combining this with Lemma 4.19 we obtain the following characterization of mixability of proper (sufficiently differentiable) loss functions.
Theorem 4.23. Let l E fn2 be proper. & is n-mizable if and only if spr(nt) slides freeky inside spr(A), where À denotes the log loss.
In general, the set & provides family of loss functions with appealing properties. Arguably, one of the most important properties is that given & E C, if we assume that é is proper then we know its principal curvatures are strictly positive. This is a strong and useful geometric feature. For example, in (Williamson & Cranko, 2022) the notion of a "inverse loss" called the anti-polar loss was investigated. Given l a proper loss (in the sense of (Williamson & Cranko, 2022), which are not necessarily smooth), they consider the O-homogeneous extension (see Remark 26 in (Williamson & Cranko, 2022)), defined on B80 and given by
goxt (p)
P
11p1|1
where ||p||1 = P1 + ... Pr. For the following we simply denote eext by l. In (Williamson & Cranko, 2022, Proposition 29) it is shown that there exists a map 8 RB50- - Rg such that
Pn-
{(p) = (lo o (p) (x) = (1 o e (x),,
for all p, T0 The map e is called the anti-polar loss of l. For the family of admissible loss function L considered in this work, we exploit the differentiability conditions to obtain in straightforward way inverse loss defined on (()n(AA)). To see this, suppose that l E L is proper. Since this is equivalent to saying that spr(f) is in C2 (KTT,, meaning that the map Uspr(E) is C diffeomorphism. Then we can define the map g-1: ((in(AA") - in" by
e- (x) = (0spr(e) (Ir)
||uapr(e) (x))11²
which is the inverse of the map E: in" ((int(A")). Recall that Uaspr(e) (z) is nothing else than the unit normal vector (pointing towards 12 at x E ((int(A")).
It of interest of finding parametrizations (or links) that simplify the expression of a given proper loss l. At theoretical level there are potentially many ways to to this. Notably have at hand the notion of canonical link in (Williamson et al., 2016) (or see Section 2.7 above for n = 2). As an example of other ways to obtain nice links we have Lemma 3.3 above, which gives nice expression in coordinates (as the form of a graph) of l. Unfortunately, to obtain that results one makes uses of the inverse function theorem which does not provide an explicit inverse but rather its existence.
5 Conclusions
We summarize the main messages of this work.
Since mixable loss functions are of great importance in prediction games, it is desirable to understand them from different perspectives. Inspired by the work of Vovk (2015), in Section 2 we studied binary loss functions from the point of view of differential geometry, hence restricting to loss functions in (Definition 2.1). To do this, we re-interpret properness as a geometric property, namely, a loss function é is proper if and only
the normal vector (belonging to 1220) to Mr- (int(AA)) at l(p) is p for any p int(A?), and
36

---

Published in Transactions on Machine Learning Research (09/2023)
the loss curve {(int(A?)) has positive curvature (with respect to b
Having this framework at hand, characterized mixability and fundamentality of proper loss f E L, as curvature comparison to the log loss blog (ef. (Vovk, 2015)).
In Section 3, extended the geometric characterization of proper loss functions to higher dimensions, and obtained the corresponding interpretation of mixability as geometric comparison (now in terms of the principal curvatures of the "loss surface"). This comparison is done by using the second fundamental forms of the "loss surfaces".
The main goal of Section 4 is to re-interpret the geometric results in Section 3 from the point of view of convex geometry. The main result in this part is new characterization of n-mixability of a proper loss function E C, as spr(n() sliding freely inside spr({log) (in general dimension). This provides an intuitive and geometric way to interpret mixability.
Since the results obtained in this work are in terms of curvature, it was necessary to re-interpret well known properties of loss functions in the language of differential geometry. Although slightly tedious, this allowed the reconciliation of the results obtained by Vovk (2015) for and by van Erven et al. (2012) for 2 2.
Theorem 4.22 connects our results (van Erven al., 2012, Theorem 10) follows. In (van Erven et al., 2012, Theorem 10) the following statements proven to be equivalent:
(i) a proper loss l E L is n-mixable,
(ii) (H -HL (t) is positive semi-definite for all t E $ 2add (int(A")), where HF((t) denotes the Hessian of at 6,
(iii) (p) Loog (p) is convex on int(A"), and
(iv) (p) Ilog (p) is convex on & 3-d (int((A)
There, they first proved the equivalence of (i) and (ii), which is the result of long direct computation done very carefully. The equivalence between (iii) and (iv) is straightforward. To connect these two sets of equivalences, standard convex geometry is used to prove the equivalence of (ii) and (iii). Note that the statements (ii) and (iv) make reference to a precise choice of parametrization of A (i.e., the standard parametrization Lstd), therefore, the work presented here is naturally not related to these statements but rather to (i) and (iii), whose equivalence can be considered to be the content of Sections and Determining whether this new approach provides simplification of the computations in (van Erven et al., 2012) not, strongly depends the differential geometry and convex geometry background of the reader. This work should be considered complementing the understanding of mixable loss functions and providing new geometric insight into them.
Acknowledgements
This work was supported by the Deutsche Forschungsgemeinscaatt under Germany's Excellence Strategy EXC number 2064/1 - Project number 390727645.
References
Shun-ichi Amari. Information geometry and its applications. Springer, 2016.
Andreas Buja, Werner Stuetzle, and Yi Shen. Loss functions for binary class probability estimation and classification: Structure and applications. Technical report, University of Pennsyloania, 2005.
Manfredo P. do Carmo. Differential geometry of curves & surfaces. Dover Publications, Inc., Mineola, NY, 2016. ISBN 978-0-486-806999-0 0-486-80699-5. Revised & updated second edition of MR0394451].
David Haussler, Jyrki Kivinen, and Manfred K. Warmuth. Tight worst-case loss bounds for predicting with expert advice. In Computational learning theory (Barcelona, 1995), volume 904 of Lecture Notes in Comput. Sci., pp. 69-83. Springer, Berlin, 1995. doi: 10.1007 00000//3550--919--- 169. URL https:
37

---

Published in Transactions on Machine Learning Research (09/2023)
David Haussler, Jykri Kivinen, and Manfred K. Warmuth. Sequential prediction of individual sequences under general loss functions. IEEE Transactions on Information Theory, 44(5):1906-199) 1925, 1998. doi:
10.1109/18.705569.
John M. Lee. Introduction Riemannian manifolds, volume 176 Graduate Texts in Mathematics. Springer, Cham, 2018. ISBN 978-3-319-91754-2; 978-3-319-91755-9 Second edition of MR1468735].
Shahar Mendelson and Robert C. Williamson. Agnostic learning nonconvex function classes. In International Conference Computational Learning Theory, pp. 1-13. Springer, 2002.
Zakaria Mhammedi and Robert C Williamson. Constant regret, generalized mixability, and mirror descent. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL https: //proceedings
Mark D. Reid and Robert C. Williamson. Composite binary losses. Journal of Machine Learning Research, 11:2387-2422, 2010. ISSN 1532-4435.
Mark D. Reid, Rafacl M. Frongillo, Robert C. Williamson, and Nishant Mehta. Generalized mixability via entropic duality. In Peter Grünwald, Elad Hazan, and Satyen Kale (eds.), Proceedings of The 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pp. 1501-1522, Paris, France, 03 06 Jul 2015. PMLR. URL https://proceeding: mlr, www.ppees///ee........... Thees/v40/Reiii1 html.
R. Tyrrell Rockafellar. Convex analysis. Princeton Mathematical Series, No. 28. Princeton University Press, Princeton, N.J., 1970.
Rolf Schneider. Convex bodies: the Brunn-Minkousk, theory, volume 151 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, expanded edition, 2014. ISBN 978-1-107-60101-7.
Emir H. Shuford, Arthur Albert, and Edward Massengill. Admissible probability measurement proce- dures. Psychometrika, 31(2):125 145, 1966. doi: 10.1007/BF0228800 URL https://doot http///....og/1..1000.00. BF02289503.
Anna P. Shveidel. Recession cones of star-shaped and co-star-shaped sets. In Optimization and related topics [Ballarat/Mllbourree, 1999), volume 47 of Appl. Optim., pp. 403-414. Kluwer Acad. Publ., Dordrecht, 2001. URL https://doi.onn org/ 10. doi: 10.1007/978--1 977-1-4757-6099-6 19.
Tim van Erven, Mark D. Reid, and Robert C. Williamson. Mixability is Bayes risk curvature relative to log loss. J. Mach. Learn. Res., 13:1639 111699-1663, 2012. ISSN 1532-4435.
Tim Van Erven, Peter Grünwald, Nishant A. Mehta, Mark Reid, and Robert C. Williamson. Fast rates in statistical and online learning. Journal of Machine Learning Research, 16:1793-1888 1861, 2015.
Vladimir Vovk. The fundamental nature of the log loss function. In Lev Beklemishev, Andreas Blass, Nachum Dershowitz, Berndt Finkbeiner, and Wolfram Schulte (eds.), Lecture Notes in Computer Science, volume 9300 of Lecture Notes in Computer Science, pp. 307-318. Springer, 2015. ISBN 978-3-319-23533-2. doi: 10.1007/978-3-311 23534-9_22
Vladimir Vovk and Fedor Zhdanov. Prediction with expert advice for the Brier game. Mach. Learn. Res., 10:2445-2471, 2009. ISSN 1532-4435. doi: 01114//1390166139992222 URL 1390156.139091
1145/ 1145/
Volodya Vovk. A game of prediction with expert advice. Journal of Computer and System Sciences, 56
(2):153-173, 1998. ISSN 0022-0000. doi: https://doo.oorg/10..000m http://oo...rr/11..00///sss.../
URL attps://www.
com http:/acccttttooecec.e.ee/eeeaaa
Volodya Vovk. Competitive on-line statistics. International Statistical Review / Revue Internationale de Statistique, 69(2):213 248, 2001. ISSN 03067734, 17515823.
38

---

Published in Transactions on Machine Learning Research (09/2023)
Robert C. Williamson and Zac Cranko. The geometry and calculus of losses, 2022. URL https://arxiv. org/abe hrg/abs/20 wwtp:/229..000 00238.. arXiv:2209.0022 000388.
Robert C. Williamson, Elodie Vernet, and Mark D. Reid. Composite multiclass losses. Journal of Machine Learning Research, 17:Paper No. 223, 52, 2016. ISSN 1532-4435.
A Differential Geometry
In this part we provide a brief summary of the concepts differential geometry that are used in this work (we assume the reader has some familiarity with the topic although we try to put emphasis on the intuition). We do not intend to give comprehensive introduction to the topic. Most of the material can be found almost any differential geometry book, however, recommend (and when possible use the notation of) (do Carmo, 2016) and (Lee, 2018).
A.1 Curvature of Curves
A parametrized curve is differentiable map (a, + R", (a < b). We are interested in studying the geometry of parametrized curves. For this it would be useful to restrict our discussions to curves with well defined tangent line at every point att) for t E (a, b) (i.e,, with non-vanishing a' a'(t)) These curves are called regular. Let yp: (a,b) + (c, d) be a diffeomorphism, the curve 3 = ((((s)) is a reporametrization of a. Note that in this case a((a, b)) = (((c, d)). The image M = a((a, b)) a 1-dimensional differentiable manifold in R" (for this it essential restrict regular curves). The study of curves of particular importance since some aspects are carried the study of the geometry of general hypersurfaces in E"
Typically, curvature is defined for curves parametrized by arc-length meaning that (0'(s) 1 for all (c, d) (and regular curve can always be parametrized this way). For these types of curves, the curvature of 3 at ((s) is defined as the length of (s), which measures "how much" a curve "curves". However, this notion does not give information about the direction on which a curve is "curving". We start looking at the case n = 2. We define the signed curvature of a general curve (ll) (11()), by (ef. (1.5)
Na (t) 2/ (t) 2² (t)=2(t)
(z (t) + x (t)2)
It can be checked that [s(()] coincides with the curvature of a when parametrized by arc-length (at the corresponding point), the signed curvature is well defined up to a sign (the sign will change if we consider reparametrization that reverses the order of (a, b), for example curve defined on (-b, aa) given by ((s) a(-s)), which motivates the discussion in Section 1.5.
For example, suppose that a planar curve is defined by a function f: (a, b) - IR is the following way:
a<tt) (t,, f()),
for e (a, b). A quick computation gives
(t) (1 (1+ (
Ka (t)
(A.1)
Given a regular curve a: (a, - 3 as above and real number n) * 0, straightforward to see that the curve B(t) (t) is also regular curve and its signed curvature is given by
(t(()= = n²>1(()= (f="((()) = (t)...
The notion of signed curvature can be extended to curves in manifolds sitting inside R= (see for example (Lee, 2018, Chapter 8)). For a(-e,e) - R parametrized by arc-length, the signed curvature (with respect to n) ct of at p (0) is given by x (0) = (n, (n,a"()), a())). It can be shown that this definition agrees with the one we gave for 2.
39

---

Published in Transactions on Machine Learning Research (09/2023)
A.2 Geometry of hypersurfaces in R"
Let M be a differentiable hypersurface inside Ik" of class O* (i.e., 1-dimensional C* manifold). By this we mean that for each p E M there is an open set U C R= and a C injective map Φ: U - M (called a parometrization of M around p). For each x E U, ( . ( forms a basis for the tangent space T.M (q = (x)) to M at q. Since (U)) C R we can consider the induced metric on M by the Euclidean metric in IR. (denoted by (,) This is a Riemannian metric on M given on the coordinates given by by the matrix
9i5 (0,0(z),0;
for E U. The metric g allows us to define the length of curves in M.
In general, if a manifold M of dimension n - is sitting inside an n-dimensional Riemannian manifold M (and M endowed with the induced metric from M) the second fundamental form carries the information on how M is "curved" inside M. Let g be the metric on M and g the induced metric on M by g. Let V denote the divita connection of g. Let n be smooth unit normal vector field M (that is n()) is perpendicular to T,MM for each p E M). The scalar second fundamental form of M with respect to n is the covariant 2-tensor h on M defined
- VXY) =
- VxY)= =
(A.2)
for X,Y Y tangent vectors to M. Note that for a hypersurface, at each point we have exactly to unit normal vectors to M at p, thus the scalar second fundamental form is well-defined up to a sign. Fixing a point p e M } and an orthonormal basis {E1, ..., } for the tangent space at p T.MM, the eigenvalues of the matrix given by bag h(E,, Ej) for i, 1, ,.., n are called the principal curvatures of M at p and the corresponding eigenspaces are called the principal directions. For details of the above see Chapter 8 in (Lee, 2018).
When M R and M is parametrized by U C R--1 - M C R", with respect to the local frame (8,0, ..., } of (UU, the scalar second fundamental form with respect to a normal unit vector field n is given by ((Lee, 2018, Proposition 8.23))
his = 0(0,0,0,0) = (0., n),
(A.3)
for i,j = 1,,.,, n-
Given any p M and u E TpM, there geodesic Tv: (a, - M of M passing through p with velocity at p. Let Mj and M2 be two hypersurfaces in 1=+1 tangent at a point E M, n M2. Choose a normal vector n and suppose that Mj lies above M2 (with respect to n). We have the following lemma from (Lee, 2018).
With the previous lemma we can obtain a comparison result for manifolds with positive principal curvatures. Lemma A.1. Suppose that M1 and M2 are tangent at p E M1 n M2 and fir a normal vector n at p. Suppose that M1 and M2 have positive principal curvatures at p. Then hy (u, v) 2 h2(v, v) for all E TpM if and only if Mj lies above M2 (with respect to n) locally around p.
Proof. First we make the following observation. Suppose that M a smooth hypersurface in R" and we have regular curve a: (-r,E) - M such that (0) p and a' a0) for some p M and T,M. Then, letting h denote the second fundamental form of M from (A.2) we have
h(v, v) = V un,
d( n o a
(t), o())
dt
o a)) a (t)
==
(n, a" a())).
Thus, if a is parametrized by arc-length, h(v, v) (n, a" (0)) x²t (0).
40

---

Published in Transactions on Machine Learning Research (09/2023)
Suppose M1 lies above M2 are tangent at p and let TμM1 TpM2 with |o| = 1. Then M1 and M2 with the plane generated by v and n. Then we obtain two curves O1 and 02 on M1 and M2, respectively, such that (0) = and (0) = v for i = 1, Moreover, we can assume that these curves are parametrized by arc-length so its Euclidean curvature is given by (a)(0), n). Since we can regard these curves as planar curves, there are functions f1 and f2 such that the curves 01 and 0g are represented the plane (v, n) by the curves
intersect
(1 = fi))) Y/ (z) (z, (z)),
with f = (0), f((0) = u, (0) > 0 (since M1 and M2 have positive principal curvatures at p) for = 1, By construction K (0) = (0) and by definition k (0) = (0), n), for 1,2.
If M1 lies above M2 at p, then (0) > f (0) and hence Net, (0) 2 Kip (0), which is equivalent hı (1 2 (2 v) for any T M with |u| = 1. Let w + E T.MM be arbitrary, then
(w w) = /w/²/;
w
z |wi 12/2
h2 hw w),
(A.4)
| |wm
|wl |w)]
as claimed.
Conversely if (A.4) holds, then that in particular holds for unitary u, which ultimately means that (0) 2 (0) for all unitary v E T.M. This implies that M1 lies above M2.
We present the following instructive example.
Example A.2. Consider the differentiable function fx(2, = x(0² + y²)) with k > O, and let M,. {(a, y, fx( y)) () & (0)). We choose the parametrization 2x(x) = (x, fx()) of My. and compute the scalar second fundamental form of Mx at p = (0,0,0) 0) in these coordinates. We have
0, y) = (1, 2k%),, 0,0(z,y) (0, 1, 2xy),
(z,4(2,8) (0,0,2x)
0 (,,0( (0,0,0),
By (zr,)) (0,0,2),
thus from (A.3) at the point (0, (0, 0), the scalar second fundamental form of Mn. with respect to n (0, 0, 1) is given by
(xx 0
[hr,(p)
0
2x
and in particular for we have
(b)](p) (2 2)
Thus, clearly we have
(0) 10)) = (2k 2
(2x00 0 2x 2
0
(A.5)
which is positive definite if and only if <>>> (when Mn. lães inside M1 and are tangent at p).
Remark A.3. We stress technical observation. The comparison (A.5) in Ezample A.2 is valid since regordless of the value of k, O (0, and (0,00 0) are the same, meaning that we can identify the tangent spaces M, and M2 at for all K, and the basis for them is given by (0 (0, 0), is not necessarily the case so one should perform a change of basis before comparing the second fundamental forms.
In general this
41


Reviews:
[{"review_id": "L65zeuQq0s", "reviewer": "Reviewer_cZM7", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n1. The main theoretical results are theoretically sound and correct. Did not find major flaws in the proof (except for some notational issues). \n2. Theorem 4.22 and the equivalent conditions for \\eta-mixable loss functions and the geometric properties of loss functions are interesting. \n3. The reconciliation between this work and previous works in Section 1.6 is interesting, providing a new point of view for mixing games. \n\nWeaknesses\n1. Motivation is unclear to me: The authors state that the motivation came from the observation made by [Vovk2015]. However, the intuitive explanation is missing here for why the observation could have a broader impact on mixing games. How could this new geometric interpretation potentially help us better understand or design games? \n2. The presentation is not ideal: The authors introduce mathematical definitions at the very beginning of the paper, which I think is good and clear, but then take a long detour in terms of arriving at the main contribution and the proposed differential geometry interpretation. More direct language is recommended, for example, the smoothness (i.e., the curvature) of the loss function is a sufficient condition for the mixability of games. The complicated content an layout of this paper makes it hard to follow. \n3. The benefit of this new viewpoint is not strong enough. Proposing a new viewpoint that we are unclear about before, in this case, the geometry, is always welcome. However, this new interpretation should not be used just as a viewpoint, but as a practical tool that provides us with new guidelines, e.g., designing \\eta, finding the limiting number of games that could be mixed, or converse results such as inmixability.\n4. Future direction is not concrete: it is highly recommended that the authors point out potential directions to follow up this paper so that to maximize its impact. \n5. As an online learning paper, I also think it is reasonable to ask for a few illustrative experiments for a proof of concept for the theory.  Readers could potentially learn more from it. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The goal of this paper is to provide interpretations for mixable loss functions in the context of prediction with expert advice by differential geometry", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please refer to the weakness part for changes. Moreover, there are some minor changes including typos, unclear notations, repeated definitions using the same symbols, etc. ", "broader_impact_concerns": "No concerns that I am aware of. \n", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "649TX6l1PE", "reviewer": "Reviewer_R4xj", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The main result of the paper is certainly correct but the paper takes a convoluted way to arrive at it. \n\nThe statement is easy to prove in much higher generality. Mixability is equivalent to convexity of the image of the set of superpredictions under the exponential transformation $x_i \\to e^{-\\eta x_i}$. As the set of superpredictions has non-empty interior, convexity is equivalent to the existence of support hyperplanes: through every point on the boundary there passes a support hyperplane, i.e, a hyperplane such that the the set is entirely on one side of it. The inverse image of this support hyperplane is the boundary of the shifted set of superpredictions for the logarithmic game.\n\nThis simple argument makes no reference to smoothness of the loss function. It dispenses with the requirement of the propriety of the loss either.\n\nThe real problem here is to find a good characterisation of the mixable losses in terms of the geometry of the original space. The excellent paper by Van Erven, Reid, and Williamson makes a very good point in terms of the curvature.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper presents a geometric characterisation of mixable games.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "As the main result of the paper is certainly correct, I have no problem with the publication.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "YVHMZttifA", "reviewer": "Reviewer_yBnk", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n+ The characterizations here for proper losses is conceptually “right” in that it is paramertization-independent. \n+ A demonstration of the strength of this interpretation lies in that it extends seamlessly (i.e., through sensible generalizations) to the multi class case; the same can’t be said about all other equivalent conditions we know.\n\nNot-Strengths\n- Beyond stating the result, it would be great to demonstrate the utility of these characterizations by using them to (re)establish the mixability eta’s for specific loses.\n- This point is not a “con” in any strict sense. The contribution here is in establishing the correct interpretation, and is not algorithmic. However, I write this in full awareness of the fact that an improved understanding that paves way for further research is equally (if not more) valuable.\n\nOverall, although the breath of contributions here is narrow, I think the result will appeal to the sub community (online learning) in question, and I hope that eventually members will further build on it.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In online learning/sequential prediction with a finite number of experts, it is well known that constant regret (in horizon) is achievable for certain classes of losses, e.g., the special case of exp-concave losses. A general characterization of such class via mixable losses was studied by Vovk in the context of his aggregation algorithm. However, unlike exp-concavity which is geometric, the original definition of mixable losses was a bit cumbersome — it’s a for-all guarantee where one must point-wise “guess” an aggregation/“mean” function. Various simpler-but-equivalent characterizations have been sought and proposed, notably a clean formula from Haussler et al for the binary case. For proper losses, this was subsequently generalized via the Hessian of the Bayes loss by van Erven et al to the multi class case. \n\nThis work provides (convex) geometric characterization of the notion of mixability for proper loss functions. Specifically, a central result here is that a loss is mixable iff its (argument-scaled) super prediction set slides freely inside that of the log loss. This distinctiveness of the log loss in particular ties with a previous result of Vovk establishing that log loss is the “most” mixable.\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The paper is well-written, but I found it to assume too much on the sequential prediction side (ironically), and market itself a bit narrowly. For example, it might be pedagogically better to introduce the definition of mixability using substitution/witness functions (like in http://onlineprediction.net/index.html?n=Main.Mixable or in Definition 6 of Mhammedi et al, even as the current definition is equivalent); that would make its applicability to SAA more transparent. ", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "BQvhRVLCoS", "reviewer": "Reviewer_ABr5", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. Authors provide plenty of comparisons and connections to previous works.\n\nWeaknesses:\n1. It's not so apparent to me the benefit brought by characterizing the mixability of a loss function by the ability of its superprediction set to slide freely inside that of the log loss. Indeed such characterization gets rid of the obscure notion of exponential projection, but that doesn't seem enough, say it still involves the notion of superprediction set, which remains mysterious throughout. So more explanations about the strengths of this new characterization are needed. \n2. There is a lack of context and intuitive interpretations of relevant technical terms. For example, the motivation for loss being proper and fundamental is not present. More details can be found in the next section.\n3. There are some technical errors that appear to have a negative effect on general reading and understanding. For example, the definition of standard parameterization is incorrect throughout the paper. In particular, I suspect that the current inapplicable definition of standard parametrization might affect the correctness of some technical results in this paper. More details can be found in the next section.\n4. The organization of the contents in this paper is hard to follow. For example, there are too many technical lemmas with lengthy proofs in the main text, which makes it hard to capture the main results and follow the line of their derivation.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors of this paper provide new characterizations about the mixability and fundamentality of proper loss functions in the setting of prediction with expert advice, from a geometric perspective. In particular, authors reveal the fact that both properties of the loss function are geometric and should not depend on the ambient coordinate system. ", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Critical: \n1. More explanations about the advantage of the proposed geometric interpretation are needed. \n2. Organization of contents should be adjusted. Lemmas and proofs that are not important to the understanding of the main results should be deferred to the appendix. \n3. Technical errors need to be fixed:\n- In the definition of standard parametrization of $\\Delta^n$, its domain shouldn't be $\\Delta^{n-1}$, otherwise it always maps $(t_1,...,t_{n-1})$ to $(t_1,...t_{n-1},0)$. As this notion is used throughout this paper, such an error may affect the proofs.\n- In Definition 2.1(ii), there is a  $n_{\\ell(p)}$ that is never mentioned or defined before, which makes the definition of map $\\textbf{n}$ ambiguous. \n- In Definition 2.1(iii), there is a $\\textbf{n}(p)$, where $p$ as the argument should be in $\\ell(int(\\Delta^2))$ as in (ii), but in fact it's in $int(\\Delta^2)$. This is confusing.\n- In chapter 4, there is no definition of $C^2_{-}(\\mathcal K^n_{*})$ which first appears in Lemma 4.14\n4. Need to add more contexts or intuitive interpretations regarding:\n- The setting of prediction with expert advice, including what kind of predictions are made by the learner and experts, what kind of outcomes are revealed by nature, and how the loss is incurred.\n- The formal definition of regret and $\\eta-$mixable games. A clearer statement about the $O(\\log n/\\eta)$ regret bound in such games is also needed.\n- Certain properties of loss functions, including properness, mixability and fundamentality.\n\nNot critical: \n1. Typos and bad notations. Here are a few of them:\n- $n$ is used as both the number of experts and the number of possible outcomes. I think these two values are different and should be denoted differently.\n- In the definition of probability simplex (on page 3 and 7), its points should have non-negative coordinates.\n- In the first formula on page 4, there should be indicator functions.\n- In the last sentence of the first paragraph of section 1.5, \"the signed curvature of $\\kappa$\" should be \"the signed curvature of $\\alpha$\".\n- In the first line of chapter 3, \"$\\mathbb R^n \\geq 0$\" should be \"$\\mathbb R^n_{\\geq 0}$\".\n- In Definition 4.11, \"$C^2_{+}(\\mathcal K^n)$\" should probably be \"$C^2_{+}(\\mathcal K^n_{*})$\".", "broader_impact_concerns": "I have no such concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers all recommended acceptance. The paper is quite technical, but it is dealing with a concept -- mixability -- that is fundamental to the subject of sequential decision making.

The reviewers raised issues around motivation. The authors have generally stuck to defending their current approach to motivation (offering a coordinate free way of reasoning / understanding mixability), which I believe is fine and justified. The authors don't offer any immediate computational consequences, but this conceptual advance should pave the way for others to deliver algorithmic ones.
Decision: Accept (poster)