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].
Dueling Convex Optimization
Authors: Aadirupa Saha, Tomer Koren, Yishay Mansour
ICML 2021 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We address the problem of convex optimization with preference (dueling) feedback. Like the traditional optimization objective, the goal is to find the optimal point with the least possible query complexity, however, without the luxury of even a zeroth order feedback. Instead, the learner can only observe a single noisy bit which is win-loss feedback for a pair of queried points based on their function values. ... For the non-stationary OCO setup, where the underlying convex function may change over time, we prove an impossibility result towards achieving the above objective. We next focus only on the stationary OCO problem, and our main contribution lies in designing a normalized gradient descent based algorithm towards finding a ϵ-best optimal point. Towards this, our algorithm is shown to yield a convergence rate of O(dβ/ϵν2) (ν being the noise parameter) when the underlying function is β-smooth. Further we show an improved convergence rate of just O(dβ/αν2 log 1 ϵ ) when the function is additionally also α-strongly convex. |
| Researcher Affiliation | Collaboration | Aadirupa Saha 1 Microsoft Research, New York City 2 Blavatnik School of Computer Science, Tel Aviv University, and Google Research Tel Aviv. |
| Pseudocode | Yes | Algorithm 1 β-NGD(x1, η, γ, Tϵ) Algorithm 2 (α, β)-NGD(ϵ) Algorithm 3 sign-recovery(x, y, δ) |
| Open Source Code | No | The paper does not provide any explicit statement about releasing source code or links to a code repository. |
| Open Datasets | No | This is a theoretical paper that does not describe experiments with datasets. Therefore, no information about public dataset availability is provided. |
| Dataset Splits | No | This is a theoretical paper that does not describe experiments with datasets. Therefore, no information about dataset splits for training, validation, or testing is provided. |
| Hardware Specification | No | This is a theoretical paper that does not describe experiments. Therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | This is a theoretical paper that does not describe experiments. Therefore, no specific software dependencies with version numbers are mentioned. |
| Experiment Setup | No | This is a theoretical paper that does not describe experiments. Therefore, no experimental setup details like hyperparameters or training configurations are provided. |