Recovery of sparse linear classifiers from mixture of responses

• URL: http://arxiv.org/abs/2010.12087v3
• Date: Thu, 24 Dec 2020 21:06:09 GMT
• Title: Recovery of sparse linear classifiers from mixture of responses
• Authors: Venkata Gandikota, Arya Mazumdar, Soumyabrata Pal
• Abstract summary: We show how 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 belongs to.
• Score: 42.228977798395846
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 belongs to. This model provides a rich representation of 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 $\ell$ unknown $k$-sparse vectors. We can query the set with another vector $\boldsymbol{a}$, to obtain the sign of the inner product of $\boldsymbol{a}$ and a randomly chosen vector from the $\ell$-set. How many queries are sufficient to identify all the $\ell$ unknown vectors? This question is significantly more challenging than both the basic 1-bit compressed sensing problem (i.e., $\ell=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.

Related papers

• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Matching Map Recovery with an Unknown Number of Outliers [0.0]
  We consider the problem of finding the matching map between two sets of $d$-dimensional noisy feature-vectors. We show that, in the high-dimensional setting, if the signal-to-noise ratio is larger than $5(dlog(4nm/alpha))1/4$, the true matching map can be recovered with probability $1-alpha$.
  arXiv  Detail & Related papers  (2022-10-24T15:59:10Z)
• Improved analysis of randomized SVD for top-eigenvector approximation [16.905540623795467]
  We present a novel analysis of the randomized SVD algorithm of citethalko2011finding and derive tight bounds in many cases of interest. Notably, this is the first work that provides non-trivial bounds of $R(hatmathbfu)$ for randomized SVD with any number of iterations.
  arXiv  Detail & Related papers  (2022-02-16T11:12:07Z)
• On the query complexity of connectivity with global queries [0.2538209532048867]
  We study the query complexity of determining if a graph is connected with global queries. We show that a zero-error randomized algorithm must make $Omega(n)$ linear queries in expectation to solve connectivity.
  arXiv  Detail & Related papers  (2021-09-05T16:22:55Z)
• Support Recovery of Sparse Signals from a Mixture of Linear Measurements [48.556633593447465]
  Recovery of support of a sparse vector from simple measurements is a widely studied problem. We consider generalizations of this problem: mixtures of linear regressions, and mixtures of linear classifiers. We provide algorithms that use a number of measurements in $k, log n$ and quasi-polynomial in $ell$ to recover the support of all the unknown vectors in the mixture.
  arXiv  Detail & Related papers  (2021-06-10T17:48:13Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  The fuzzy or soft objective is a popular generalization of the well-known $k$-means problem. We show that by making few queries, the problem becomes easier to solve.
  arXiv  Detail & Related papers  (2021-06-04T02:32:26Z)
• Optimal Spectral Recovery of a Planted Vector in a Subspace [80.02218763267992]
  We study efficient estimation and detection of a planted vector $v$ whose $ell_4$ norm differs from that of a Gaussian vector with the same $ell$ norm. We show that in the regime $n rho gg sqrtN$, any spectral method from a large class (and more generally, any low-degree of the input) fails to detect the planted vector.
  arXiv  Detail & Related papers  (2021-05-31T16:10:49Z)
• Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems [58.83118651518438]
  We consider the general problem of learning about a matrix through vector-matrix-vector queries. These queries provide the value of $boldsymbolumathrmTboldsymbolMboldsymbolv$ over a fixed field. We provide new upper and lower bounds for a wide variety of problems, spanning linear algebra, statistics, and graphs.
  arXiv  Detail & Related papers  (2020-06-24T19:33:49Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.