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].
First Order Stochastic Optimization with Oblivious Noise
Authors: Ilias Diakonikolas, Sushrut Karmalkar, Jong Ho Park, Christos Tzamos
NeurIPS 2023 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We initiate the study of stochastic optimization with oblivious noise, broadly generalizing the standard heavy-tailed noise setup. In our setting, in addition to random observation noise, the stochastic gradient may be subject to independent oblivious noise, which may not have bounded moments and is not necessarily centered. Our main result is an efficient list-decodable learner that recovers a small list of candidates, at least one of which is close to the true solution. Along the way, we develop a rejection-sampling-based algorithm to perform noisy location estimation, which may be of independent interest. |
| Researcher Affiliation | Collaboration | Ilias Diakonikolas Department of Computer Sciences University of Wisconsin-Madison EMAIL Sushrut Karmalkar Department of Computer Sciences University of Wisconsin-Madison EMAIL Jongho Park KRAFTON EMAIL Christos Tzamos Department of Informatics University of Athens EMAIL |
| Pseudocode | Yes | Algorithm 1 One-dimensional Location Estimation: Shift1D(S1, S2, η, σ, α) ... Algorithm 2 Noisy Gradient Optimization: Noisy Grad Desc(α, τ, δ, O, AG, AME) ... Algorithm 3 Inexact Gradient Oracle: Inexact Oracle(x; Oα,σ,f, τ, L0) ... Algorithm 4 One-dimensional Location Estimation: Shift1D(S1, S2, η, σ, α) ... Algorithm 5 High-dimensional Location Estimation: Shift High D(S1, S2, η, σ, α) |
| Open Source Code | No | The paper does not provide any explicit statements about releasing source code or links to a code repository for the described methodology. |
| Open Datasets | No | This is a theoretical paper and does not involve experimental evaluation on datasets. Therefore, it does not mention training data or its public availability. |
| Dataset Splits | No | This is a theoretical paper and does not involve experimental evaluation on datasets. Therefore, it does not provide information about validation splits. |
| Hardware Specification | No | The paper is theoretical and does not describe experiments. Therefore, it does not specify any hardware used for computations. |
| Software Dependencies | No | The paper is theoretical and does not describe implementation details that would require specific software dependencies or versions. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setup, hyperparameters, or training configurations. |