We address the problem of minimizing a convex function over the space of large matrices with low rank. While this optimization problem is hard in general, we propose an efficient greedy algorithm and derive its formal approximation guarantees. Each iteration of the algorithm involves (approximately) finding the left and right singular vectors corresponding to the largest singular value of a certain matrix, which can be calculated in linear time. This leads to an algorithm which can scale to large matrices arising in several applications such as matrix completion for collaborative filtering and robust low rank matrix approximation.
The algorithm we propose is also related to Hazan's algorithm @cite_15 for solving PSD problems, which in turns relies on Frank-Wolfe algorithm @cite_8 (see Clarkson @cite_19 ), as well as to the follow-up paper of @cite_14 , which applies Hazan's algorithm for optimizing with trace-norm constraints. There are several important changes though. First, we tackle the problem directly and do not enforce neither PSDness of the matrix nor a bounded trace-norm. Second, our algorithm is "fully corrective", that is, it extracts all the information from existing components before adding a new component. These differences between the approaches are analogous to the difference between Frank-Wolfe algorithm and fully corrective greedy selection, for minimizing over sparse vectors, as discussed in @cite_24 . Finally, while each iteration of both methods involves approximately finding leading eigenvectors, in @cite_15 the quality of approximation should improve as the algorithm progresses while our algorithm can always rely on the same constant approximation factor.
@cite_14 @cite_8 @cite_24 @cite_19 @cite_15
1574851760 2136885855 1994520254 2621075174 1775587472
Optimization problems with a nuclear norm regularization, such as e.g. low norm matrix factorizations, have seen many applications recently. We propose a new approximation algorithm building upon the recent sparse approximate SDP solver of (Hazan, 2008). The experimental efficiency of our method is demonstrated on large matrix completion problems such as the Netflix dataset. The algorithm comes with strong convergence guarantees, and can be interpreted as a first theoretically justified variant of Simon-Funk-type SVD heuristics. The method is free of tuning parameters, and very easy to parallelize. We study the problem of minimizing the expected loss of a linear predictor while constraining its sparsity, i.e., bounding the number of features used by the predictor. While the resulting optimization problem is generally NP-hard, several approximation algorithms are considered. We analyze the performance of these algorithms, focusing on the characterization of the trade-off between accuracy and sparsity of the learned predictor in different scenarios. The problem of maximizing a concave function f(x) in a simplex S can be solved approximately by a simple greedy algorithm. For given k, the algorithm can find a point x(k) on a k-dimensional face of S, such that f(x(k)) ≥ f(x*) - O(1 k). Here f(x*) is the maximum value of f in S. This algorithm and analysis were known before, and related to problems of statistics and machine learning, such as boosting, regression, and density mixture estimation. In other work, coming from computational geometry, the existence of e-coresets was shown for the minimum enclosing ball problem, by means of a simple greedy algorithm. Similar greedy algorithms, that are special cases of the Frank-Wolfe algorithm, were described for other enclosure problems. Here these results are tied together, stronger convergence results are reviewed, and several coreset bounds are generalized or strengthened. We propose an algorithm for approximately maximizing a concave function over the bounded semi-definite cone, which produces sparse solutions. Sparsity for SDP corresponds to low rank matrices, and is a important property for both computational as well as learning theoretic reasons. As an application, building on Aaronson's recent work, we derive a linear time algorithm for Quantum State Tomography.