A scaled Bregman theorem with applications
Bregman divergences play a central role in the design and analysis of a range of machine learning algorithms through a handful of popular theorems. We present a new theorem which shows that "Bregman distortions" (employing a potentially non-convex generator) may be exactly re-written as a scaled Bregman divergence computed over transformed data. This property can be viewed from the standpoints of geometry (a scaled isometry with adaptive metrics) or convex optimization (relating generalized perspective transforms). Admissible distortions include geodesic distances on curved manifolds and projections or gauge-normalisation. Our theorem allows one to leverage to the wealth and convenience of Bregman divergences when analysing algorithms relying on the aforementioned Bregman distortions. We illustrate this with three novel applications of our theorem: a reduction from multi-class density ratio to class-probability estimation, a new adaptive projection free yet norm-enforcing dual norm mirror descent algorithm, and a reduction from clustering on flat manifolds to clustering on curved manifolds. Experiments on each of these domains validate the analyses and suggest that the scaled Bregman theorem might be a worthy addition to the popular handful of Bregman divergence properties that have been pervasive in machine learning.
Problem A Problem B that Theorem 1 reduces A to Reference Multiclass density-ratio estimation Multiclass class-probability estimation §3, Lemma 2 Online optimisation on L q ball Convex unconstrained online learning §4, Lemma 4 Clustering on curved manifolds Clustering on flat manifolds §5, Lemma 5 Table 1: Applications of our scaled Bregman Theorem (Theorem 1) -"Reduction" encompasses shortcuts on algorithms and on analyses (algorithm/proof A uses algorithm/proof B as subroutine).
differentiable scalar convex ϕ, for g(x) = 1 + x andφ(x)
= g(x) · ϕ(x/g(x)), g(x) · D ϕ (x/g(x) y/g(y)) = Dφ(x y) , ∀x, y.
Since the binary class-probability function η(x) = Pr(Y = 1|X = x) is related to the classconditional density ratio r(x) = Pr(X = x|Y = 1)/ Pr(X = x|Y = −1) via Bayes' rule as η(x) = r(x)/g(r(x)) ( [24] assume Pr(Y = 1) = 1/2), anyη with small D ϕ (η η) implicitly produces anr with low Dφ(r r) i.e. a good estimate of the density ratio. The Bregman property of eq.
(1) thus establishes a reduction from DRE to CPE. Two questions arise from this analysis: can we generalise eq.
(1) to other g(·), and if so, can we similarly relate other problems to each other?
This paper presents a new Bregman identity (Theorem 1), the scaled Bregman theorem, a significant generalisation of Menon and Ong [24, Lemma 2]. It shows that general distortions Dφ -which are not necessarily convex, positive, bounded or symmetric -may be re-expressed as a Bregman divergence D ϕ computed over transformed data, and thus inherit their good properties despite appearing prima facie to be a very different object. This transformation can be as simple as a projection or normalisation by a gauge, or more involved like the exponential map on lifted coordinates for a curved manifold. Our theorem can be summarized in two ways. The first is geometric as it specializes to a scaled isometry involving adaptive metrics. The second calls to a fundamental object of convex analysis, generalized perspective transforms [11,22,23]. Indeed, our theorem states when "the perspective of a Bregman divergence equals the distortion of a perspective", for a perspective (φ in eq. 1) which is analytically a generalized perspective transform but does not rely on the same convexity and sign requirements as in Maréchal [22,23]. We note that the perspective of a Bregman divergence (the left-hand side of eq. 1) is a special case of conformal divergence [27], yet to our knowledge it has never been formally defined. As with the aforementioned key properties of Bregman divergences, Theorem 1 has potentially wide implications for ML. We give three such novel applications to vastly different problems (see Table 1):
• a reduction of multiple density ratio estimation to multiclass-probability estimation ( §3), generalising the results of [24] for the binary label case, • a projection-free yet norm-enforcing mirror gradient algorithm (enforced norms are those of mirrored vectors and of the offset) with guarantees for adaptive filtering ( §4), and • a seeding approach for clustering on positively or negatively (constant) curved manifolds based on a popular seeding for flat manifolds and with the same approximation guarantees ( §5).
Experiments on each of these domains ( §6) validate our analysis. The Supplementary Material (SM) details the proofs of all results, provides the experimental results in extenso and some additional (nascent) applications to exponential families and computational information geometry. = {1, 2, ..., k} for k ∈ N. For any differentiable (but not necessarily convex) ϕ : X → R, we define the Bregman distortion D ϕ as
If ϕ is convex, D ϕ is the familiar Bregman divergence with generator ϕ. Without further ado, we present our main result.
Theorem 1 Let, ϕ : X → R be convex differentiable, and g : X → R * be differentiable. Then,   Remark. If X g is a vector space, ϕ satisfies eq. (5) if and only if it is positive homogeneous of degree 1 on X g (i.e. ϕ(αz) = α · ϕ(z) for any α > 0) from Euler's homogenous function theorem. When X g is not a vector space, this only holds for α such that αz ∈ X g as well. We thus call the gradient condition of eq. (5) "restricted positive homogeneity" for simplicity.
Remark. Appendix IV gives a "deep composition" extension of Theorem 1.
For the special case where X = R, and g(x) = 1 + x, Theorem 1 is exactly [24, Lemma 2] (c.f. eq. 1). We wish to highlight a few points with regard to our more general result. First, the "distortion" generatorφ may be 1 non-convex, as the following illustrates.
Example. Suppose ϕ(x) = (1/2) x 2 2 , the generator for squared Euclidean distance. Then, for g(x) = 1 + 1 x, we haveφ(
Whenφ is non-convex, the right hand side in eq. (3) is an object that ostensibly bears only a superficial similarity to a Bregman divergence; it is somewhat remarkable that Theorem 1 shows this general "distortion" between a pair (x, y) to be entirely equivalent to a (scaling of a) Bregman divergence between some transformation of the points. Second, when g is linear, eq. (3) holds for any convex ϕ (This was the case considered in [24]). When g is non-linear, however, ϕ must be chosen carefully so that (ϕ, g) satisfies the restricted homogeneity conditon 2 of eq. (5). In general, given a convex ϕ, one can "reverse engineer" a suitable g, as illustrated by the following example.
2 )/2. Then, eq. (5) requires that x 2 2 = 1 for every x ∈ X g , i.e. X g is (a subset of) the unit sphere. This is afforded by the choice g(x) = x 2 .
Third, Theorem 1 is not merely a mathematical curiosity: we now show that it facilitates novel results in three very different domains, namely estimating multiclass density ratios, constrained online optimisation, and clustering data on a manifold with non-zero curvature. We discuss nascent applications to exponential families and computational geometry in Appendices V and VI.
This paper aims to provide further understanding of how the *Bregman divergence* behaves under a certain type of transformation, in particular where the inputs are modified by a scaling function. The Bregman divergence is a generalization of a "distance measure" that arises in many areas of Machine Learning and is a key tool in understanding various aspects of convex analysis and optimization. The key result of the paper is to give full conditions under which the Bregman divergence is "well behaved" under scaling; that is under the mapping x --> x / g(x) where g() is some given function. The paper gives a central result along these lines, and then proceeds to describe three applications of the theorem: (a) a new way to compute multiclass density ratios, (b) an interesting approach to dual-norm mirror descent, and (c) some analysis tools for clustering on manifolds. 
 My overall assessment is mixed. Here are my high level points:  1. As someone who has worked a lot with Bregman divergences, I do find the main result to be quite appealing and intriguing. For general transformations, whenever you do map your inputs from one space to the other, it's typically never that simple to see what happens to the Bregman divergence on the resulting space. So this result seems to provide some clarity here in addition to being a generic tool. Also, the three applications provided are quite diverse and surprising, and these lend credibility to the claim that the result is broadly useful.  2. On the other hand, when you think about what the result is saying, it is fundamentally just a calculus identity. The authors are just showing that one has two different ways in which to compute "divergence from the linear approximation", under certain constraints on the function g(). When stated this way, it's more difficult to see this as an ML-ish result.  3. Finally, upon looking at the paper again, it does feel like the authors never really explain what the main theorem really means. The thing that gets me is that the transformation, x --> x / g(x), is just a weird one. The result seems to want to let g() be generic, but outside of normalization (i.e. dividing by a p-norm), how often does this type of transformation arise? And what do you do when g(x) = 0? The paper seems to want us to rely on the applications to answer these questions, but I would like further intuition as well.   The authors may want to provide additional thoughts in their rebuttal.