Timezone: »
Poster
Learning to Approximate a Bregman Divergence
Ali Siahkamari · XIDE XIA · Venkatesh Saligrama · David Castañón · Brian Kulis
Bregman divergences generalize measures such as the squared Euclidean distance and the KL divergence, and arise throughout many areas of machine learning. In this paper, we focus on the problem of approximating an arbitrary Bregman divergence from supervision, and we provide a well-principled approach to analyzing such approximations. We develop a formulation and algorithm for learning arbitrary Bregman divergences based on approximating their underlying convex generating function via a piecewise linear function. We provide theoretical approximation bounds using our parameterization and show that the generalization error $O_p(m^{-1/2})$ for metric learning using our framework matches the known generalization error in the strictly less general Mahalanobis metric learning setting. We further demonstrate empirically that our method performs well in comparison to existing metric learning methods, particularly for clustering and ranking problems.
Author Information
Ali Siahkamari (Boston University)
I'm a PhD candidate at Boston University, EE department. I'm graduating May 2021. My research focuses on statistical machine learning and algorithms. I have proposed a general piecewise linear modeling framework that can be implemented efficiently in high dimensions via GPUs. This framework enjoys statistical guarantees. Applications include regression, classification, anomaly detection and active learning.
XIDE XIA (Boston University)
Venkatesh Saligrama (Boston University)
David Castañón (Boston University)
Brian Kulis (Boston University and Amazon)
More from the Same Authors
-
2021 Spotlight: Online Selective Classification with Limited Feedback »
Aditya Gangrade · Anil Kag · Ashok Cutkosky · Venkatesh Saligrama -
2021 : Surprisingly Simple Semi-Supervised Domain Adaptation with Pretraining and Consistency »
Samarth Mishra · Kate Saenko · Venkatesh Saligrama -
2022 Poster: How Transferable are Video Representations Based on Synthetic Data? »
Yo-whan Kim · Samarth Mishra · SouYoung Jin · Rameswar Panda · Hilde Kuehne · Leonid Karlinsky · Venkatesh Saligrama · Kate Saenko · Aude Oliva · Rogerio Feris -
2021 Poster: Online Selective Classification with Limited Feedback »
Aditya Gangrade · Anil Kag · Ashok Cutkosky · Venkatesh Saligrama -
2021 Poster: Bandit Quickest Changepoint Detection »
Aditya Gopalan · Braghadeesh Lakshminarayanan · Venkatesh Saligrama -
2020 Poster: Online Algorithm for Unsupervised Sequential Selection with Contextual Information »
Arun Verma · Manjesh Kumar Hanawal · Csaba Szepesvari · Venkatesh Saligrama -
2020 Poster: Limits on Testing Structural Changes in Ising Models »
Aditya Gangrade · Bobak Nazer · Venkatesh Saligrama -
2019 Poster: Efficient Near-Optimal Testing of Community Changes in Balanced Stochastic Block Models »
Aditya Gangrade · Praveen Venkatesh · Bobak Nazer · Venkatesh Saligrama -
2019 Poster: Shallow RNN: Accurate Time-series Classification on Resource Constrained Devices »
Don Dennis · Durmus Alp Emre Acar · Vikram Mandikal · Vinu Sankar Sadasivan · Venkatesh Saligrama · Harsha Vardhan Simhadri · Prateek Jain -
2017 Poster: Adaptive Classification for Prediction Under a Budget »
Feng Nan · Venkatesh Saligrama -
2016 Poster: Pruning Random Forests for Prediction on a Budget »
Feng Nan · Joseph Wang · Venkatesh Saligrama -
2016 Poster: Man is to Computer Programmer as Woman is to Homemaker? Debiasing Word Embeddings »
Tolga Bolukbasi · Kai-Wei Chang · James Y Zou · Venkatesh Saligrama · Adam T Kalai -
2015 Poster: Efficient Learning by Directed Acyclic Graph For Resource Constrained Prediction »
Joseph Wang · Kirill Trapeznikov · Venkatesh Saligrama -
2014 Poster: Efficient Minimax Signal Detection on Graphs »
Jing Qian · Venkatesh Saligrama -
2012 Poster: Local Supervised Learning through Space Partitioning »
Joseph Wang · Venkatesh Saligrama -
2010 Poster: Probabilistic Belief Revision with Structural Constraints »
Peter B Jones · Venkatesh Saligrama · Sanjoy K Mitter -
2009 Poster: Anomaly Detection with Score functions based on Nearest Neighbor Graphs »
Manqi Zhao · Venkatesh Saligrama -
2009 Spotlight: Anomaly Detection with Score functions based on Nearest Neighbor Graphs »
Manqi Zhao · Venkatesh Saligrama