Private Truly-Everlasting Robust-Prediction
Authors: Uri Stemmer
ICML 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We present two conceptual modifications to the definition of PEP, as well as new constructions exhibiting significant improvements over prior work. Specifically, we incorporate robustness against poisoning attacks into the definition of PEP; we present a relaxed privacy definition, suitable for PEP, that allows us to disconnect the privacy parameter δ from the number of total time steps T; and we present new constructions for axis-aligned rectangles and decision-stumps exhibiting improved sample complexity and runtime. We present our new PEP constructions. Our constructions outperform the generic construction of Naor et al. (2023) on three aspects: (1) our constructions are computationally efficient; (2) our constructions exhibit sample complexity linear in the VC dimension rather than quadratic; and (3) our constructions achieve significantly stronger robustness guarantees than our robust extension to the construction of Naor et al. (2023). Theorem 4.6. Rectangles PERP is (ε, δ)-private, as in Definition 3.8, where Σp tp δp ≤ δ. Proof. Using the notations of Rectangles PERP, we define the function δ : N → [0, 1] where δ(i) = δp(i) and where p(i) denote the phase to which i belongs. (Throughout the paper, there are many definitions, theorems, lemmas, and algorithms presented with proofs and theoretical analysis, without empirical data evaluation.) |
| Researcher Affiliation | Collaboration | Uri Stemmer 1 1Tel Aviv University and Google Research, Israel. Correspondence to: Uri Stemmer <u@uri.co.il>. |
| Pseudocode | Yes | Algorithm 1 RSC (Cohen et al., 2023) Input: Dataset D ∈ Xn and parameters τ, ε, δ. For i = 1, . . . , τ do: ... Algorithm 2 Stopper Input: Privacy parameters ε, δ, threshold t, and a dataset D containing input bits. ... Algorithm 3 Between Thresholds (Bun et al., 2017) Input: Dataset S ⊆ X, privacy parameters ε, δ, number of medium reports k, and thresholds tl < th. ... Algorithm 4 Challenge BT Input: Dataset S ⊆ X, privacy parameters ε, δ, number of medium reports k where k ≥ 4 log(4/δ), thresholds tl, th satisfying th − tl ≥ 32/ε, a bound on the number of steps T, and an adaptively chosen stream of queries fi : X → R with sensitivity 1. ... Algorithm 5 Rectangles PERP Initial input: Labeled dataset S ∈ (Rd × {0, 1})n and parameters ε, δ, α, β, γ. ... Algorithm 6 Defining sub-regions of RECTANGLE(c) ... Algorithm 7 Decision PERP Initial input: Labeled dataset S ∈ (Rd × {0, 1})n and parameters ε, δ, α, β, γ. ... |
| Open Source Code | No | The paper does not contain any explicit statement about releasing open-source code or a link to a code repository for the methodology described in this paper. |
| Open Datasets | No | The paper is theoretical, presenting conceptual modifications and new constructions for private everlasting prediction. It discusses 'training sets' and 'training data' in the context of the learning problem (e.g., 'initial training set', 'labeled training set sampled according to some fixed (but unknown) distribution D'), but it does not use or provide access to any specific, named public datasets for empirical evaluation. |
| Dataset Splits | No | The paper focuses on theoretical contributions, algorithm design, and privacy/utility analyses. It does not report on empirical experiments with datasets, and therefore, it does not specify any training/validation/test dataset splits or cross-validation setups. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithm design, definitions, and proofs. It does not report on computational experiments or their performance, and therefore, does not describe any specific hardware (e.g., GPU/CPU models, memory) used. |
| Software Dependencies | No | The paper describes algorithms and theoretical concepts. It does not mention any specific software components, libraries, frameworks, or their version numbers that would be required to implement or run the described methods. |
| Experiment Setup | No | The paper focuses on theoretical contributions, providing formal definitions, algorithms, and proofs. It does not include an experimental setup section or details on hyperparameters, training configurations, or system-level settings, as it does not report on empirical experiments. |