When are Non-Parametric Methods Robust?

• URL: http://arxiv.org/abs/2003.06121v2
• Date: Mon, 28 Dec 2020 22:18:08 GMT
• Title: When are Non-Parametric Methods Robust?
• Authors: Robi Bhattacharjee and Kamalika Chaudhuri
• Abstract summary: We study general non-parametric methods, with a view towards understanding when they are robust to these modifications. We establish general conditions under which non-parametric methods are r-consistent.
• Score: 30.56004276586835
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A growing body of research has shown that many classifiers are susceptible to {\em{adversarial examples}} -- small strategic modifications to test inputs that lead to misclassification. In this work, we study general non-parametric methods, with a view towards understanding when they are robust to these modifications. We establish general conditions under which non-parametric methods are r-consistent -- in the sense that they converge to optimally robust and accurate classifiers in the large sample limit. Concretely, our results show that when data is well-separated, nearest neighbors and kernel classifiers are r-consistent, while histograms are not. For general data distributions, we prove that preprocessing by Adversarial Pruning (Yang et. al., 2019) -- that makes data well-separated -- followed by nearest neighbors or kernel classifiers also leads to r-consistency.

Related papers

• Geometric Median Matching for Robust k-Subset Selection from Noisy Data [75.86423267723728]
  We propose a novel k-subset selection strategy that leverages Geometric Median -- a robust estimator with an optimal breakdown point of 1/2. Our method iteratively selects a k-subset such that the mean of the subset approximates the GM of the (potentially) noisy dataset, ensuring robustness even under arbitrary corruption.
  arXiv  Detail & Related papers  (2025-04-01T09:22:05Z)
• Intriguing Properties of Robust Classification [19.858602457988194]
  We show that in certain settings robust generalization is only possible with unrealistically large amounts of data. We explore how well robust classifiers generalize on datasets such as CIFAR-10.
  arXiv  Detail & Related papers  (2024-12-05T15:27:39Z)
• Late Stopping: Avoiding Confidently Learning from Mislabeled Examples [61.00103151680946]
  We propose a new framework, Late Stopping, which leverages the intrinsic robust learning ability of DNNs through a prolonged training process. We empirically observe that mislabeled and clean examples exhibit differences in the number of epochs required for them to be consistently and correctly classified. Experimental results on benchmark-simulated and real-world noisy datasets demonstrate that the proposed method outperforms state-of-the-art counterparts.
  arXiv  Detail & Related papers  (2023-08-26T12:43:25Z)
• Boosting Differentiable Causal Discovery via Adaptive Sample Reweighting [62.23057729112182]
  Differentiable score-based causal discovery methods learn a directed acyclic graph from observational data. We propose a model-agnostic framework to boost causal discovery performance by dynamically learning the adaptive weights for the Reweighted Score function, ReScore.
  arXiv  Detail & Related papers  (2023-03-06T14:49:59Z)
• Intra-class Adaptive Augmentation with Neighbor Correction for Deep Metric Learning [99.14132861655223]
  We propose a novel intra-class adaptive augmentation (IAA) framework for deep metric learning. We reasonably estimate intra-class variations for every class and generate adaptive synthetic samples to support hard samples mining. Our method significantly improves and outperforms the state-of-the-art methods on retrieval performances by 3%-6%.
  arXiv  Detail & Related papers  (2022-11-29T14:52:38Z)
• Malign Overfitting: Interpolation Can Provably Preclude Invariance [30.776243638012314]
  We show that "benign overfitting" in which models generalize well despite interpolating might not favorably extend to settings in which robustness or fairness are desirable. We propose and analyze an algorithm that successfully learns a non-interpolating classifier that is provably invariant.
  arXiv  Detail & Related papers  (2022-11-28T19:17:31Z)
• Parametric Classification for Generalized Category Discovery: A Baseline Study [70.73212959385387]
  Generalized Category Discovery (GCD) aims to discover novel categories in unlabelled datasets using knowledge learned from labelled samples. We investigate the failure of parametric classifiers, verify the effectiveness of previous design choices when high-quality supervision is available, and identify unreliable pseudo-labels as a key problem. We propose a simple yet effective parametric classification method that benefits from entropy regularisation, achieves state-of-the-art performance on multiple GCD benchmarks and shows strong robustness to unknown class numbers.
  arXiv  Detail & Related papers  (2022-11-21T18:47:11Z)
• When Noisy Labels Meet Long Tail Dilemmas: A Representation Calibration Method [40.25499257944916]
  Real-world datasets are both noisily labeled and class-imbalanced. We propose a representation calibration method RCAL. We derive theoretical results to discuss the effectiveness of our representation calibration.
  arXiv  Detail & Related papers  (2022-11-20T11:36:48Z)
• Relieving Long-tailed Instance Segmentation via Pairwise Class Balance [85.53585498649252]
  Long-tailed instance segmentation is a challenging task due to the extreme imbalance of training samples among classes. It causes severe biases of the head classes (with majority samples) against the tailed ones. We propose a novel Pairwise Class Balance (PCB) method, built upon a confusion matrix which is updated during training to accumulate the ongoing prediction preferences.
  arXiv  Detail & Related papers  (2022-01-08T07:48:36Z)
• Good Classifiers are Abundant in the Interpolating Regime [64.72044662855612]
  We develop a methodology to compute precisely the full distribution of test errors among interpolating classifiers. We find that test errors tend to concentrate around a small typical value $varepsilon*$, which deviates substantially from the test error of worst-case interpolating model. Our results show that the usual style of analysis in statistical learning theory may not be fine-grained enough to capture the good generalization performance observed in practice.
  arXiv  Detail & Related papers  (2020-06-22T21:12:31Z)
• Dynamic Decision Boundary for One-class Classifiers applied to non-uniformly Sampled Data [0.9569316316728905]
  A typical issue in Pattern Recognition is the non-uniformly sampled data. In this paper, we propose a one-class classifier based on the minimum spanning tree with a dynamic decision boundary.
  arXiv  Detail & Related papers  (2020-04-05T18:29:36Z)

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.