This equation, and others, probably overlap quite substantially with the approaches taken in e.g. "Optimization Algorithms on Matrix Manifolds" by Absil, P., Mahony, R., Sepulchre, R. ( this reference also addresses more general gradient flows, stepsize, retraction ("projection"), and convergence issues). S. Bonnabel, "Stochastic gradient descent on Riemannian manifolds" (arXiv) A. Edelman et al. "THE GEOMETRY OF ALGORITHMS WITH ORTHOGONALITY CONSTRAINTS" - The perspective of gradient descent on matrix manifolds is, to this reviewer, a major omission. The paper could greatly benefit from a discussion as to how this slice of the literature fits in to the picture, in terms of both practical algorithms and theory. I understand that space is a constraint. But if the authors decide to ultimately write a journal version of the submission, careful, considered inclusion of the above would make for a fantastic, authoritative paper bridging all of the major points of view on the topic.

We study PCA as a stochastic optimization problem and propose a novel stochastic approximation algorithm which we refer to as "Matrix Stochastic Gradient" (MSG), as well as a practical variant, Capped MSG. We study the method both theoretically and empirically.

The paper tackles the difficult problem of hierarchical parameter estimation in Markov random fields. The model consists of a Dirichlet process prior for parameters, and the computational contribution is an approximate MCMC method, since exact'' MCMC seems somewhat out of reach for this problem. The solution is not particularly elegant, but to be fair the problem is among the worst for MCMC samplers to tackle. It would be interesting to understand which of the main features of the solution contribute most for the results. To begin with, a trace of the approximate MCMC progression is absent.

We propose a fast algorithm for ridge regression when the number of features is much larger than the number of observations (p n).

SUMMARY This paper studies the problem of low rank matrix completion which exists in many real-world applications such as collaborative filtering for recommender systems. A previous work (ref [4]) proposed a scalable algorithm called Soft-Impute for solving a convex optimization problem involving the nuclear norm as a regularizer. Like previous work such as probabilistic matrix factorization (PMF), this paper gives the problem a probabilistic interpretation by relating the (non-probabilistic) optimization problem to a MAP estimation problem. Different (concave) penalty functions of the nuclear norm are proposed and then an EM algorithm is proposed to solve the MAP estimation problem. The algorithms proposed in this paper are more general than the Soft-Impute algorithm proposed in [4] in that the latter comes as a particular case.

This paper addresses the problem of unsupervised feature learning for text data. Our method is grounded in the principle of minimum description length and uses a dictionary-based compression scheme to extract a succinct feature set. Specifically, our method finds a set of word k-grams that minimizes the cost of reconstructing the text losslessly. We formulate document compression as a binary optimization task and show how to solve it approximately via a sequence of reweighted linear programs that are efficient to solve and parallelizable. As our method is unsupervised, features may be extracted once and subsequently used in a variety of tasks. We demonstrate the performance of these features over a range of scenarios including unsupervised exploratory analysis and supervised text categorization. Our compressed feature space is two orders of magnitude smaller than the full k-gram space and matches the text categorization accuracy achieved in the full feature space. This dimensionality reduction not only results in faster training times, but it can also help elucidate structure in unsupervised learning tasks and reduce the amount of training data necessary for supervised learning.

Knowing or approximating this ratio is needed in various problems of inference and integration often referred to as importance sampling in statistical inference. It is also closely related to the problem of covariate shift in transfer learning. Our approach is based on reformulating the problem of estimating the ratio as an inverse problem in terms of an integral operator corresponding to a kernel, known as the Fredholm problem of the first kind. This formulation, combined with the techniques of regularization leads to a principled framework for constructing algorithms and for analyzing them theoretically. The resulting family of algorithms (FIRE, for Fredholm Inverse Regularized Estimator) is flexible, simple and easy to implement.

Review of "Low-rank matrix reconstruction and clustering" This paper contributes a new algorithm for low-rank matrix reconstruction which is based on an application of Belief Propagation (BP) message-passing to a Bayesian model of the reconstruction problem. The algorithm, as described in the "Supplementary Material", incorporates two simplifying approximations, based on assuming a large number of rows and columns, respectively, in the input matrix. The algorithm is evaluated in a novel manner against Lloyd's K-means algorithm by formulating clustering as a matrix reconstruction problem. It is also compared against Variational Bayes Matrix Factorization (VBMF), which seems to be the only previous message-passing reconstruction algorithm. Cons There are some arguments against accepting the paper.

We study the problem of reconstructing low-rank matrices from their noisy observations. We formulate the problem in the Bayesian framework, which allows us to exploit structural properties of matrices in addition to low-rankedness, such as sparsity. We propose an efficient approximate message passing algorithm, derived from the belief propagation algorithm, to perform the Bayesian inference for matrix reconstruction. We have also successfully applied the proposed algorithm to a clustering problem, by reformulating it as a low-rank matrix reconstruction problem with an additional structural property. Numerical experiments show that the proposed algorithm outperforms Lloyd's K-means algorithm.

Inference in general Ising models is difficult, due to high treewidth making treebased algorithms intractable. Moreover, when interactionsarestrong,Gibbssampling may take exponential time to converge to the stationary distribution. We present an algorithm to project Ising model parameters onto aparametersetthat is guaranteed to be fast mixing, under several divergences. We find that Gibbs sampling using the projected parameters is more accurate than with the original parameters when interaction strengths are strong and when limited time is available for sampling.