Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1]
L-SVRG and L-Katyusha with Arbitrary Sampling
Authors: Xun Qian, Zheng Qu, Peter Richtárik
JMLR 2021 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We tested L-SVRG (Algorithm 1) and L-Katyusha (Algorithm 2) on the logistic regression problem i=1 log(1 + ebi A i x) + λ1 x 1 + λ2 2 x 2, (38) with fixed λ1 = 10 4 and different values of λ2. The data sets that we used are all downloaded from https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/. In all the plots, L-SVRG and L-Katyusha refer respectively to Algorithm 1 and Algorithm 2 with the uniform sampling strategy. L-SVRG IP and L-Katyusha IP mean that importance sampling with replacement as described in Section 6.5 is used. Katyusha refers to the original Katyusha algorithm proposed in (Allen-Zhu, 2017). Since in practice group sampling and sampling with replacement have similar convergence behaviour, here we only show the results obtained with sampling with replacement. In all the plots, the y-axis corresponds to the primal-dual gap of the iterates {xk}. The x-axis may be the number of epochs, counted as kτ/n plus the number of times we change wk, or the actual running time. The experiments were carried out on a Mac Book (1.2 GHz Intel Core m3 with 16 GB RAM) running mac OS High Sierra 10.13.1. Comparison of L-SVRG and L-Katyusha: In Figure 1 and Figure 2 we compare L-SVRG with L-Katyusha, both with the importance sampling strategy for w8a and cod_rna and three different values of λ2. In each plot, we compare three different minibatch sizes τ. The numerical results show that the number of epochs of L-SVRG generally increases with τ (since L/Lf is not large in these examples), while that of L-Katyusha is stable and thus achieves a linear speedup in terms of the number of epochs, as predicted in Section 6.6. |
| Researcher Affiliation | Academia | Xun Qian EMAIL Division of Computer, Electrical and Mathematical Sciences, and Engineering King Abdullah University of Science and Technology Thuwal, Saudi Arabia Zheng Qu EMAIL Department of Mathematics The University of Hong Kong Hong Kong Peter Richtárik EMAIL Division of Computer, Electrical and Mathematical Sciences, and Engineering King Abdullah University of Science and Technology Thuwal, Saudi Arabia |
| Pseudocode | Yes | Algorithm 1 Loopless SVRG (L-SVRG) Algorithm 2 Loopless Katyusha (L-Katyusha) Algorithm 3 Adapt Reg(A) (Allen-Zhu and Hazan, 2016) Algorithm 4 Adapt Reg-L-Katyusha Algorithm 5 x =delayed_update(t0, t1, u, x, η) Algorithm 6 ( y, z) =delayed_update2(t0, t1, u, y, z, w, η) |
| Open Source Code | No | The paper mentions "All the missing proofs and the efficient implementations for L-SVRG, L-Katyusha, and Katyusha for sparse data can be found in the Appendix." However, this refers to descriptions of how to implement the algorithms efficiently in the Appendix, not to a release of open-source code for the work described in the paper. No specific link or explicit statement of code release is provided. |
| Open Datasets | Yes | The data sets that we used are all downloaded from https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/. |
| Dataset Splits | No | The paper mentions using specific datasets (w8a, cod_rna, real-sim, astro_ph, a9a) and the logistic regression problem, but does not provide any specific information regarding how these datasets were split into training, validation, or test sets for the experiments. It does not mention percentages, sample counts, or refer to standard splits with citations. |
| Hardware Specification | Yes | The experiments were carried out on a Mac Book (1.2 GHz Intel Core m3 with 16 GB RAM) running mac OS High Sierra 10.13.1. |
| Software Dependencies | No | The paper mentions the operating system version used for experiments: "mac OS High Sierra 10.13.1." However, it does not specify any other software dependencies such as programming languages, libraries, or frameworks with their version numbers that would be required to reproduce the experiments (e.g., Python, PyTorch, TensorFlow, etc.). |
| Experiment Setup | Yes | We tested L-SVRG (Algorithm 1) and L-Katyusha (Algorithm 2) on the logistic regression problem i=1 log(1 + ebi A i x) + λ1 x 1 + λ2 2 x 2, (38) with fixed λ1 = 10 4 and different values of λ2. Require: stepsize parameters η > 0, L > 0, σ1 ≥ 0, θ1, θ2 ∈ (0, 1); probability p ∈ (0, 1]; multiset sampling distribution S (from Algorithm 2). if the stepsize parameters are set as follows L = max (L2, Lf) , σ1 = µf/L , θ2 = L2/(2L), θ1 = min( sqrt(µ/(3L)), L2/(2Lpθ2), θ2) if Lf <= L2/(2p) then θ1 = min(sqrt(µ/(3L)), L2/(2Lpθ2), θ2) else θ1 = min(sqrt(µ/(3L)), L2/(2Lpθ2), θ2) if Lf > L2/(2p) then L = Lf else L=L2, θ2 = L2/(2L), η = 1/(3θ1). |