Timezone: »
Poster
ELIAS: End-to-End Learning to Index and Search in Large Output Spaces
Nilesh Gupta · Patrick Chen · Hsiang-Fu Yu · Cho-Jui Hsieh · Inderjit Dhillon
Extreme multi-label classification (XMC) is a popular framework for solving many real-world problems that require accurate prediction from a very large number of potential output choices. A popular approach for dealing with the large label space is to arrange the labels into a shallow tree-based index and then learn an ML model to efficiently search this index via beam search. Existing methods initialize the tree index by clustering the label space into a few mutually exclusive clusters based on pre-defined features and keep it fixed throughout the training procedure. This approach results in a sub-optimal indexing structure over the label space and limits the search performance to the quality of choices made during the initialization of the index. In this paper, we propose a novel method ELIAS which relaxes the tree-based index to a specialized weighted graph-based index which is learned end-to-end with the final task objective. More specifically, ELIAS models the discrete cluster-to-label assignments in the existing tree-based index as soft learnable parameters that are learned jointly with the rest of the ML model. ELIAS achieves state-of-the-art performance on several large-scale extreme classification benchmarks with millions of labels. In particular, ELIAS can be up to 2.5% better at precision@$1$ and up to 4% better at recall@$100$ than existing XMC methods. A PyTorch implementation of ELIAS along with other resources is available at https://github.com/nilesh2797/ELIAS.
Author Information
Nilesh Gupta (University of Texas at Austin)

PhD student at UT Austin working on large-scale machine learning
Patrick Chen (UCLA)
Hsiang-Fu Yu (Amazon)
Cho-Jui Hsieh (UCLA, Amazon)
Inderjit Dhillon (Google & UT Austin)
More from the Same Authors
-
2022 : Differentially Private Federated Learning with Normalized Updates »
Rudrajit Das · Abolfazl Hashemi · Sujay Sanghavi · Inderjit Dhillon -
2022 : FedDM: Iterative Distribution Matching for Communication-Efficient Federated Learning »
Yuanhao Xiong · Ruochen Wang · Minhao Cheng · Felix Yu · Cho-Jui Hsieh -
2022 : On the Adversarial Robustness of Vision Transformers »
Rulin Shao · Zhouxing Shi · Jinfeng Yi · Pin-Yu Chen · Cho-Jui Hsieh -
2022 : Evaluating Worst Case Adversarial Weather Perturbations Robustness »
Yihan Wang · Yunhao Ba · Howard Zhang · Huan Zhang · Achuta Kadambi · Stefano Soatto · Alex Wong · Cho-Jui Hsieh -
2022 Poster: Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems »
Yue Kang · Cho-Jui Hsieh · Thomas Chun Man Lee -
2022 Poster: Syndicated Bandits: A Framework for Auto Tuning Hyper-parameters in Contextual Bandit Algorithms »
QIN DING · Yue Kang · Yi-Wei Liu · Thomas Chun Man Lee · Cho-Jui Hsieh · James Sharpnack -
2022 Poster: S3GC: Scalable Self-Supervised Graph Clustering »
Fnu Devvrit · Aditya Sinha · Inderjit Dhillon · Prateek Jain -
2022 Poster: DC-BENCH: Dataset Condensation Benchmark »
Justin CUI · Ruochen Wang · Si Si · Cho-Jui Hsieh -
2022 Poster: Efficiently Computing Local Lipschitz Constants of Neural Networks via Bound Propagation »
Zhouxing Shi · Yihan Wang · Huan Zhang · J. Zico Kolter · Cho-Jui Hsieh -
2022 Poster: Efficient Non-Parametric Optimizer Search for Diverse Tasks »
Ruochen Wang · Yuanhao Xiong · Minhao Cheng · Cho-Jui Hsieh -
2022 Poster: Are AlphaZero-like Agents Robust to Adversarial Perturbations? »
Li-Cheng Lan · Huan Zhang · Ti-Rong Wu · Meng-Yu Tsai · I-Chen Wu · Cho-Jui Hsieh -
2022 Poster: Random Sharpness-Aware Minimization »
Yong Liu · Siqi Mai · Minhao Cheng · Xiangning Chen · Cho-Jui Hsieh · Yang You -
2022 Poster: General Cutting Planes for Bound-Propagation-Based Neural Network Verification »
Huan Zhang · Shiqi Wang · Kaidi Xu · Linyi Li · Bo Li · Suman Jana · Cho-Jui Hsieh · J. Zico Kolter -
2021 Poster: Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Neural Network Robustness Verification »
Shiqi Wang · Huan Zhang · Kaidi Xu · Xue Lin · Suman Jana · Cho-Jui Hsieh · J. Zico Kolter -
2021 Poster: Learnable Fourier Features for Multi-dimensional Spatial Positional Encoding »
Yang Li · Si Si · Gang Li · Cho-Jui Hsieh · Samy Bengio -
2021 Poster: Fast Multi-Resolution Transformer Fine-tuning for Extreme Multi-label Text Classification »
Jiong Zhang · Wei-Cheng Chang · Hsiang-Fu Yu · Inderjit Dhillon -
2021 Poster: Label Disentanglement in Partition-based Extreme Multilabel Classification »
Xuanqing Liu · Wei-Cheng Chang · Hsiang-Fu Yu · Cho-Jui Hsieh · Inderjit Dhillon -
2021 Poster: DRONE: Data-aware Low-rank Compression for Large NLP Models »
Patrick Chen · Hsiang-Fu Yu · Inderjit Dhillon · Cho-Jui Hsieh -
2021 Poster: DynamicViT: Efficient Vision Transformers with Dynamic Token Sparsification »
Yongming Rao · Wenliang Zhao · Benlin Liu · Jiwen Lu · Jie Zhou · Cho-Jui Hsieh -
2021 Poster: Fast Certified Robust Training with Short Warmup »
Zhouxing Shi · Yihan Wang · Huan Zhang · Jinfeng Yi · Cho-Jui Hsieh -
2020 Poster: Automatic Perturbation Analysis for Scalable Certified Robustness and Beyond »
Kaidi Xu · Zhouxing Shi · Huan Zhang · Yihan Wang · Kai-Wei Chang · Minlie Huang · Bhavya Kailkhura · Xue Lin · Cho-Jui Hsieh -
2020 Poster: Provably Robust Metric Learning »
Lu Wang · Xuanqing Liu · Jinfeng Yi · Yuan Jiang · Cho-Jui Hsieh -
2020 Poster: Elastic-InfoGAN: Unsupervised Disentangled Representation Learning in Class-Imbalanced Data »
Utkarsh Ojha · Krishna Kumar Singh · Cho-Jui Hsieh · Yong Jae Lee -
2020 Poster: Robust Deep Reinforcement Learning against Adversarial Perturbations on State Observations »
Huan Zhang · Hongge Chen · Chaowei Xiao · Bo Li · Mingyan Liu · Duane Boning · Cho-Jui Hsieh -
2020 Spotlight: Robust Deep Reinforcement Learning against Adversarial Perturbations on State Observations »
Huan Zhang · Hongge Chen · Chaowei Xiao · Bo Li · Mingyan Liu · Duane Boning · Cho-Jui Hsieh -
2020 Poster: An Efficient Adversarial Attack for Tree Ensembles »
Chong Zhang · Huan Zhang · Cho-Jui Hsieh -
2020 Poster: Multi-Stage Influence Function »
Hongge Chen · Si Si · Yang Li · Ciprian Chelba · Sanjiv Kumar · Duane Boning · Cho-Jui Hsieh -
2019 : Lunch Break and Posters »
Xingyou Song · Elad Hoffer · Wei-Cheng Chang · Jeremy Cohen · Jyoti Islam · Yaniv Blumenfeld · Andreas Madsen · Jonathan Frankle · Sebastian Goldt · Satrajit Chatterjee · Abhishek Panigrahi · Alex Renda · Brian Bartoldson · Israel Birhane · Aristide Baratin · Niladri Chatterji · Roman Novak · Jessica Forde · YiDing Jiang · Yilun Du · Linara Adilova · Michael Kamp · Berry Weinstein · Itay Hubara · Tal Ben-Nun · Torsten Hoefler · Daniel Soudry · Hsiang-Fu Yu · Kai Zhong · Yiming Yang · Inderjit Dhillon · Jaime Carbonell · Yanqing Zhang · Dar Gilboa · Johannes Brandstetter · Alexander R Johansen · Gintare Karolina Dziugaite · Raghav Somani · Ari Morcos · Freddie Kalaitzis · Hanie Sedghi · Lechao Xiao · John Zech · Muqiao Yang · Simran Kaur · Qianli Ma · Yao-Hung Hubert Tsai · Ruslan Salakhutdinov · Sho Yaida · Zachary Lipton · Daniel Roy · Michael Carbin · Florent Krzakala · Lenka Zdeborová · Guy Gur-Ari · Ethan Dyer · Dilip Krishnan · Hossein Mobahi · Samy Bengio · Behnam Neyshabur · Praneeth Netrapalli · Kris Sankaran · Julien Cornebise · Yoshua Bengio · Vincent Michalski · Samira Ebrahimi Kahou · Md Rifat Arefin · Jiri Hron · Jaehoon Lee · Jascha Sohl-Dickstein · Samuel Schoenholz · David Schwab · Dongyu Li · Sang Keun Choe · Henning Petzka · Ashish Verma · Zhichao Lin · Cristian Sminchisescu -
2019 Poster: Stochastic Shared Embeddings: Data-driven Regularization of Embedding Layers »
Liwei Wu · Shuqing Li · Cho-Jui Hsieh · James Sharpnack -
2019 Poster: A Convex Relaxation Barrier to Tight Robustness Verification of Neural Networks »
Hadi Salman · Greg Yang · Huan Zhang · Cho-Jui Hsieh · Pengchuan Zhang -
2019 Poster: Provable Non-linear Inductive Matrix Completion »
Kai Zhong · Zhao Song · Prateek Jain · Inderjit Dhillon -
2019 Poster: Inverting Deep Generative models, One layer at a time »
Qi Lei · Ajil Jalal · Inderjit Dhillon · Alex Dimakis -
2019 Poster: Think Globally, Act Locally: A Deep Neural Network Approach to High-Dimensional Time Series Forecasting »
Rajat Sen · Hsiang-Fu Yu · Inderjit Dhillon -
2019 Poster: AutoAssist: A Framework to Accelerate Training of Deep Neural Networks »
Jiong Zhang · Hsiang-Fu Yu · Inderjit Dhillon -
2019 Poster: Robustness Verification of Tree-based Models »
Hongge Chen · Huan Zhang · Si Si · Yang Li · Duane Boning · Cho-Jui Hsieh -
2019 Poster: Convergence of Adversarial Training in Overparametrized Neural Networks »
Ruiqi Gao · Tianle Cai · Haochuan Li · Cho-Jui Hsieh · Liwei Wang · Jason Lee -
2019 Spotlight: Convergence of Adversarial Training in Overparametrized Neural Networks »
Ruiqi Gao · Tianle Cai · Haochuan Li · Cho-Jui Hsieh · Liwei Wang · Jason Lee -
2019 Poster: Primal-Dual Block Generalized Frank-Wolfe »
Qi Lei · JIACHENG ZHUO · Constantine Caramanis · Inderjit Dhillon · Alex Dimakis -
2019 Poster: A Unified Framework for Data Poisoning Attack to Graph-based Semi-supervised Learning »
Xuanqing Liu · Si Si · Jerry Zhu · Yang Li · Cho-Jui Hsieh -
2017 Poster: A Greedy Approach for Budgeted Maximum Inner Product Search »
Hsiang-Fu Yu · Cho-Jui Hsieh · Qi Lei · Inderjit Dhillon -
2016 Workshop: Learning in High Dimensions with Structure »
Nikhil Rao · Prateek Jain · Hsiang-Fu Yu · Ming Yuan · Francis Bach -
2016 Poster: Asynchronous Parallel Greedy Coordinate Descent »
Yang You · Xiangru Lian · Ji Liu · Hsiang-Fu Yu · Inderjit Dhillon · James Demmel · Cho-Jui Hsieh -
2016 Poster: Coordinate-wise Power Method »
Qi Lei · Kai Zhong · Inderjit Dhillon -
2016 Poster: Structured Sparse Regression via Greedy Hard Thresholding »
Prateek Jain · Nikhil Rao · Inderjit Dhillon -
2016 Poster: Mixed Linear Regression with Multiple Components »
Kai Zhong · Prateek Jain · Inderjit Dhillon -
2016 Poster: Temporal Regularized Matrix Factorization for High-dimensional Time Series Prediction »
Hsiang-Fu Yu · Nikhil Rao · Inderjit Dhillon -
2016 Poster: Dual Decomposed Learning with Factorwise Oracle for Structural SVM of Large Output Domain »
Ian En-Hsu Yen · Xiangru Huang · Kai Zhong · Ruohan Zhang · Pradeep Ravikumar · Inderjit Dhillon -
2015 Workshop: Multiresolution methods for large-scale learning »
Inderjit Dhillon · Risi Kondor · Rob Nowak · Michael O'Neil · Nedelina Teneva -
2015 : Temporal Regularized Matrix Factorization »
Hsiang-Fu Yu -
2015 Poster: Matrix Completion with Noisy Side Information »
Kai-Yang Chiang · Cho-Jui Hsieh · Inderjit Dhillon -
2015 Poster: Collaborative Filtering with Graph Information: Consistency and Scalable Methods »
Nikhil Rao · Hsiang-Fu Yu · Pradeep Ravikumar · Inderjit Dhillon -
2015 Spotlight: Collaborative Filtering with Graph Information: Consistency and Scalable Methods »
Nikhil Rao · Hsiang-Fu Yu · Pradeep Ravikumar · Inderjit Dhillon -
2015 Spotlight: Matrix Completion with Noisy Side Information »
Kai-Yang Chiang · Cho-Jui Hsieh · Inderjit Dhillon -
2015 Poster: Sparse Linear Programming via Primal and Dual Augmented Coordinate Descent »
Ian En-Hsu Yen · Kai Zhong · Cho-Jui Hsieh · Pradeep Ravikumar · Inderjit Dhillon -
2015 Poster: Fixed-Length Poisson MRF: Adding Dependencies to the Multinomial »
David I Inouye · Pradeep Ravikumar · Inderjit Dhillon -
2015 Poster: Consistent Multilabel Classification »
Oluwasanmi Koyejo · Nagarajan Natarajan · Pradeep Ravikumar · Inderjit Dhillon -
2014 Poster: QUIC & DIRTY: A Quadratic Approximation Approach for Dirty Statistical Models »
Cho-Jui Hsieh · Inderjit Dhillon · Pradeep Ravikumar · Stephen Becker · Peder A Olsen -
2014 Poster: Consistent Binary Classification with Generalized Performance Metrics »
Sanmi Koyejo · Nagarajan Natarajan · Pradeep Ravikumar · Inderjit Dhillon -
2014 Poster: Fast Prediction for Large-Scale Kernel Machines »
Cho-Jui Hsieh · Si Si · Inderjit Dhillon -
2014 Poster: Multi-Scale Spectral Decomposition of Massive Graphs »
Si Si · Donghyuk Shin · Inderjit Dhillon · Beresford N Parlett -
2014 Poster: Sparse Random Feature Algorithm as Coordinate Descent in Hilbert Space »
Ian En-Hsu Yen · Ting-Wei Lin · Shou-De Lin · Pradeep Ravikumar · Inderjit Dhillon -
2014 Spotlight: Consistent Binary Classification with Generalized Performance Metrics »
Sanmi Koyejo · Nagarajan Natarajan · Pradeep Ravikumar · Inderjit Dhillon -
2014 Poster: Proximal Quasi-Newton for Computationally Intensive L1-regularized M-estimators »
Kai Zhong · Ian En-Hsu Yen · Inderjit Dhillon · Pradeep Ravikumar -
2014 Poster: Capturing Semantically Meaningful Word Dependencies with an Admixture of Poisson MRFs »
David I Inouye · Pradeep Ravikumar · Inderjit Dhillon -
2014 Poster: Constant Nullspace Strong Convexity and Fast Convergence of Proximal Methods under High-Dimensional Settings »
Ian En-Hsu Yen · Cho-Jui Hsieh · Pradeep Ravikumar · Inderjit Dhillon -
2013 Poster: BIG & QUIC: Sparse Inverse Covariance Estimation for a Million Variables »
Cho-Jui Hsieh · Matyas A Sustik · Inderjit Dhillon · Pradeep Ravikumar · Russell Poldrack -
2013 Oral: BIG & QUIC: Sparse Inverse Covariance Estimation for a Million Variables »
Cho-Jui Hsieh · Matyas A Sustik · Inderjit Dhillon · Pradeep Ravikumar · Russell Poldrack -
2013 Poster: Large Scale Distributed Sparse Precision Estimation »
Huahua Wang · Arindam Banerjee · Cho-Jui Hsieh · Pradeep Ravikumar · Inderjit Dhillon -
2013 Poster: Learning with Noisy Labels »
Nagarajan Natarajan · Inderjit Dhillon · Pradeep Ravikumar · Ambuj Tewari -
2012 Poster: A Divide-and-Conquer Method for Sparse Inverse Covariance Estimation »
Cho-Jui Hsieh · Inderjit Dhillon · Pradeep Ravikumar · Arindam Banerjee -
2011 Poster: Greedy Algorithms for Structurally Constrained High Dimensional Problems »
Ambuj Tewari · Pradeep Ravikumar · Inderjit Dhillon -
2011 Poster: Sparse Inverse Covariance Matrix Estimation Using Quadratic Approximation »
Cho-Jui Hsieh · Matyas A Sustik · Inderjit Dhillon · Pradeep Ravikumar -
2011 Poster: Nearest Neighbor based Greedy Coordinate Descent »
Inderjit Dhillon · Pradeep Ravikumar · Ambuj Tewari -
2011 Poster: Orthogonal Matching Pursuit with Replacement »
Prateek Jain · Ambuj Tewari · Inderjit Dhillon -
2010 Spotlight: Guaranteed Rank Minimization via Singular Value Projection »
Prateek Jain · Raghu Meka · Inderjit Dhillon -
2010 Poster: Guaranteed Rank Minimization via Singular Value Projection »
Prateek Jain · Raghu Meka · Inderjit Dhillon -
2010 Spotlight: Inductive Regularized Learning of Kernel Functions »
Prateek Jain · Brian Kulis · Inderjit Dhillon -
2010 Poster: Inductive Regularized Learning of Kernel Functions »
Prateek Jain · Brian Kulis · Inderjit Dhillon -
2009 Poster: Matrix Completion from Power-Law Distributed Samples »
Raghu Meka · Prateek Jain · Inderjit Dhillon -
2008 Poster: Online Metric Learning and Fast Similarity Search »
Prateek Jain · Brian Kulis · Inderjit Dhillon · Kristen Grauman -
2008 Oral: Online Metric Learning and Fast Similarity Search »
Prateek Jain · Brian Kulis · Inderjit Dhillon · Kristen Grauman -
2006 Poster: Differential Entropic Clustering of Multivariate Gaussians »
Jason V Davis · Inderjit Dhillon