# On Traceability in ℓp Stochastic Convex Optimization

arXiv: https://arxiv.org/abs/2502.17384 · HTML: https://mlsanity.com/paper/2502.17384/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Feb 2025.

## Built on by (most cited first, 2 of 2)

- [Tighter Information-Theoretic Generalization Bounds via a Novel Class of Change of Measure Inequalities](https://mlsanity.com/paper/2602.07999/) (2026)
- [An Accuracy-Information Tradeoff for Loss-Difference Conditional Mutual Information](https://mlsanity.com/paper/2610.09206/) (2026)

## Abstract (arXiv)

In this paper, we investigate the necessity of traceability for accurate learning in stochastic convex optimization (SCO) under ℓp geometries. Informally, we say a learning algorithm 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∈ [1,∞), we establish the existence of an excess risk threshold below which every sample-efficient learner is traceable with the number of samples which is a constant fraction of its training sample. For p∈ [1,2], this threshold coincides with the best excess risk of differentially private (DP) algorithms, i.e., above this threshold, there exist algorithms that are not traceable, which corresponds to a sharp phase transition. For p ∈ (2,∞), this threshold instead gives novel lower bounds for DP learning, partially closing an open problem in this setup. En route to establishing these results, we prove a sparse variant of the fingerprinting lemma, which is of independent interest to the community.