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].
Improved Generalization Bounds for Adversarially Robust Learning
Authors: Idan Attias, Aryeh Kontorovich, Yishay Mansour
JMLR 2022 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main results consist of generalization bounds for the binary and multiclass classification, as well as the real-valued case (regression). For the binary classification setting, we both tighten the generalization bound of Feige et al. (2015), and are also able to handle infinite hypothesis classes. The sample complexity is improved from O( 1 ϵ4 log( |H| δ )) to O 1 ϵ2 (k VC(H) log 3 2 +α(k VC(H)) + log( 1 δ ) for any α > 0. Additionally, we extend the algorithm and generalization bound from the binary to the multiclass and real-valued cases. Along the way, we obtain results on fat-shattering dimension and Rademacher complexity of k-fold maxima over function classes; these may be of independent interest. |
| Researcher Affiliation | Collaboration | Idan Attias EMAIL Aryeh Kontorovich EMAIL Department of Computer Science Ben-Gurion University of the Negev, Beer Sheva, Israel Yishay Mansour EMAIL Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv Israel and Google Research, Tel Aviv |
| Pseudocode | Yes | Algorithm 1 parameter: η > 0 1: for all (x, y) S, z ρ(x) do initialize weights and distributions vector 2: w1(z, (x, y)) 1, (x, y) S, z ρ(x) 3: P 1(z, (x, y)) w1(z,(x,y)) P z ρ(x) w1(z ,(x,y)) for each (x, y) S we have a distribution over ρ(x) 5: for t = 1:T do 6: ht arg min h HE(z,y) DP t[ℓ(h(z), y] using the ERM oracle for H 7: for all (x, y) S, z ρ(x) do update weights for P t+1 8: wt+1(z, (x, y)) (1 + η [ℓ(ht(z), y)]) wt(z, (x, y)) 9: P t+1(z, (x, y)) wt+1(z,(x,y)) P z ρ(x) wt+1(z ,(x,y)) 10: end for 11: end for 12: return h1, . . . , h T for the learner, 1 T PT t=1 P t for the adversary |
| Open Source Code | No | The paper does not contain any explicit statement about releasing source code for the methodology, nor does it provide a link to a code repository. |
| Open Datasets | No | The paper is theoretical and focuses on generalization bounds and algorithms. It does not conduct experiments using specific datasets and therefore does not mention any publicly available datasets or provide access information for them. |
| Dataset Splits | No | The paper is theoretical and focuses on generalization bounds and algorithms. It does not conduct experiments using specific datasets and therefore does not mention any dataset splits. |
| Hardware Specification | No | The paper is theoretical and focuses on generalization bounds and algorithms. It does not conduct experiments and therefore does not mention any hardware specifications used. |
| Software Dependencies | No | The paper is theoretical and focuses on generalization bounds and algorithms. It does not conduct experiments and therefore does not mention any specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and focuses on generalization bounds and algorithms. It does not conduct experiments and therefore does not mention specific experimental setup details, hyperparameters, or training configurations. |