Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity
Authors: Haim Kaplan, Yishay Mansour, Uri Stemmer, Eliad Tsfadia
NeurIPS 2020 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We present a differentially private learner for halfspaces over a finite grid G in Rd with sample complexity d2.5 2log |G|, which improves the state-of-the-art result of [Beimel et al., COLT 2019] by a d2 factor. The building block for our learner is a new differentially private algorithm for approximately solving the linear feasibility problem: Given a feasible collection of m linear constraints of the form Ax b, the task is to privately identify a solution x that satisfies most of the constraints. Our algorithm is iterative, where each iteration determines the next coordinate of the constructed solution x. The paper focuses on theoretical contributions, algorithm design, and proofs related to sample complexity, which is characteristic of theoretical research. |
| Researcher Affiliation | Collaboration | Haim Kaplan Tel Aviv University and Google Research EMAIL Yishay Mansour Tel Aviv University and Google Research EMAIL Uri Stemmer Ben-Gurion University and Google Research EMAIL Eliad Tsfadia Tel Aviv University and Google Research EMAIL |
| Pseudocode | Yes | Figure 1: Algorithm AOptimize High Dim Func (i) Let α, β, ε, δ (0, 1) be the utility/privacy parameters, let S X be an input dataset, let n Xi( ) od i=1 be an iterative sequence of finite domains, and let 1. (ii) For i = 1 to d do: (a) Let Qx 1,...,x i 1 be the function from Definition 3.3. (b) Let Xi = Xi(x 1, . . . , x i 1). (c) Execute ARec Concave with the function Qx 1,...,x i 1, domain Xi, and parameters: r = (1 α 2d )i 1MS, α = α 2d , β = β d , ε = ε 2 2d ln(2/δ), δ = δ 2d. Let x i be its output. (iii) Return x = (x 1, . . . , x d). |
| Open Source Code | No | The paper does not provide any concrete statement about releasing its own source code, nor does it provide a link to a repository for the described methodology. |
| Open Datasets | No | This is a theoretical paper focusing on algorithm design and sample complexity. It does not use specific real-world datasets for training or provide information on their public availability. |
| Dataset Splits | No | This is a theoretical paper. It does not describe any empirical experiments, and therefore no training, validation, or test dataset splits are provided. |
| Hardware Specification | No | This is a theoretical paper. It does not discuss any specific hardware used for computations or experiments. |
| Software Dependencies | No | This is a theoretical paper. It does not mention any specific software components or their version numbers that would be required to replicate its findings. |
| Experiment Setup | No | This is a theoretical paper. It does not describe any empirical experimental setup details or hyperparameters. |