arXiv:2210.02713

On Optimal Learning Under Targeted Data Poisoning

Steve Hanneke, Amin Karbasi, Mohammad Mahmoody, Idan Mehalel, Shay Moran

제출 2022-10-06

원문 초록

Consider the task of learning a hypothesis class $\mathcal{H}$ in the presence of an adversary that can replace up to an $\eta$ fraction of the examples in the training set with arbitrary adversarial examples. The adversary aims to fail the learner on a particular target test point $x$ which is known to the adversary but not to the learner. In this work we aim to characterize the smallest achievable error $\epsilon=\epsilon(\eta)$ by the learner in the presence of such an adversary in both realizable and agnostic settings. We fully achieve this in the realizable setting, proving that $\epsilon=\Theta(\mathtt{VC}(\mathcal{H})\cdot \eta)$, where $\mathtt{VC}(\mathcal{H})$ is the VC dimension of $\mathcal{H}$. Remarkably, we show that the upper bound can be attained by a deterministic learner. In the agnostic setting we reveal a more elaborate landscape: we devise a deterministic learner with a multiplicative regret guarantee of $\epsilon \leq C\cdot\mathtt{OPT} + O(\mathtt{VC}(\mathcal{H})\cdot \eta)$, where $C > 1$ is a universal numerical constant. We complement this by showing that for any deterministic learner there is an attack which worsens its error to at least $2\cdot \mathtt{OPT}$. This implies that a multiplicative deterioration in the regret is unavoidable in this case. Finally, the algorithms we develop for achieving the optimal rates are inherently improper. Nevertheless, we show that for a variety of natural concept classes, such as linear classifiers, it is possible to retain the dependence $\epsilon=\Theta_{\mathcal{H}}(\eta)$ by a proper algorithm in the realizable setting. Here $\Theta_{\mathcal{H}}$ conceals a polynomial dependence on $\mathtt{VC}(\mathcal{H})$.

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2406.05670v3cs.LG공통 태그 Data Poisoning공식 코드 · Papers with Code

그래디언트 기반 학습에서 데이터 중독에 대한 인증된 견고성

Certified Robustness to Data Poisoning in Gradient-Based Training

현대 기계학습 파이프라인은 대량의 공개 데이터를 활용하므로 데이터 품질을 보장하기 어렵고, 모델이 데이터 중독(data poisoning) 및 백도어(backdoor) 공격에 노출됩니다. 이러한 공격 하에서 모델 동작을 증명 가능하게 한정하는 것은 여전히 미해결 문제입니다. 본 연구에서는 모델이나 학습 알고리즘을 수정하지 않고도 잠재적으로 조작된 데이터로 학습된 모델의 동작에 대한 증명 가능한 보장을 제공하는 최초의 프레임워크를 개발하여 이 문제에 대응합니다. 특히 본 프레임워크는 학습 입력과 레이블에 대한 유계 및 무계 조작에 대해 비표적 및 표적 중독과 백도어 공격 모두에 대한 견고성을 인증합니다. 본 방법은 볼록 완화(convex relaxation)를 활용하여 주어진 중독 위협 모델에 대한 모든 가능한 매개변수 업데이트 집합을 과대 근사함으로써, 모든 그래디언트 기반 학습 알고리즘에 대해 도달 가능한 매개변수 집합 전체를 경계합니다. 이 매개변수 집합을 바탕으로 모델 성능과 백도어 성공률을 포함한 최악의 경우 동작에 대한 경계를 제공합니다. 에너지 소비, 의료 영상, 자율 주행 등의 응용 분야에서 다수의 실제 데이터셋에 대해 본 접근법을 시연합니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.