`

Timezone: »

 
Poster
Recovery of sparse linear classifiers from mixture of responses
Venkata Gandikota · Arya Mazumdar · Soumyabrata Pal

Wed Dec 09 09:00 PM -- 11:00 PM (PST) @ Poster Session 4 #1243

In the problem of learning a mixture of linear classifiers, the aim is to learn a collection of hyperplanes from a sequence of binary responses. Each response is a result of querying with a vector and indicates the side of a randomly chosen hyperplane from the collection the query vector belong to. This model is quite rich while dealing with heterogeneous data with categorical labels and has only been studied in some special settings. We look at a hitherto unstudied problem of query complexity upper bound of recovering all the hyperplanes, especially for the case when the hyperplanes are sparse. This setting is a natural generalization of the extreme quantization problem known as 1-bit compressed sensing. Suppose we have a set of l unknown k-sparse vectors. We can query the set with another vector a, to obtain the sign of the inner product of a and a randomly chosen vector from the l-set. How many queries are sufficient to identify all the l unknown vectors? This question is significantly more challenging than both the basic 1-bit compressed sensing problem (i.e., l = 1 case) and the analogous regression problem (where the value instead of the sign is provided). We provide rigorous query complexity results (with efficient algorithms) for this problem.

Author Information

Venkata Gandikota (Syracuse University)
Arya Mazumdar (University of California, San Diego)
Soumyabrata Pal (University of Massachusetts Amherst)

I am a fourth year grad student in the Department of Computer Science at the University of Massachusetts Amherst.

More from the Same Authors

  • 2021 Poster: Support Recovery of Sparse Signals from a Mixture of Linear Measurements »
    Soumyabrata Pal · Arya Mazumdar · Venkata Gandikota
  • 2021 Poster: Fuzzy Clustering with Similarity Queries »
    Wasim Huleihel · Arya Mazumdar · Soumyabrata Pal
  • 2020 Poster: Multilabel Classification by Hierarchical Partitioning and Data-dependent Grouping »
    Shashanka Ubaru · Sanjeeb Dash · Arya Mazumdar · Oktay Gunluk
  • 2020 Poster: Distributed Newton Can Communicate Less and Resist Byzantine Workers »
    Avishek Ghosh · Raj Kumar Maity · Arya Mazumdar
  • 2019 : Poster Session »
    Gergely Flamich · Shashanka Ubaru · Charles Zheng · Josip Djolonga · Kristoffer Wickstrøm · Diego Granziol · Konstantinos Pitas · Jun Li · Robert Williamson · Sangwoong Yoon · Kwot Sin Lee · Julian Zilly · Linda Petrini · Ian Fischer · Zhe Dong · Alexander Alemi · Bao-Ngoc Nguyen · Rob Brekelmans · Tailin Wu · Aditya Mahajan · Alexander Li · Kirankumar Shiragur · Yair Carmon · Linara Adilova · SHIYU LIU · Bang An · Sanjeeb Dash · Oktay Gunluk · Arya Mazumdar · Mehul Motani · Julia Rosenzweig · Michael Kamp · Marton Havasi · Leighton P Barnes · Zhengqing Zhou · Yi Hao · Dylan Foster · Yuval Benjamini · Nati Srebro · Michael Tschannen · Paul Rubenstein · Sylvain Gelly · John Duchi · Aaron Sidford · Robin Ru · Stefan Zohren · Murtaza Dalal · Michael A Osborne · Stephen J Roberts · Moses Charikar · Jayakumar Subramanian · Xiaodi Fan · Max Schwarzer · Nicholas Roberts · Simon Lacoste-Julien · Vinay Prabhu · Aram Galstyan · Greg Ver Steeg · Lalitha Sankar · Yung-Kyun Noh · Gautam Dasarathy · Frank Park · Ngai-Man (Man) Cheung · Ngoc-Trung Tran · Linxiao Yang · Ben Poole · Andrea Censi · Tristan Sylvain · R Devon Hjelm · Bangjie Liu · Jose Gallego-Posada · Tyler Sypherd · Kai Yang · Jan Nikolas Morshuis
  • 2019 : Poster Session »
    Jonathan Scarlett · Piotr Indyk · Ali Vakilian · Adrian Weller · Partha P Mitra · Benjamin Aubin · Bruno Loureiro · Florent Krzakala · Lenka Zdeborová · Kristina Monakhova · Joshua Yurtsever · Laura Waller · Hendrik Sommerhoff · Michael Moeller · Rushil Anirudh · Shuang Qiu · Xiaohan Wei · Zhuoran Yang · Jayaraman Thiagarajan · Salman Asif · Michael Gillhofer · Johannes Brandstetter · Sepp Hochreiter · Felix Petersen · Dhruv Patel · Assad Oberai · Akshay Kamath · Sushrut Karmalkar · Eric Price · Ali Ahmed · Zahra Kadkhodaie · Sreyas Mohan · Eero Simoncelli · Carlos Fernandez-Granda · Oscar Leong · Wesam Sakla · Rebecca Willett · Stephan Hoyer · Jascha Sohl-Dickstein · Samuel Greydanus · Gauri Jagatap · Chinmay Hegde · Michael Kellman · Jonathan Tamir · Nouamane Laanait · Ousmane Dia · Mirco Ravanelli · Jonathan Binas · Negar Rostamzadeh · Shirin Jalali · Tiantian Fang · Alex Schwing · Sébastien Lachapelle · Philippe Brouillard · Tristan Deleu · Simon Lacoste-Julien · Stella Yu · Arya Mazumdar · Ankit Singh Rawat · Yue Zhao · Jianshu Chen · Xiaoyang Li · Hubert Ramsauer · Gabrio Rizzuti · Nikolaos Mitsakos · Dingzhou Cao · Thomas Strohmer · Yang Li · Pei Peng · Gregory Ongie
  • 2019 Poster: Superset Technique for Approximate Recovery in One-Bit Compressed Sensing »
    Larkin Flodin · Venkata Gandikota · Arya Mazumdar
  • 2019 Poster: Sample Complexity of Learning Mixture of Sparse Linear Regressions »
    Akshay Krishnamurthy · Arya Mazumdar · Andrew McGregor · Soumyabrata Pal
  • 2019 Poster: Same-Cluster Querying for Overlapping Clusters »
    Wasim Huleihel · Arya Mazumdar · Muriel Medard · Soumyabrata Pal
  • 2017 : The Geometric Block Model (poster). »
    Soumyabrata Pal
  • 2017 Poster: Clustering with Noisy Queries »
    Arya Mazumdar · Barna Saha
  • 2017 Poster: Semisupervised Clustering, AND-Queries and Locally Encodable Source Coding »
    Arya Mazumdar · Soumyabrata Pal
  • 2017 Spotlight: Semisupervised Clustering, AND-Queries and Locally Encodable Source Coding »
    Arya Mazumdar · Soumyabrata Pal
  • 2017 Poster: Query Complexity of Clustering with Side Information »
    Arya Mazumdar · Barna Saha
  • 2015 Poster: Associative Memory via a Sparse Recovery Model »
    Arya Mazumdar · Ankit Singh Rawat