Self-Directed Linear Classification

• URL: http://arxiv.org/abs/2308.03142v1
• Date: Sun, 6 Aug 2023 15:38:44 GMT
• Title: Self-Directed Linear Classification
• Abstract summary: In online classification, a learner aims to predict their labels in an online fashion so as to minimize the total number of mistakes. Here we study the power of choosing the prediction order and establish the first strong separation between worst-order and random-order learning.
• Score: 50.659479930171585
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In online classification, a learner is presented with a sequence of examples and aims to predict their labels in an online fashion so as to minimize the total number of mistakes. In the self-directed variant, the learner knows in advance the pool of examples and can adaptively choose the order in which predictions are made. Here we study the power of choosing the prediction order and establish the first strong separation between worst-order and random-order learning for the fundamental task of linear classification. Prior to our work, such a separation was known only for very restricted concept classes, e.g., one-dimensional thresholds or axis-aligned rectangles. We present two main results. If $X$ is a dataset of $n$ points drawn uniformly at random from the $d$-dimensional unit sphere, we design an efficient self-directed learner that makes $O(d \log \log(n))$ mistakes and classifies the entire dataset. If $X$ is an arbitrary $d$-dimensional dataset of size $n$, we design an efficient self-directed learner that predicts the labels of $99\%$ of the points in $X$ with mistake bound independent of $n$. In contrast, under a worst- or random-ordering, the number of mistakes must be at least $\Omega(d \log n)$, even when the points are drawn uniformly from the unit sphere and the learner only needs to predict the labels for $1\%$ of them.

Related papers

• Adversarial Online Classification with a Preview [17.495168716195476]
  Worst-case online classification is governed by sequential complexity, such as Littlestone dimension.<n>We show that a random preview can replace worst-case sequential complexity by classical statistical dimensions without randomizing the online order.
  arXiv  Detail & Related papers  (2026-08-30T01:38:49Z)
• Optimal Rates for Learning with Monotone Adversaries [7.053805156684374]
  A monotone adversary observes an i.i.d. labeled sample and appends a finite number of further examples of its choice.<n>Every example is correctly labeled, but the insertions depend on the clean sample, so the combined sample is not exchangeable.<n>Larsen, Pabbaraju, and Shetty, who introduced this model, show that empirical risk minimization attains expected error $O((d/n)log(n/d))$ for classes of VC dimension $d$.
  arXiv  Detail & Related papers  (2026-08-06T17:45:32Z)
• Efficiently Learning Drifting Halfspaces with Massart Noise [50.4331323695175]
  We study the problem of learning a drifting concept in the presence of Massart noise.<n>In this framework, an online learner has access to a history of independent samples.<n>The goal is to output, in each round, a hypothesis with small prediction error.
  arXiv  Detail & Related papers  (2026-06-09T17:35:18Z)
• Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginals [38.241216472571786]
  We show that the standard multiclass perceptron requires super-polynomially many samples and updates, even with clean labels and Gaussian marginals.<n>We develop a sharper localization-based framework which leads to error $O(mathrmopt)+$ for $k=3, and error $mathrmpoly(k)mathrmopt+$ for geometrically regulark-class linear classifiers.
  arXiv  Detail & Related papers  (2026-05-20T17:19:30Z)
• Online Set Learning from Precision and Recall Feedback [60.00180898830079]
  We consider the problem of learning an unknown subset $N_texttarget$ of a domain in an online setting.<n>This simple online set learning problem abstracts a variety of learning scenarios with precision- and recall-type feedback.<n>We show that a hypothesis class is learnable in this setting if and only if it has finite Vapnik-Chervonenkis dimension.
  arXiv  Detail & Related papers  (2026-05-10T14:28:05Z)
• Reliable Abstention under Adversarial Injections: Tight Lower Bounds and New Upper Bounds [16.636823007179082]
  We study online learning in the adversarial injection model introduced by [Goel et al. 2017].<n>We prove a matching $(sqrtT)$ lower bound for VC dimension $1$, establishing a sharp separation between the two information regimes.<n>We introduce a potential-based framework driven by emphrobust witnesses, small subsets of labeled examples that certify predictions remaining resilient to adversarial contamination.
  arXiv  Detail & Related papers  (2026-02-23T18:30:48Z)
• Optimal Unconstrained Self-Distillation in Ridge Regression: Strict Improvements, Precise Asymptotics, and One-Shot Tuning [61.07540493350384]
  Self-distillation (SD) is the process of retraining a student on a mixture of ground-truth and the teacher's own predictions.<n>We show that for any prediction risk, the optimally mixed student improves upon the ridge teacher for every regularization level.<n>We propose a consistent one-shot tuning method to estimate $star$ without grid search, sample splitting, or refitting.
  arXiv  Detail & Related papers  (2026-02-19T17:21:15Z)
• Data Selection for ERMs [67.57726352698933]
  We study how well can $mathcalA$ perform when trained on at most $nll N$ data points selected from a population of $N$ points. Our results include optimal data-selection bounds for mean estimation, linear classification, and linear regression.
  arXiv  Detail & Related papers  (2025-04-20T11:26:01Z)
• Transfer Learning for Latent Variable Network Models [18.31057192626801]
  We study transfer learning for estimation in latent variable network models. We show that if the latent variables are shared, then vanishing error is possible. Our algorithm achieves $o(1)$ error and does not assume a parametric form on the source or target networks.
  arXiv  Detail & Related papers  (2024-06-05T16:33:30Z)
• Online Learning of Halfspaces with Massart Noise [47.71073318490341]
  We study the task of online learning in the presence of Massart noise. We present a computationally efficient algorithm that achieves mistake bound $eta T + o(T)$. We use our Massart online learner to design an efficient bandit algorithm that obtains expected reward at least $(1-1/k) Delta T - o(T)$ bigger than choosing a random action at every round.
  arXiv  Detail & Related papers  (2024-05-21T17:31:10Z)
• High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representation [89.21686761957383]
  We study the first gradient descent step on the first-layer parameters $boldsymbolW$ in a two-layer network. Our results demonstrate that even one step can lead to a considerable advantage over random features.
  arXiv  Detail & Related papers  (2022-05-03T12:09:59Z)
• Online Selective Classification with Limited Feedback [82.68009460301585]
  We study selective classification in the online learning model, wherein a predictor may abstain from classifying an instance. Two salient aspects of the setting we consider are that the data may be non-realisable, due to which abstention may be a valid long-term action. We construct simple versioning-based schemes for any $mu in (0,1],$ that make most $Tmu$ mistakes while incurring smash$tildeO(T1-mu)$ excess abstention against adaptive adversaries.
  arXiv  Detail & Related papers  (2021-10-27T08:00:53Z)
• Littlestone Classes are Privately Online Learnable [28.04975353867202]
  We consider the problem of online classification under a privacy constraint. In this setting a learner observes sequentially a stream of labelled examples $(x_t, y_t)$, for $1 leq t leq T$, and returns at each iteration a hypothesis $h_t$ which is used to predict the label of each new example $x_t$. The learner's performance is measured by her regret against a known hypothesis class $mathcalH$.
  arXiv  Detail & Related papers  (2021-06-25T09:08:33Z)
• Locality defeats the curse of dimensionality in convolutional teacher-student scenarios [69.2027612631023]
  We show that locality is key in determining the learning curve exponent $beta$. We conclude by proving, using a natural assumption, that performing kernel regression with a ridge that decreases with the size of the training set leads to similar learning curve exponents to those we obtain in the ridgeless case.
  arXiv  Detail & Related papers  (2021-06-16T08:27:31Z)
• Coresets for Classification -- Simplified and Strengthened [19.54307474041768]
  We give relative error coresets for training linear classifiers with a broad class of loss functions. Our construction achieves $tilde O(d cdot mu_y(X)2/epsilon2)$ points, where $mu_y(X)$ is a natural complexity measure of the data matrix $X in mathbbRn times d$ and label vector $y in -1,1n$.
  arXiv  Detail & Related papers  (2021-06-08T11:24:18Z)
• Remember What You Want to Forget: Algorithms for Machine Unlearning [37.656345901739506]
  We study the problem of forgetting datapoints from a learnt model. We provide an unlearning algorithm that can delete up to $O(n/d1/4)$ samples.
  arXiv  Detail & Related papers  (2021-03-04T19:28:57Z)
• Variance-Aware Confidence Set: Variance-Dependent Bound for Linear Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
  We show how to construct variance-aware confidence sets for linear bandits and linear mixture Decision Process (MDP) For linear bandits, we obtain an $widetildeO(mathrmpoly(d)sqrt1 + sum_i=1Ksigma_i2) regret bound, where $d is the feature dimension. For linear mixture MDP, we obtain an $widetildeO(mathrmpoly(d)sqrtK)$ regret bound, where
  arXiv  Detail & Related papers  (2021-01-29T18:57:52Z)
• The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime [11.252856459394854]
  Modern machine learning classifiers often exhibit vanishing classification error on the training set. Motivated by these phenomena, we revisit high-dimensional maximum margin classification for linearly separable data.
  arXiv  Detail & Related papers  (2019-11-05T00:15:27Z)

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.