Geometric Algorithms for $k$-NN Poisoning
We propose a label poisoning attack on geometric data sets against $k$-nearest neighbor classification. We provide an algorithm that can compute an $\varepsilon n$-additive approximation of the optimal poisoning in $n\cdot 2^{2^{O(d+k/\varepsilon)}}$ time for a given data set $X \in \mathbb{R}^d$, where $|X| = n$. Our algorithm achieves its objectives through the application of multi-scale random partitions.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Sonic: Fast and Transferable Data Poisoning on Clustering Algorithms
Data poisoning attacks on clustering algorithms have received limited attention, with existing methods struggling to scale efficiently as dataset sizes and feature counts increase. These attacks typically require re-clus…
ClusteringData PoisoningIndiscriminate Poisoning Attacks on Unsupervised Contrastive Learning
Indiscriminate data poisoning attacks are quite effective against supervised learning. However, not much is known about their impact on unsupervised contrastive learning (CL). This paper is the first to consider indiscri…
Contrastive LearningData AugmentationData PoisoningMatrix CompletionA Geometric Approach to Problems in Optimization and Data Science
We give new results for problems in computational and statistical machine learning using tools from high-dimensional geometry and probability. We break up our treatment into two parts. In Part I, we focus on computationa…
Data PoisoningGraph ClusteringTowards Poisoning of Deep Learning Algorithms with Back-gradient Optimization
A number of online services nowadays rely upon machine learning to extract valuable information from data collected in the wild. This exposes learning algorithms to the threat of data poisoning, i.e., a coordinate attack…
Data PoisoningDeep LearningHandwritten Digit RecognitionMalware DetectionRegularisation Can Mitigate Poisoning Attacks: A Novel Analysis Based on Multiobjective Bilevel Optimisation
Machine Learning (ML) algorithms are vulnerable to poisoning attacks, where a fraction of the training data is manipulated to deliberately degrade the algorithms' performance. Optimal poisoning attacks, which can be form…
Bilevel OptimizationData PoisoningL2 RegularizationMultiobjective Optimization