On The Complexity of First-Order Methods in Stochastic Bilevel Optimization
Authors: Jeongyeol Kwon, Dohyun Kwon, Hanbaek Lyu
ICML 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the complexity of finding stationary points with such an y -aware oracle: we propose a simple firstorder method that converges to an ϵ stationary point using O(ϵ 6), O(ϵ 4) access to first-order y -aware oracles. Our upper bounds also apply to standard unbiased first-order oracles, improving the best-known complexity of first-order methods by O(ϵ) with minimal assumptions. We then provide the matching Ω(ϵ 6), Ω(ϵ 4) lower bounds without and with an additional smoothness assumption on y -aware oracles, respectively. |
| Researcher Affiliation | Academia | 1Wisconsin Institute for Discovery, Wisconsin, USA 2Department of Mathematics, University of Seoul, Republic of Korea 3Center for AI and Natural Sciences, Korea Institute for Advanced Study, Republic of Korea. Correspondence to: Jeongyeol Kwon <jeongyeol.kwon@wisc.edu>, Dohyun Kwon <dh.dohyun.kwon@gmail.com>. |
| Pseudocode | Yes | Algorithm 1: Penalty Methods with Lower-Level Coupling and Algorithm 2: Proj |
| Open Source Code | No | The paper does not contain any statements about open-sourcing code or links to repositories. The paper is theoretical in nature. |
| Open Datasets | No | No information on publicly available datasets or their access is provided, as the paper is purely theoretical and does not conduct empirical studies. |
| Dataset Splits | No | No information on dataset splits for training, validation, or testing is provided, as the paper is purely theoretical and does not conduct empirical studies. |
| Hardware Specification | No | No hardware specifications are provided, as the paper is purely theoretical and does not involve experimental computation. |
| Software Dependencies | No | No software dependencies with specific version numbers are mentioned, as the paper is purely theoretical and does not involve computational experiments. |
| Experiment Setup | No | No experimental setup details, hyperparameters, or training configurations are provided, as the paper is purely theoretical and does not conduct empirical studies. |