On the Dichotomy Between Privacy and Traceability in $\ell_p$ Stochastic Convex Optimization
원문 초록
In this paper, we investigate the necessity of memorization in stochastic convex optimization (SCO) under $\ell_p$ geometries. Informally, we say a learning algorithm memorizes $m$ samples (or is $m$-traceable) if, by analyzing its output, it is possible to identify at least $m$ of its training samples. Our main results uncover a fundamental tradeoff between traceability and excess risk in SCO. For every $p\in [1,\infty)$, we establish the existence of a risk threshold below which any sample-efficient learner must memorize a \em{constant fraction} of its sample. For $p\in [1,2]$, this threshold coincides with best risk of differentially private (DP) algorithms, i.e., above this threshold, there are algorithms that do not memorize even a single sample. This establishes a sharp dichotomy between privacy and traceability for $p \in [1,2]$. For $p \in (2,\infty)$, this threshold instead gives novel lower bounds for DP learning, partially closing an open problem in this setup. En route of proving these results, we introduce a complexity notion we term \em{trace value} of a problem, which unifies privacy lower bounds and traceability results, and prove a sparse variant of the fingerprinting lemma.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Reasoning or Memorization? Unreliable Results of Reinforcement Learning Due to Data Contamination
Identifying the Smallest Adversarial Load Perturbations that Render DC-OPF Infeasible
Distributed Lyapunov Functions for Nonlinear Networks
Dataset distillation for memorized data: Soft labels can leak held-out teacher knowledge
LexiMark: Robust Watermarking via Lexical Substitutions to Enhance Membership Verification of an LLM's Textual Training Data
Capacity Matters: a Proof-of-Concept for Transformer Memorization on Real-World Data
토론
이 논문과 연결된 포럼 글이 아직 없습니다.