Monotone Classification with Relative Approximations

• URL: http://arxiv.org/abs/2506.10775v1
• Date: Thu, 12 Jun 2025 14:51:14 GMT
• Title: Monotone Classification with Relative Approximations
• Authors: Yufei Tao,
• Abstract summary: In monotone classification, the input is a multi-set $P$ of points in $mathbbRd$, each associated with a hidden label from $-1, 1$.<n>The goal is to identify a monotone function $h$, which acts as a classifier, mapping from $mathbbRd$ to $-1, 1$ with a small em error.
• Score: 4.750077838548594
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In monotone classification, the input is a multi-set $P$ of points in $\mathbb{R}^d$, each associated with a hidden label from $\{-1, 1\}$. The goal is to identify a monotone function $h$, which acts as a classifier, mapping from $\mathbb{R}^d$ to $\{-1, 1\}$ with a small {\em error}, measured as the number of points $p \in P$ whose labels differ from the function values $h(p)$. The cost of an algorithm is defined as the number of points having their labels revealed. This article presents the first study on the lowest cost required to find a monotone classifier whose error is at most $(1 + \epsilon) \cdot k^*$ where $\epsilon \ge 0$ and $k^*$ is the minimum error achieved by an optimal monotone classifier -- in other words, the error is allowed to exceed the optimal by at most a relative factor. Nearly matching upper and lower bounds are presented for the full range of $\epsilon$. All previous work on the problem can only achieve an error higher than the optimal by an absolute factor.

Related papers

• Surrogate to Poincaré inequalities on manifolds for dimension reduction in nonlinear feature spaces [49.1574468325115]
  We aim to approximate a continuously differentiable function $u:mathbbRd rightarrow mathbbRm$ by a composition of functions $fcirc g$ where $g:mathbbRd rightarrow mathbbRm$, $mleq d$, and $f : mathbbRm rightarrow mathbbRR$.<n>For a fixed $g$, we build $f$ using classical regression methods, involving evaluations
  arXiv  Detail & Related papers  (2025-05-03T12:37:27Z)
• Bandit Multiclass List Classification [28.483435983018616]
  We study the problem of multiclass list classification with (semi-)bandit feedback, where input examples are mapped into subsets of size $m$ of a collection of $K$ possible labels.<n>Our results generalize and extend prior work in the simpler single-label setting (Erez et al. '24), and apply more generally to contextual semi-bandit problems with $s$sparse rewards.
  arXiv  Detail & Related papers  (2025-02-13T12:13:25Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions [49.69852011882769]
  We show the first algorithms for the problem of regression for generalized linear models (GLMs) in the presence of additive oblivious noise. We present an algorithm that tackles newthis problem in its most general distribution-independent setting. This is the first newalgorithmic result for GLM regression newwith oblivious noise which can handle more than half the samples being arbitrarily corrupted.
  arXiv  Detail & Related papers  (2023-09-20T21:41:59Z)
• Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
  Detection of a planted dense subgraph in a random graph is a fundamental statistical and computational problem. We consider detecting the presence of a planted $Gr(ngamma, n-alpha)$ subhypergraph in a $Gr(n, n-beta) hypergraph. Our results are already new in the graph case $r=2$, as we consider the subtle log-density regime where hardness based on average-case reductions is not known.
  arXiv  Detail & Related papers  (2023-04-17T10:38:08Z)
• Sparse Signal Detection in Heteroscedastic Gaussian Sequence Models: Sharp Minimax Rates [1.0309387309011746]
  We study the signal detection problem against sparse alternatives, for known sparsity $s$. We find minimax upper and lower bounds over the minimax separation radius $epsilon*$ and prove that they are always matching. Our results reveal new phase transitions regarding the behavior of $epsilon*$ with respect to the level of sparsity, to the $Lt$ metric, and to the heteroscedasticity profile of $Sigma$.
  arXiv  Detail & Related papers  (2022-11-15T23:53:39Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering [42.526664955704746]
  We develop a novel, conceptually simpler technique for list-decodable sparse mean estimation. In particular, for distributions with "certifiably bounded" $t-th moments in $k$-sparse directions, our algorithm achieves error of $(1/alpha)O (1/t)$ with sample complexity $m = (klog(n))O(t)/alpha(mnt)$. For the special case of Gaussian inliers, our algorithm achieves the optimal error guarantee of $Theta (sqrtlog
  arXiv  Detail & Related papers  (2022-06-10T17:38:18Z)
• Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise [9.378684220920562]
  tightest statistical query (SQ) lower bounds for learnining halfspaces in the presence of Massart noise. We show that for arbitrary $eta in [0,1/2]$ every SQ algorithm achieving misclassification error better than $eta$ requires queries of superpolynomial accuracy.
  arXiv  Detail & Related papers  (2022-01-24T17:33:19Z)
• Self-training Converts Weak Learners to Strong Learners in Mixture Models [86.7137362125503]
  We show that a pseudolabeler $boldsymbolbeta_mathrmpl$ can achieve classification error at most $C_mathrmerr$. We additionally show that by running gradient descent on the logistic loss one can obtain a pseudolabeler $boldsymbolbeta_mathrmpl$ with classification error $C_mathrmerr$ using only $O(d)$ labeled examples.
  arXiv  Detail & Related papers  (2021-06-25T17:59:16Z)
• Locally Private $k$-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Error [10.632986841188]
  We bridge the gap between the exponents of $n$ in the upper and lower bounds on the additive error with two new algorithms. It is possible to solve the locally private $k$-means problem in a constant number of rounds with constant factor multiplicative approximation.
  arXiv  Detail & Related papers  (2021-05-31T14:41:40Z)
• Active Local Learning [22.823171570933397]
  We consider active local learning: given a query point $x$, and active access to an unlabeled training set $S$, output the prediction $h(x)$ of a near-optimal $h in H$. In particular, the number of label queries should be independent of the complexity of $H$, and the function $h$ should be well-defined, independent of $x$. This immediately also implies an algorithm for distance estimation: estimating the value $opt(H)$ from many fewer labels than needed to actually learn a near-optimal $h in
  arXiv  Detail & Related papers  (2020-08-31T05:39:35Z)
• A Multiclass Classification Approach to Label Ranking [2.6905021039717987]
  In multiclass classification, the goal is to learn how to predict a random label $Y$, valued in $mathcalY=1,; ldots,; K $ with $Kgeq 3$. This article is devoted to the analysis of this statistical learning problem, halfway between multiclass classification and posterior probability estimation.
  arXiv  Detail & Related papers  (2020-02-21T17:12:43Z)

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.