The Role of Randomness in Stability
Authors: Max Hopkins, Shay Moran
ICML 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We prove a weak-to-strong boosting theorem for stability in these settings: the randomness complexity of a task M is tightly controlled by the best replication probability of any deterministic algorithm solving M, a parameter known as M s global stability (Chase, Moran, Yehudayoff FOCS 2023). |
| Researcher Affiliation | Collaboration | 1Department of Computer Science, Princeton University, Princeton, USA 2Faculty of Mathematics, Technion, Haifa, Israel 3Google Research, Tel-Aviv, Israel. |
| Pseudocode | Yes | Algorithm 1 Global Stability Certificate Complexity |
| Open Source Code | No | The paper is highly theoretical and focuses on proofs and theorems. There is no mention of open-source code for the methodology described in this paper. |
| Open Datasets | No | The paper defines general statistical tasks using concepts like a 'data domain X' and 'distributions D over X', but it does not specify or use any concrete publicly available or open datasets for empirical evaluation. |
| Dataset Splits | No | The paper focuses on theoretical analysis and does not involve empirical experiments with datasets, therefore, there are no mentions of training/test/validation dataset splits. |
| Hardware Specification | No | The paper is a theoretical work focusing on mathematical proofs and algorithmic design principles; it does not describe any experimental setup or specific hardware used for computations. |
| Software Dependencies | No | The paper is entirely theoretical, presenting theorems and proofs without implementation details or experimental results, and thus does not list any software dependencies or their versions. |
| Experiment Setup | No | This is a theoretical paper providing mathematical proofs and analyses of algorithmic stability and randomness complexity. It does not describe any empirical experiments, and therefore, no experimental setup details such as hyperparameters or training configurations are provided. |