Timezone: »
Complex performance measures, beyond the popular measure of accuracy, are increasingly being used in the context of binary classification. These complex performance measures are typically not even decomposable, that is, the loss evaluated on a batch of samples cannot typically be expressed as a sum or average of losses evaluated at individual samples, which in turn requires new theoretical and methodological developments beyond standard treatments of supervised learning. In this paper, we advance this understanding of binary classification for complex performance measures by identifying two key properties: a so-called Karmic property, and a more technical threshold-quasi-concavity property, which we show is milder than existing structural assumptions imposed on performance measures. Under these properties, we show that the Bayes optimal classifier is a threshold function of the conditional probability of positive class. We then leverage this result to come up with a computationally practical plug-in classifier, via a novel threshold estimator, and further, provide a novel statistical analysis of classification error with respect to complex performance measures.
Author Information
Bowei Yan (University of Texas at Austin)
Sanmi Koyejo (University of Illinois at Urbana-Champaign)

Sanmi (Oluwasanmi) Koyejo is an Assistant Professor in the Department of Computer Science at Stanford University. Koyejo was previously an Associate Professor in the Department of Computer Science at the University of Illinois at Urbana-Champaign. Koyejo's research interests are in developing the principles and practice of trustworthy machine learning, focusing on applications to neuroscience and healthcare. Koyejo completed a Ph.D. in Electrical Engineering at the University of Texas at Austin, advised by Joydeep Ghosh, and postdoctoral research at Stanford University with Russell A. Poldrack and Pradeep Ravikumar. Koyejo has been the recipient of several awards, including a best paper award from the conference on uncertainty in artificial intelligence, a Skip Ellis Early Career Award, a Sloan Fellowship, a Terman faculty fellowship, an NSF CAREER award, a Kavli Fellowship, an IJCAI early career spotlight, and a trainee award from the Organization for Human Brain Mapping. Koyejo spends time at Google as a part of the Brain team, serves on the Neural Information Processing Systems Foundation Board, the Association for Health Learning and Inference Board, and as president of the Black in AI organization.
Kai Zhong (University of Texas at Austin)
Pradeep Ravikumar (Carnegie Mellon University)
Related Events (a corresponding poster, oral, or spotlight)
-
2018 Poster: Binary Classification with Karmic, Threshold-Quasi-Concave Metrics »
Thu. Jul 12th 04:15 -- 07:00 PM Room Hall B #162
More from the Same Authors
-
2021 : When Is Generalizable Reinforcement Learning Tractable? »
Dhruv Malik · Yuanzhi Li · Pradeep Ravikumar -
2022 : Adapting to Shifts in Latent Confounders via Observed Concepts and Proxies »
Matt Kusner · Ibrahim Alabdulmohsin · Stephen Pfohl · Olawale Salaudeen · Arthur Gretton · Sanmi Koyejo · Jessica Schrouff · Alexander D'Amour -
2023 : Layer-Wise Feedback Alignment is Conserved in Deep Neural Networks »
Zach Robertson · Sanmi Koyejo -
2023 : FACADE: A Framework for Adversarial Circuit Anomaly Detection and Evaluation »
Dhruv Pai · Andres Carranza · Rylan Schaeffer · Arnuv Tandon · Sanmi Koyejo -
2023 : Identifying Causal Mechanism Shifts among Nonlinear Additive Noise Models »
Tianyu Chen · Kevin Bello · Bryon Aragam · Pradeep Ravikumar -
2023 : Learning Linear Causal Representations from Interventions under General Nonlinear Mixing »
Simon Buchholz · Goutham Rajendran · Elan Rosenfeld · Bryon Aragam · Bernhard Schölkopf · Pradeep Ravikumar -
2023 : Learning Linear Causal Representations from Interventions under General Nonlinear Mixing »
Simon Buchholz · Goutham Rajendran · Elan Rosenfeld · Bryon Aragam · Bernhard Schölkopf · Pradeep Ravikumar -
2023 : Beyond Scale: the Diversity Coefficient as a Data Quality Metric Demonstrates LLMs are Pre-trained on Formally Diverse Data »
Alycia Lee · Brando Miranda · Brando Miranda · Sanmi Koyejo -
2023 : Is Pre-training Truly Better Than Meta-Learning? »
Brando Miranda · Patrick Yu · Saumya Goyal · Yu-Xiong Wang · Sanmi Koyejo -
2023 : Leveraging Side Information for Communication-Efficient Federated Learning »
Berivan Isik · Francesco Pase · Deniz Gunduz · Sanmi Koyejo · Tsachy Weissman · Michele Zorzi -
2023 : Learning with Explanation Constraints »
Rattana Pukdee · Dylan Sam · Nina Balcan · Pradeep Ravikumar -
2023 : Invalid Logic, Equivalent Gains: The Bizarreness of Reasoning in Language Model Prompting »
Rylan Schaeffer · Kateryna Pistunova · Samar Khanna · Sarthak Consul · Sanmi Koyejo -
2023 : Learning Linear Causal Representations from Interventions under General Nonlinear Mixing »
Simon Buchholz · Goutham Rajendran · Elan Rosenfeld · Bryon Aragam · Bernhard Schölkopf · Pradeep Ravikumar -
2023 : GPT-Zip: Deep Compression of Finetuned Large Language Models »
Berivan Isik · Hermann Kumbong · Wanyi Ning · Xiaozhe Yao · Sanmi Koyejo · Ce Zhang -
2023 : Beyond Scale: the Diversity Coefficient as a Data Quality Metric Demonstrates LLMs are Pre-trained on Formally Diverse Data »
Alycia Lee · Brando Miranda · Sanmi Koyejo -
2023 : Are Emergent Abilities of Large Language Models a Mirage? »
Rylan Schaeffer · Brando Miranda · Sanmi Koyejo -
2023 : Thomas: Learning to Explore Human Preference via Probabilistic Reward Model »
Sang Truong · Duc Nguyen · Tho Quan · Sanmi Koyejo -
2023 : Global Optimality in Bivariate Gradient-based DAG Learning »
Chang Deng · Kevin Bello · Pradeep Ravikumar · Bryon Aragam -
2023 : On learning domain general predictors »
Sanmi Koyejo -
2023 : Deceptive Alignment Monitoring »
Andres Carranza · Dhruv Pai · Rylan Schaeffer · Arnuv Tandon · Sanmi Koyejo -
2023 : Vignettes on Pairwise-Feedback Mechanisms for Learning with Uncertain Preferences »
Sanmi Koyejo -
2023 Workshop: 2nd ICML Workshop on New Frontiers in Adversarial Machine Learning »
Sijia Liu · Pin-Yu Chen · Dongxiao Zhu · Eric Wong · Kathrin Grosse · Baharan Mirzasoleiman · Sanmi Koyejo -
2023 Panel: The Societal Impacts of AI »
Sanmi Koyejo · Samy Bengio · Ashia Wilson · Kirikowhai Mikaere · Joelle Pineau -
2023 Poster: Pairwise Ranking Losses of Click-Through Rates Prediction for Welfare Maximization in Ad Auctions »
Boxiang Lyu · Zhe Feng · Zach Robertson · Sanmi Koyejo -
2023 Poster: Optimizing NOTEARS Objectives via Topological Swaps »
Chang Deng · Kevin Bello · Bryon Aragam · Pradeep Ravikumar -
2023 Poster: Representer Point Selection for Explaining Regularized High-dimensional Models »
Che-Ping Tsai · Jiong Zhang · Hsiang-Fu Yu · Eli Chien · Cho-Jui Hsieh · Pradeep Ravikumar -
2023 Poster: Faith-Shap: The Faithful Shapley Interaction Index »
Che-Ping Tsai · Chih-Kuan Yeh · Pradeep Ravikumar -
2022 Workshop: New Frontiers in Adversarial Machine Learning »
Sijia Liu · Pin-Yu Chen · Dongxiao Zhu · Eric Wong · Kathrin Grosse · Hima Lakkaraju · Sanmi Koyejo -
2022 Poster: Building Robust Ensembles via Margin Boosting »
Dinghuai Zhang · Hongyang Zhang · Aaron Courville · Yoshua Bengio · Pradeep Ravikumar · Arun Sai Suggala -
2022 Spotlight: Building Robust Ensembles via Margin Boosting »
Dinghuai Zhang · Hongyang Zhang · Aaron Courville · Yoshua Bengio · Pradeep Ravikumar · Arun Sai Suggala -
2022 Poster: Adversarially Robust Models may not Transfer Better: Sufficient Conditions for Domain Transferability from the View of Regularization »
Xiaojun Xu · Yibo Zhang · Evelyn Ma · Hyun Ho Son · Sanmi Koyejo · Bo Li -
2022 Spotlight: Adversarially Robust Models may not Transfer Better: Sufficient Conditions for Domain Transferability from the View of Regularization »
Xiaojun Xu · Yibo Zhang · Evelyn Ma · Hyun Ho Son · Sanmi Koyejo · Bo Li -
2021 Poster: Uncovering the Connections Between Adversarial Transferability and Knowledge Transferability »
Kaizhao Liang · Yibo Zhang · Boxin Wang · Zhuolin Yang · Sanmi Koyejo · Bo Li -
2021 Spotlight: Uncovering the Connections Between Adversarial Transferability and Knowledge Transferability »
Kaizhao Liang · Yibo Zhang · Boxin Wang · Zhuolin Yang · Sanmi Koyejo · Bo Li -
2021 Poster: DORO: Distributional and Outlier Robust Optimization »
Runtian Zhai · Chen Dan · Zico Kolter · Pradeep Ravikumar -
2021 Poster: Optimizing Black-box Metrics with Iterative Example Weighting »
Gaurush Hiranandani · Jatin Mathur · Harikrishna Narasimhan · Mahdi Milani Fard · Sanmi Koyejo -
2021 Spotlight: DORO: Distributional and Outlier Robust Optimization »
Runtian Zhai · Chen Dan · Zico Kolter · Pradeep Ravikumar -
2021 Spotlight: Optimizing Black-box Metrics with Iterative Example Weighting »
Gaurush Hiranandani · Jatin Mathur · Harikrishna Narasimhan · Mahdi Milani Fard · Sanmi Koyejo -
2021 Poster: On Proximal Policy Optimization's Heavy-tailed Gradients »
Saurabh Garg · Joshua Zhanson · Emilio Parisotto · Adarsh Prasad · Zico Kolter · Zachary Lipton · Sivaraman Balakrishnan · Ruslan Salakhutdinov · Pradeep Ravikumar -
2021 Spotlight: On Proximal Policy Optimization's Heavy-tailed Gradients »
Saurabh Garg · Joshua Zhanson · Emilio Parisotto · Adarsh Prasad · Zico Kolter · Zachary Lipton · Sivaraman Balakrishnan · Ruslan Salakhutdinov · Pradeep Ravikumar -
2020 Poster: Uniform Convergence of Rank-weighted Learning »
Justin Khim · Liu Leqi · Adarsh Prasad · Pradeep Ravikumar -
2020 Poster: Sharp Statistical Guaratees for Adversarially Robust Gaussian Classification »
Chen Dan · Yuting Wei · Pradeep Ravikumar -
2020 Poster: On the consistency of top-k surrogate losses »
Forest Yang · Sanmi Koyejo -
2020 Poster: Class-Weighted Classification: Trade-offs and Robust Approaches »
Ziyu Xu · Chen Dan · Justin Khim · Pradeep Ravikumar -
2020 Poster: Optimization and Analysis of the pAp@k Metric for Recommender Systems »
Gaurush Hiranandani · Warut Vijitbenjaronk · Sanmi Koyejo · Prateek Jain -
2020 Poster: Certified Robustness to Label-Flipping Attacks via Randomized Smoothing »
Elan Rosenfeld · Ezra Winston · Pradeep Ravikumar · Zico Kolter -
2020 Poster: Zeno++: Robust Fully Asynchronous SGD »
Cong Xie · Sanmi Koyejo · Indranil Gupta -
2019 Poster: Partially Linear Additive Gaussian Graphical Models »
Sinong Geng · Minhao Yan · Mladen Kolar · Sanmi Koyejo -
2019 Oral: Partially Linear Additive Gaussian Graphical Models »
Sinong Geng · Minhao Yan · Mladen Kolar · Sanmi Koyejo -
2019 Poster: Zeno: Distributed Stochastic Gradient Descent with Suspicion-based Fault-tolerance »
Cong Xie · Sanmi Koyejo · Indranil Gupta -
2019 Oral: Zeno: Distributed Stochastic Gradient Descent with Suspicion-based Fault-tolerance »
Cong Xie · Sanmi Koyejo · Indranil Gupta -
2018 Poster: Loss Decomposition for Fast Learning in Large Output Spaces »
En-Hsu Yen · Satyen Kale · Felix Xinnan Yu · Daniel Holtmann-Rice · Sanjiv Kumar · Pradeep Ravikumar -
2018 Oral: Loss Decomposition for Fast Learning in Large Output Spaces »
En-Hsu Yen · Satyen Kale · Felix Xinnan Yu · Daniel Holtmann-Rice · Sanjiv Kumar · Pradeep Ravikumar -
2018 Poster: Deep Density Destructors »
David Inouye · Pradeep Ravikumar -
2018 Oral: Deep Density Destructors »
David Inouye · Pradeep Ravikumar -
2017 Poster: Consistency Analysis for Binary Classification Revisited »
Krzysztof Dembczynski · Wojciech Kotlowski · Sanmi Koyejo · Nagarajan Natarajan -
2017 Talk: Consistency Analysis for Binary Classification Revisited »
Krzysztof Dembczynski · Wojciech Kotlowski · Sanmi Koyejo · Nagarajan Natarajan -
2017 Poster: Ordinal Graphical Models: A Tale of Two Approaches »
ARUN SAI SUGGALA · Eunho Yang · Pradeep Ravikumar -
2017 Poster: Recovery Guarantees for One-hidden-layer Neural Networks »
Kai Zhong · Zhao Song · Prateek Jain · Peter Bartlett · Inderjit Dhillon -
2017 Poster: Doubly Greedy Primal-Dual Coordinate Descent for Sparse Empirical Risk Minimization »
Qi Lei · En-Hsu Yen · Chao-Yuan Wu · Inderjit Dhillon · Pradeep Ravikumar -
2017 Poster: Latent Feature Lasso »
En-Hsu Yen · Wei-Cheng Lee · Sung-En Chang · Arun Suggala · Shou-De Lin · Pradeep Ravikumar -
2017 Talk: Doubly Greedy Primal-Dual Coordinate Descent for Sparse Empirical Risk Minimization »
Qi Lei · En-Hsu Yen · Chao-Yuan Wu · Inderjit Dhillon · Pradeep Ravikumar -
2017 Talk: Ordinal Graphical Models: A Tale of Two Approaches »
ARUN SAI SUGGALA · Eunho Yang · Pradeep Ravikumar -
2017 Talk: Recovery Guarantees for One-hidden-layer Neural Networks »
Kai Zhong · Zhao Song · Prateek Jain · Peter Bartlett · Inderjit Dhillon -
2017 Talk: Latent Feature Lasso »
En-Hsu Yen · Wei-Cheng Lee · Sung-En Chang · Arun Suggala · Shou-De Lin · Pradeep Ravikumar