Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions
Authors: Xufeng Cai, Ahmet Alacaoglu, Jelena Diakonikolas
ICLR 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We provide preliminary numerical results for our proposed algorithms. We compare Alg. 1 and Alg. 2 with existing algorithms on matrix games and a special quadratic program used for lower bound derivations in Ouyang & Xu (2021). We summarize our numerical results and plot the operator norm against the number of epochs in Fig. 1, where one epoch means n individual component operator evaluations. |
| Researcher Affiliation | Academia | 1Department of Computer Sciences, University of Wisconsin Madison 2Wisconsin Institute for Discovery, University of Wisconsin Madison |
| Pseudocode | Yes | Algorithm 1 Halpern iteration with variance reduction; Algorithm 2 Inexact Halpern iteration with VR Fo RB; Algorithm 3 VR Fo RB(u, M, A + B, Q) |
| Open Source Code | Yes | Code is available at https://github.com/zephyr-cai/Finite-Sum-Halpern-Iteration. |
| Open Datasets | No | The paper describes the problem instances (matrix game with a specific matrix type, quadratic program from a cited work) and their parameters (e.g., m1=m2=500), but it does not mention the use of a pre-existing publicly available dataset, nor does it provide links or access information for one. |
| Dataset Splits | No | The paper describes the problem instances used for evaluation but does not specify any dataset splits (training, validation, or testing). |
| Hardware Specification | No | The paper states: 'run the experiments on Google Colab standard CPU backend.' This describes the general environment but does not provide specific hardware models (e.g., CPU model, number of cores, memory) to allow for reproduction. |
| Software Dependencies | No | The paper states: 'We implement all the algorithms in Python'. It does not list any specific software libraries or their version numbers that are critical dependencies for replication. |
| Experiment Setup | Yes | First problem is a matrix game with simplex constraints, i.e., minx m1 maxy m2 Ax, y with m1 = m2 = 500. We use the policeman and burglar matrix (Nemirovski, 2013). Second problem we consider is a quadratic program from Ouyang & Xu (2021) equivalent to the problem minx Rm1 maxy Rm2 1 2x Hx h x Ax b, y , where m1 = m2 = 200. We use uniform sampling for all the algorithms, set Mk = 0.05n log(k + 2) for Alg. 2, and tune the stepsizes for each method individually. |