The authors present a new method for robust principal component regression for non-Gaussian data. First, they show that principal component regression outperforms classical linear regression when the dimensionality and the sample size are allowed to increase by being insensitive to collinearity and exploiting low rank structure. They demonstrate their theoretical calculations by sweeping parameters and show that mean square error follows theory. Then the authors develop a new method for doing principal component regression by assuming the random vector and noise are elliptically distributed, a more general assumption than the standard Gaussian assumption. They demonstrate that this more general method outperforms traditional principal component regression on different elliptical distributions (multivariate-t, EC1, EC2), and show that it achieves similar performance for Gaussian distributions.

In this paper we focus on the principal component regression and its application to high dimension non-Gaussian data. The major contributions are two folds. First, in low dimensions and under the Gaussian model, by borrowing the strength from recent development in minimax optimal principal component estimation, we first time sharply characterize the potential advantage of classical principal component regression over least square estimation. Secondly, we propose and analyze a new robust sparse principal component regression on high dimensional elliptically distributed data. The elliptical distribution is a semiparametric generalization of the Gaussian, including many well known distributions such as multivariate Gaussian, rank-deficient Gaussian, t, Cauchy, and logistic. It allows the random vector to be heavy tailed and have tail dependence. These extra flexibilities make it very suitable for modeling finance and biomedical imaging data. Under the elliptical model, we prove that our method can estimate the regression coefficients in the optimal parametric rate and therefore is a good alternative to the Gaussian based methods. Experiments on synthetic and real world data are conducted to illustrate the empirical usefulness of the proposed method.

The control variate is a vector which hopefully has high correlation with the noisy gradient but for which the expectation is easier to compute. Standard convergence rates for stochastic gradient optimization depend on the variance of the gradient estimates, and thus a variance reduction technique should yield an acceleration of convergence. The authors give examples of control variates by using Taylor approximations of the gradient estimate for the optimization problem arising in regularized logistic regression as well as for MAP estimation for the latent Dirichlet Allocation (LDA) model. They compare constant step-size SGD with and without variance reduction for logistic regression on the covtype dataset, claiming that the variance reduction allows to use bigger step-sizes without having the problem of high variance and thus yields faster empirical convergence. For LDA, they compare the adaptive step-size version of the stochastic optimization method of [10] with and without variance reduction, showing a faster convergence on the held-out test log-likelihood on three large corpora. EVALUATION: Pros: - I like the general idea of variance reduction for SGD using control variates -- it could have a big impact given the popularity of SGD. - The motivation is compelling; the concrete examples of control variates are convincing; and the the general idea (Taylor approximation to define them) seems generalizable - The paper is fairly easy to read. Cons: - The experiments are somewhat weak: only one dataset for logistic regression; and a lack of standardized setup for LDA. - The related work is not covered. QUALITY: The theoretical motivation for the approach is compelling (reducing the variance of the gradient estimates reduces the constant in the convergence rate), but the execution in the empirical section is fairly weak.

Stochastic gradient optimization is a class of widely used algorithms for training machine learning models. To optimize an objective, it uses the noisy gradient computed from the random data samples instead of the true gradient computed from the entire dataset. However, when the variance of the noisy gradient is large, the algorithm might spend much time bouncing around, leading to slower convergence and worse performance. In this paper, we develop a general approach of using control variate for variance reduction in stochastic gradient. Data statistics such as low-order moments (pre-computed or estimated online) is used to form the control variate. We demonstrate how to construct the control variate for two practical problems using stochastic gradient optimization. One is convex--the MAP estimation for logistic regression, and the other is non-convex--stochastic variational inference for latent Dirichlet allocation. On both problems, our approach shows faster convergence and better performance than the classical approach.

These problems involve Vandermonde matrices which arise naturally in various statistical modeling settings, including classical polynomial fitting problems, additive models and approximations to recently developed randomized techniques for scalable kernel methods. We show that this structure can be exploited to further accelerate the solution of the regression problem, achieving running times that are faster than "input sparsity".

We propose a boosting method, DirectBoost, a greedy coordinate descent algorithm that builds an ensemble classifier of weak classifiers through directly minimizing empirical classification error over labeled training examples; once the training classification error is reduced to a local coordinatewise minimum, Direct-Boost runs a greedy coordinate ascent algorithm that continuously adds weak classifiers to maximize any targeted arbitrarily defined margins until reaching a local coordinatewise maximum of the margins in a certain sense.

Incorporating invariance information is important for many learning problems. To exploit invariances, most existing methods resort to approximations that either lead to expensive optimization problems such as semi-definite programming, or rely on separation oracles to retain tractability. Some methods further limit the space of functions and settle for non-convex models. In this paper, we propose a framework for learning in reproducing kernel Hilbert spaces (RKHS) using local invariances that explicitly characterize the behavior of the target function around data instances. These invariances are compactly encoded as linear functionals whose value are penalized by some loss function. Based on a representer theorem that we establish, our formulation can be efficiently optimized via a convex program. For the representer theorem to hold, the linear functionals are required to be bounded in the RKHS, and we show that this is true for a variety of commonly used RKHS and invariances. Experiments on learning with unlabeled data and transform invariances show that the proposed method yields better or similar results compared with the state of the art.

Summary: This paper presents a multitask learning method which entails jointly solving a collection of k-nearest neighbor (kNN) based prediction tasks, leveraging the relationships among the tasks. Whereas single task learning for kNN would only consider neighbors from the task which the test point belongs to (referred to as "homogeneous neighborhood" in the paper), the multitask variant proposed here considers neighbors from all tasks (referred to as "heterogeneous neighborhood" in the paper), suitably weighting the contribution of each neighbor by the pairwise similarity between the task the test point belongs o and the task the neighbor belongs to. The pairwise task similarities are learned from data. Experimental results show that the proposed method performs better than a kNN based multitask learning method anda global multitask learning method that learns a common feature represent of all tasks and learns predictors using that representation. Quality: The proposed model makes sense, especially the way a local learning problem (neighborhood based kNN) has been reformulated as a global learning problem (like SVM) and then cast as a standard global multitask learning problem. Clarity: The paper is well-written and the idea is easy to follow.

All the existing multi-task local learning methods are defined on homogeneous neighborhood which consists of all data points from only one task. In this paper, different from existing methods, we propose local learning methods for multitask classification and regression problems based on heterogeneous neighborhood which is defined on data points from all tasks. Specifically, we extend the k-nearest-neighbor classifier by formulating the decision function for each data point as a weighted voting among the neighbors from all tasks where the weights are task-specific. By defining a regularizer to enforce the task-specific weight matrix to approach a symmetric one, a regularized objective function is proposed and an efficient coordinate descent method is developed to solve it. For regression problems, we extend the kernel regression to multi-task setting in a similar way to the classification case. Experiments on some toy data and real-world datasets demonstrate the effectiveness of our proposed methods.

The paper presents a iterative algorithm to a robust principal component matrix factorization. The data is modeled as a sum of a low rank matrix approximation and a sparse noise matrix. Constraining the norms of the row and column factors of the former part of the sum allows to implement the nuclear norm minimization of the batch robust pca algorithm in an online stochastic gradient descent fashion. The approach taken by the authors resembles very much the approach taken by Marial et al 2009 (ICML) and 2010 (JMLR), only that the objective is slightly different (Robust PCA was not dealt with in the JMLR version). One difference between the JMLR and the ICML version is that a standard stochastic gradient version of the objective function did not perform as well as the proposed online dictionary learning approach (in which the statistics of the data are accumulated in the matrices A and B) in the ICML version, but in the JMLR version, a standard stochastic gradient implementation with appropriately chosen learning rate seemed to perform ok.