Efficient Active Learning Halfspaces with Tsybakov Noise: A Non-convex Optimization Approach

• URL: http://arxiv.org/abs/2310.15411v2
• Date: Sat, 20 Jul 2024 00:01:06 GMT
• Title: Efficient Active Learning Halfspaces with Tsybakov Noise: A Non-convex Optimization Approach
• Authors: Yinan Li, Chicheng Zhang,
• Abstract summary: We study the problem of computationally label efficient active learning. In this paper, we prove any approximate. first-order stationary light point of a structured un-labeled data set.
• Score: 28.518140532315776
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of computationally and label efficient PAC active learning $d$-dimensional halfspaces with Tsybakov Noise~\citep{tsybakov2004optimal} under structured unlabeled data distributions. Inspired by~\cite{diakonikolas2020learning}, we prove that any approximate first-order stationary point of a smooth nonconvex loss function yields a halfspace with a low excess error guarantee. In light of the above structural result, we design a nonconvex optimization-based algorithm with a label complexity of $\tilde{O}(d (\frac{1}{\epsilon})^{\frac{8-6\alpha}{3\alpha-1}})$, under the assumption that the Tsybakov noise parameter $\alpha \in (\frac13, 1]$, which narrows down the gap between the label complexities of the previously known efficient passive or active algorithms~\citep{diakonikolas2020polynomial,zhang2021improved} and the information-theoretic lower bound in this setting.

Related papers

• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  We revisit the input perturbations framework for differential privacy where noise is added to the input $Ain mathcalS$. We first design novel efficient algorithms to privately release pair-wise cosine similarities. We derive a novel algorithm to compute $k$-way marginal queries over $n$ features.
  arXiv  Detail & Related papers  (2024-06-07T12:07:16Z)
• Stochastic Nested Compositional Bi-level Optimization for Robust Feature Learning [11.236838268731804]
  We develop and analyze algorithms for solving nested bi-level optimization problems. Our proposed algorithm does not rely on matrix complexity or mini-batches.
  arXiv  Detail & Related papers  (2023-07-11T15:52:04Z)
• Lattice partition recovery with dyadic CART [79.96359947166592]
  We study piece-wise constant signals corrupted by additive Gaussian noise over a $d$-dimensional lattice. Data of this form naturally arise in a host of applications, and the tasks of signal detection or testing, de-noising and estimation have been studied extensively in the statistical and signal processing literature. In this paper we consider instead the problem of partition recovery, i.e.of estimating the partition of the lattice induced by the constancy regions of the unknown signal. We prove that a DCART-based procedure consistently estimates the underlying partition at a rate of order $sigma2 k*
  arXiv  Detail & Related papers  (2021-05-27T23:41:01Z)
• Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Construction [18.65143269806133]
  We consider Proximal Incremental First-order (PIFO) algorithms which have access to gradient and proximal oracle for each individual component. We develop a novel approach for constructing adversarial problems, which partitions the tridiagonal matrix of classical examples into $n$ groups.
  arXiv  Detail & Related papers  (2021-03-15T11:20:31Z)
• A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm for Bilevel Optimization [112.59170319105971]
  We propose a new algorithm -- the Momentum- Single-timescale Approximation (MSTSA) -- for tackling problems. MSTSA allows us to control the error in iterations due to inaccurate solution to the lower level subproblem.
  arXiv  Detail & Related papers  (2021-02-15T07:10:33Z)
• Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noise [29.890039126644776]
  We develop a PAC active learning algorithm for $d$-dimensional homogeneous halfspaces that can tolerate Massart noisecitepmassart2006risk and Tsybakov noiseciteptsybakov2004. Under the more challenging Tsybakov noise condition, we identify two subfamilies of noise conditions, under which our algorithm achieves computational efficiency and provide label complexity guarantees strictly lower than passive learning algorithms.
  arXiv  Detail & Related papers  (2021-02-10T08:17:17Z)
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic [142.1492359556374]
  Bilevel optimization is a class of problems which exhibit a two-level structure. We propose a two-timescale approximation (TTSA) algorithm for tackling such a bilevel problem. We show that a two-timescale natural actor-critic policy optimization algorithm can be viewed as a special case of our TTSA framework.
  arXiv  Detail & Related papers  (2020-07-10T05:20:02Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  We study the learnability of halfspaces in the presence of Tsybakov noise. We give an algorithm that achieves misclassification error $epsilon$ with respect to the true halfspace.
  arXiv  Detail & Related papers  (2020-06-11T14:25:02Z)
• Attribute-Efficient Learning of Halfspaces with Malicious Noise: Near-Optimal Label Complexity and Noise Tolerance [21.76197397540397]
  This paper is concerned with computationally efficient learning of homogeneous sparse halfspaces in $mathbbRd$ under noise. We show that the sample complexity is $tildeObig(frac 1 epsilon s2 log5 d big)$ which also enjoys the attribute efficiency.
  arXiv  Detail & Related papers  (2020-06-06T04:57:39Z)
• Efficiently Learning Adversarially Robust Halfspaces with Noise [69.01459748050453]
  We study the problem of learning adversarially robust halfspaces in the distribution-independent setting. In the realizable setting, we provide necessary and sufficient conditions on the adversarial perturbation sets under which halfspaces are efficiently robustly learnable.
  arXiv  Detail & Related papers  (2020-05-15T17:13:54Z)

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.