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 and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Global and Quadratic Convergence of Newton Hard-Thresholding Pursuit
Authors: Shenglong Zhou, Naihua Xiu, Hou-Duo Qi
JMLR 2021 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | The efficiency of NHTP was demonstrated on both synthetic and real data in compressed sensing and sparse logistic regression. Keywords: sparse optimization, stationary point, Newton s method, hard thresholding, global convergence, quadratic convergence rate |
| Researcher Affiliation | Academia | Shenglong Zhou EMAIL School of Mathematical Sciences University of Southampton Southampton SO17 1BJ, UK Naihua Xiu EMAIL Department of Applied Mathematics Beijing Jiaotong University Beijing, China Hou-Duo Qi EMAIL School of Mathematical Sciences and CORMSIS University of Southampton Southampton SO17 1BJ, UK |
| Pseudocode | Yes | NHTP: Newton Hard-Thresholding Pursuit Step 0 Initialize x0. Choose η, γ > 0, σ (0, 1/2), β (0, 1). Set k 0. Step 1 Choose Tk T (xk; η). Step 2 If Tolη(xk; Tk) = 0, then stop. Otherwise, go to Step 3. Step 3 Compute the search direction dk by (22). Step 4 Find the smallest integer ℓ= 0, 1, . . . such that f(xk(βℓ)) f(xk) + σβℓ f(xk), dk . (27) Set αk = βℓ, xk+1 = xk(αk) and k k + 1, go to Step 1. Table 1: Framework of NHTP |
| Open Source Code | No | The paper provides links to code for benchmark methods (HTP, NIHT, GP, OMP, CoSaMP, SP, GraSP) but does not provide specific access information or a direct statement for the open-source release of the NHTP method described in this paper. |
| Open Datasets | Yes | Example 5 (Real data) This example comprises of seven real data sets for binary classification. They are colon-cancer1, arcene2, newsgroup3, news20.binary1, duke breastcancer1, leukemia1, rcv1.binary1, which are summarized in the following table, where the last three data sets have testing data. 1https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/ 2http://archive.ics.uci.edu/ml/index.php 3https://web.stanford.edu/~hastie/glmnet_matlab/ |
| Dataset Splits | Yes | Example 5 (Real data) This example comprises of seven real data sets for binary classification. They are colon-cancer1, arcene2, newsgroup3, news20.binary1, duke breastcancer1, leukemia1, rcv1.binary1, which are summarized in the following table, where the last three data sets have testing data. Data name m samples n features training size m1 testing size m2 colon-cancer 62 2000 62 0 arcene 100 10000 100 0 newsgroup 11314 777811 11314 0 news20.binary 19996 1355191 19996 0 duke breast-cancer 42 7129 38 4 leukemia 72 7129 38 34 rcv1.binary 40242 47236 20242 20000 |
| Hardware Specification | Yes | All experiments were conducted by using MATLAB (R2018a) on a desktop of 8GB memory and Inter(R) Core(TM) i5-4570 3.2Ghz CPU. |
| Software Dependencies | Yes | All experiments were conducted by using MATLAB (R2018a) on a desktop of 8GB memory and Inter(R) Core(TM) i5-4570 3.2Ghz CPU. |
| Experiment Setup | Yes | We initialize NHTP with x0 = 0 if f(0) = 0 and x0 = 1 if f(0) = 0. Parameters are set as σ = 10^-4/2, β = 0.5. For γ, theoretically any positive γ m2s is fine, but in practice to guarantee more steps using Newton directions, it is supposed to be relatively small (De Luca et al., 1996; Facchinei and Kanzow, 1997). Thus we choose γ = γk with updating ( 10^-10, if xk T c k = 0, 10^-4, if xk T c k = 0. For parameter η, in spite of that Theorem 10 has suggested to set 0 < η < η, it is still difficult to fix a proper one since M2s is not easy to compute in general. Overall, we choose to update η adaptively. Typically, we use the following rule: starting η with a fixed scalar associated with the dimensions of a problem and then update it as, η0 = 10(1 + s/n) min{10, ln(n)} > 1, ηk/1.05, if mod(k, 10) = 0 and Fηk(xk; Tk) > k^2, 1.05ηk, if mod(k, 10) = 0 and Fηk(xk; Tk) k^2, ηk, otherwise. where mod (k, 10) = 0 means k is a multiple of 10. We terminate our method if at kth step it meets one of the following conditions: Tolηk(xk; Tk) 10^-6, where Tolη(x, T) is defined as (15); |f(xk+1) f(xk)| < 10^-6(1 + |f(xk)|). k reaches the maximum number (e.g., 2000) of iterations. |