On the Hardness of Online Nonconvex Optimization with Single Oracle Feedback
Authors: Ziwei Guan, Yi Zhou, Yingbin Liang
ICLR 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we focus on the more challenging and practical setting, where access to only a single oracle is allowed per time step, and take the local regret of the original (i.e., unsmoothed) objective functions as the performance metric. Specifically, for both settings respectively with a single exact and stochastic gradient oracle feedback, we derive lower bounds on the local regret and show that the classical online (stochastic) gradient descent algorithms are optimal in the class of linear-span algorithms. Moreover, for the more challenging setting with a single function value oracle feedback, we develop an online algorithm based on a one-point running difference gradient estimator, and show that such an algorithm achieves a local regret that a generic stochastic gradient oracle can best achieve. |
| Researcher Affiliation | Academia | Department of Electrical and Computer Engineering, Ohio State University Department of Electrical and Computer Engineering, University of Utah |
| Pseudocode | Yes | Algorithm 1 Online Gradient Descent (OGD) Input: Initial point x1, stepsizes η for t = 1, . . . , T do Update xt+1 based on eq. (3) end for |
| Open Source Code | No | The paper does not contain any explicit statements or links indicating the release of open-source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments involving datasets, thus no information about public datasets is provided. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments involving datasets, thus no information about dataset splits is provided. |
| Hardware Specification | No | The paper is theoretical and does not report on experimental hardware used. |
| Software Dependencies | No | The paper is theoretical and does not report on software dependencies with specific version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe experimental setups with hyperparameters or training configurations. |