Gradient descent finds halfspaces with low error for agnostic learning.
problem Agnostic learning of linear halfspaces with convex surrogates.
method Gradient descent on convex surrogates for zero-one loss.
result Gradient descent finds halfspaces with error O ( O P T 1 / 2 + ε ) O(\mathsf{OPT}^{1/2} + \varepsilon) O ( OPT 1/2 + ε ) in poly time and sample complexity. The study establishes SQ lower bounds for learning halfspaces and ReLUs under Gaussian marginals.
problem Agnostically learning halfspaces and ReLUs under Gaussian marginals.
method Statistical Query (SQ) lower bounds analysis.
result Proves SQ lower bounds of d p o l y ( 1 / ε ) d^{\mathrm{poly}(1/ε)} d poly ( 1/ ε ) for both problems. We present new differentially private algorithms for learning a large-margin halfspace. In contrast to previous algorithms, which are based on either differentially private simulations of the statistical query model or on private convex optimization, the sample complexity of our algorithms depends only on the margin of…
Efficient algorithms improve learning of large-margin halfspaces.
problem Learning large-margin halfspaces efficiently and reproducibly.
method Design of efficient, dimension-independent, polynomial-time algorithms; SGD-based approach; DP-to-Replicability reduction.
result Improved sample complexity compared to previous algorithms, with optimal sample complexity for one algorithm.
We present an improved algorithm for {\em quasi-properly} learning convex polyhedra in the realizable PAC setting from data with a margin. Our learning algorithm constructs a consistent polyhedron as an intersection of about t log t t \log t t log t halfspaces with constant-size margins in time polynomial in t t t (where t t t is the nu…
New algorithms for privately learning decision lists and halfspaces.
problem Private learning of decision lists and halfspaces.
method Differentially private algorithms for PAC and online models.
result Private algorithms match or surpass non-private guarantees.
We introduce a simple framework for designing private boosting algorithms. We give natural conditions under which these algorithms are differentially private, efficient, and noise-tolerant PAC learners. To demonstrate our framework, we use it to construct noise-tolerant and private PAC learners for large-margin halfspa…
New algorithm learns halfspaces with near-optimal sample complexity in noisy conditions.
problem Learning margin halfspaces with Massart noise.
method Computational efficient algorithm using online SGD on carefully selected convex losses.
result Sample complexity of Θ ~ ( 1 / ( γ 2 ε 2 ) ) \widetilde{\Theta}(1/(γ^2 ε^2)) Θ ( 1/ ( γ 2 ε 2 )) , nearly matching lower bound. Non-convex SGD learns halfspaces with adversarial label noise efficiently.
problem Agnostically learning halfspaces in adversarial label noise settings.
method Non-convex SGD optimization for halfspace learning.
result Non-convex SGD achieves misclassification error close to optimal with adversarial noise.
Study shows a tradeoff between sample complexity and computational efficiency for learning halfspaces with random noise.
problem PAC learning γ-margin halfspaces with Random Classification Noise.
method Established an information-computation tradeoff and provided a simple efficient algorithm with sample complexity O(1/(γ^2 ε^2)). Also, proved lower bounds for SQ algorithms and low-degree polynomial tests.
result Inherent gap between sample complexity and computational efficiency for learning halfspaces with random noise.
First proper learning algorithm for Gaussian halfspaces with matching sample and computational complexity.
problem Agnostically learning halfspaces under Gaussian distribution.
method First proper learning algorithm with matching sample and computational complexity.
result First proper learning algorithm for agnostically learning halfspaces under Gaussian distribution with matching sample and computational complexity.
Self-training algorithm improves classifier performance with labeled and unlabeled data.
problem Improving classifier performance with limited labeled data.
method Iterative learning of halfspaces, exploration and pruning phases.
result Misclassification error is bounded and never degrades compared to initial labeled set.
Study efficient learning of halfspaces with constant noise tolerance.
problem Learning halfspaces in the presence of both instance and label corruption.
method Develops an algorithm to minimize reweighted hinge loss for robustness.
result Achieves constant noise tolerance for halfspace learning.
New algorithm for reliable learning of Gaussian halfspaces with improved sample and computational complexity.
problem Learning halfspaces under Gaussian marginals with reliable agnostic model.
method Developed a new algorithm for reliable learning of Gaussian halfspaces with specific sample and computational complexity.
result Achieved a new algorithm with improved sample and computational complexity for reliable learning of Gaussian halfspaces.
We derive and analyze a new, efficient, pool-based active learning algorithm for halfspaces, called ALuMA. Most previous algorithms show exponential improvement in the label complexity assuming that the distribution over the instance space is close to uniform. This assumption rarely holds in practical applications. Ins…
New algorithm learns halfspaces with adversarial noise efficiently.
problem Learning halfspaces in the presence of adversarial noise.
method Polynomial-time Perceptron-like online active learning algorithm.
result Near-optimal label and sample complexity with isotropic log-concave marginal distribution.
We study the problem of {\em properly} learning large margin halfspaces in the agnostic PAC model. In more detail, we study the complexity of properly learning d d d -dimensional halfspaces on the unit ball within misclassification error α ⋅ O P T γ + ε α\cdot \mathrm{OPT}_γ + ε α ⋅ OPT γ + ε , where O P T γ \mathrm{OPT}_γ OPT γ is the optimal γ γ γ -margin error r…
Christoffel function characterizes the corruption a bounded-degree certificate cannot remove in robust halfspace learning.
problem Robust halfspace learning under malicious noise
method Sum-of-Squares degree of outlier-removal certificate
result Christoffel function bounds the corruption a bounded-degree certificate cannot remove
Efficiently learns complex Boolean functions under Gaussian distributions.
problem Learning complex Boolean functions of halfspaces under Gaussian marginals.
method First efficient proper agnostic learning algorithm for arbitrary Boolean functions of K halfspaces.
result Matches the best known improper learning algorithm's run-time dependence on dimension.
Near-optimal SQ hardness shows learning halfspaces with Massart noise is hard.
problem Learning halfspaces with Massart noise in the presence of label corruption.
method Statistical Query (SQ) model analysis.
result No efficient SQ algorithm can achieve better than Ω ( η ) Ω(η) Ω ( η ) error, even for optimal noise levels. Polynomial-time algorithm learns high-dimensional halfspaces without labels.
problem Learning high-dimensional halfspaces with margins in polynomial time.
method Contrastive moments and polynomial-time algorithm.
result Establishes the unique and efficient identifiability of the hidden halfspace.
Universal tester-learner for halfspaces over structured distributions.
problem Learning halfspaces over a wide class of structured distributions.
method Uses a fully polynomial tester-learner based on hypercontractivity and sum-of-squares (SOS) programs.
result Achieves error O ( o p t ) + ε O(\mathrm{opt}) + ε O ( opt ) + ε on any labeled distribution that the tester accepts. We study the problem of {\em distribution-independent} PAC learning of halfspaces in the presence of Massart noise. Specifically, we are given a set of labeled examples ( x , y ) (\mathbf{x}, y) ( x , y ) drawn from a distribution D \mathcal{D} D on R d + 1 \mathbb{R}^{d+1} R d + 1 such that the marginal distribution on the unlabeled points $\mathbf{x}…
Hardness proof for agnostically learning halfspaces from worst-case lattice problems.
problem Agnostically learning halfspaces in the presence of noise.
method Reduction to worst-case lattice problems (GapSVP, SIVP).
result No efficient algorithm can achieve misclassification error better than 1/2 - γ under given hardness assumptions.
Generalizes halfspace theorems to higher dimensions for self-shrinkers.
problem Limitations of halfspace theorems in higher dimensions for self-shrinkers.
method Extends codimension 1 results to arbitrary codimension.
result Establishes new halfspace theorems for self-shrinkers in arbitrary codimension.
We provide new results for noise-tolerant and sample-efficient learning algorithms under s s s -concave distributions. The new class of s s s -concave distributions is a broad and natural generalization of log-concavity, and includes many important additional distributions, e.g., the Pareto distribution and t t t -distribution.…
Polynomial-time tester-learner for general halfspaces with Gaussian adversarial noise.
problem Learning general halfspaces with adversarial label noise.
method Reduction to testable learning of nearly homogeneous halfspaces.
result First polynomial time tester-learner for general halfspaces with dimension-independent misclassification error.
Efficient algorithms for monophonic halfspaces in graphs simplify learning and compression.
problem Learning and compressing monophonic halfspaces in graphs.
method 2-satisfiability based decomposition theorem, efficient algorithms for various learning problems.
result Achieved efficient and nearly optimal algorithms for various learning problems.
Study efficient learning of robust halfspaces with noise.
problem Learning robust halfspaces in the presence of adversarial perturbations and random label noise.
method Provides conditions for robust learnability and a simple algorithm for any ℓ_p perturbation.
result Simple computationally efficient algorithm for robust learning with random label noise.
New lower bounds show learning intersections of halfspaces is hard even for a few halfspaces.
problem Learning intersections of halfspaces in polynomial time under standard assumptions.
method Unified connection to parallel pancakes distribution for proving hardness.
result Learning ω ( log log N ) ω(\log \log N) ω ( log log N ) halfspaces in dimension N N N requires super-polynomial time under standard assumptions. We develop the Lorentzian geometry of a crooked halfspace in 2+1-dimensional Minkowski space. We calculate the affine, conformal and isometric automorphism groups of a crooked halfspace, and discuss its stratification into orbit types, giving an explicit slice for the action of the automorphism group. The set of parall…
Solves learning halfspaces with Massart noise for log-concave distributions.
problem Learning halfspaces with Massart noise in distribution-specific PAC model.
method Identifies a smooth non-convex surrogate loss and uses SGD to solve the learning problem.
result First computationally efficient algorithm for learning halfspaces with Massart noise for a broad family of distributions.
Efficiently learns monophonic halfspaces in graph vertices.
problem Learning binary classifiers on graph vertices using monophonic halfspaces.
method Polynomial-time algorithm for consistent hypothesis checking, based on structural insights and reduction to 2-satisfiability.
result Near-optimal passive sample complexity for monophonic halfspaces in polynomial time.
New SQ lower bound shows complexity nearly matches known upper bound for smoothed agnostic learning.
problem Smoothed agnostic learning of halfspaces under subgaussian distributions.
method Statistical Query (SQ) lower bound using moment-matching hard distribution and linear programming duality.
result First non-trivial lower bound on complexity nearly matches known upper bound.
Study learning halfspaces with Massart noise under Gaussian distribution, improving previous results.
problem Learning halfspaces with Massart noise under Gaussian distribution, especially when the parameter is 1/2.
method Developed algorithms for general and homogeneous halfspaces with sample and computational complexities.
result Established qualitatively matching lower bounds for the complexities of learning algorithms.
Study privacy and robustness in learning halfspaces, proving hard trade-offs.
problem Balancing privacy and robustness in learning halfspaces.
method Proves nearly tight bounds on sample complexity for robust private learning of halfspaces.
result Robust and private learning is harder than robust or private learning alone.
Polynomial-time algorithm for learning halfspaces with Gaussian-distributed data and adversarial noise.
problem Learning halfspaces in the presence of adversarial label noise.
method Iterative soft localization technique enhanced with appropriate testers.
result Output a halfspace with misclassification error $O(\opt)+\eps$ .
Study on learning halfspaces under adversarial perturbations, finding computational hardness.
problem Learning halfspaces in the presence of adversarial noise.
method Introduced an efficient learning algorithm and proved a nearly matching computational hardness result.
result The L ∞ L_{\infty} L ∞ perturbations case is provably computationally harder than 2 ≤ p < ∞ 2 \leq p < \infty 2 ≤ p < ∞ . Adversarial training improves robustness of halfspaces in noisy data.
problem Learning robust halfspaces in the presence of label noise.
method Adversarial training with binary cross-entropy or nonconvex sigmoidal loss.
result Adversarial training yields robust halfspaces with improved classification error.
Strongly polynomial algorithm for approximate Forster transforms and halfspace learning.
problem Computing approximate Forster transforms and halfspace learning.
method Strongly polynomial time algorithm for approximate Forster transforms and halfspace learning.
result First strongly polynomial time algorithm for distribution-free PAC learning of halfspaces.
Introduces Polar Depth for analyzing multivariate heavy-tailed data extremes.
problem Analyzing the behavior of extremes from multivariate heavy-tailed distributions.
method Introduces Polar Depth, a novel statistical depth function expressed in polar coordinates.
result The polar depth of the largest observations converges to the polar depth of the limiting distribution as the threshold increases.
New algorithm learns halfspaces over hypercube with random bit flips.
problem Agnostic learning of Boolean halfspaces over discrete domains is computationally hard.
method Smoothed analysis with random bit flips for discrete inputs.
result First efficient algorithm for smoothed agnostic learning of halfspaces over Boolean hypercube.
Study efficient active learning for halfspaces with Tsybakov noise using non-convex optimization.
problem Efficiently learn halfspaces with Tsybakov noise under structured unlabeled data.
method Non-convex optimization approach to find approximate first-order stationary points.
result Designs an algorithm with improved label complexity compared to previous methods.
While it is well known from examples that no interesting `halfspace theorem' holds for properly immersed complete n n n -dimensional self-translating mean curvature flow solitons in Euclidean space R n + 1 \mathbb{R}^{n+1} R n + 1 , we show that they must all obey a general `bi-halfspace theorem': Two transverse vertical halfspaces can …
Algorithm learns halfspaces with Tsybakov noise in polynomial time.
problem PAC learning halfspaces with adversarial noise.
method Reduction to certifying non-optimality, iterative process, warm-start algorithm.
result First polynomial-time algorithm for learning halfspaces with Tsybakov noise.
Study near-optimal bounds for learning Gaussian halfspaces with random noise.
problem Learning general halfspaces with Gaussian distribution and random classification noise.
method Established nearly-matching algorithmic and SQ lower bounds, developed a computationally efficient learning algorithm.
result Sample complexity of learning algorithm is O ( d / ε + d / ( max { p , ε } ) 2 ) O(d/ε + d/(\max\{p, ε\})^2) O ( d / ε + d / ( max { p , ε } ) 2 ) , SQ lower bound is Ω ( d 1 / 2 / ( max { p , ε } ) 2 ) Ω(d^{1/2}/(\max\{p, ε\})^2) Ω ( d 1/2 / ( max { p , ε } ) 2 ) . Algorithm learns halfspaces in noisy data efficiently.
problem Learning halfspaces with Tsybakov noise.
method Novel semi-definite programming and online convex optimization.
result First non-trivial PAC learning algorithm for Tsybakov noise.
A new depth measure for non-convex data supports, faster than halfspace depth.
problem Non-convex data supports in multivariate statistics.
method Extending halfspace depth to Reproducing Kernel Hilbert Space (RKHS).
result The new depth measure is consistent and can be computed faster.