Timezone: »

 
Poster
A scaled Bregman theorem with applications
Richard Nock · Aditya Menon · Cheng Soon Ong

Wed Dec 07 09:00 AM -- 12:30 PM (PST) @ Area 5+6+7+8 #61
in Wednesday Posters »

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.

Keywords: Clustering · Learning Theory · Online Learning · (Other) Classification · Convex Optimization

Author Information

Richard Nock (Data61 and ANU)
Aditya Menon (NICTA)
Cheng Soon Ong (Data61)

Cheng Soon Ong is a principal research scientist at the Machine Learning Research Group, Data61, CSIRO, and is the director of the machine learning and artificial intelligence future science platform at CSIRO. He is also an adjunct associate professor at the Australian National University. He is interested in enabling scientific discovery by extending statistical machine learning methods.

More from the Same Authors