Quantum Algorithms and Lower Bounds for Finite-Sum Optimization
Authors: Yexin Zhang, Chenyi Zhang, Cong Fang, Liwei Wang, Tongyang Li
ICML 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We give a quantum algorithm with complexity O n + ℓ/µ n1/3d1/3 + n 2/3d5/6 ,1 improving the classical tight bound Θ n + p nℓ/µ . We also prove a quantum lower bound Ω(n + n3/4(ℓ/µ)1/4) when d is large enough. |
| Researcher Affiliation | Academia | 1School of Electronics Engineering and Computer Science, Peking University, China 2Computer Science Department, Stanford University, USA 3National Key Lab of General Artificial Intelligence, School of Intelligence Science and Technology, Peking University 4Institute for Artificial Intelligence, Peking University 5Center on Frontiers of Computing Studies, Peking University, China 6School of Computer Science, Peking University, China. |
| Pseudocode | Yes | Algorithm 1: Q-Katyusha |
| Open Source Code | No | The paper does not contain any explicit statements about releasing source code or links to a code repository. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments with datasets. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments involving dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe any specific hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not list any specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setup details such as hyperparameters or training configurations. |