Timezone: »
Iterative hard thresholding (IHT) is a projected gradient descent algorithm, known to achieve state of the art performance for a wide range of structured estimation problems, such as sparse inference. In this work, we consider IHT as a solution to the problem of learning sparse discrete distributions. We study the hardness of using IHT on the space of measures. As a practical alternative, we propose a greedy approximate projection which simultaneously captures appropriate notions of sparsity in distributions, while satisfying the simplex constraint, and investigate the convergence behavior of the resulting procedure in various settings. Our results show, both in theory and practice, that IHT can achieve state of the art results for learning sparse distributions.
Author Information
Jacky Zhang (UIUC)
Rajiv Khanna (University of California at Berkeley)
Anastasios Kyrillidis (Rice University)
Sanmi Koyejo (UIUC)

Sanmi Koyejo an Assistant Professor in the Department of Computer Science at Stanford University. Koyejo also spends time at Google as a part of the Brain team. Koyejo's research interests are in developing the principles and practice of trustworthy machine learning. Additionally, Koyejo focuses on applications to neuroscience and healthcare. Koyejo has been the recipient of several awards, including a best paper award from the conference on uncertainty in artificial intelligence (UAI), a Skip Ellis Early Career Award, and a Sloan Fellowship. Koyejo serves as the president of the Black in AI organization.
More from the Same Authors
-
2021 : Acceleration and Stability of the Stochastic Proximal Point Algorithm »
Junhyung Lyle Kim · Panos Toulis · Anastasios Kyrillidis -
2021 : Acceleration and Stability of the Stochastic Proximal Point Algorithm »
Junhyung Lyle Kim · Panos Toulis · Anastasios Kyrillidis -
2021 : Probabilistic Performance Metric Elicitation »
Zachary Robertson · Hantao Zhang · Sanmi Koyejo -
2021 : Robust and Personalized Federated Learning with Spurious Features: an Adversarial Approach »
Xiaoyang Wang · Han Zhao · Klara Nahrstedt · Sanmi Koyejo -
2021 : RVFR: Robust Vertical Federated Learning via Feature Subspace Recovery »
Jing Liu · Chulin Xie · Krishnaram Kenthapadi · Sanmi Koyejo · Bo Li -
2021 : Secure Byzantine-Robust Distributed Learning via Clustering »
Raj Kiriti Velicheti · Sanmi Koyejo -
2021 : Exploiting Causal Chains for Domain Generalization »
Olawale Salaudeen · Sanmi Koyejo -
2021 : Distribution Preserving Bayesian Coresets using Set Constraints »
Shovik Guha · Rajiv Khanna · Sanmi Koyejo -
2022 : LOFT: Finding Lottery Tickets through Filter-wise Training »
Qihan Wang · Chen Dun · Fangshuo Liao · Christopher Jermaine · Anastasios Kyrillidis -
2022 : Strong Lottery Ticket Hypothesis with $\epsilon$–perturbation »
Fangshuo Liao · Zheyang Xiong · Anastasios Kyrillidis -
2022 : Strong Lottery Ticket Hypothesis with $\epsilon$–perturbation »
Fangshuo Liao · Zheyang Xiong · Anastasios Kyrillidis -
2022 : Efficient and Light-Weight Federated Learning via Asynchronous Distributed Dropout »
Chen Dun · Mirian Hipolito Garcia · Dimitrios Dimitriadis · Christopher Jermaine · Anastasios Kyrillidis -
2022 : Metric Elicitation; Moving from Theory to Practice »
Safinah Ali · Sohini Upadhyay · Gaurush Hiranandani · Elena Glassman · Sanmi Koyejo -
2022 : GIST: Distributed Training for Large-Scale Graph Convolutional Networks »
Cameron Wolfe · Jingkang Yang · Fangshuo Liao · Arindam Chowdhury · Chen Dun · Artun Bayer · Santiago Segarra · Anastasios Kyrillidis -
2022 : The Curse of Low Task Diversity: On the Failure of Transfer Learning to Outperform MAML and Their Empirical Equivalence »
Brando Miranda · Patrick Yu · Yu-Xiong Wang · Sanmi Koyejo -
2022 : Batch Active Learning from the Perspective of Sparse Approximation »
Maohao Shen · Yibo Jacky Zhang · Bowen Jiang · Sanmi Koyejo -
2022 Spotlight: Lightning Talks 1A-4 »
Siwei Wang · Jing Liu · Nianqiao Ju · Shiqian Li · Eloïse Berthier · Muhammad Faaiz Taufiq · Arsene Fansi Tchango · Chen Liang · Chulin Xie · Jordan Awan · Jean-Francois Ton · Ziad Kobeissi · Wenguan Wang · Xinwang Liu · Kewen Wu · Rishab Goel · Jiaxu Miao · Suyuan Liu · Julien Martel · Ruobin Gong · Francis Bach · Chi Zhang · Rob Cornish · Sanmi Koyejo · Zhi Wen · Yee Whye Teh · Yi Yang · Jiaqi Jin · Bo Li · Yixin Zhu · Vinayak Rao · Wenxuan Tu · Gaetan Marceau Caron · Arnaud Doucet · Xinzhong Zhu · Joumana Ghosn · En Zhu -
2022 Spotlight: CoPur: Certifiably Robust Collaborative Inference via Feature Purification »
Jing Liu · Chulin Xie · Sanmi Koyejo · Bo Li -
2022 Poster: Diagnosing failures of fairness transfer across distribution shift in real-world medical settings »
Jessica Schrouff · Natalie Harris · Sanmi Koyejo · Ibrahim Alabdulmohsin · Eva Schnider · Krista Opsahl-Ong · Alexander Brown · Subhrajit Roy · Diana Mincu · Christina Chen · Awa Dieng · Yuan Liu · Vivek Natarajan · Alan Karthikesalingam · Katherine Heller · Silvia Chiappa · Alexander D'Amour -
2022 Poster: A Reduction to Binary Approach for Debiasing Multiclass Datasets »
Ibrahim Alabdulmohsin · Jessica Schrouff · Sanmi Koyejo -
2022 Poster: CoPur: Certifiably Robust Collaborative Inference via Feature Purification »
Jing Liu · Chulin Xie · Sanmi Koyejo · Bo Li -
2022 Poster: Fair Wrapping for Black-box Predictions »
Alexander Soen · Ibrahim Alabdulmohsin · Sanmi Koyejo · Yishay Mansour · Nyalleng Moorosi · Richard Nock · Ke Sun · Lexing Xie -
2022 Poster: A Nonconvex Framework for Structured Dynamic Covariance Recovery »
Katherine Tsai · Mladen Kolar · Sanmi Koyejo -
2020 Poster: CSER: Communication-efficient SGD with Error Reset »
Cong Xie · Shuai Zheng · Sanmi Koyejo · Indranil Gupta · Mu Li · Haibin Lin -
2020 Poster: Fairness with Overlapping Groups; a Probabilistic Perspective »
Forest Yang · Mouhamadou M Cisse · Sanmi Koyejo -
2020 Poster: Fair Performance Metric Elicitation »
Gaurush Hiranandani · Harikrishna Narasimhan · Sanmi Koyejo -
2019 : Final remarks »
Anastasios Kyrillidis · Albert Berahas · Fred Roosta · Michael Mahoney -
2019 Workshop: Beyond first order methods in machine learning systems »
Anastasios Kyrillidis · Albert Berahas · Fred Roosta · Michael Mahoney -
2019 : Opening Remarks »
Anastasios Kyrillidis · Albert Berahas · Fred Roosta · Michael Mahoney -
2019 Poster: Multiclass Performance Metric Elicitation »
Gaurush Hiranandani · Shant Boodaghians · Ruta Mehta · Sanmi Koyejo -
2019 Tutorial: Representation Learning and Fairness »
Moustapha Cisse · Sanmi Koyejo -
2018 Poster: Boosting Black Box Variational Inference »
Francesco Locatello · Gideon Dresdner · Rajiv Khanna · Isabel Valera · Gunnar Ratsch -
2018 Spotlight: Boosting Black Box Variational Inference »
Francesco Locatello · Gideon Dresdner · Rajiv Khanna · Isabel Valera · Gunnar Ratsch -
2017 : Poster Session »
Shunsuke Horii · Heejin Jeong · Tobias Schwedes · Qing He · Ben Calderhead · Ertunc Erdil · Jaan Altosaar · Patrick Muchmore · Rajiv Khanna · Ian Gemp · Pengfei Zhang · Yuan Zhou · Chris Cremer · Maria DeYoreo · Alexander Terenin · Brendan McVeigh · Rachit Singh · Yaodong Yang · Erik Bodin · Trefor Evans · Henry Chai · Shandian Zhe · Jeffrey Ling · Vincent ADAM · Lars Maaløe · Andrew Miller · Ari Pakman · Josip Djolonga · Hong Ge -
2016 Oral: Examples are not enough, learn to criticize! Criticism for Interpretability »
Been Kim · Sanmi Koyejo · Rajiv Khanna -
2016 Poster: Generalized Correspondence-LDA Models (GC-LDA) for Identifying Functional Regions in the Brain »
Timothy Rubin · Sanmi Koyejo · Michael Jones · Tal Yarkoni -
2016 Poster: Preference Completion from Partial Rankings »
Suriya Gunasekar · Sanmi Koyejo · Joydeep Ghosh -
2016 Poster: Examples are not enough, learn to criticize! Criticism for Interpretability »
Been Kim · Sanmi Koyejo · Rajiv Khanna -
2015 Poster: Consistent Multilabel Classification »
Oluwasanmi Koyejo · Nagarajan Natarajan · Pradeep Ravikumar · Inderjit Dhillon -
2014 Poster: On Prior Distributions and Approximate Inference for Structured Variables »
Sanmi Koyejo · Rajiv Khanna · Joydeep Ghosh · Russell Poldrack -
2014 Poster: Consistent Binary Classification with Generalized Performance Metrics »
Sanmi Koyejo · Nagarajan Natarajan · Pradeep Ravikumar · Inderjit Dhillon -
2014 Spotlight: Consistent Binary Classification with Generalized Performance Metrics »
Sanmi Koyejo · Nagarajan Natarajan · Pradeep Ravikumar · Inderjit Dhillon -
2014 Poster: Sparse Bayesian structure learning with dependent relevance determination prior »
Anqi Wu · Mijung Park · Sanmi Koyejo · Jonathan W Pillow