Dueling Convex Optimization
Authors: Aadirupa Saha, Tomer Koren, Yishay Mansour
ICML 2021 | Conference PDF | Archive PDF | Plain Text | 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. |