Efficient Alternating Minimization with Applications to Weighted Low Rank Approximation

We express our deepest gratitude for your insightful comments and sincerely appreciate your evaluation of our work as technically sound, with techniques that can be applied to other optimization and machine learning problems. Your feedback is extremely valuable to us and reinforces our belief that our work will have a meaningful impact on the optimization and machine learning communities. Below, we address your concerns about our work.

Concern: It is beneficial to include numerical illustrations to verify the theoretical findings and show the usefulness of the proposed method.

Answer: Regarding the first weakness, we kindly refer you to our global response. We have conducted preliminary experiments demonstrating that our algorithm is indeed faster than the exact solver proposed in (Li et al., 2016). We believe that our experimental results strongly suggest that our algorithm will perform effectively in practice.

Concern: In Line 223, the paper shows that Assumption 3 is a generalization to the RIP condition. Although the reviewer agrees that the assumption is more general in the sense that it contains the weight matrix $W$, the reviewer thinks it is more restrictive than the RIP condition.

Answer: We agree with your observation that our wording is imprecise in referring to it as generalized RIP. For a matrix $A$ to be RIP, one requires for any subset of columns of size $s$, we have $(1-\delta_s) I_s \preceq A_s^\top A_s\leq (1+\delta_s) I_s$, but here, we only have that $\alpha I_k \preceq U^\top D_{W_i} U \preceq \beta I_k$ for all $n$ columns of $W$. This should instead be treated as a generalization of Assumption A2 in (Bhojanapalli et al., 2014), where they consider the noisy matrix completion problem and $D_{W_i}$ is a binary diagonal matrix. A more precise description of this assumption is that it represents a stronger condition than incoherence, which is itself implied by the stronger incoherence assumption in (Candès et al., 2010).

Question: Theorem 4.6: I wonder if the time complexity also depends on the scale of $M^*$ and $N$. For example, let $c > 0$ be a constant. If we multiply $M^*$ and $N$ by $c$, then the solution $\tilde{M}$ will also be multiplied by $c$. However, the value $\epsilon$ is not changed in the error bound. In addition, Assumption 2.3 does not bound the scale of $M^*$ and $N$ either. If I did not miss anything, I feel that the number of iterations or the error $\epsilon$ should depend on the scale of $M^*$ and $N$.

Answer: Our runtime actually does not depend on the scale of $M$ and $M^*$. Intuitively, this is because the scaling is accounted for by the alternating minimization: if we scale $M$ by a factor of $c>0$, then the singular vectors remain unchanged, and singular values are scaled by $c$. For simplicity, assuming in Algorithm 1, we do not need to perform Clip, and instead of randomly initializing $Y$, we set $Y$ to be the right singular vectors of $W\circ M$. Note that in the iteration, when solving for $X$, the magnitude of $X$ will account for the scaling of $M$, i.e., compared to the original $X$ without scaling by $c$, the new $X$ will be scaled by a factor of $C$. After properly renormalizing $X$, the new $Y$ will also account for the scaling of $M$. If one inspects our proof, we essentially prove that the distance between the subspace spanned by the optimal right singular vectors of $M^*$ and the initial $Y$ is at most $\frac{1}{2}$, and we inductively prove that the distance shrinks geometrically. The distance between subspaces is invariant under scaling as they are defined in terms of the orthonormal basis for the subspace, therefore the $\epsilon$ term is not affected by the scaling of $M$. Of course, in the most rigorous sense, it is not precise to state that our runtime “does not depend on the scale of $M$”, as we implicitly assume that operations such as matrix multiplication, inversion, and SVD can be done in $O(n^3)$ time, which is not true if the entries of $M$ are too large (exponentially large, which would require $\mathrm{poly}(n)$ bits to write down).

We express our deepest gratitude for your insightful comments! We truly appreciate your recognition that our theoretical results are solid, interesting, and have the potential to influence other theoretical areas. Below, we address your concerns about our work.

Concern: The writing of the paper could be improved, for example, Algorithm 1 is outlined in a dense way in Section 3. Also, lines 270 - 180 contain numerous sentences that are a bit awkward and hard to understand.

Answer: We note that we do not introduce any algorithm in Section 3. We assume you are referring to the bottom of Section 1, where we introduce Algorithm 1. Compared to the original work of (Li et al., 2016), the main innovation of our algorithm is a strong and robust analysis when the alternating updates $\vec X$ and $\vec Y$ are computed approximately and efficiently. We have marked these two lines in red to emphasize this distinction. In the revised version of our paper (see Remark 1.2 that we added), we explicitly state that the general framework of our main algorithm (Algorithm 1) is a strengthening of the traditional alternating minimization, by replacing the exact update with an approximate update (lines 7 and 10) to make the overall algorithm faster and more robust. We hope this clarification will help readers understand that while our main algorithm is lengthy, the key contribution lies in our approximate fast solver (Algorithms 2 and 3). And the majority of Section 33 is centered around these two topics: 1. How to design a faster solver for approximate alternating updates, 2. How to prove the convergence of the algorithm under the presence of errors introduced by approximate updates. Regarding Lines 270 to 280, thank you very much for pointing this out. There is a typo on Line 279 (which is now Line 281 in the updated version). The first word on that line should be “forward” instead of “backward.” In general, we intended to convey that, although the traditional sketching technique is fast, it has a limitation that makes it unsuitable for implementation in our algorithm. Specifically, it provides a relative error guarantee on the regression cost (forward error). While this forward error can be transformed into the desired backward error, it ultimately causes the backward error to blow up, which negatively impacts the running time of our algorithm.

Concern: The paper lacks numerical experiments, I suggest that the authors at least run some synthetic experiments to demonstrate a reduction in real runtime.

Answer: We kindly refer you to our global response. We have conducted preliminary experiments demonstrating that our algorithm is indeed faster than the exact solver proposed in (Li et al., 2016). We believe that our experimental results strongly indicate that our algorithm will perform well in practice.

Again, we deeply appreciate all of your insightful comments. We have changed our manuscript accordingly to highlight the important parts of our Algorithm 1 and refer the readers to (Li et al., 2016) for more alternating minimization background to understand the remaining parts of our Algorithm 1 (as specified above), and we have fixed our typo, making Lines 270 to 280 more clear.

Yuanzhi Li, Yingyu Liang, and Andrej Risteski. "Recovery guarantee of weighted low-rank approximation via alternating minimization." ICML’16.

We express our deepest gratitude to the reviewer for the time and effort in giving us insightful feedback, and thank you for evaluating our work as well-motivated, well-presented, and significantly contributing to theory. Below, we want to address your concerns about our work.

Concern: The authors didn’t conduct experiments to verify the performance of their algorithm.

Answer: We kindly refer you to our global response. We have conducted preliminary experiments demonstrating that our algorithm is indeed faster than the exact solver proposed in (Li et al., 2016). We believe that our experimental results strongly indicate that our algorithm is practical and effective.

Question: Could the authors explain the connection between the problem they considered (Problem 2.4) and the original problem? Are they equivalent under some conditions?

Answer: To see the connection, define $f(K):=\\| W \circ (M - K) \\|_F^2$ where $K$ is rank-$k$. The original weighted low rank approximation problem aims to find an approximate solution with small forward error, i.e., finding a $\widetilde K$ such that $f$ is approximately minimized. Note that $f$ is non-convex, so even if we can find $\widetilde K$ where $f(\widetilde K)$ is small, it is not guaranteed that $\widetilde K$ is close to $M$ in any form. On the other hand, the goal defined in Problem 2.4 seeks to find a matrix that is not only close to $M$ in spectral norm but also assumes $M=M^*+N$ where $M^*$ is rank-$k$ ground truth and $N$ is a high-rank noise. The objective is to find a $\widetilde M$ that is close to the ground truth $M^*$. In other words, the guarantee we achieve in this paper is the backward error guarantee. Note that $\widetilde M$ is close to $M^*$ already implies that $f(\widetilde M)$ is small. Therefore, the guarantee provided in this paper strengthens the original weighted low rank approximation problem. Our algorithm not only solves the original problem efficiently in $\\|W\\|_0 k$ time but also addresses a stronger and more challenging problem.

Question: Could the authors explain the meaning of $\epsilon_0$ in Line 351?

Answer: We appreciate you for pointing this out, the $\epsilon_0$ in Line 351 is in fact a typo, and it was supposed to be $\epsilon$. We have fixed this issue in the updated manuscript.

We thank you again for your insightful comments. We hope that our comments may address your concerns. If you have any further questions or concerns about our work, we are more than happy to address them.

Yuanzhi Li, Yingyu Liang, and Andrej Risteski. "Recovery guarantee of weighted low-rank approximation via alternating minimization." ICML’16.

We express our deepest gratitude to the reviewer for these insightful comments. We thank you for pointing out that the problem we study is important and the reduction in the running time over the top algorithm analyzed in (Li et al., 2016). Below, we want to address your concerns about our work.

Concern: The assumption that $\\|W - J \\|\leq \gamma n$ with $\gamma=O(n^{-c})$ is quite strong compared to $\gamma=O(1)$ in (Li et al., 2016). Can you justify the slightly stronger assumption on $W$?

Answer: We note that our result is best compared to the random initialization of (Li et al., 2016) (Theorem 3), where they additionally impose a bound on $\\|W \\|\_{1, \infty}\leq O(\frac{\alpha n}{k^2\mu\log n})$ (in their notation, $\\|W \\|\_{\infty}$). Note that $\\|W \\|\_{1, \infty}$ gives an upper bound on the spectral norm, thereby implicitly bounding $\\| W - J \\|$ and the choice of $\gamma$. To simplify their additional assumption, we choose $\gamma$ to be smaller, such that it directly implies the desired $\\|W\\|_{1, \infty}$ bound as in (Li et al., 2016). To obtain a similar bound for $\gamma$ that is roughly $O(\frac{1}{\mu^2 k^{2.5}})$, we could instead pose the same assumptions on $\\|W\\|\_{1, \infty}\leq O(\frac{\alpha n}{k^2 \mu \log n})$. Therefore, our result should be interpreted as a robustification and direct speedup of (Li et al., 2016) without introducing stronger assumptions or restricting parameter choices (up to polylogarithmic factors). In the appendix (see Theorem G.7), we prove a similar result as the SVD initialization of (Li et al., 2016) that does not need the bound on $\\|W\\|\_{1, \infty}$.

Concern: The key techniques used in this paper were introduced in prior works, so it lacks novelty a bit in that sense.

Answer: While we build on existing techniques, we would like to emphasize a major novel insight of our proofs: a significant simplification of the analysis for noiseless matrix completion introduced by (Gu et al., 2024). In that work, the authors develop a convoluted framework to accelerate noiseless matrix completion. Their analysis, in particular, is heavily built on the specific structure of that problem, making it unclear how to generalize their techniques to more complex problems, such as matrix completion with noise or weighted low rank approximation. In contrast, our analysis is both simpler and more robust, and we believe it could be extended to problems such as multi-view learning (though we leave this as a future direction). We hope our work provides insights into developing robust and efficient alternating minimization methods for a broader range of problems.

Question: Are you aware of any practical application where the improvement in the running time by a factor of $k$ obtained in this paper may be significant to applications, and where one might expect assumptions to hold?

Answer: As demonstrated by our synthetic experiments, even for $n=800, k=100$, our algorithm already offers a speedup compared to the exact alternating minimization.

We would also like to emphasize that, beyond shaving off a $k$ factor and achieving nearly optimal runtime, we also provide a robust analytical framework for alternating minimization. As a powerful and widely used primitive in practice, most theoretical analyses of alternating minimization focus on exactly computing the updates. For example, if one carefully inspects the analysis in (Li et al., 2016), it heavily exploits the closed-form solution to quantify the distances between subspaces. Unfortunately, this analytical framework is not robust enough. As we have shown in our analysis, perturbing the solutions output by the solvers can lead to polynomially large errors in the final quality of the algorithm. This is in contrast with reality, where the updates can only be computed approximately. Moreover, fast solvers are used in practice to produce these approximate updates efficiently (Avron et al., 2010, Meng et al, 2014). We provide a robust analytical framework that effectively resolves this issue by using a high-accuracy solver and bounding the condition number. Thus, our work could be interpreted as a theoretical explanation of why alternating minimization works well in practice despite the presence of errors.

Again, we thank you for your insightful comments, and we hope that our response may address your concerns. Please let us know if you have any further questions or concerns. We will be very happy to address them.

We test the performance of regression solvers for $n=10^6, k = 500$ with a sketch size $m=5500$, and run our solver for 5 iterations. The results are as follows:

Our data matrices $A$ and response vectors $b$ are generated according to standard Gaussian, Laplace and power law distribution with $p=5$, and we measure the $\ell_\infty$ error of the solution, i.e., let $\hat x$ denote the vector outputted by the solver, we measure $\\|\hat x - x^*\\|\_\infty$ where $x^*=\arg\min_{x\in \mathbb{R}^k} \\|Ax-b\\|_2^2$. The speedup obtained here ranges from 20% to 30%, so we have strong grounds to believe that the acceleration will even be more evident when $n$ is large. However, performing weighted low rank approximation on $10^6\times 10^6$ size matrices is currently out of the scope of our computational power, we hence leave this as a future direction.

Due to the limited time and computational resources, we only test our algorithm under these two settings. We intend to keep conducting and integrating additional experiments on weighted low rank approximation under different settings in the final version of our paper.

Yuanzhi Li, Yingyu Liang, and Andrej Risteski. "Recovery guarantee of weighted low-rank approximation via alternating minimization." ICML’16.

Moses Charikar, Kevin Chen, and Martin Farach-Colton. "Finding frequent items in data streams." ICALP’02