Forster Decomposition and Learning Halfspaces with Noise

• URL: http://arxiv.org/abs/2107.05582v1
• Date: Mon, 12 Jul 2021 17:00:59 GMT
• Title: Forster Decomposition and Learning Halfspaces with Noise
• Authors: Ilias Diakonikolas and Daniel M. Kane and Christos Tzamos
• Abstract summary: A Forster transform is an operation that turns a distribution into one with good anti-concentration properties. We show that any distribution can be decomposed efficiently as a disjoint mixture of few distributions for which a Forster transform exists and can be computed efficiently.
• Score: 60.691817861402676
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A Forster transform is an operation that turns a distribution into one with good anti-concentration properties. While a Forster transform does not always exist, we show that any distribution can be efficiently decomposed as a disjoint mixture of few distributions for which a Forster transform exists and can be computed efficiently. As the main application of this result, we obtain the first polynomial-time algorithm for distribution-independent PAC learning of halfspaces in the Massart noise model with strongly polynomial sample complexity, i.e., independent of the bit complexity of the examples. Previous algorithms for this learning problem incurred sample complexity scaling polynomially with the bit complexity, even though such a dependence is not information-theoretically necessary.

Related papers

• Distributed Extra-gradient with Optimal Complexity and Communication Guarantees [60.571030754252824]
  We consider monotone variational inequality (VI) problems in multi-GPU settings where multiple processors/workers/clients have access to local dual vectors. Extra-gradient, which is a de facto algorithm for monotone VI problems, has not been designed to be communication-efficient. We propose a quantized generalized extra-gradient (Q-GenX), which is an unbiased and adaptive compression method tailored to solve VIs.
  arXiv  Detail & Related papers  (2023-08-17T21:15:04Z)
• A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning [56.86097988183311]
  The Forster transform is a method of regularizing a dataset by placing it in em radial isotropic position while maintaining some of its essential properties.
  arXiv  Detail & Related papers  (2022-12-06T14:32:02Z)
• On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
  Social and real-world considerations have given rise to multi-distribution learning paradigms. We establish the optimal sample complexity of these learning paradigms and give algorithms that meet this sample complexity. Our algorithm design and analysis are enabled by our extensions of online learning techniques for solving zero-sum games.
  arXiv  Detail & Related papers  (2022-10-22T19:07:26Z)
• Sample-Optimal PAC Learning of Halfspaces with Malicious Noise [4.8728183994912415]
  We study efficient PAC learning of halfspaces in $mathRd$ in the presence of malicious noise of Valiant(1985) We present a new analysis for the algorithm of Awasthi et al.( 2017) and show that it essentially achieves the near-optimal sample complexity bound of $tildeO(d)$. We extend the algorithm and analysis to the more general and stronger nasty noise model of Bbbshoutyetal (2002), showing that it is still possible to achieve near-optimal noise tolerance and sample complexity in time.
  arXiv  Detail & Related papers  (2021-02-11T20:18:20Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  We propose a simple and efficient unsupervised feature selection method, by combining reconstruction error with $l_2,p$-norm regularization. We present an efficient optimization algorithm to solve the proposed unsupervised model, and analyse the convergence and computational complexity of the algorithm theoretically.
  arXiv  Detail & Related papers  (2020-12-29T04:08:38Z)
• Learning Structured Distributions From Untrusted Batches: Faster and Simpler [26.57313255285721]
  We revisit the problem of learning from untrusted batches introduced by Qiao and Valiant [QV17]. We find an appealing way to synthesize the techniques of [JO19] and [CLM19] to give the best of both worlds: an algorithm which runs in monotone time and can exploit structure in the underlying distribution to achieve sublinear sample.
  arXiv  Detail & Related papers  (2020-02-24T18:32:10Z)
• SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  SURF is an algorithm for approximating distributions by piecewises. It outperforms state-of-the-art algorithms in experiments.
  arXiv  Detail & Related papers  (2020-02-22T01:03:33Z)

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.