We propose a consolidated cross-validation (CV) algorithm for training and tuning the support vector machines (SVM) on reproducing kernel Hilbert spaces. Our consolidated CV algorithm utilizes a recently proposed exact leave-one-out formula for the SVM and accelerates the SVM computation via a data reduction strategy. In addition, to compute the SVM with the bias term (intercept), which is not handled by the existing data reduction methods, we propose a novel two-stage consolidated CV algorithm. With numerical studies, we demonstrate that our algorithm is about an order of magnitude faster than the two mainstream SVM solvers, kernlab and LIBSVM, with almost the same accuracy.

Nonparametric regression on complex domains has been a challenging task as most existing methods, such as ensemble models based on binary decision trees, are not designed to account for intrinsic geometries and domain boundaries. This article proposes a Bayesian additive regression spanning trees (BAST) model for nonparametric regression on manifolds, with an emphasis on complex constrained domains or irregularly shaped spaces embedded in Euclidean spaces. Our model is built upon a random spanning tree manifold partition model as each weak learner, which is capable of capturing any irregularly shaped spatially contiguous partitions while respecting intrinsic geometries and domain boundary constraints. Equipped with a soft prediction scheme, BAST is demonstrated to significantly outperform other competing methods in simulation experiments and in an application to the chlorophyll data in Aral Sea, due to its strong local adaptivity to different levels of smoothness.

A novel approach to rank estimation, called geometric order learning (GOL), is proposed in this paper. First, we construct an embedding space, in which the direction and distance between objects represent order and metric relations between their ranks, by enforcing two geometric constraints: the order constraint compels objects to be sorted according to their ranks, while the metric constraint makes the distance between objects reflect their rank difference. Then, we perform the simple k nearest neighbor ( k -NN) search in the embedding space to estimate the rank of a test object. Moreover, to assess the quality of embedding spaces for rank estimation, we propose a metric called discriminative ratio for ranking (DRR). Extensive experiments on facial age estimation, historical color image (HCI) classification, and aesthetic score regression demonstrate that GOL constructs effective embedding spaces and thus yields excellent rank estimation performances.

In this paper, the authors present an algorithm for decentralized parallel stochastic gradient descent (PSGD). In contrast to centralized PSGD where worker nodes compute local gradients and the weights of a model are updated on a central node, decentralized PSGD seeks to perform training without a central node, in regimes where each node in a network can communicate with only a handful of adjacent nodes. While this network architecture has typically been viewed as a limitation, the authors present a theoretical analysis of their algorithm that suggests D-PSGD can achieve a linear speedup comparable to C-PSGD, but with significantly lower communication overhead. As a result, in certain low bandwidth or high latency network scenarios, D-PSGD can outperform C-PSGD. Overall, I believe the technical contributions of this paper could be very valuable.

This paper studies the use of oblivious dimensionality reduction for approximating a point set with a subspace. It gives a sketching and solve algorithm that reduces both the number of points, and the dimension that they are in, to numbers close to the dimensional of the goal subspace. It then empirically demonstrates that the proposed methods perform better than SVDs. While subspace approximation is important, I'm doubtful of the value of this work for several reasons. First, unlike previous results on oblivious subspace embeddings that introduced new tools, this paper appears to be almost entirely applying existing tools to a mathematically natural variant of the problem. It does not discuss the connections and applications related to this problem.

This paper presents an asymptotic analysis for nonparametric sequential prediction when there are multiple objectives. While the paper has some relevance to a certain subset of the machine learning community, I have some concerns about the paper's relevance to NIPS, and I also am unclear on some of the basic setup of the paper. I discuss these issues in the remainder of the review. Overall, I think the results in the paper are technically strong and, with the right motivation for \gamma -feasibility (see below) I would be weakly positive on the paper. Relevance: While I can see that the contents of the paper have some relevance to machine learning, I feel that this sort of paper would fit much better in a conference like COLT or ALT, given the technical level and given how much this paper can benefit from the additional space offered by those venues.

The authors propose a variational Bayes method for model selection in sigmoid belief networks. The method can eliminate nodes in the hidden layers of multilayer networks. The derivation of the criterion appears technically solid and a fair amount of experimental support for the good performance of the method is provided. I have to say I'm no expert in this area, and I hope other reviewers can comment on the level of novelty. You forgot to define b. - p. 5, ll.

The paper presents a novel method of exactly recovering a vector of coefficients in high-dimensional linear regression, with high probability as the dimension goes to infinity. The method assumes that the correct coefficients come from a finite discrete set of bounded rational values, but it does not - as is commonplace - assume that the coefficient vector is sparse. To achieve this, the authors extend a classical algorithm for lattice basis reduction. Crucially, this approach does not require the sample size to grow with the dimension, thus in certain cases the algorithm is able to recover the exact coefficient vector from just a single sample (with the dimension sufficiently large). A novel connection between high-dimensional linear regression and lattice basis reduction is the main strength of the paper.

The authors of this paper introduce a novel approach to GP classification, called GPD. The authors use a GP to produce the parameters of a Dirichlet distribution, and use a categorical likelihood for multi-class classification problems. After applying a log-normal approximation to the Dirichlet distribution, inference for GPD is the same as exact-GP inference (i.e. The authors show that GPD has competitive accuracy, is well calibrated, and offers a speedup over existing GP-classificaiton methods. Quality: The method introduced by this paper is a clever probabilistic formulation of Bayesian classification.

The paper considers the online sparse regression problem introduced by Kale (COLT'14), in which the online algorithm can only observe a subset of k features of each data point and has to sequentially predict a label based only on this limited observation (it can thus only use a sparse predictor for each prediction). Without further assumptions, this problem has been recently shown to be computationally hard by Foster et al (ALT'16). To circumvent this hardness, the authors assume a stochastic i.i.d. The results are not particularly exciting, but they do give a nice counter to the recent computational impossibility of Foster et al, in a setting where the data is i.i.d. and well-specified by a k-sparse vector. One of the main things I was missing in the paper is a proper discussion relating its setup, assumptions and results to the literature on sparse recovery / compressed sensing / sparse linear regression.