Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusions
Authors: Xufeng Cai, Chaobing Song, Cristóbal Guzmán, Jelena Diakonikolas
NeurIPS 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We now illustrate the empirical performance of stochastic Halpern iteration on robust least square problems. Specifically, given data matrix A ∈ R n×d and noisy observation vector b ∈ R n subject to bounded deterministic perturbation δ with ‖δ‖ ∞, robust least square (RLS) minimizes the worst-case residue as minx∈R d maxδ:‖δ‖∞≤ε ‖Ax − y‖ 2 2 with y = b + δ [16]. We consider solving MI induced from RLS with Lagrangian relaxation where u = (x, y)T and F(u) = |
| Researcher Affiliation | Academia | Xufeng Cai Department of Computer Sciences University of Wisconsin-Madison xcai74@wisc.edu Chaobing Song Department of Computer Sciences University of Wisconsin-Madison songcb16@gmail.com Cristóbal Guzmán Institute for Mathematical and Computational Eng. Facultad de Matemáticas and Escuela de Ingeniería Pontificia Universidad Católica de Chile crguzmanp@mat.uc.cl Jelena Diakonikolas Department of Computer Sciences University of Wisconsin-Madison jelena@cs.wisc.edu |
| Pseudocode | Yes | Algorithm 1: Stochastic Halpern-Cocoercive (Halpern) Algorithm 2: Extrapolated Stochastic Halpern-Monotone (E-Halpern) Algorithm 3: Restarted Extrapolated Stochastic Halpern-Sharp (Restarted E-Halpern) |
| Open Source Code | Yes | 2Code is available at https://github.com/zephyr-cai/Halpern. |
| Open Datasets | Yes | We use a real-world superconductivity dataset [22] from UCI Machine Learning Repository [15] for our experiment, which is of size 21263 × 81. To ensure the problem is concave in y, we need that λ > 1; in the experiments, we set λ = 1.5. For the experiment, we compare Halpern, E-Halpern, and Restarted E-Halpern algorithms with gradient descent-ascent (GDA), extragradient (EG) [28], and Popov’s method [42] in stochastic settings. |
| Dataset Splits | No | The main text describes the dataset but does not provide specific training/test/validation split percentages, sample counts, or detailed splitting methodology. |
| Hardware Specification | Yes | We implement all the algorithms in Python and run each algorithm using one CPU core on a mac OS machine with Intel 2.3GHz Dual Core i5 Processor and 8GB RAM. |
| Software Dependencies | No | The paper mentions implementation in 'Python' but does not specify its version or any other software dependencies with version numbers. |
| Experiment Setup | Yes | We use constant batch sizes and constant step sizes for GDA, EG, and Popov. We also choose the batch sizes of PAGE estimator to ensure E[‖F(uk) − e F(uk)‖^2] = O(1/k), which handles error accumulation [29] and early stagnation of stochastic Halpern iteration. We implement all the algorithms in Python and run each algorithm using one CPU core on a mac OS machine with Intel 2.3GHz Dual Core i5 Processor and 8GB RAM.2 |