Agnostically Learning Halfspaces
From MaRDI portal
Publication:3549323
DOI10.1137/060649057zbMath1155.68030OpenAlexW2106458073MaRDI QIDQ3549323
Adam R. Klivans, Yishay Mansour, Adam Tauman Kalai, Rocco A. Servedio
Publication date: 22 December 2008
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/060649057
Computational learning theory (68Q32) Learning and adaptive systems in artificial intelligence (68T05)
Related Items (34)
Hardness Amplification and the Approximate Degree of Constant-Depth Circuits ⋮ Learning from binary labels with instance-dependent noise ⋮ Approximate Degree in Classical and Quantum Computing ⋮ Nearly Optimal Solutions for the Chow Parameters Problem and Low-Weight Approximation of Halfspaces ⋮ A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting ⋮ The average sensitivity of an intersection of half spaces ⋮ Submodular Functions: Learnability, Structure, and Optimization ⋮ Improved approximation of linear threshold functions ⋮ Unnamed Item ⋮ On the hardness of learning intersections of two halfspaces ⋮ Unnamed Item ⋮ The regularized least squares algorithm and the problem of learning halfspaces ⋮ A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$ ⋮ Unnamed Item ⋮ A complete characterization of statistical query learning with applications to evolvability ⋮ Reliable agnostic learning ⋮ Polynomial regression under arbitrary product distributions ⋮ Learning $$AC^0$$ Under k-Dependent Distributions ⋮ Algorithmic Polynomials ⋮ Agnostic Learning from Tolerant Natural Proofs ⋮ Approximating the Noise Sensitivity of a Monotone Boolean Function ⋮ The hardest halfspace ⋮ Unnamed Item ⋮ Surrogate losses in passive and active learning ⋮ Tight bounds on \(\ell_1\) approximation and learning of self-bounding functions ⋮ Quantum matchgate computations and linear threshold gates ⋮ A theory of learning with similarity functions ⋮ Algorithms and lower bounds for de morgan formulas of low-communication leaf gates ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Dual lower bounds for approximate degree and Markov-Bernstein inequalities ⋮ Agnostically Learning Boolean Functions with Finite Polynomial Representation ⋮ Depth separations in neural networks: what is actually being separated?
This page was built for publication: Agnostically Learning Halfspaces
