Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Construction
Authors: Yuze Han, Guangzeng Xie, Zhihua Zhang
JMLR 2024 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper we study the lower complexity bounds for finite-sum optimization problems, where the objective is the average of n individual component functions. We develop a novel approach to constructing the hard instances, which partitions the tridiagonal matrix of classical examples into n groups. This construction is friendly to the analysis of PIFO algorithms. Based on this construction, we establish the lower complexity bounds for finite-sum minimax optimization problems when the objective is convex-concave or nonconvex-strongly-concave and the class of component functions is L-average smooth. |
| Researcher Affiliation | Academia | Yuze Han EMAIL School of Mathematical Sciences Peking University Beijing, China. Guangzeng Xie EMAIL Academy for Advanced Interdisciplinary Studies Peking University Beijing, China. Zhihua Zhang EMAIL School of Mathematical Sciences Peking University Beijing, China. |
| Pseudocode | Yes | Definition 11 Consider a randomized PIFO algorithm A to solve Problem (1). Denote the point obtained by A after step t by (xt, yt), which is generated by the following procedure. 1. Initialize the set H as {(x0, y0)}, the distribution D over [n], a positive number q c0/n and set t = 1. 2. Sample it D and query the oracle h PIFO fit at the current point (xt 1, yt 1) and also at a previous point in {(xl, yl)}0 l<t 1, if necessary. 3. Sample a Bernoulli random variable at with expectation equal to q. If at = 1, query the oracle h FO f at point (xt 1, yt 1) and add (xt 1, yt 1) to H. 4. Obtain ( xt, yt) following the linear-span protocol ... 5. Projection step: xt = PX ( xt), yt = PY( yt). 6. Output (xt, yt), or increase t by 1 and go back to step 2. |
| Open Source Code | No | No explicit statement or link to source code for the methodology described in this paper is provided. The license information provided is for the paper itself, not for companion code. |
| Open Datasets | No | The paper is theoretical and focuses on lower complexity bounds for optimization problems. It does not conduct experiments using specific datasets, therefore no concrete access information for publicly available datasets is provided. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical evaluation on datasets. Therefore, it does not provide any information regarding training/test/validation dataset splits. |
| Hardware Specification | No | The paper is purely theoretical and does not describe any experimental setup or results that would require specific hardware. Thus, no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is purely theoretical and focuses on mathematical proofs and constructions. It does not describe any experimental implementation, and therefore, no software dependencies with version numbers are mentioned. |
| Experiment Setup | No | The paper is theoretical and focuses on deriving lower complexity bounds for optimization problems. It does not include any experimental results or their setup details, such as hyperparameters or training configurations. |