Inductive Matrix Completion: No Bad Local Minima and a Fast Algorithm
Authors: Pini Zilber, Boaz Nadler
ICML 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Empirically, given entries observed uniformly at random, GNIMC recovers the underlying matrix substantially faster than several competing methods. |
| Researcher Affiliation | Academia | 1Faculty of Mathematics and Computer Science, Weizmann Institute of Science, Israel. Correspondence to: Pini Zilber <pini.zilber@weizmann.ac.il>, Boaz Nadler <boaz.nadler@weizmann.ac.il>. |
| Pseudocode | Yes | Algorithm 1 GNIMC input sampling operator PΩ, observed matrix Y , side information matrices (A, B), maximal number of iterations T, initialization (U0, V0) output rank-r (approximate) solution to PΩ( ˆX) = Y |
| Open Source Code | Yes | MATLAB and Python code implementations of GNIMC, Alt Min, GD and RGD are available at github.com/pizilber/IMC. |
| Open Datasets | No | In each simulation we construct U Rd1 r, V Rd2 r, A Rn1 d1 and B Rn2 d2 with entries i.i.d. from the standard normal distribution, and orthonormalize their columns. We then set X = AUDV B where D Rr r is diagonal with entries linearly interpolated between 1 and κ. |
| Dataset Splits | No | The paper does not specify explicit train/validation/test dataset splits. Data is synthetically generated for each simulation run. |
| Hardware Specification | No | The paper does not provide specific hardware details (e.g., exact GPU/CPU models, memory amounts) used for running its experiments. |
| Software Dependencies | Yes | L-BFGS: limited-memory quasi-Newton BFGS algorithm, as implemented in MATLAB R2022a. |
| Experiment Setup | Yes | For each simulation setting, we tuned the optimal parameter out of 10 logarithmically-scaled values. The permitted values for Maxide were 10 5, ..., 10 14; for MPPF, GD and RGD were 10 2/κ, ..., 10 1 2 /κ where κ is the condition number of X ; for Scaled GD were 10 2, ..., 10 1 2 ; and for L-BFGS were 1, ..., 103. For GNIMC, in all simulations we identically set the maximal number of iterations for the inner least-squares solver to 10 if the observed error is low, PΩ(Xt) Y F Y F 10 4, and 1000 otherwise. We used the following two stopping criteria for all methods: (i) small relative observed RMSE, PΩ(Xt) Y F Y F ϵ, or (ii) small relative estimate change PΩ(Xt Xt 1) F PΩ(Xt) F ϵ. In our simulations, we set ϵ = 10 14. |