Efficient Alternating Minimization with Applications to Weighted Low Rank Approximation

Authors: Zhao Song, Mingquan Ye, Junze Yin, Lichen Zhang
Primary area: optimization
Keywords: weighted low rank approximation, sketching, alternating minimization

Abstract:
Weighted low rank approximation is a fundamental problem in numerical linear algebra, and it has many applications in machine learning. Given a matrix $M \in \mathbb{R}^{n \times n}$, a non-negative weight matrix $W \in \mathbb{R}_{\geq 0}^{n \times n}$, a parameter $k$, the goal is to output two matrices $X,Y\in \mathbb{R}^{n \times k}$ such that $\\| W \circ (M - X Y^\top) \\|_F$ is minimized, where $\circ$ denotes the Hadamard product. It naturally generalizes the well-studied low rank matrix completion problem. Such a problem is known to be NP-hard and even hard to approximate assuming the Exponential Time Hypothesis. Meanwhile, alternating minimization is a good heuristic solution for weighted low rank approximation. In particular, [Li, Liang and Risteski, ICML'16] shows that, under mild assumptions, alternating minimization does provide provable guarantees. In this work, we develop an efficient and robust framework for alternating minimization that allows the alternating updates to be computed approximately. For weighted low rank approximation, this improves the runtime of [Li, Liang and Risteski, ICML'16] from $\\|W\\|_0k^2$ to $\\|W\\|_0 k$ where $\\|W\\|_0$ denotes the number of nonzero entries of the weight matrix. At the heart of our framework is a high-accuracy multiple response regression solver together with a robust analysis of alternating minimization.

Decision: accept (poster)
Reviewer scores: 6, 6, 5, 6

Reviews and discussion:
<thread>
creation date:
1730334799817

thread_type:
official_review

<thread_object>
creator: reviewer_5ic9

<content>
summary:
In this work, the authors proposed a new alternating minimization method for the weighted low-rank matrix approximation problem. They utilized an efficient multiple-response regression solver to reduce the computational time from ${O}((\|W\|_0k^2 + nk^3)\log(1/\epsilon))$ to $\tilde{O}((\|W\|_0k + nk^3)\log(1/\epsilon))$.

strengths:
The paper provides a novel algorithm for the low-rank matrix approximation problem. The results in this work may also be applied to other optimization and machine learning problems. After checking the paper, I think the theoretical results in the paper should be sound, although I did not check all proofs due to the time limit.

weaknesses:
Although this paper is mostly a theoretical paper, I think it is still beneficial to include numerical illustrations to verify the theoretical findings and show the usefulness of the proposed method. For example, the authors may generate artificial datasets that satisfy the assumptions in this work and compare their method with the methods in (Li et al., 2016). It would be even better if the authors can verify that Assumption 2.3 holds in some practical examples and exhibit the empirical performance on these real-world examples.

Moreover, in Line 223, the authors claimed that Assumption 3 is a generalization to the RIP condition. Although I agree with the authors that the assumption is more general in the sense that it contains the weight matrix $W$, I think it is more restrictive than the RIP condition. Suppose that $W$ is a boolean matrix and each column of $W$ contains at most $k$ 1's. In this case, the assumption considers at most $n$ combinations of rows of $U$ and $V$. In contrast, the RIP condition requires the error bound to hold for all $k$-dimensional subspace. In addition, I feel that Assumption 3 is not directly comparable with the classical RIP condition. The definition of the classic $(r, \delta)$-RIP condition would imply that $(1-\delta) \lVert K \rVert_F^{2} \leq \lVert W \circ K \rVert_F^{2} \leq (1+\delta) \lVert K \rVert_{F}^{2}$ holds for any matrix $K$ of rank at most $k$, which is independent of $M^*$. I would suggest the authors include more detailed explanations to this claim.

questions:
I have a few other minor comments for the authors to consider:

- 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$.


- Line 499: it would be helpful if the authors could provide supporting evidence for the claim that the spectral norm is more robust than the Frobenius norm.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730411880238

thread_type:
official_review

<thread_object>
creator: reviewer_j2kz

<content>
summary:
This paper considers the weighted low-rank approximation problem, which can be solved using alternating minimization. In previous methods, the alternating minimization algorithm requires solving n linear regression problems each iteration. In this work, the authors develop a framework based sketching, and they prove that alternating minimization is robust enough such that the approximate solution return each iteration also converges towards the optimal solution. As a result, they obtain an improved running time compared to Li et al. 2016.

strengths:
I think the theoretical results in this paper is solid: the proof that the alternating minimization framework is robust enough to tolerate large errors induced in the approximate solution is interesting, and can possibly be generalized to other similar problems in matrix optimization.

weaknesses:
I see two main weaknesses. First, I think the writing of this paper needs to be improved, especially in section 3, where the algorithm is first introduced. Algorithm 1 is outlined in a dense way that makes it hard for the reader to parse exactly what is going on. Also, lines 270-280 contain numerous sentences that are a bit awkward or hard to understand. I suggest that the authors use a separate section to slowly present algorithm 1 step by step, and describe which parts are new. 

Another weakness i see is the lack of any numerical results. In the introduction (lines 80) the authors say that the results of Li et al. 2016 are hard to deploy in practice because of the high time complexity. While this paper reduces the time complexity in theory, there are no numerical section to demonstrate that the reduction in time complexity is useful in practice. I suggest that the authors at least run some synthetic experiments to demonstrate a reduction in real runtime.

questions:
Can the authors comment on the performance of their algorithm on some real or even synthetic problems?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730554185684

thread_type:
official_review

<thread_object>
creator: reviewer_mhu4

<content>
summary:
The authors propose an efficient framework for alternating minimization, which allows the subproblems to be solved approximately. They apply the framework to the weighted low rank approximation problem, theoretically improving the runtime.

strengths:
1. The authors propose a high-precision regression solver and extend it to the weighted case. They also demonstrate the robustness of the alternating minimization framework. The theoretical analysis is a significant contribution.
2. The motivation behind their method is detailed and well-presented in the paper.

weaknesses:
The authors did not conduct experiments to verify the performance of their algorithm. I am interested in whether the algorithm is feasible in practice.

questions:
1. Could the authors explain the connection between the problem they considered (Problem 2.4) and the original problem? Are they equivalent under some conditions?
2. Could the authors explain the meaning of $\epsilon_0$ in Line 351?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730692223016

thread_type:
official_review

<thread_object>
creator: reviewer_ds4q

<content>
summary:
This paper studies the problem of weighted low-rank matrix approximation. In this problem one is given a weight matrix W
 and observes a matrix M', and the goal is to recover a matrix M of rank at most k that minimizes  $\Vert W \circ (M'- M)\Vert$..

This paper provides new theoretical guarantees within the alternating minimization framework for weighted low-rank matrix approximation. The authors propose a new alternating minimization algorithm that uses high-accuracy regression solver based on sketching instead of exact regression solvers in the optimization step of the algorithm compared to the work of (Li et al, 2016). This allows authors to improve runtime by a factor of $k$. 
.

strengths:
The problem of weighted low-rank matrix approximation is an important practical problem and an important algorithmic primitive that arises in numerical linear algebra, and various machine learning applications. The problem naturally generalizes classical low-rank matrix approximation problems and a matrix completion problem. Alternating minimization is an extremely successful practical approach to matrix completion problem, so establishing theoretical guarantees for this approach to the weighted low-rank matrix approximation problem is of high interest.

This paper builds on top algorithm analyzed in (Li et al., 2016) and the key difference between the algorithm in (Li et al., 2016) and this paper is that exact solvers for linear regression is replaced with an approximate solver that can be traced back to (Rokhlin & Tygert, 2008). This allows authors to improve runtime by a factor of $k$ and to get a nearly optimal runtime.

weaknesses:
The assumption 2.4.2 asks that $||W - J||<\gamma n$, where J is an all-one matrix with $\gamma = O(n^{-c})$ (compared to O(1) in  (Li et al., 2016)). This assumption sounds quite strong to me. This means that in the matrix completion scenario, this allows one to have only o(1)-fraction of entries not observed in every row. Considering that one of the key regimes for low-rank problems assumes that the rank satisfies k = O(1), I am not sure if improvement in runtime completely justifies slightly stronger assumption on W.

Another slight weakness of the paper is that most of the key techniques used in this paper were introduced in prior work, so the paper lacks a bit of novelty in this sense.

questions:
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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732243921987

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Global Response--Part 1

comment:
We would like to express our deepest gratitude to all the reviewers, program chairs, and (senior) area chairs for their insightful comments and consideration of our paper. All reviewers agree that our theoretical contribution is sound. Additionally, since 1. weighted low rank approximation is a fundamental problem in numerical linear algebra, 2. our work improves upon the top algorithm of the well-known work (Li et al., 2016), 3. alternating minimization is a widely used and very successful algorithm in practice, 4. Our work further improves the applicability of alternating minimization by improving the running time and robustness, our work is evaluated as well-motivated and well-presented. 

One concern that multiple reviewers have regarding our work is that our work lacks the experimental result or numerical illustration (Reviewer MHu4, Reviewer j2kz, and Reviewer 5iC9). Instead of using experimental results to strengthen the contribution, reviewers actually hope to see the actual reduction in running time, and our technique may indeed work well in practice. Therefore, reviewers suggest that a synthetic experiment verifying the performance of our algorithm would be sufficient.

To address reviewers' concerns, we conducted two experiments, showing the performance of our main algorithm (Algorithm 1). In both experiments, we set $M=M^*+N \in \mathbb{R}^{n \times n}$, where $M^*$ is the rank-$k$ ground truth and $N$ is a higher-rank noise matrix. We set $n=800$ and $k=100$. We generate the noise matrix $N$ as an $n\times n$ random matrix with i.i.d. Gaussian entries of zero mean and variance $1/k$. We apply the sketching matrix $S \in \mathbb{R}^{m \times n}$ with $m=150$ (we choose the CountSketch matrix (Charikar et al., 2002)) when solving for the regression problems (see Lines 7 and 10 from our Algorithm 1). We iterate the alternating minimization steps (see Line 6) for $T = 20$ times. To show the performance of our algorithm, we compare the running time and error between our Algorithm 1 and the exact solver from (Li et al., 2016).  

The first experiment is the matrix completion problem. For each row of the weight matrix $W\in \mathbb{R}^{n\times n}_{\geq 0}$, we randomly select 400 entries to be equal to 1 and the remaining 400 entries to be 0. The second experiment is the general weighted low rank approximation where the weight matrix $W$ is constructed via ${\bf 1}_n{\bf 1}_n^\top+G$ for $G$ being a random matrix with standard Gaussian entries. 

Below, we present our experimental results of the matrix completion problem. We generate the ground truth $M^*=XY^\top$ by a pair $X, Y\in \mathbb{R}^{n\times k}$ with random i.i.d. entries scaled by $1/\sqrt{k}$, and the distributions are Laplace, Gaussian and uniform, respectively. Our time is measured in seconds.

|Distribution|Time for exact solve|Time for approx solve|Percentage speedup|Error for exact solve|Error for approx solve|
|---------------------|----------------------------|--------------------------------|--------------------------------|-----------|-----------|
|Laplace|234|$\mathbf{205}$|$\mathbf{12.39}$%|$1.54 \times 10^{-4}$|$3.56 \times 10^{-3}$|
|Gaussian|247|$\mathbf{216}$|$\mathbf{12.55}$%|$3.85 \times 10^{-4}$|$1.33 \times 10^{-3}$|
|Uniform|248|$\mathbf{207}$|$\mathbf{16.53}$%|$1.34 \times 10^{-5}$|$4.99 \times 10^{-4}$|


We present our second experimental results as follows (recall the weight matrix is all-1’s matrix plus a noise matrix with i.i.d. standard Gaussian entries):

|Distribution|Time for exact solve|Time for approx solve|Percentage speedup|Error for exact solve|Error for approx solve|
|---------------------|----------------------------|--------------------------------|--------------------------------|-----------|-----------|
|Laplace|249|$\mathbf{222}$|$\mathbf{10.84}$%|$2.11 \times 10^{-4}$|$4.71\times 10^{-4}$|
|Gaussian|223|$\mathbf{204}$|$\mathbf{8.52}$%|$6.29 \times 10^{-5}$|$2.15 \times 10^{-4}$|
|Uniform|221|$\mathbf{215}$|$\mathbf{2.71}$%|$3.00 \times 10^{-5}$|$7.13 \times 10^{-5}$|

We note that in these two settings, our algorithm achieves a speedup compared to the algorithm of (Li et al., 2016). For the matrix completion setting, our speedup is in the range of 12%-16%, while for the dense weights regime, our speedup is roughly 10%. In 20 iterations, our approximate solver obtains similar errors as the exact solver. We expect the speedup will be more significant once the discrepancy between $n$ and $k$ is larger, as sketching is known to work well in the regime where $n\gg k$, as evidenced by the following experiment on using sketching to solve the regression $\min_{x\in \mathbb{R}^k} \\|Ax-b\\|_2^2$ for $A\in \mathbb{R}^{n\times k}$ and $b\in\mathbb{R}^n$.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733007761896

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Thank you for all of your valuable and insightful comments! We kindly remind you that the discussion period will soon end.

comment:
Dear Reviewers, Program Chairs, and (Senior) Area Chairs,

Again, we would like to express our deepest gratitude for the time and effort that the reviewers, program chairs, and (senior) area chairs have dedicated to our manuscript, as well as for their insightful and valuable comments. We kindly remind you that the discussion period will soon end. We sincerely appreciate your recognition of the strengths of our work and have carefully addressed each of the weaknesses mentioned by the reviewers. Should there be any further concerns, we are eager to engage in additional discussions with the reviewers. Below, we summarize the main strengths and weaknesses of our work as assessed by the reviewers, along with our responses to address these weaknesses.

## Strengths

All four reviewers evaluated our work as having good soundness, presentation, and contribution (3: good), except that Reviewer j2kz rated our presentation as (2: fair). Specifically:

$\bullet$ Reviewer dS4q noted that our work addresses an important practical problem with applications in numerical linear algebra and machine learning, builds on the well-known alternating minimization approach, and achieves a speedup by a factor of $k$, resulting in a nearly optimal runtime.

$\bullet$ Reviewer MHu4 assessed that our work provides **significant theoretical contributions** with well-motivated and well-presented approaches, as well as a robust framework for high-precision regression solving.

$\bullet$ Reviewer j2kz and Reviewer 5iC9 commented that our work demonstrates solid theoretical results, with a framework and novel algorithm that could potentially generalize to other matrix optimization problems.

## Weaknesses and how we address them

Generally, several reviewers (Reviewer MHu4, Reviewer j2kz, and Reviewer 5iC9) raised concerns about the lack of experimental results in our paper. We addressed this primary criticism by including comprehensive numerical results demonstrating 12-16% speedups (see our global response). Specifically:

$\bullet$ Reviewer dS4q expressed concern that our assumption is stronger than those in prior works and that our key techniques were introduced in prior work (Gu et al. 2024). We clarified that our assumption is comparable to (Li et al. 2016), making the direct improvement and comparison in runtime with (Li et al. 2016) fair. Additionally, we outlined the differences between our work and (Gu et al. 2024), highlighting our novel contributions.

$\bullet$ Reviewer MHu4 questioned the connection between Problem 2.4 and the meaning of $\epsilon_0$. We provided a detailed response to these questions, and Reviewer MHu4 expressed satisfaction with our rebuttal.

$\bullet$ Reviewer j2kz raised concerns about the clarity of a specific portion of our technique overview. We clarified the algorithm presentation and addressed this unclear section.

$\bullet$ Reviewer 5iC9 mentioned that the generalization of the RIP condition required better explanation and raised questions about the dependence on problem parameters. We revised and clarified our claims regarding RIP conditions, acknowledged and corrected imprecise wording, provided detailed technical explanations about parameter dependencies and scaling behavior, and elaborated on the robustness advantages of the spectral norm over the Frobenius norm.


## Conclusion

We are confident that we have **addressed all the reviewers' comments** and eagerly anticipate their valuable responses. We remain fully committed to revising our manuscript further to ensure its suitability for ICLR 2025. Once again, we extend our gratitude to all reviewers, program chairs, and (senior) area chairs for considering our manuscript. 

Best regards, 

Authors. 

Yuzhou Gu, Zhao Song, Junze Yin, and Lichen Zhang. "Low rank matrix completion via robust alternating minimization in nearly linear time." ICLR’24.

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

</thread>


Metareview:
metareview:
This paper introduces a new framework for weighted low-rank approximation based on approximate alternating updates. With the proposed approach, the authors show that the algorithm’s runtime is reduced from $\|W\|_0 k^2$ to $\|W\|_0 k$ , where 
$k$ is the rank of the sought matrix. The paper provides a solid theoretical analysis, and the reviewers acknowledge its technical soundness, the significance of the work, and the potential for generalizing the results to other low-rank matrix estimation problems. During the rebuttal phase, the authors addressed the reviewers’ concerns and provided numerical results that corroborate their theoretical findings.  I believe that the paper offers valuable insights into an important problem and thus recommend its acceptance to ICLR.