Research map / Optimization / Nonconvex and smooth optimization
On Traceability in $\ell_p$ Stochastic Convex Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Theoretical study of traceability (number of identifiable training samples) versus excess risk in ℓp stochastic convex optimization, via a subgaussian trace value framework and a new sparse fingerprinting lemma, yielding a phase transition for p in [1,2] and improved DP-SCO lower bounds for p>2.
Problem
How many training samples must an accurate learner in ℓp stochastic convex optimization memorize (be traceable), and how does this trade off with excess risk relative to differentially private learning?
Approach
Introduces the subgaussian trace value as a complexity measure that converts fingerprinting-type correlation lower bounds into traceability and DP lower bounds, plus a sparse fingerprinting lemma whose correlation scales with d/k, applied to sparse ℓp hard instances.
Key results
- For p in [1,2], every alpha-learner with alpha up to the DP threshold alpha_DP/log^2(n) is (xi,m)-traceable with m = Omega(1/alpha^2), matching the sample complexity.
- For p=1, the recall lower bound improves to Omega(log(d)/alpha^2), closing the log(d) gap relative to prior mean-estimation tracing results.
- For p>2, the paper proves a DP-SCO lower bound of order (d/(eps^2 n^2))^{1/p} for (eps,delta)-DP learners, improving prior bounds when d >= eps n.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Require excess risk α in the stated range for ℓp SCO with p ∈ [1,2) | Every α-learner · ℓp SCO, p ∈ [1,2) | traceable samples: m ∈ Ω(α^{-2}) | Helped |
| Require excess risk α in the stated range for ℓ1 SCO | Every α-learner · ℓ1 SCO | traceable samples: m ∈ Ω(log(d)/α^2) | Helped |
| Require excess risk α in the stated range for ℓp SCO with p ≥ 2 | Every α-learner · ℓp SCO, p ∈ [2,∞) | traceable samples: m ∈ Ω(1/(6α)^p) | Helped |
| Require (ε,δ)-differential privacy for the learner | ℓp SCO, p ∈ [2,∞) · ℓp DP-SCO | excess risk: α ≥ c · min{ (d/(ε^2 n^2))^{1/p} , d^{1-1/p}/(ε n) , 1 } | Hurt |
| Use a tracer for binary classification PAC learning with VC dimension d_vc | Every tracer · Binary classification PAC learning | tracer recall: O(d_vc log^2(n)) | Hurt |
| Use the threshold-class result, removing the log^2(n) factor | Every tracer · Threshold-class PAC learning | tracer recall upper bound | Helped |
Surprising findings
- The subgaussian trace value recovers non-private sample complexity lower bounds for all p in [1,infinity).
Limitations
- For p>2, the optimal DP excess risk remains open; the derived bound is a lower bound only.
- Results are for worst-case hard instances and asymptotic/up-to-constant regimes rather than practical algorithms.
- Tracers restricted to subgaussian processes over the domain.
Experimental setup
Metrics: excess risk recall soundness
Builds on: fingerprinting lemma differential privacy lower bounds for SCO tracing attacks in DP
Closest papers by meaning
- Information Complexity of Stochastic Convex Optimization: Applications to Generalization, Memorization, and Tracing (ICML 2024 · similarity 0.89)
- The Sample Complexity of Gradient Descent in Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.88)
- Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions (NeurIPS 2024 · similarity 0.87)
- Improved Lower Bounds for First-order Stochastic Non-convex Optimization under Markov Sampling (ICML 2025 · similarity 0.87)
- Sample complexity of stochastic optimization with integer variables (NeurIPS 2026 · similarity 0.87)
- Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization (ICML 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.