Timezone: »
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 1bit compressed sensing. Suppose we have a set of l unknown ksparse 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 lset. How many queries are sufficient to identify all the l unknown vectors? This question is significantly more challenging than both the basic 1bit 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 Datadependent 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: Superset Technique for Approximate Recovery in OneBit 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: SameCluster Querying for Overlapping Clusters »
Wasim Huleihel · Arya Mazumdar · Muriel Medard · Soumyabrata Pal 
2017 Poster: Semisupervised Clustering, ANDQueries and Locally Encodable Source Coding »
Arya Mazumdar · Soumyabrata Pal 
2017 Spotlight: Semisupervised Clustering, ANDQueries and Locally Encodable Source Coding »
Arya Mazumdar · Soumyabrata Pal