Timezone: »
Oral
Learning a Compressed Sensing Measurement Matrix via Gradient Unrolling
Shanshan Wu · Alexandros Dimakis · Sujay Sanghavi · Felix Xinnan Yu · Daniel Holtmann-Rice · Dmitry Storcheus · Afshin Rostamizadeh · Sanjiv Kumar
Linear encoding of sparse vectors is widely popular, but is commonly data-independent -- missing any possible extra (but a-priori unknown) structure beyond sparsity. In this paper we present a new method to learn linear encoders that adapt to data, while still performing well with the widely used $\ell_1$ decoder. The convex $\ell_1$ decoder prevents gradient propagation as needed in standard gradient-based training. Our method is based on the insight that unrolling the convex decoder into $T$ projected subgradient steps can address this issue. Our method can be seen as a data-driven way to learn a compressed sensing measurement matrix. We compare the empirical performance of 10 algorithms over 6 sparse datasets (3 synthetic and 3 real). Our experiments show that there is indeed additional structure beyond sparsity in the real datasets. Our method is able to discover it and exploit it to create excellent reconstructions with fewer measurements (by a factor of 1.1-3x) compared to the previous state-of-the-art methods. We illustrate an application of our method in learning label embeddings for extreme multi-label classification. Our experiments show that our method is able to match or outperform the precision scores of SLEEC, which is one of the state-of-the-art embedding-based approaches for extreme multi-label learning.
Author Information
Shanshan Wu (University of Texas at Austin)
Alexandros Dimakis (UT Austin)
Alex Dimakis is an Associate Professor at the Electrical and Computer Engineering department, University of Texas at Austin. He received his Ph.D. in electrical engineering and computer sciences from UC Berkeley. He received an ARO young investigator award in 2014, the NSF Career award in 2011, a Google faculty research award in 2012 and the Eli Jury dissertation award in 2008. He is the co-recipient of several best paper awards including the joint Information Theory and Communications Society Best Paper Award in 2012. His research interests include information theory, coding theory and machine learning.
Sujay Sanghavi (UT Austin)
Felix Xinnan Yu (Google AI)
Daniel Holtmann-Rice (Google Inc)
Dmitry Storcheus (Google Research)
Afshin Rostamizadeh (Google)
Sanjiv Kumar (Google Research, NY)
Related Events (a corresponding poster, oral, or spotlight)
-
2019 Poster: Learning a Compressed Sensing Measurement Matrix via Gradient Unrolling »
Thu. Jun 13th 01:30 -- 04:00 AM Room Pacific Ballroom #189
More from the Same Authors
-
2022 : Positive Unlabeled Contrastive Representation Learning »
Anish Acharya · Sujay Sanghavi · Li Jing · Bhargav Bhushanam · Michael Rabbat · Dhruv Choudhary · Inderjit Dhillon -
2023 : SpecTr: Fast Speculative Decoding via Optimal Transport »
Ziteng Sun · Ananda Suresh · Jae Ro · Ahmad Beirami · Himanshu Jain · Felix Xinnan Yu · Michael Riley · Sanjiv Kumar -
2023 : UCB Provably Learns From Inconsistent Human Feedback »
Shuo Yang · Tongzheng Ren · Inderjit Dhillon · Sujay Sanghavi -
2023 : Contextual Set Selection Under Human Feedback With Model Misspecification »
Shuo Yang · Rajat Sen · Sujay Sanghavi -
2023 : Pretrained deep models outperform GBDTs in Learning-To-Rank under label scarcity »
Charlie Hou · Kiran Thekumparampil · Michael Shavlovsky · Giulia Fanti · Yesh Dattatreya · Sujay Sanghavi -
2023 Poster: Beyond Uniform Lipschitz Condition in Differentially Private Optimization »
Rudrajit Das · Satyen Kale · Zheng Xu · Tong Zhang · Sujay Sanghavi -
2023 Poster: Understanding Self-Distillation in the Presence of Label Noise »
Rudrajit Das · Sujay Sanghavi -
2023 Poster: Restoration-Degradation Beyond Linear Diffusions: A Non-Asymptotic Analysis For DDIM-type Samplers »
Sitan Chen · Giannis Daras · Alexandros Dimakis -
2023 Poster: Efficient Training of Language Models using Few-Shot Learning »
Sashank Jakkam Reddi · Sobhan Miryoosefi · Stefani Karp · Shankar Krishnan · Satyen Kale · Seungyeon Kim · Sanjiv Kumar -
2022 Poster: In defense of dual-encoders for neural ranking »
Aditya Menon · Sadeep Jayasumana · Ankit Singh Rawat · Seungyeon Kim · Sashank Jakkam Reddi · Sanjiv Kumar -
2022 Poster: Asymptotically-Optimal Gaussian Bandits with Side Observations »
Alexia Atsidakou · Orestis Papadigenopoulos · Constantine Caramanis · Sujay Sanghavi · Sanjay Shakkottai -
2022 Spotlight: Asymptotically-Optimal Gaussian Bandits with Side Observations »
Alexia Atsidakou · Orestis Papadigenopoulos · Constantine Caramanis · Sujay Sanghavi · Sanjay Shakkottai -
2022 Spotlight: In defense of dual-encoders for neural ranking »
Aditya Menon · Sadeep Jayasumana · Ankit Singh Rawat · Seungyeon Kim · Sashank Jakkam Reddi · Sanjiv Kumar -
2022 Poster: Robust Training of Neural Networks Using Scale Invariant Architectures »
Zhiyuan Li · Srinadh Bhojanapalli · Manzil Zaheer · Sashank Jakkam Reddi · Sanjiv Kumar -
2022 Poster: Score-Guided Intermediate Level Optimization: Fast Langevin Mixing for Inverse Problems »
Giannis Daras · Yuval Dagan · Alexandros Dimakis · Constantinos Daskalakis -
2022 Spotlight: Score-Guided Intermediate Level Optimization: Fast Langevin Mixing for Inverse Problems »
Giannis Daras · Yuval Dagan · Alexandros Dimakis · Constantinos Daskalakis -
2022 Oral: Robust Training of Neural Networks Using Scale Invariant Architectures »
Zhiyuan Li · Srinadh Bhojanapalli · Manzil Zaheer · Sashank Jakkam Reddi · Sanjiv Kumar -
2022 Poster: Linear Bandit Algorithms with Sublinear Time Complexity »
Shuo Yang · Tongzheng Ren · Sanjay Shakkottai · Eric Price · Inderjit Dhillon · Sujay Sanghavi -
2022 Poster: Correlated Quantization for Distributed Mean Estimation and Optimization »
Ananda Suresh · Ziteng Sun · Jae Ro · Felix Xinnan Yu -
2022 Spotlight: Correlated Quantization for Distributed Mean Estimation and Optimization »
Ananda Suresh · Ziteng Sun · Jae Ro · Felix Xinnan Yu -
2022 Spotlight: Linear Bandit Algorithms with Sublinear Time Complexity »
Shuo Yang · Tongzheng Ren · Sanjay Shakkottai · Eric Price · Inderjit Dhillon · Sujay Sanghavi -
2021 : Invited Talk: Alex Dimakis »
Alexandros Dimakis -
2021 Poster: Provable Lipschitz Certification for Generative Models »
Matt Jordan · Alexandros Dimakis -
2021 Spotlight: Provable Lipschitz Certification for Generative Models »
Matt Jordan · Alexandros Dimakis -
2021 Poster: Fairness for Image Generation with Uncertain Sensitive Attributes »
Ajil Jalal · Sushrut Karmalkar · Jessica Hoffmann · Alexandros Dimakis · Eric Price -
2021 Poster: Active Covering »
Heinrich Jiang · Afshin Rostamizadeh -
2021 Spotlight: Active Covering »
Heinrich Jiang · Afshin Rostamizadeh -
2021 Spotlight: Fairness for Image Generation with Uncertain Sensitive Attributes »
Ajil Jalal · Sushrut Karmalkar · Jessica Hoffmann · Alexandros Dimakis · Eric Price -
2021 Poster: Solving Inverse Problems with a Flow-based Noise Model »
Jay Whang · Qi Lei · Alexandros Dimakis -
2021 Spotlight: Solving Inverse Problems with a Flow-based Noise Model »
Jay Whang · Qi Lei · Alexandros Dimakis -
2021 Poster: Instance-Optimal Compressed Sensing via Posterior Sampling »
Ajil Jalal · Sushrut Karmalkar · Alexandros Dimakis · Eric Price -
2021 Poster: A statistical perspective on distillation »
Aditya Menon · Ankit Singh Rawat · Sashank Jakkam Reddi · Seungyeon Kim · Sanjiv Kumar -
2021 Poster: Intermediate Layer Optimization for Inverse Problems using Deep Generative Models »
Giannis Daras · Joseph Dean · Ajil Jalal · Alexandros Dimakis -
2021 Poster: Composing Normalizing Flows for Inverse Problems »
Jay Whang · Erik Lindgren · Alexandros Dimakis -
2021 Poster: Disentangling Sampling and Labeling Bias for Learning in Large-output Spaces »
Ankit Singh Rawat · Aditya Menon · Wittawat Jitkrittum · Sadeep Jayasumana · Felix Xinnan Yu · Sashank Jakkam Reddi · Sanjiv Kumar -
2021 Spotlight: Intermediate Layer Optimization for Inverse Problems using Deep Generative Models »
Giannis Daras · Joseph Dean · Ajil Jalal · Alexandros Dimakis -
2021 Spotlight: Instance-Optimal Compressed Sensing via Posterior Sampling »
Ajil Jalal · Sushrut Karmalkar · Alexandros Dimakis · Eric Price -
2021 Spotlight: A statistical perspective on distillation »
Aditya Menon · Ankit Singh Rawat · Sashank Jakkam Reddi · Seungyeon Kim · Sanjiv Kumar -
2021 Spotlight: Composing Normalizing Flows for Inverse Problems »
Jay Whang · Erik Lindgren · Alexandros Dimakis -
2021 Spotlight: Disentangling Sampling and Labeling Bias for Learning in Large-output Spaces »
Ankit Singh Rawat · Aditya Menon · Wittawat Jitkrittum · Sadeep Jayasumana · Felix Xinnan Yu · Sashank Jakkam Reddi · Sanjiv Kumar -
2020 Poster: SGD Learns One-Layer Networks in WGANs »
Qi Lei · Jason Lee · Alexandros Dimakis · Constantinos Daskalakis -
2020 Poster: Does label smoothing mitigate label noise? »
Michal Lukasik · Srinadh Bhojanapalli · Aditya Menon · Sanjiv Kumar -
2020 Poster: Low-Rank Bottleneck in Multi-head Attention Models »
Srinadh Bhojanapalli · Chulhee Yun · Ankit Singh Rawat · Sashank Jakkam Reddi · Sanjiv Kumar -
2020 Poster: Accelerating Large-Scale Inference with Anisotropic Vector Quantization »
Ruiqi Guo · Philip Sun · Erik Lindgren · Quan Geng · David Simcha · Felix Chern · Sanjiv Kumar -
2020 Poster: Extreme Multi-label Classification from Aggregated Labels »
Yanyao Shen · Hsiang-Fu Yu · Sujay Sanghavi · Inderjit Dhillon -
2020 Poster: Federated Learning with Only Positive Labels »
Felix Xinnan Yu · Ankit Singh Rawat · Aditya Menon · Sanjiv Kumar -
2019 : Alex Dimakis: Coding Theory for Distributed Learning »
Alexandros Dimakis -
2019 : Structured matrices for efficient deep learning »
Sanjiv Kumar -
2019 Poster: Escaping Saddle Points with Adaptive Gradient Methods »
Matthew Staib · Sashank Jakkam Reddi · Satyen Kale · Sanjiv Kumar · Suvrit Sra -
2019 Poster: Categorical Feature Compression via Submodular Optimization »
Mohammad Hossein Bateni · Lin Chen · Hossein Esfandiari · Thomas Fu · Vahab Mirrokni · Afshin Rostamizadeh -
2019 Oral: Categorical Feature Compression via Submodular Optimization »
Mohammad Hossein Bateni · Lin Chen · Hossein Esfandiari · Thomas Fu · Vahab Mirrokni · Afshin Rostamizadeh -
2019 Oral: Escaping Saddle Points with Adaptive Gradient Methods »
Matthew Staib · Sashank Jakkam Reddi · Satyen Kale · Sanjiv Kumar · Suvrit Sra -
2019 Poster: Learning with Bad Training Data via Iterative Trimmed Loss Minimization »
Yanyao Shen · Sujay Sanghavi -
2019 Oral: Learning with Bad Training Data via Iterative Trimmed Loss Minimization »
Yanyao Shen · Sujay Sanghavi -
2018 Poster: Gradient Coding from Cyclic MDS Codes and Expander Graphs »
Netanel Raviv · Rashish Tandon · Alexandros Dimakis · Itzhak Tamo -
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 Oral: Gradient Coding from Cyclic MDS Codes and Expander Graphs »
Netanel Raviv · Rashish Tandon · Alexandros Dimakis · Itzhak Tamo -
2017 Poster: Identifying Best Interventions through Online Importance Sampling »
Rajat Sen · Karthikeyan Shanmugam · Alexandros Dimakis · Sanjay Shakkottai -
2017 Poster: Cost-Optimal Learning of Causal Graphs »
Murat Kocaoglu · Alexandros Dimakis · Sriram Vishwanath -
2017 Poster: Stochastic Generative Hashing »
Bo Dai · Ruiqi Guo · Sanjiv Kumar · Niao He · Le Song -
2017 Poster: On Approximation Guarantees for Greedy Low Rank Optimization »
RAJIV KHANNA · Ethan R. Elenberg · Alexandros Dimakis · Joydeep Ghosh · Sahand Negahban -
2017 Talk: Identifying Best Interventions through Online Importance Sampling »
Rajat Sen · Karthikeyan Shanmugam · Alexandros Dimakis · Sanjay Shakkottai -
2017 Talk: Stochastic Generative Hashing »
Bo Dai · Ruiqi Guo · Sanjiv Kumar · Niao He · Le Song -
2017 Talk: On Approximation Guarantees for Greedy Low Rank Optimization »
RAJIV KHANNA · Ethan R. Elenberg · Alexandros Dimakis · Joydeep Ghosh · Sahand Negahban -
2017 Talk: Cost-Optimal Learning of Causal Graphs »
Murat Kocaoglu · Alexandros Dimakis · Sriram Vishwanath -
2017 Poster: Distributed Mean Estimation with Limited Communication »
Ananda Theertha Suresh · Felix Xinnan Yu · Sanjiv Kumar · Brendan McMahan -
2017 Poster: Exact MAP Inference by Avoiding Fractional Vertices »
Erik Lindgren · Alexandros Dimakis · Adam Klivans -
2017 Poster: Compressed Sensing using Generative Models »
Ashish Bora · Ajil Jalal · Eric Price · Alexandros Dimakis -
2017 Poster: Gradient Coding: Avoiding Stragglers in Distributed Learning »
Rashish Tandon · Qi Lei · Alexandros Dimakis · Nikos Karampatziakis -
2017 Talk: Gradient Coding: Avoiding Stragglers in Distributed Learning »
Rashish Tandon · Qi Lei · Alexandros Dimakis · Nikos Karampatziakis -
2017 Talk: Distributed Mean Estimation with Limited Communication »
Ananda Theertha Suresh · Felix Xinnan Yu · Sanjiv Kumar · Brendan McMahan -
2017 Talk: Compressed Sensing using Generative Models »
Ashish Bora · Ajil Jalal · Eric Price · Alexandros Dimakis -
2017 Talk: Exact MAP Inference by Avoiding Fractional Vertices »
Erik Lindgren · Alexandros Dimakis · Adam Klivans