A polynomial-time algorithm for learning noisy linear threshold functions
From MaRDI portal
Publication:1271190
DOI10.1007/PL00013833zbMath0910.68169WikidataQ57401546 ScholiaQ57401546MaRDI QIDQ1271190
Santosh Vempala, Avrim L. Blum, Alan M. Frieze, Ravindran Kannan
Publication date: 11 November 1998
Published in: Algorithmica (Search for Journal in Brave)
Related Items (22)
On the Complexity of Random Satisfiability Problems with Planted Solutions ⋮ Learning DNF in time \(2^{\widetilde O(n^{1/3})}\) ⋮ Optimal outlier removal in high-dimensional spaces ⋮ Learning from binary labels with instance-dependent noise ⋮ On the Power of Learning from k-Wise Queries ⋮ An algorithmic theory of learning: robust concepts and random projection ⋮ Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization ⋮ On the hardness of learning intersections of two halfspaces ⋮ Learning Kernel Perceptrons on Noisy Data Using Random Projections ⋮ A complete characterization of statistical query learning with applications to evolvability ⋮ Online transfer learning ⋮ A simple polynomial-time rescaling algorithm for solving linear programs ⋮ An algorithmic theory of learning: Robust concepts and random projection ⋮ A deterministic rescaled perceptron algorithm ⋮ Robust logics ⋮ Unconditional lower bounds for learning intersections of halfspaces ⋮ Boosting in the presence of noise ⋮ Worst-case analysis of the Perceptron and Exponentiated Update algorithms ⋮ Learning fixed-dimension linear thresholds from fragmented data ⋮ Statistical active learning algorithms for noise tolerance and differential privacy ⋮ Pseudorandom Functions: Three Decades Later ⋮ Unconfused ultraconservative multiclass algorithms
This page was built for publication: A polynomial-time algorithm for learning noisy linear threshold functions
