text:
Cosma Rohilla and Schervish, Mark},
title = {Nonparametric Risk Bounds for Time-Series Forecasting},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We derive generalization error bounds for traditional time-series forecasting models. Our results hold for many standard forecasting tools including autoregressive models, moving average models, and, more generally, linear state-space models. These nonasymptotic bounds need only weak assumptions on the data-generating process, yet allow forecasters to select among competing models and to guarantee, with high probability, that their chosen model will perform well. We motivate our techniques with and apply them to standard economic and financial forecasting tools--a GARCH model for predicting equity volatility and a dynamic stochastic general equilibrium model (DSGE), the standard tool in macroeconomic forecasting. We demonstrate in particular how our techniques can aid forecasters and policy makers in choosing models which behave well under uncertainty and mis-specification.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1044–1083},
numpages = {40},
keywords = {generalization error, statespace models, model selection, linear time-invariant systems, VC dimension, prediction risk}
}

@article{10.5555/3122009.3122040,
author = {Gao, Ziyuan and Ries, Christoph and Simon, Hans U. and Zilles, Sandra},
title = {Preference-Based Teaching},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We introduce a new model of teaching named "preference-based teaching" and a corresponding complexity parameter--the preference-based teaching dimension (PBTD)--representing the worstcase number of examples needed to teach any concept in a given concept class. Although the PBTD coincides with the well-known recursive teaching dimension (RTD) on finite classes, it is radically different on infinite ones: the RTD becomes infinite already for trivial infinite classes (such as half-intervals) whereas the PBTD evaluates to reasonably small values for a wide collection of infinite classes including classes consisting of so-called closed sets w.r.t. a given closure operator, including various classes related to linear sets over N0 (whose RTD had been studied quite recently) and including the class of Euclidean half-spaces. On top of presenting these concrete results, we provide the reader with a theoretical framework (of a combinatorial flavor) which helps to derive bounds on the PBTD.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1012–1043},
numpages = {32},
keywords = {learning half-spaces, linear sets, recursive teaching dimension, teaching dimension, preference relation}
}

@article{10.5555/3122009.3122039,
author = {Hu, Yaohua and Li, Chong and Meng, Kaiwen and Qin, Jing and Yang, Xiaoqi},
title = {Group Sparse Optimization via lp,q Regularization},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {In this paper, we investigate a group sparse optimization problem via lp,q regularization in three aspects: theory, algorithm and application. In the theoretical aspect, by introducing a notion of group restricted eigenvalue condition, we establish an oracle property and a global recovery bound of order O(λ2/2-q) for any point in a level set of the lp,q regularization problem, and by virtue of modern variational analysis techniques, we also provide a local analysis of recovery bound of order O(λ2) for a path of local minima. In the algorithmic aspect, we apply the well-known proximal gradient method to solve the p,q regularization problems, either by analytically solving some specific lp,q regularization subproblems, or by using the Newton method to solve general lp,q regularization subproblems. In particular, we establish a local linear convergence rate of the proximal gradient method for solving the l1,q regularization problem under some mild conditions and by first proving a second-order growth condition. As a consequence, the local linear convergence rate of proximal gradient method for solving the usual lq regularization problem (0 < q < 1) is obtained. Finally in the aspect of application, we present some numerical results on both the simulated data and the real data in gene transcriptional regulation.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {960–1011},
numpages = {52},
keywords = {restricted eigenvalue condition, group sparse optimization, gene regulation network, lower-order regularization, iterative thresholding algorithm, proximal gradient method, nonconvex optimization}
}

@article{10.5555/3122009.3122038,
author = {Bertsimas, Dimitris and Copenhaver, Martin S. and Mazumder, Rahul},
title = {Certifiably Optimal Low Rank Factor Analysis},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Factor Analysis (FA) is a technique of fundamental importance that is widely used in classical and modern multivariate statistics, psychometrics, and econometrics. In this paper, we revisit the classical rank-constrained FA problem which seeks to approximate an observed covariance matrix (Σ) by the sum of a Positive Semidefinite (PSD) low-rank component (θ) and a diagonal matrix (Φ) (with nonnegative entries) subject to Σ - Φ being PSD. We propose a flexible family of rank-constrained, nonlinear Semidefinite Optimization based formulations for this task. We introduce a reformulation of the problem as a smooth optimization problem with convex, compact constraints and propose a unified algorithmic framework, utilizing state of the art techniques in nonlinear optimization to obtain high-quality feasible solutions for our proposed formulation. At the same time, by using a variety of techniques from discrete and global optimization, we show that these solutions are certifiably optimal in many cases, even for problems with thousands of variables. Our techniques are general and make no assumption on the underlying problem data. The estimator proposed herein aids statistical interpretability and provides computational scalability and significantly improved accuracy when compared to current, publicly available popular methods for rank-constrained FA. We demonstrate the effectiveness of our proposal on an array of synthetic and real-life datasets. To our knowledge, this is the first paper that demonstrates how a previously intractable rank-constrained optimization problem can be solved to provable optimality by coupling developments in convex analysis and in global and discrete optimization.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {907–959},
numpages = {53},
keywords = {global optimization, nonlinear optimization, discrete optimization, semidefinite optimization, rank minimization, first order methods, factor analysis}
}

@article{10.5555/3122009.3122037,
author = {Bouchard-C\^{o}t\'{e}, Alexandre and Doucet, Arnaud and Roth, Andrew},
title = {Particle Gibbs Split-Merge Sampling for Bayesian Inference in Mixture Models},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {This paper presents an original Markov chain Monte Carlo method to sample from the posterior distribution of conjugate mixture models. This algorithm relies on a flexible split-merge procedure built using the particle Gibbs sampler introduced in Andrieu et al. (2009, 2010). The resulting so-called Particle Gibbs Split-Merge sampler does not require the computation of a complex acceptance ratio and can be implemented using existing sequential Monte Carlo libraries. We investigate its performance experimentally on synthetic problems as well as on geolocation data. Our results show that for a given computational budget, the Particle Gibbs Split-Merge sampler empirically outperforms existing split merge methods. The code and instructions allowing to reproduce the experiments is available at https://github.com/aroth85/pgsm.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {868–906},
numpages = {39},
keywords = {particle Gibbs sampler, Gibbs sampler, dirichlet process mixture models, sequential Monte Carlo}
}

@article{10.5555/3122009.3122036,
author = {Caron, Fran\c{c}ois and Neiswanger, Willie and Wood, Frank and Doucet, Arnaud and Davy, Manuel},
title = {Generalized P\'{o}Ya Urn for Time-Varying Pitman-Yor Processes},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {This article introduces a class of first-order stationary time-varying Pitman-Yor processes. Subsuming our construction of time-varying Dirichlet processes presented in (Caron et al., 2007), these models can be used for time-dynamic density estimation and clustering. Our intuitive and simple construction relies on a generalized P\'{o}lya urn scheme. Significantly, this construction yields marginal distributions at each time point that can be explicitly characterized and easily controlled. Inference is performed using Markov chain Monte Carlo and sequential Monte Carlo methods. We demonstrate our models and algorithms on epidemiological and video tracking data.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {836–867},
numpages = {32},
keywords = {Bayesian nonparametrics, clustering, dynamic models, mixture models, particle Markov chain Monte Carlo, sequential Monte Carlo}
}

@article{10.5555/3122009.3122035,
author = {Egorov, Maxim and Sunberg, Zachary N. and Balaban, Edward and Wheeler, Tim A. and Gupta, Jayesh K. and Kochenderfer, Mykel J.},
title = {POMDPs.Jl: A Framework for Sequential Decision Making under Uncertainty},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {POMDPs.jl is an open-source framework for solving Markov decision processes (MDPs) and partially observable MDPs (POMDPs). POMDPs.jl allows users to specify sequential decision making problems with minimal effort without sacrificing the expressive nature of POMDPs, making this framework viable for both educational and research purposes. It is written in the Julia language to allow flexible prototyping and large-scale computation that leverages the high-performance nature of the language. The associated JuliaPOMDP community also provides a number of state-of-the-art MDP and POMDP solvers and a rich library of support tools to help with implementing new solvers and evaluating the solution results. The most recent version of POMDPs.jl, the related packages, and documentation can be found at https://github.com/JuliaPOMDP/POMDPs.jl.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {831–835},
numpages = {5},
keywords = {sequential decision making, Julia, POMDP, open-source, MDP}
}

@article{10.5555/3122009.3122034,
author = {Kotthoff, Lars and Thornton, Chris and Hoos, Holger H. and Hutter, Frank and Leyton-Brown, Kevin},
title = {Auto-WEKA 2.0: Automatic Model Selection and Hyperparameter Optimization in WEKA},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {WEKA is a widely used, open-source machine learning platform. Due to its intuitive interface, it is particularly popular with novice users. However, such users often find it hard to identify the best approach for their particular dataset among the many available. We describe the new version of Auto-WEKA, a system designed to help such users by automatically searching through the joint space of WEKA's learning algorithms and their respective hyperparameter settings to maximize performance, using a state-of-the-art Bayesian optimization method. Our new package is tightly integrated with WEKA, making it just as accessible to end users as any other learning algorithm.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {826–830},
numpages = {5},
keywords = {hyperparameter optimization, feature selection, model selection}
}

@article{10.5555/3122009.3122033,
author = {Nevo, Daniel and Ritov, Ya'acov},
title = {Identifying a Minimal Class of Models for High-Dimensional Data},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Model selection consistency in the high-dimensional regression setting can be achieved only if strong assumptions are fulfilled. We therefore suggest to pursue a different goal, which we call a minimal class of models. The minimal class of models includes models that are similar in their prediction accuracy but not necessarily in their elements. We suggest a random search algorithm to reveal candidate models. The algorithm implements simulated annealing while using a score for each predictor that we suggest to derive using a combination of the lasso and the elastic net. The utility of using a minimal class of models is demonstrated in the analysis of two data sets.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {797–825},
numpages = {29},
keywords = {model selection, elastic net, high-dimensional data, simulated annealing, lasso}
}

@article{10.5555/3122009.3122032,
author = {Raff, Edward},
title = {JSAT: Java Statistical Analysis Tool, a Library for Machine Learning},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Java Statistical Analysis Tool (JSAT) is a Machine Learning library written in pure Java. It works to fill a void in the Java ecosystem for a general purpose library that is relatively high performance and flexible, which is not adequately fulfilled by Weka (Hall et al., 2009) and Java-ML (Abeel et al., 2009). Almost all of the algorithms are independently implemented using an Object-Oriented framework. JSAT is made available under the GNU GPL license here: https://github.com/EdwardRaff/JSAT.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {792–796},
numpages = {5},
keywords = {java library, machine learning software, open source, java, machine learning}
}

@article{10.5555/3122009.3122031,
author = {Anandkumar, Animashree and Ge, Rong and Janzamin, Majid},
title = {Analyzing Tensor Power Method Dynamics in Overcomplete Regime},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We present a novel analysis of the dynamics of tensor power iterations in the overcomplete regime where the tensor CP rank is larger than the input dimension. Finding the CP decomposition of an overcomplete tensor is NP-hard in general. We consider the case where the tensor components are randomly drawn, and show that the simple power iteration recovers the components with bounded error under mild initialization conditions. We apply our analysis to unsupervised learning of latent variable models, such as multiview mixture models and spherical Gaussian mixtures. Given the third order moment tensor, we learn the parameters using tensor power iterations. We prove it can correctly learn the model parameters when the number of hidden components k is much larger than the data dimension d, up to k = o(d1.5). We initialize the power iterations with data samples and prove its success under mild conditions on the signal-to-noise ratio of the samples. Our analysis significantly expands the class of latent variable models where spectral methods are applicable. Our analysis also deals with noise in the input tensor leading to sample complexity result in the application to learning latent variable models.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {752–791},
numpages = {40},
keywords = {tensor power iteration, unsupervised learning, latent variable models, tensor decomposition, overcomplete representation}
}

@article{10.5555/3122009.3122030,
author = {Bach, Francis},
title = {On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We show that kernel-based quadrature rules for computing integrals can be seen as a special case of random feature expansions for positive definite kernels, for a particular decomposition that always exists for such kernels. We provide a theoretical analysis of the number of required samples for a given approximation error, leading to both upper and lower bounds that are based solely on the eigenvalues of the associated integral operator and match up to logarithmic terms. In particular, we show that the upper bound may be obtained from independent and identically distributed samples from a specific non-uniform distribution, while the lower bound if valid for any set of points. Applying our results to kernel-based quadrature, while our results are fairly general, we recover known upper and lower bounds for the special cases of Sobolev spaces. Moreover, our results extend to the more general problem of full function approximations (beyond simply computing an integral), with results in L2- and L∞-norm that match known results for special cases. Applying our results to random features, we show an improvement of the number of random features needed to preserve the generalization guarantees for learning with Lipshitz-continuous losses.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {714–751},
numpages = {38},
keywords = {quadrature, integral operators, positive-definite kernels}
}

@article{10.5555/3122009.3122029,
author = {Si, Si and Hsieh, Cho-Jui and Dhillon, Inderjit S.},
title = {Memory Efficient Kernel Approximation},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Scaling kernel machines to massive data sets is a major challenge due to storage and computation issues in handling large kernel matrices, that are usually dense. Recently, many papers have suggested tackling this problem by using a low-rank approximation of the kernel matrix. In this paper, we first make the observation that the structure of shift-invariant kernels changes from low-rank to block-diagonal (without any low-rank structure) when varying the scale parameter. Based on this observation, we propose a new kernel approximation framework - Memory Efficient Kernel Approximation (MEKA), which considers both low-rank and clustering structure of the kernel matrix. We show that the resulting algorithm outperforms state-of-the-art low-rank kernel approximation methods in terms of speed, approximation error, and memory usage. As an example, on the covtype dataset with half a million samples, MEKA takes around 70 seconds and uses less than 80 MB memory on a single machine to achieve 10% relative approximation error, while standard Nystr\"{o}m approximation is about 6 times slower and uses more than 400MB memory to achieve similar approximation. We also present extensive experiments on applying MEKA to speed up kernel ridge regression.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {682–713},
numpages = {32},
keywords = {kernel methods, kernel approximation, Nystr\"{o}m method}
}

@article{10.5555/3122009.3122028,
author = {Bach, Francis},
title = {Breaking the Curse of Dimensionality with Convex Neural Networks},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We consider neural networks with a single hidden layer and non-decreasing positively homogeneous activation functions like the rectified linear units. By letting the number of hidden units grow unbounded and using classical non-Euclidean regularization tools on the output weights, they lead to a convex optimization problem and we provide a detailed theoretical analysis of their generalization performance, with a study of both the approximation and the estimation errors. We show in particular that they are adaptive to unknown underlying linear structures, such as the dependence on the projection of the input variables onto a low-dimensional subspace. Moreover, when using sparsity-inducing norms on the input weights, we show that high-dimensional non-linear variable selection may be achieved, without any strong assumption regarding the data and with a total number of variables potentially exponential in the number of observations. However, solving this convex optimization problem in infinite dimensions is only possible if the nonconvex subproblem of addition of a new unit can be solved efficiently. We provide a simple geometric interpretation for our choice of activation functions and describe simple conditions for convex relaxations of the finite-dimensional non-convex subproblem to achieve the same generalization error bounds, even when constant-factor approximations cannot be found. We were not able to find strong enough convex relaxations to obtain provably polynomialtime algorithms and leave open the existence or non-existence of such tractable algorithms with non-exponential sample complexities.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {629–681},
numpages = {53},
keywords = {non-parametric estimation, convex relaxation, neural networks, convex optimization}
}

@article{10.5555/3122009.3122027,
author = {Ollivier, Yann and Arnold, Ludovic and Auger, Anne and Hansen, Nikolaus},
title = {Information-Geometric Optimization Algorithms: A Unifying Picture via Invariance Principles},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We present a canonical way to turn any smooth parametric family of probability distributions on an arbitrary search space X into a continuous-time black-box optimization method on X, the information-geometric optimization (IGO) method. Invariance as a major design principle keeps the number of arbitrary choices to a minimum. The resulting IGO flow is the flow of an ordinary differential equation conducting the natural gradient ascent of an adaptive, time-dependent transformation of the objective function. It makes no particular assumptions on the objective function to be optimized.The IGO method produces explicit IGO algorithms through time discretization. It naturally recovers versions of known algorithms and offers a systematic way to derive new ones. In continuous search spaces, IGO algorithms take a form related to natural evolution strategies (NES). The cross-entropy method is recovered in a particular case with a large time step, and can be extended into a smoothed, parametrization-independent maximum likelihood update (IGO-ML). When applied to the family of Gaussian distributions on Rd, the IGO framework recovers a version of the well-known CMA-ES algorithm and of xNES. For the family of Bernoulli distributions on {0, 1}d, we recover the seminal PBIL algorithm and cGA. For the distributions of restricted Boltzmann machines, we naturally obtain a novel algorithm for discrete optimization on {0, 1}d. All these algorithms are natural instances of, and unified under, the single information-geometric optimization framework.The IGO method achieves, thanks to its intrinsic formulation, maximal invariance properties: invariance under reparametrization of the search space X, under a change of parameters of the probability distribution, and under increasing transformation of the function to be optimized. The latter is achieved through an adaptive, quantile-based formulation of the objective.Theoretical considerations strongly suggest that IGO algorithms are essentially characterized by a minimal change of the distribution over time. Therefore they have minimal loss in diversity through the course of optimization, provided the initial diversity is high. First experiments using restricted Boltzmann machines confirm this insight. As a simple consequence, IGO seems to provide, from information theory, an elegant way to simultaneously explore several valleys of a fitness landscape in a single run.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {564–628},
numpages = {65},
keywords = {randomized optimization, information-geometric optimization, natural gradient, stochastic optimization, invariance, evolution strategy, black-box optimization}
}

@article{10.5555/3122009.3122026,
author = {Lema\^{\i}tre, Guillaume and Nogueira, Fernando and Aridas, Christos K.},
title = {Imbalanced-Learn: A Python Toolbox to Tackle the Curse of Imbalanced Datasets in Machine Learning},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {imbalanced-learn is an open-source python toolbox aiming at providing a wide range of methods to cope with the problem of imbalanced dataset frequently encountered in machine learning and pattern recognition. The implemented state-of-the-art methods can be categorized into 4 groups: (i) under-sampling, (ii) over-sampling, (iii) combination of over-and under-sampling, and (iv) ensemble learning methods. The proposed toolbox depends only on numpy, scipy, and scikit-learn and is distributed under MIT license. Furthermore, it is fully compatible with scikit-learn and is part of the scikit-learn-contrib supported project. Documentation, unit tests as well as integration tests are provided to ease usage and contribution. Source code, binaries, and documentation can be downloaded from https://github.com/scikit-learn-contrib/imbalanced-learn.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {559–563},
numpages = {5},
keywords = {python, imbalanced dataset, under-sampling, machine learning, over-sampling, ensemble learning}
}

@article{10.5555/3122009.3122025,
author = {Ito, Naoki and Takeda, Akiko and Toh, Kim-Chuan},
title = {A Unified Formulation and Fast Accelerated Proximal Gradient Method for Classification},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Binary classification is the problem of predicting the class a given sample belongs to. To achieve a good prediction performance, it is important to find a suitable model for a given dataset. However, it is often time consuming and impractical for practitioners to try various classification models because each model employs a different formulation and algorithm. The difficulty can be mitigated if we have a unified formulation and an efficient universal algorithmic framework for various classification models to expedite the comparison of performance of different models for a given dataset. In this paper, we present a unified formulation of various classification models (including C-SVM, l2-SVM, ν-SVM, MM-FDA, MM-MPM, logistic regression, distance weighted discrimination) and develop a general optimization algorithm based on an accelerated proximal gradient (APG) method for the formulation. We design various techniques such as backtracking line search and adaptive restarting strategy in order to speed up the practical convergence of our method. We also give a theoretical convergence guarantee for the proposed fast APG algorithm. Numerical experiments show that our algorithm is stable and highly competitive to specialized algorithms designed for specific models (e.g., sequential minimal optimization (SMO) for SVM).},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {510–558},
numpages = {49},
keywords = {minimum norm problem, binary classification, vector projection computation, support vector machine, restarted accelerated proximal gradient method}
}

@article{10.5555/3122009.3122024,
author = {Wainer, Jacques and Cawley, Gavin},
title = {Empirical Evaluation of Resampling Procedures for Optimising SVM Hyperparameters},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Tuning the regularisation and kernel hyperparameters is a vital step in optimising the generalisation performance of kernel methods, such as the support vector machine (SVM). This is most often performed by minimising a resampling/cross-validation based model selection criterion, however there seems little practical guidance on the most suitable form of resampling. This paper presents the results of an extensive empirical evaluation of resampling procedures for SVM hyperparameter selection, designed to address this gap in the machine learning literature. We tested 15 different resampling procedures on 121 binary classification data sets in order to select the best SVM hyperparameters. We used three very different statistical procedures to analyse the results: the standard multi-classifier/multidata set procedure proposed by Dem\v{s}ar, the confidence intervals on the excess loss of each procedure in relation to 5-fold cross validation, and the Bayes factor analysis proposed by Barber. We conclude that a 2-fold procedure is appropriate to select the hyperparameters of an SVM for data sets for 1000 or more datapoints, while a 3-fold procedure is appropriate for smaller data sets.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {475–509},
numpages = {35},
keywords = {cross-validation, bootstrap, resampling, SVM, k-fold, hyperparameters}
}

@article{10.5555/3122009.3122023,
author = {Kucukelbir, Alp and Tran, Dustin and Ranganath, Rajesh and Gelman, Andrew and Blei, David M.},
title = {Automatic Differentiation Variational Inference},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Probabilistic modeling is iterative. A scientist posits a simple model, fits it to her data, refines it according to her analysis, and repeats. However, fitting complex models to large data is a bottleneck in this process. Deriving algorithms for new models can be both mathematically and computationally challenging, which makes it difficult to efficiently cycle through the steps. To this end, we develop automatic differentiation variational inference (ADVI). Using our method, the scientist only provides a probabilistic model and a dataset, nothing else. ADVI automatically derives an efficient variational inference algorithm, freeing the scientist to refine and explore many models. ADVI supports a broad class of models--no conjugacy assumptions are required. We study ADVI across ten modern probabilistic models and apply it to a dataset with millions of observations. We deploy ADVI as part of Stan, a probabilistic programming system.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {430–474},
numpages = {45},
keywords = {approximate inference, probabilistic programming, Bayesian inference}
}

@article{10.5555/3122009.3122022,
author = {Jaeger, Herbert},
title = {Using Conceptors to Manage Neural Long-Term Memories for Temporal Patterns},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Biological brains can learn, recognize, organize, and re-generate large repertoires of temporal patterns. Here I propose a mechanism of neurodynamical pattern learning and representation, called conceptors, which offers an integrated account of a number of such phenomena and functionalities. It becomes possible to store a large number of temporal patterns in a single recurrent neural network. In the recall process, stored patterns can be morphed and "focussed". Parametric families of patterns can be learnt from a very small number of examples. Stored temporal patterns can be content-addressed in ways that are analog to recalling static patterns in Hopfield networks.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {387–429},
numpages = {43},
keywords = {recurrent neural network, neural long-term memory, temporal pattern learning, neural dynamics}
}

@article{10.5555/3122009.3122021,
author = {Kim, Daeil and Swanson, Benjamin F. and Hughes, Michael C. and Sudderth, Erik B.},
title = {Refinery: An Open Source Topic Modeling Web Platform},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We introduce Refinery, an open source platform for exploring large text document collections with topic models. Refinery is a standalone web application driven by a graphical interface, so it is usable by those without machine learning or programming expertise. Users can interactively organize articles by topic and also refine this organization with phrase-level analysis. Under the hood, we train Bayesian nonparametric topic models that can adapt model complexity to the provided data with scalable learning algorithms. The project website http://daeilkim.github.io/refinery/ contains Python code and further documentation.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {382–386},
numpages = {5},
keywords = {topic models, software, visualization}
}

@article{10.5555/3122009.3122020,
author = {Dimitrakakis, Christos and Nelson, Blaine and Zhang, Zuhe and Mitrokotsa, Aikaterini and Rubinstein, Benjamin I. P.},
title = {Differential Privacy for Bayesian Inference through Posterior Sampling},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Differential privacy formalises privacy-preserving mechanisms that provide access to a database. Can Bayesian inference be used directly to provide private access to data? The answer is yes: under certain conditions on the prior, sampling from the posterior distribution can lead to a desired level of privacy and utility. For a uniform treatment, we define differential privacy over arbitrary data set metrics, outcome spaces and distribution families. This allows us to also deal with non-i.i.d or non-tabular data sets. We then prove bounds on the sensitivity of the posterior to the data, which delivers a measure of robustness. We also show how to use posterior sampling to provide differentially private responses to queries, within a decision-theoretic framework. Finally, we provide bounds on the utility of answers to queries and on the ability of an adversary to distinguish between data sets. The latter are complemented by a novel use of Le Cam's method to obtain lower bounds on distinguishability. Our results hold for arbitrary metrics, including those for the common definition of differential privacy. For specific choices of the metric, we give a number of examples satisfying our assumptions.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {343–381},
numpages = {39},
keywords = {robustness, differential privacy, adversarial learning, Bayesian inference}
}

@article{10.5555/3122009.3122019,
author = {Atchad\'{e}, Yves F. and Fort, Gersende and Moulines, Eric},
title = {On Perturbed Proximal Gradient Algorithms},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We study a version of the proximal gradient algorithm for which the gradient is intractable and is approximated by Monte Carlo methods (and in particular Markov Chain Monte Carlo). We derive conditions on the step size and the Monte Carlo batch size under which convergence is guaranteed: both increasing batch size and constant batch size are considered. We also derive non-asymptotic bounds for an averaged version. Our results cover both the cases of biased and unbiased Monte Carlo approximation. To support our findings, we discuss the inference of a sparse generalized linear model with random effect and the problem of learning the edge structure and parameters of sparse undirected graphical models.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {310–342},
numpages = {33},
keywords = {Monte Carlo approximations, stochastic optimization, proximal gradient methods, perturbed majorization-minimization algorithms}
}

@article{10.5555/3122009.3122018,
author = {Arias-Castro, Ery and Lerman, Gilad and Zhang, Teng},
title = {Spectral Clustering Based on Local PCA},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We propose a spectral clustering method based on local principal components analysis (PCA). After performing local PCA in selected neighborhoods, the algorithm builds a nearest neighbor graph weighted according to a discrepancy between the principal subspaces in the neighborhoods, and then applies spectral clustering. As opposed to standard spectral methods based solely on pairwise distances between points, our algorithm is able to resolve intersections. We establish theoretical guarantees for simpler variants within a prototypical mathematical framework for multi-manifold clustering, and evaluate our algorithm on various simulated data sets.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {253–309},
numpages = {57},
keywords = {spectral clustering, intersecting clusters, local principal component analysis, multi-manifold clustering}
}

@article{10.5555/3122009.3122017,
author = {Adams, Henry and Emerson, Tegan and Kirby, Michael and Neville, Rachel and Peterson, Chris and Shipman, Patrick and Chepushtanova, Sofya and Hanson, Eric and Motta, Francis and Ziegelmeier, Lori},
title = {Persistence Images: A Stable Vector Representation of Persistent Homology},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Many data sets can be viewed as a noisy sampling of an underlying space, and tools from topological data analysis can characterize this structure for the purpose of knowledge discovery. One such tool is persistent homology, which provides a multiscale description of the homological features within a data set. A useful representation of this homological information is a persistence diagram (PD). Efforts have been made to map PDs into spaces with additional structure valuable to machine learning tasks. We convert a PD to a finite-dimensional vector representation which we call a persistence image (PI), and prove the stability of this transformation with respect to small perturbations in the inputs. The discriminatory power of PIs is compared against existing methods, showing significant performance gains. We explore the use of PIs with vector-based machine learning tools, such as linear sparse support vector machines, which identify features containing discriminating topological information. Finally, high accuracy inference of parameter values from the dynamic output of a discrete dynamical system (the linked twist map) and a partial differential equation (the anisotropic Kuramoto-Sivashinsky equation) provide a novel application of the discriminatory power of PIs.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {218–252},
numpages = {35},
keywords = {persistent homology, topological data analysis, persistence images, machine learning, dynamical systems}
}

@article{10.5555/3122009.3122016,
author = {Charles, Adam S. and Yin, Dong and Rozell, Christopher J.},
title = {Distributed Sequence Memory of Multidimensional Inputs in Recurrent Networks},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Recurrent neural networks (RNNs) have drawn interest from machine learning researchers because of their effectiveness at preserving past inputs for time-varying data processing tasks. To understand the success and limitations of RNNs, it is critical that we advance our analysis of their fundamental memory properties. We focus on echo state networks (ESNs), which are RNNs with simple memoryless nodes and random connectivity. In most existing analyses, the short-term memory (STM) capacity results conclude that the ESN network size must scale linearly with the input size for unstructured inputs. The main contribution of this paper is to provide general results characterizing the STM capacity for linear ESNs with multidimensional input streams when the inputs have common low-dimensional structure: sparsity in a basis or significant statistical dependence between inputs. In both cases, we show that the number of nodes in the network must scale linearly with the information rate and poly-logarithmically with the input dimension. The analysis relies on advanced applications of random matrix theory and results in explicit non-asymptotic bounds on the recovery error. Taken together, this analysis provides a significant step forward in our understanding of the STM properties in RNNs.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {181–217},
numpages = {37},
keywords = {short-term memory, recurrent neural networks, restricted isometry property, low-rank recovery, sparse signal recovery}
}

@article{10.5555/3122009.3122015,
author = {Raymond, Jack and Ricci-Tersenghi, Federico},
title = {Improving Variational Methods via Pairwise Linear Response Identities},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Inference methods are often formulated as variational approximations: these approximations allow easy evaluation of statistics by marginalization or linear response, but these estimates can be inconsistent. We show that by introducing constraints on covariance, one can ensure consistency of linear response with the variational parameters, and in so doing inference of marginal probability distributions is improved. For the Bethe approximation and its generalizations, improvements are achieved with simple choices of the constraints. The approximations are presented as variational frameworks; iterative procedures related to message passing are provided for finding the minima.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {145–180},
numpages = {36},
keywords = {message passing algorithms, graphical models, statistical physics, variational inference, linear response}
}

@article{10.5555/3122009.3122014,
author = {Lee, Jason D. and Liu, Qiang and Sun, Yuekai and Taylor, Jonathan E.},
title = {Communication-Efficient Sparse Regression},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We devise a communication-efficient approach to distributed sparse regression in the high-dimensional setting. The key idea is to average "debiased" or "desparsified" lasso estimators. We show the approach converges at the same rate as the lasso as long as the dataset is not split across too many machines, and consistently estimates the support under weaker conditions than the lasso. On the computational side, we propose a new parallel and computationally-efficient algorithm to compute the approximate inverse covariance required in the debiasing approach, when the dataset is split across samples. We further extend the approach to generalized linear models.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {115–144},
numpages = {30},
keywords = {lasso, high-dimensional statistics, distributed sparse regression, averaging, debiasing}
}

@article{10.5555/3122009.3122013,
author = {Hallac, David and Wong, Christopher and Diamond, Steven and Sharang, Abhijit and Sosic, Rok and Boyd, Stephen and Leskovec, Jure},
title = {SnapVX: A Network-Based Convex Optimization Solver},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {SnapVX is a high-performance solver for convex optimization problems defined on networks. For problems of this form, SnapVX provides a fast and scalable solution with guaranteed global convergence. It combines the capabilities of two open source software packages: Snap.py and CVXPY. Snap.py is a large scale graph processing library, and CVXPY provides a general modeling framework for small-scale subproblems. SnapVX offers a customizable yet easy-to-use Python interface with "out-of-the-box" functionality. Based on the Alternating Direction Method of Multipliers (ADMM), it is able to efficiently store, analyze, parallelize, and solve large optimization problems from a variety of different applications. Documentation, examples, and more can be found on the SnapVX website at http://snap.stanford.edu/snapvx.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {110–114},
numpages = {5},
keywords = {convex optimization, data mining, graphs, network analytics, ADMM}
}

@article{10.5555/3122009.3122012,
author = {Awasthi, Pranjal and Balcan, Maria Florina and Voevodski, Konstantin},
title = {Local Algorithms for Interactive Clustering},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We study the design of interactive clustering algorithms. The user supervision that we consider is in the form of cluster split/merge requests; such feedback is easy for users to provide because it only requires a high-level understanding of the clusters. Our algorithms start with any initial clustering and only make local changes in each step; both are desirable properties in many applications. Local changes are desirable because in practice edits of other parts of the clustering are considered churn - changes that are perceived as quality-neutral or quality-negative. We show that in this framework we can still design provably correct algorithms given that our data satisfies natural separability properties. We also show that our framework works well in practice.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {75–109},
numpages = {35}
}

@article{10.5555/3122009.3122011,
author = {Du, Nan and Liang, Yingyu and Balcan, Maria-Florina and Gomez-Rodriguez, Manuel and Zha, Hongyuan and Song, Le},
title = {Scalable Inuence Maximization for Multiple Products in Continuous-Time Diffusion Networks},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {A typical viral marketing model identifies influential users in a social network to maximize a single product adoption assuming unlimited user attention, campaign budgets, and time. In reality, multiple products need campaigns, users have limited attention, convincing users incurs costs, and advertisers have limited budgets and expect the adoptions to be maximized soon. Facing these user, monetary, and timing constraints, we formulate the problem as a submodular maximization task in a continuous-time diffusion model under the intersection of one matroid and multiple knapsack constraints. We propose a randomized algorithm estimating the user inuence in a network (|V| nodes, |E| edges) to an accuracy of ε with n = O(1/ε2) randomizations and O (n|E|+n|V|) computations. By exploiting the influence estimation algorithm as a subroutine, we develop an adaptive threshold greedy algorithm achieving an approximation factor ka/(2 + 2k) of the optimal when ka out of the k knapsack constraints are active. Extensive experiments on networks of millions of nodes demonstrate that the proposed algorithms achieve the state-of-the-art in terms of effectiveness and scalability.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {30–74},
numpages = {45},
keywords = {knapsack, influence maximization, model, matroid, influence estimation, continuous-time diffusion}
}

@article{10.5555/3122009.3122010,
author = {Ishiguro, Katsuhiko and Sato, Issei and Ueda, Naonori},
title = {Averaged Collapsed Variational Bayes Inference},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {This paper presents the Averaged CVB (ACVB) inference and oers convergence-guaranteed and practically useful fast Collapsed Variational Bayes (CVB) inferences. CVB inferences yield more precise inferences of Bayesian probabilistic models than Variational Bayes (VB) inferences. However, their convergence aspect is fairly unknown and has not been scrutinized. To make CVB more useful, we study their convergence behaviors in a empirical and practical approach. We develop a convergence-guaranteed algorithm for any CVB-based inference called ACVB, which enables automatic convergence detection and frees non-expert practitioners from the difficult and costly manual monitoring of inference processes. In experiments, ACVB inferences are comparable to or better than those of existing inference methods and deterministic, fast, and provide easier convergence detection. These features are especially convenient for practitioners who want precise Bayesian inference with assured convergence.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1–29},
numpages = {29},
keywords = {collapsed variational Bayes inference, nonparametric Bayes, averaged CVB}
}

@article{10.5555/2946645.3053518,
author = {Alquier, Pierre and Ridgway, James and Chopin, Nicolas},
title = {On the Properties of Variational Approximations of Gibbs Posteriors},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {The PAC-Bayesian approach is a powerful set of techniques to derive nonasymptotic risk bounds for random estimators. The corresponding optimal distribution of estimators, usually called the Gibbs posterior, is unfortunately often intractable. One may sample from it using Markov chain Monte Carlo, but this is usually too slow for big datasets. We consider instead variational approximations of the Gibbs posterior, which are fast to compute. We undertake a general study of the properties of such approximations. Our main finding is that such a variational approximation has often the same rate of convergence as the original PAC-Bayesian procedure it approximates. In addition, we show that, when the risk function is convex, a variational approximation can be obtained in polynomial time using a convex solver. We give finite sample oracle inequalities for the corresponding estimator. We specialize our results to several learning tasks (classification, ranking, matrix completion), discuss how to implement a variational approximation in each case, and illustrate the good properties of said approximation on real datasets.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {8374–8414},
numpages = {41}
}

@article{10.5555/2946645.3053517,
author = {Mirzasoleiman, Baharan and Karbasi, Amin and Sarkar, Rik and Krause, Andreas},
title = {Distributed Submodular Maximization},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Many large-scale machine learning problems-clustering, non-parametric learning, kernel machines, etc.-require selecting a small yet representative subset from a large dataset. Such problems can often be reduced to maximizing a submodular set function subject to various constraints. Classical approaches to submodular optimization require centralized access to the full dataset, which is impractical for truly large-scale problems. In this paper, we consider the problem of submodular function maximization in a distributed fashion. We develop a simple, two-stage protocol GREEDI, that is easily implemented using MapReduce style computations. We theoretically analyze our approach, and show that under certain natural conditions, performance close to the centralized approach can be achieved. We begin with monotone submodular maximization subject to a cardinality constraint, and then extend this approach to obtain approximation guarantees for (not necessarily monotone) submodular maximization subject to more general constraints including matroid or knapsack constraints. In our extensive experiments, we demonstrate the effectiveness of our approach on several applications, including sparse Gaussian process inference and exemplar based clustering on tens of millions of examples using Hadoop.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {8330–8373},
numpages = {44},
keywords = {submodular functions, greedy algorithms, distributed computing, approximation algorithms, map-reduce}
}

@article{10.5555/2946645.3053516,
author = {Hazan, Tamir and Schwing, Alexander G. and Urtasun, Raquel},
title = {Blending Learning and Inference in Conditional Random Fields},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Conditional random fields maximize the log-likelihood of training labels given the training data, e.g., objects given images. In many cases the training labels are structures that consist of a set of variables and the computational complexity for estimating their likelihood is exponential in the number of the variables. Learning algorithms relax this computational burden using approximate inference that is nested as a sub-procedure. In this paper we describe the objective function for nested learning and inference in conditional random fields. The devised objective maximizes the log-beliefs -- probability distributions over subsets of training variables that agree on their marginal probabilities. This objective is concave and consists of two types of variables that are related to the learning and inference tasks respectively. Importantly, we afterwards show how to blend the learning and inference procedure and effectively get to the identical optimum much faster. The proposed algorithm currently achieves the state-of-the-art in various computer vision applications.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {8305–8329},
numpages = {25}
}

@article{10.5555/2946645.3053515,
author = {Peng, Bo and Wang, Lan and Wu, Yichao},
title = {An Error Bound for L1-Norm Support Vector Machine Coefficients in Ultra-High Dimension},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Comparing with the standard L2-norm support vector machine (SVM), the L1-norm SVM enjoys the nice property of simultaneously preforming classification and feature selection. In this paper, we investigate the statistical performance of L1-norm SVM in ultra-high dimension, where the number of features p grows at an exponential rate of the sample size n. Different from existing theory for SVM which has been mainly focused on the generalization error rates and empirical risk, we study the asymptotic behavior of the coefficients of L1- norm SVM. Our analysis reveals that the estimated L1-norm SVM coefficients achieve near oracle rate, that is, with high probability, the L2 error bound of the estimated L1- norm SVM coefficients is of order Op(√q log p/n), where q is the number of features with nonzero coefficients. Furthermore, we show that if the L1-norm SVM is used as an initial value for a recently proposed algorithm for solving non-convex penalized SVM (Zhang et al., 2016b), then in two iterative steps it is guaranteed to produce an estimator that possesses the oracle property in ultra-high dimension, which in particular implies that with probability approaching one the zero coefficients are estimated as exactly zero. Simulation studies demonstrate the fine performance of L1-norm SVM as a sparse classifier and its effectiveness to be utilized to solve non-convex penalized SVM problems in high dimension.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {8279–8304},
numpages = {26},
keywords = {feature selection, error bound, oracle property, L1-norm SVM, non-convex penalty, ulta-high dimension, support vector machine}
}

@article{10.5555/2946645.3053514,
author = {Schulam, Peter and Saria, Suchi},
title = {Integrative Analysis Using Coupled Latent Variable Models for Individualizing Prognoses},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Complex chronic diseases (e.g., autism, lupus, and Parkinson's) are remarkably heterogeneous across individuals. This heterogeneity makes treatment difficult for caregivers because they cannot accurately predict the way in which the disease will progress in order to guide treatment decisions. Therefore, tools that help to predict the trajectory of these complex chronic diseases can help to improve the quality of health care. To build such tools, we can leverage clinical markers that are collected at baseline when a patient first presents and longitudinally over time during follow-up visits. Because complex chronic diseases are typically systemic, the longitudinal markers often track disease progression in multiple organ systems. In this paper, our goal is to predict a function of time that models the future trajectory of a single target clinical marker tracking a disease process of interest. We want to make these predictions using the histories of many related clinical markers as input. Our proposed solution tackles several key challenges. First, we can easily handle irregularly and sparsely sampled markers, which are standard in clinical data. Second, the number of parameters and the computational complexity of learning our model grows linearly in the number of marker types included in the model. This makes our approach applicable to diseases where many different markers are recorded over time. Finally, our model accounts for latent factors influencing disease expression, whereas standard regression models rely on observed features alone to explain variability. Moreover, our approach can be applied dynamically in continous-time and updates its predictions as soon as any new data is available. We apply our approach to the problem of predicting lung disease trajectories in scleroderma, a complex autoimmune disease. We show that our model improves over state-of-the-art baselines in predictive accuracy and we provide a qualitative analysis of our model's output. Finally, the variability of disease presentation in scleroderma makes clinical trial recruitment challenging. We show that a prognostic tool that integrates multiple types of routinely collected longitudinal data can be used to identify individuals at greatest risk of rapid progression and to target trial recruitment.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {8244–8278},
numpages = {35},
keywords = {latent variable models, prediction of functional targets, conditional random fields, gaussian processes, precision medicine, disease trajectories}
}

@article{10.5555/2946645.3053513,
author = {Asbeh, Nuaman and Lerner, Boaz},
title = {Learning Latent Variable Models by Pairwise Cluster Comparison Part II: Algorithm and Evaluation},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {It is important for causal discovery to identify any latent variables that govern a problem and the relationships among them, given measurements in the observed world. In Part I of this paper, we were interested in learning a discrete latent variable model (LVM) and introduced the concept of pairwise cluster comparison (PCC) to identify causal relationships from clusters of data points and an overview of a two-stage algorithm for learning PCC (LPCC). First, LPCC learns exogenous latent variables and latent colliders, as well as their observed descendants, by using pairwise comparisons between data clusters in the measurement space that may explain latent causes. Second, LPCC identifies endogenous latent non-colliders with their observed children. In Part I, we showed that if the true graph has no serial connections, then LPCC returns the true graph, and if the true graph has a serial connection, then LPCC returns a pattern of the true graph. In this paper (Part II), we formally introduce the LPCC algorithm that implements the PCC concept. In addition, we thoroughly evaluate LPCC using simulated and real-world data sets in comparison to state-of-the-art algorithms. Besides using three real-world data sets, which have already been tested in learning an LVM, we also evaluate the algorithms using data sets that represent two original problems. The first problem is identifying young drivers' involvement in road accidents, and the second is identifying cellular subpopulations of the immune system from mass cytometry. The results of our evaluation show that LPCC improves in accuracy with the sample size, can learn large LVMs, and is accurate in learning compared to state-of-the-art algorithms. The code for the LPCC algorithm and data sets used in the experiments reported here are available online.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {8199–8243},
numpages = {45},
keywords = {graphical models, pure measurement model, clustering, learning latent variable models}
}

@article{10.5555/2946645.3053512,
author = {Ackerman, Margareta and Ben-David, Shai},
title = {A Characterization of Linkage-Based Hierarchical Clustering},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {The class of linkage-based algorithms is perhaps the most popular class of hierarchical algorithms. We identify two properties of hierarchical algorithms, and prove that linkage-based algorithms are the only ones that satisfy both of these properties. Our characterization clearly delineates the difference between linkage-based algorithms and other hierarchical methods. We formulate an intuitive notion of locality of a hierarchical algorithm that distinguishes between linkage-based and "global" hierarchical algorithms like bisecting k-means, and prove that popular divisive hierarchical algorithms produce clusterings that cannot be produced by any linkage-based algorithm.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {8182–8198},
numpages = {17}
}

@article{10.5555/2946645.3053511,
author = {Chichignoud, Micha\"{e}l and Lederer, Johannes and Wainwright, Martin J.},
title = {A Practical Scheme and Fast Algorithm to Tune the Lasso with Optimality Guarantees},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We introduce a novel scheme for choosing the regularization parameter in high-dimensional linear regression with Lasso. This scheme, inspired by Lepski's method for bandwidth selection in non-parametric regression, is equipped with both optimal finite-sample guarantees and a fast algorithm. In particular, for any design matrix such that the Lasso has low sup-norm error under an "oracle choice" of the regularization parameter, we show that our method matches the oracle performance up to a small constant factor, and show that it can be implemented by performing simple tests along a single Lasso path. By applying the Lasso to simulated and real data, we find that our novel scheme can be faster and more accurate than standard schemes such as Cross-Validation.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {8162–8181},
numpages = {20},
keywords = {oracle inequalities, high-dimensional regression, regularization parameter, lasso, tuning parameter}
}

@article{10.5555/2946645.3053510,
author = {Ma, Chenxin and Tappenden, Rachael and Tak\'{a}\v{c}, Martin},
title = {Linear Convergence of Randomized Feasible Descent Methods under the Weak Strong Convexity Assumption},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {In this paper we generalize the framework of the Feasible Descent Method (FDM) to a Randomized (R-FDM) and a Randomized Coordinate-wise Feasible Descent Method (RCFDM) framework. We show that many machine learning algorithms, including the famous SDCA algorithm for optimizing the SVM dual problem, or the stochastic coordinate descent method for the LASSO problem, fits into the framework of RC-FDM. We prove linear convergence for both R-FDM and RC-FDM under the weak strong convexity assumption. Moreover, we show that the duality gap converges linearly for RC-FDM, which implies that the duality gap also converges linearly for SDCA applied to the SVM dual problem.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {8138–8161},
numpages = {24},
keywords = {iteration complexity, convergence theory, weak strong convexity, stochastic methods, feasible descent method}
}

@article{10.5555/2946645.3053509,
author = {Kwon, Joon and Perchet, Vianney},
title = {Gains and Losses Are Fundamentally Different in Regret Minimization: The Sparse Case},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We demonstrate that, in the classical non-stochastic regret minimization problem with d decisions, gains and losses to be respectively maximized or minimized are fundamentally different. Indeed, by considering the additional sparsity assumption (at each stage, at most s decisions incur a nonzero outcome), we derive optimal regret bounds of different orders. Specifically, with gains, we obtain an optimal regret guarantee after T stages of order √T log s, so the classical dependency in the dimension is replaced by the sparsity size. With losses, we provide matching upper and lower bounds of order √Ts log(d)/d, which is decreasing in d. Eventually, we also study the bandit setting, and obtain an upper bound of order √Ts log(d/s) when outcomes are losses. This bound is proven to be optimal up to the logarithmic factor √log(d/s).},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {8106–8137},
numpages = {32},
keywords = {sparsity, bandit, regret minimization}
}

@article{10.5555/2946645.3053508,
author = {Furmston, Thomas and Lever, Guy and Barber, David},
title = {Approximate Newton Methods for Policy Search in Markov Decision Processes},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Approximate Newton methods are standard optimization tools which aim to maintain the benefits of Newton's method, such as a fast rate of convergence, while alleviating its drawbacks, such as computationally expensive calculation or estimation of the inverse Hessian. In this work we investigate approximate Newton methods for policy optimization in Markov decision processes (MDPs). We first analyse the structure of the Hessian of the total expected reward, which is a standard objective function for MDPs. We show that, like the gradient, the Hessian exhibits useful structure in the context of MDPs and we use this analysis to motivate two Gauss-Newton methods for MDPs. Like the Gauss-Newton method for non-linear least squares, these methods drop certain terms in the Hessian. The approximate Hessians possess desirable properties, such as negative definiteness, and we demonstrate several important performance guarantees including guaranteed ascent directions, invariance to afine transformation of the parameter space and convergence guarantees. We finally provide a unifying perspective of key policy search algorithms, demonstrating that our second Gauss-Newton algorithm is closely related to both the EM-algorithm and natural gradient ascent applied to MDPs, but performs significantly better in practice on a range of challenging domains.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {8055–8105},
numpages = {51},
keywords = {reinforcement learning, function Approximation, Newton method, Markov decision processes}
}

@article{10.5555/2946645.3053507,
author = {Savitsky, Terrance D.},
title = {Scalable Approximate Bayesian Inference for Outlier Detection under Informative Sampling},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Government surveys of business establishments receive a large volume of submissions where a small subset contain errors. Analysts need a fast-computing algorithm to ag this subset due to a short time window between collection and reporting. We offer a computationally-scalable optimization method based on non-parametric mixtures of hierarchical Dirichlet processes that allows discovery of multiple industry-indexed local partitions linked to a set of global cluster centers. Outliers are nominated as those clusters containing few observations. We extend an existing approach with a new "merge" step that reduces sensitivity to hyperparameter settings. Survey data are typically acquired under an informative sampling design where the probability of inclusion depends on the surveyed response such that the distribution for the observed sample is different from the population. We extend the derivation of a penalized objective function to use a pseudo-posterior that incorporates sampling weights that "undo" the informative design. We provide a simulation study to demonstrate that our approach produces unbiased estimation for the outlying cluster under informative sampling. The method is applied for outlier nomination for the Current Employment Statistics survey conducted by the Bureau of Labor Statistics.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {8006–8054},
numpages = {49},
keywords = {bayesian hierarchical models, hierarchical dirichlet process, clustering, survey sampling, optimization}
}

@article{10.5555/2946645.3053506,
author = {Van Den Burg, Gerrit J. J. and Groenen, Patrick J. F.},
title = {GenSVM: A Generalized Multiclass Support Vector Machine},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Traditional extensions of the binary support vector machine (SVM) to multiclass problems are either heuristics or require solving a large dual optimization problem. Here, a generalized multiclass SVM is proposed called GenSVM. In this method classification boundaries for a K-class problem are constructed in a (K - 1)-dimensional space using a simplex encoding. Additionally, several different weightings of the misclassification errors are incorporated in the loss function, such that it generalizes three existing multiclass SVMs through a single optimization problem. An iterative majorization algorithm is derived that solves the optimization problem without the need of a dual formulation. This algorithm has the advantage that it can use warm starts during cross validation and during a grid search, which significantly speeds up the training phase. Rigorous numerical experiments compare linear GenSVM with seven existing multiclass SVMs on both small and large data sets. These comparisons show that the proposed method is competitive with existing methods in both predictive accuracy and training time, and that it significantly outperforms several existing methods on these criteria.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7964–8005},
numpages = {42},
keywords = {iterative majorization, MM algorithm, classifier comparison, support vector machines, multiclass classification, SVM}
}

@article{10.5555/2946645.3053505,
author = {Asbeh, Nuaman and Lerner, Boaz},
title = {Learning Latent Variable Models by Pairwise Cluster Comparison Part I: Theory and Overview},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Identification of latent variables that govern a problem and the relationships among them, given measurements in the observed world, are important for causal discovery. This identification can be accomplished by analyzing the constraints imposed by the latents in the measurements. We introduce the concept of pairwise cluster comparison (PCC) to identify causal relationships from clusters of data points and provide a two-stage algorithm called learning PCC (LPCC) that learns a latent variable model (LVM) using PCC. First, LPCC learns exogenous latents and latent colliders, as well as their observed descendants, by using pairwise comparisons between data clusters in the measurement space that may explain latent causes. Since in this first stage LPCC cannot distinguish endogenous latent non-colliders from their exogenous ancestors, a second stage is needed to extract the former, with their observed children, from the latter. If the true graph has no serial connections, LPCC returns the true graph, and if the true graph has a serial connection, LPCC returns a pattern of the true graph. LPCC's most important advantage is that it is not limited to linear or latent-tree models and makes only mild assumptions about the distribution. The paper is divided in two parts: Part I (this paper) provides the necessary preliminaries, theoretical foundation to PCC, and an overview of LPCC; Part II formally introduces the LPCC algorithm and experimentally evaluates its merit in different synthetic and real domains. The code for the LPCC algorithm and data sets used in the experiments reported in Part II are available online.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7912–7963},
numpages = {52},
keywords = {clustering, learning latent variable model, causal discovery, multiple indicator model, pure measurement model}
}

@article{10.5555/2946645.3053504,
author = {Williamson, Robert C. and Vernet, Elodie and Reid, Mark D.},
title = {Composite Multiclass Losses},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We consider loss functions for multiclass prediction problems. We show when a multiclass loss can be expressed as a "proper composite loss", which is the composition of a proper loss and a link function. We extend existing results for binary losses to multiclass losses. We subsume results on "classification calibration" by relating it to properness. We determine the stationarity condition, Bregman representation, order-sensitivity, and quasi-convexity of multiclass proper losses. We then characterise the existence and uniqueness of the composite representation for multiclass losses. We show how the composite representation is related to other core properties of a loss: mixability, admissibility and (strong) convexity of multiclass losses which we characterise in terms of the Hessian of the Bayes risk. We show that the simple integral representation for binary proper losses can not be extended to multiclass losses but offer concrete guidance regarding how to design different loss functions. The conclusion drawn from these results is that the proper composite representation is a natural and convenient tool for the design of multiclass loss functions.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7860–7911},
numpages = {52},
keywords = {superprediction set, classification calibration, margin losses, minimaxity, convexity and quasi-convexity of losses, proper losses, parametrisations and representations of loss functions, admissibility, mixability, multiclass losses, link functions}
}

@article{10.5555/2946645.3053503,
author = {London, Ben and Huang, Bert and Getoor, Lise},
title = {Stability and Generalization in Structured Prediction},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Structured prediction models have been found to learn effectively from a few large examples-- sometimes even just one. Despite empirical evidence, canonical learning theory cannot guarantee generalization in this setting because the error bounds decrease as a function of the number of examples. We therefore propose new PAC-Bayesian generalization bounds for structured prediction that decrease as a function of both the number of examples and the size of each example. Our analysis hinges on the stability of joint inference and the smoothness of the data distribution. We apply our bounds to several common learning scenarios, including max-margin and soft-max training of Markov random fields. Under certain conditions, the resulting error bounds can be far more optimistic than previous results and can even guarantee generalization from a single large example.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7808–7859},
numpages = {52},
keywords = {generalization bounds, learning theory, structured prediction, PAC-bayes}
}

@article{10.5555/2946645.3053502,
author = {Pahikkala, Tapio and Airola, Antti},
title = {RLScore: Regularized Least-Squares Learners},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {RLScore is a Python open source module for kernel based machine learning. The library provides implementations of several regularized least-squares (RLS) type of learners. RLS methods for regression and classification, ranking, greedy feature selection, multi-task and zero-shot learning, and unsupervised classification are included. Matrix algebra based computational short-cuts are used to ensure efficiency of both training and cross-validation. A simple API and extensive tutorials allow for easy use of RLScore.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7803–7807},
numpages = {5},
keywords = {regularized least-squares, python, pair-input learning, cross-validation, kernel methods, Kronecker product kernel, feature selection}
}

@article{10.5555/2946645.3053501,
author = {Yu, Huizhen},
title = {Weak Convergence Properties of Constrained Emphatic Temporal-Difference Learning with Constant and Slowly Diminishing Stepsize},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We consider the emphatic temporal-difference (TD) algorithm, ETD(λ), for learning the value functions of stationary policies in a discounted, finite state and action Markov decision process. The ETD(λ) algorithm was recently proposed by Sutton, Mahmood, and White (2016) to solve a long-standing divergence problem of the standard TD algorithm when it is applied to off-policy training, where data from an exploratory policy are used to evaluate other policies of interest. The almost sure convergence of ETD(λ) has been proved in our recent work under general off-policy training conditions, but for a narrow range of diminishing stepsize. In this paper we present convergence results for constrained versions of ETD(λ) with constant stepsize and with diminishing stepsize from a broad range. Our results characterize the asymptotic behavior of the trajectory of iterates produced by those algorithms, and are derived by combining key properties of ETD(λ) with powerful convergence theorems from the weak convergence methods in stochastic approximation theory. For the case of constant stepsize, in addition to analyzing the behavior of the algorithms in the limit as the stepsize parameter approaches zero, we also analyze their behavior for a fixed stepsize and bound the deviations of their averaged iterates from the desired solution. These results are obtained by exploiting the weak Feller property of the Markov chains associated with the algorithms, and by using ergodic theorems for weak Feller Markov chains, in conjunction with the convergence results we get from the weak convergence methods. Besides ETD(λ), our analysis also applies to the off-policy TD(λ) algorithm, when the divergence issue is avoided by setting λ sufficiently large. It yields, for that case, new results on the asymptotic convergence properties of constrained off-policy TD(λ) with constant or slowly diminishing stepsize.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7745–7802},
numpages = {58},
keywords = {importance sampling, Markov decision processes, temporal-difference methods, approximate policy evaluation, reinforcement learning, convergence, stochastic approximation}
}

@article{10.5555/2946645.3053500,
author = {Chen, Xi and Guntuboyina, Adityanand and Zhang, Yuchen},
title = {On Bayes Risk Lower Bounds},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {This paper provides a general technique for lower bounding the Bayes risk of statistical estimation, applicable to arbitrary loss functions and arbitrary prior distributions. A lower bound on the Bayes risk not only serves as a lower bound on the minimax risk, but also characterizes the fundamental limit of any estimator given the prior knowledge. Our bounds are based on the notion of f-informativity (Csisz\'{a}r, 1972), which is a function of the underlying class of probability measures and the prior. Application of our bounds requires upper bounds on the f-informativity, thus we derive new upper bounds on f-informativity which often lead to tight Bayes risk lower bounds. Our technique leads to generalizations of a variety of classical minimax bounds (e.g., generalized Fano's inequality). Our Bayes risk lower bounds can be directly applied to several concrete estimation problems, including Gaussian location models, generalized linear models, and principal component analysis for spiked covariance models. To further demonstrate the applications of our Bayes risk lower bounds to machine learning problems, we present two new theoretical results: (1) a precise characterization of the minimax risk of learning spherical Gaussian mixture models under the smoothed analysis framework, and (2) lower bounds for the Bayes risk under a natural prior for both the prediction and estimation errors for high-dimensional sparse linear regression under an improper learning setting.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7687–7744},
numpages = {58},
keywords = {f-divergence, minimax risk, Fano's inequality, f-informativity, Bayes risk, smoothed analysis}
}

@article{10.5555/2946645.3053499,
author = {Dutta, Subhajit and Sarkar, Soham and Ghosh, Anil K.},
title = {Multi-Scale Classification Using Localized Spatial Depth},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {In this article, we develop and investigate a new classifier based on features extracted using spatial depth. Our construction is based on fitting a generalized additive model to posterior probabilities of different competing classes. To cope with possible multi-modal as well as non-elliptic nature of the population distribution, we also develop a localized version of spatial depth and use that with varying degrees of localization to build the classifier. Final classification is done by aggregating several posterior probability estimates, each of which is obtained using this localized spatial depth with a fixed scale of localization. The proposed classifier can be conveniently used even when the dimension of the data is larger than the sample size, and its good discriminatory power for such data has been established using theoretical as well as numerical results.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7657–7686},
numpages = {30},
keywords = {uniform strong consistency, generalized additive models, Bayes classifier, weighted aggregation of posteriors, elliptic distributions, HDLSS asymptotics}
}

@article{10.5555/2946645.3053498,
author = {Chen, Xi and Jiao, Kevin and Lin, Qihang},
title = {Bayesian Decision Process for Cost-Efficient Dynamic Ranking via Crowdsourcing},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Rank aggregation based on pairwise comparisons over a set of items has a wide range of applications. Although considerable research has been devoted to the development of rank aggregation algorithms, one basic question is how to efficiently collect a large amount of high-quality pairwise comparisons for the ranking purpose. Because of the advent of many crowdsourcing services, a crowd of workers are often hired to conduct pairwise comparisons with a small monetary reward for each pair they compare. Since different workers have different levels of reliability and different pairs have different levels of ambiguity, it is desirable to wisely allocate the limited budget for comparisons among the pairs of items and workers so that the global ranking can be accurately inferred from the comparison results. To this end, we model the active sampling problem in crowdsourced ranking as a Bayesian Markov decision process, which dynamically selects item pairs and workers to improve the ranking accuracy under a budget constraint. We further develop a computationally efficient sampling policy based on knowledge gradient as well as a moment matching technique for posterior approximation. Experimental evaluations on both synthetic and real data show that the proposed policy achieves high ranking accuracy with a lower labeling cost.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7617–7656},
numpages = {40},
keywords = {crowdsourced ranking, knowledge gradient, moment matching, Markov decision process, dynamic programming, Bayesian}
}

@article{10.5555/2946645.3053497,
author = {Erdogdu, Murat A.},
title = {Newton-Stein Method: An Optimization Method for GLMs via Stein's Lemma},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We consider the problem of efficiently computing the maximum likelihood estimator in Generalized Linear Models (GLMs) when the number of observations is much larger than the number of coefficients (n ≫ p ≫ 1). In this regime, optimization algorithms can immensely benefit from approximate second order information. We propose an alternative way of constructing the curvature information by formulating it as an estimation problem and applying a Stein-type lemma, which allows further improvements through subsampling and eigenvalue thresholding. Our algorithm enjoys fast convergence rates, resembling that of second order methods, with modest per-iteration cost. We provide its convergence analysis for the general case where the rows of the design matrix are samples from a sub-Gaussian distribution. We show that the convergence has two phases, a quadratic phase followed by a linear phase. Finally, we empirically demonstrate that our algorithm achieves the highest performance compared to various optimization algorithms on several data sets.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7565–7616},
numpages = {52},
keywords = {sub-sampling, generalized linear models, optimization, Newton's method}
}

@article{10.5555/2946645.3053496,
author = {Johnson, Jason K. and Oyen, Diane and Chertkov, Michael and Netrapalli, Praneeth},
title = {Learning Planar Ising Models},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Inference and learning of graphical models are both well-studied problems in statistics and machine learning that have found many applications in science and engineering. However, exact inference is intractable in general graphical models, which suggests the problem of seeking the best approximation to a collection of random variables within some tractable family of graphical models. In this paper, we focus on the class of planar Ising models, for which exact inference is tractable using techniques of statistical physics. Based on these techniques and recent methods for planarity testing and planar embedding, we propose a greedy algorithm for learning the best planar Ising model to approximate an arbitrary collection of binary random variables (possibly from sample data). Given the set of all pairwise correlations among variables, we select a planar graph and optimal planar Ising model defined on this graph to best approximate that set of correlations. We demonstrate our method in simulations and for two applications: modeling senate voting records and identifying geo-chemical depth trends from Mars rover data.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7539–7564},
numpages = {26},
keywords = {ising models, graphical models}
}

@article{10.5555/2946645.3053495,
author = {Raskutti, Garvesh and Mahoney, Michael W.},
title = {A Statistical Perspective on Randomized Sketching for Ordinary Least-Squares},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We consider statistical as well as algorithmic aspects of solving large-scale least-squares (LS) problems using randomized sketching algorithms. For a LS problem with input data (X, Y) ∈ Rn\texttimes{}p \texttimes{} Rn, sketching algorithms use a "sketching matrix," S ∈ Rr\texttimes{}n, where r ≪ n. Then, rather than solving the LS problem using the full data (X, Y), sketching algorithms solve the LS problem using only the "sketched data" (SX, SY). Prior work has typically adopted an algorithmic perspective, in that it has made no statistical assumptions on the input X and Y, and instead it has been assumed that the data (X, Y) are fixed and worst-case (WC). Prior results show that, when using sketching matrices such as random projections and leverage-score sampling algorithms, with p ≲ r ≪ n, the WC error is the same as solving the original problem, up to a small constant. From a statistical perspective, we typically consider the mean-squared error performance of randomized sketching algorithms, when data (X, Y) are generated according to a statistical linear model Y = Xβ+ε, where ε is a noise process. In this paper, we provide a rigorous comparison of both perspectives leading to insights on how they differ. To do this, we first develop a framework for assessing, in a unified manner, algorithmic and statistical aspects of randomized sketching methods. We then consider the statistical prediction efficiency (PE) and the statistical residual efficiency (RE) of the sketched LS estimator; and we use our framework to provide upper bounds for several types of random projection and random sampling sketching algorithms. Among other results, we show that the RE can be upper bounded when p ≲ r ≪ n while the PE typically requires the sample size r to be substantially larger. Lower bounds developed in subsequent results show that our upper bounds on PE can not be improved.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7508–7538},
numpages = {31},
keywords = {statistical leverage, randomized linear algebra, random projection, statistical efficiency, sketching, algorithmic leveraging}
}

@article{10.5555/2946645.3053494,
author = {Zhao, Anqi and Feng, Yang and Wang, Lie and Tong, Xin},
title = {Neyman-Pearson Classification under High-Dimensional Settings},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Most existing binary classification methods target on the optimization of the overall classification risk and may fail to serve some real-world applications such as cancer diagnosis, where users are more concerned with the risk of misclassifying one specific class than the other. Neyman-Pearson (NP) paradigm was introduced in this context as a novel statistical framework for handling asymmetric type I/II error priorities. It seeks classifiers with a minimal type II error and a constrained type I error under a user specified level. This article is the first attempt to construct classifiers with guaranteed theoretical performance under the NP paradigm in high-dimensional settings. Based on the fundamental Neyman-Pearson Lemma, we used a plug-in approach to construct NP-type classifiers for Naive Bayes models. The proposed classifiers satisfy the NP oracle inequalities, which are natural NP paradigm counterparts of the oracle inequalities in classical binary classification. Besides their desirable theoretical properties, we also demonstrated their numerical advantages in prioritized error control via both simulation and real data studies.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7469–7507},
numpages = {39},
keywords = {screening, plug-in approach, Naive Bayes, high-dimension, NP oracle inequality, classification, Neyman-Pearson (NP) paradigm}
}

@article{10.5555/2946645.3053493,
author = {Reshef, Yakir A. and Reshef, David N. and Finucane, Hilary K. and Sabeti, Pardis C. and Mitzenmacher, Michael},
title = {Measuring Dependence Powerfully and Equitably},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Given a high-dimensional data set, we often wish to find the strongest relationships within it. A common strategy is to evaluate a measure of dependence on every variable pair and retain the highest-scoring pairs for follow-up. This strategy works well if the statistic used (a) has good power to detect non-trivial relationships, and (b) is equitable, meaning that for some measure of noise it assigns similar scores to equally noisy relationships regardless of relationship type (e.g., linear, exponential, periodic). In this paper, we define and theoretically characterize two new statistics that together yield an efficient approach for obtaining both power and equitability. To do this, we first introduce a new population measure of dependence and show three equivalent ways that it can be viewed, including as a canonical "smoothing" of mutual information. We then introduce an efficiently computable consistent estimator of our population measure of dependence, and we empirically establish its equitability on a large class of noisy functional relationships. This new statistic has better bias/variance properties and better runtime complexity than a previous heuristic approach. Next, we derive a second, related statistic whose computation is a trivial side-product of our algorithm and whose goal is powerful independence testing rather than equitability. We prove that this statistic yields a consistent independence test and show in simulations that the test has good power against independence. Taken together, our results suggest that these two statistics are a valuable pair of tools for exploratory data analysis.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7406–7468},
numpages = {63},
keywords = {maximal information coefficient, equitability, statistical power, total information coefficient, mutual information}
}

@article{10.5555/2946645.3053492,
author = {Lizotte, Daniel J. and Laber, Eric B.},
title = {Multi-Objective Markov Decision Processes for Data-Driven Decision Support},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We present new methodology based on Multi-Objective Markov Decision Processes for developing sequential decision support systems from data. Our approach uses sequential decision-making data to provide support that is useful to many different decision-makers, each with different, potentially time-varying preference. To accomplish this, we develop an extension of fitted-Q iteration for multiple objectives that computes policies for all scalarization functions, i.e. preference functions, simultaneously from continuous-state, finite-horizon data. We identify and address several conceptual and computational challenges along the way, and we introduce a new solution concept that is appropriate when different actions have similar expected outcomes. Finally, we demonstrate an application of our method using data from the Clinical Antipsychotic Trials of Intervention Effectiveness and show that our approach offers decision-makers increased choice by a larger class of optimal policies.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7378–7405},
numpages = {28},
keywords = {evidence-based medicine, multi-objective optimization, reinforcement learning, clinical decision support, Markov decision processes}
}

@article{10.5555/2946645.3053491,
author = {Wang, Shusen and Zhang, Zhihua and Zhang, Tong},
title = {Towards More Efficient SPSD Matrix Approximation and CUR Matrix Decomposition},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Symmetric positive semi-definite (SPSD) matrix approximation methods have been extensively used to speed up large-scale eigenvalue computation and kernel learning methods. The standard sketch based method, which we call the prototype model, produces relatively accurate approximations, but is inefficient on large square matrices. The Nystr\"{o}m method is highly efficient, but can only achieve low accuracy. In this paper we propose a novel model that we call the fast SPSD matrix approximation model. The fast model is nearly as efficient as the Nystr\"{o}m method and as accurate as the prototype model. We show that the fast model can potentially solve eigenvalue problems and kernel learning problems in linear time with respect to the matrix size n to achieve 1 + ε relative-error, whereas both the prototype model and the Nystr\"{o}m method cost at least quadratic time to attain comparable error bound. Empirical comparisons among the prototype model, the Nystr\"{o}m method, and our fast model demonstrate the superiority of the fast model. We also contribute new understandings of the Nystr\"{o}m method. The Nystr\"{o}m method is a special instance of our fast model and is approximation to the prototype model. Our technique can be straightforwardly applied to make the CUR matrix decomposition more efficiently computed without much affecting the accuracy.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7329–7377},
numpages = {49},
keywords = {kernel approximation, matrix factorization, the Nystr\"{o}m method, CUR matrix decomposition}
}

@article{10.5555/2946645.3053490,
author = {Arlot, Sylvain and Lerasle, Matthieu},
title = {Choice of V for V-Fold Cross-Validation in Least-Squares Density Estimation},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {This paper studies V-fold cross-validation for model selection in least-squares density estimation. The goal is to provide theoretical grounds for choosing V in order to minimize the least-squares loss of the selected estimator. We first prove a non-asymptotic oracle inequality for V-fold cross-validation and its bias-corrected version (V-fold penalization). In particular, this result implies that V-fold penalization is asymptotically optimal in the nonparametric case. Then, we compute the variance of V-fold cross-validation and related criteria, as well as the variance of key quantities for model selection performance. We show that these variances depend on V like 1 + 4/(V - 1), at least in some particular cases, suggesting that the performance increases much from V = 2 to V = 5 or 10, and then is almost constant. Overall, this can explain the common advice to take V = 5--at least in our setting and when the computational power is limited--, as supported by some simulation experiments. An oracle inequality and exact formulas for the variance are also proved for Monte-Carlo cross-validation, also known as repeated cross-validation, where the parameter V is replaced by the number B of random splits of the data.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7256–7305},
numpages = {50},
keywords = {leave-p-out, V-fold cross-validation, resampling penalties, monte-carlo cross-validation, leave-one-out, penalization, density estimation, model selection}
}

@article{10.5555/2946645.3053489,
author = {Shah, Rajen D.},
title = {Modelling Interactions in High-Dimensional Data with Backtracking},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We study the problem of high-dimensional regression when there may be interacting variables. Approaches using sparsity-inducing penalty functions such as the Lasso can be useful for producing interpretable models. However, when the number variables runs into the thousands, and so even two-way interactions number in the millions, these methods may become computationally infeasible. Typically variable screening based on model fits using only main effects must be performed first. One problem with screening is that important variables may be missed if they are only useful for prediction when certain interaction terms are also present in the model.To tackle this issue, we introduce a new method we call Backtracking. It can be incorporated into many existing high-dimensional methods based on penalty functions, and works by building increasing sets of candidate interactions iteratively. Models fitted on the main effects and interactions selected early on in this process guide the selection of future interactions. By also making use of previous fits for computation, as well as performing calculations is parallel, the overall run-time of the algorithm can be greatly reduced.The effectiveness of our method when applied to regression and classification problems is demonstrated on simulated and real data sets. In the case of using Backtracking with the Lasso, we also give some theoretical support for our procedure.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7225–7255},
numpages = {31},
keywords = {lasso, high-dimensional data, path algorithm, interactions}
}

@article{10.5555/2946645.3053488,
author = {Arias-Castro, Ery and Mason, David and Pelletier, Bruno},
title = {ERRATA: On the Estimation of the Gradient Lines of a Density and the Consistency of the Mean-Shift Algorithm},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7221–7224},
numpages = {4}
}

@article{10.5555/2946645.3053487,
author = {Uria, Benigno and C\^{o}t\'{e}, Marc-Alexandre and Gregor, Karol and Murray, Iain and Larochelle, Hugo},
title = {Neural Autoregressive Distribution Estimation},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We present Neural Autoregressive Distribution Estimation (NADE) models, which are neural network architectures applied to the problem of unsupervised distribution and density estimation. They leverage the probability product rule and a weight sharing scheme inspired from restricted Boltzmann machines, to yield an estimator that is both tractable and has good generalization performance. We discuss how they achieve competitive performance in modeling both binary and real-valued observations. We also present how deep NADE models can be trained to be agnostic to the ordering of input dimensions used by the autoregressive product rule decomposition. Finally, we also show how to exploit the topological structure of pixels in images using a deep convolutional architecture for NADE.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7184–7220},
numpages = {37},
keywords = {deep learning, density modeling, neural networks, unsupervised learning}
}

@article{10.5555/2946645.3053486,
author = {Zhu, Hongxiao and Strawn, Nate and Dunson, David B.},
title = {Bayesian Graphical Models for Multivariate Functional Data},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Graphical models express conditional independence relationships among variables. Although methods for vector-valued data are well established, functional data graphical models remain underdeveloped. By functional data, we refer to data that are realizations of random functions varying over a continuum (e.g., images, signals). We introduce a notion of conditional independence between random functions, and construct a framework for Bayesian inference of undirected, decomposable graphs in the multivariate functional data context. This framework is based on extending Markov distributions and hyper Markov laws from random variables to random processes, providing a principled alternative to naive application of multivariate methods to discretized functional data. Markov properties facilitate the composition of likelihoods and priors according to the decomposition of a graph. Our focus is on Gaussian process graphical models using orthogonal basis expansions. We propose a hyper-inverse-Wishart-process prior for the covariance kernels of the infinite coefficient sequences of the basis expansion, and establish its existence and uniqueness. We also prove the strong hyper Markov property and the conjugacy of this prior under a finite rank condition of the prior kernel parameter. Stochastic search Markov chain Monte Carlo algorithms are developed for posterior inference, assessed through simulations, and applied to a study of brain activity and alcoholism.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7157–7183},
numpages = {27},
keywords = {gaussian process, model uncertainty, functional data analysis, graphical model, stochastic search}
}

@article{10.5555/2946645.3053485,
author = {Fan, Jianqing and Zhou, Wen-Xin},
title = {Guarding against Spurious Discoveries in High Dimensions},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Many data mining and statistical machine learning algorithms have been developed to select a subset of covariates to associate with a response variable. Spurious discoveries can easily arise in high-dimensional data analysis due to enormous possibilities of such selections. How can we know statistically our discoveries better than those by chance? In this paper, we define a measure of goodness of spurious fit, which shows how good a response variable can be fitted by an optimally selected subset of covariates under the null model, and propose a simple and effective LAMM algorithm to compute it. It coincides with the maximum spurious correlation for linear models and can be regarded as a generalized maximum spurious correlation. We derive the asymptotic distribution of such goodness of spurious fit for generalized linear models and L1 regression. Such an asymptotic distribution depends on the sample size, ambient dimension, the number of variables used in the fit, and the covariance information. It can be consistently estimated by multiplier bootstrapping and used as a benchmark to guard against spurious discoveries. It can also be applied to model selection, which considers only candidate models with goodness of fits better than those by spurious fits. The theory and method are convincingly illustrated by simulated examples and an application to the binary outcomes from German Neuroblastoma Trials.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7123–7156},
numpages = {34},
keywords = {sparsity, spurious correlation, L1 regression, spurious fit, bootstrap, generalized linear models, model selection, Gaussian approximation}
}

@article{10.5555/2946645.3053484,
author = {Williamson, Sinead A.},
title = {Nonparametric Network Models for Link Prediction},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Many data sets can be represented as a sequence of interactions between entities--for example communications between individuals in a social network, protein-protein interactions or DNA-protein interactions in a biological context, or vehicles' journeys between cities. In these contexts, there is often interest in making predictions about future interactions, such as who will message whom.A popular approach to network modeling in a Bayesian context is to assume that the observed interactions can be explained in terms of some latent structure. For example, tra_c patterns might be explained by the size and importance of cities, and social network interactions might be explained by the social groups and interests of individuals. Unfortunately, while elucidating this structure can be useful, it often does not directly translate into an effective predictive tool. Further, many existing approaches are not appropriate for sparse networks, a class that includes many interesting real-world situations.In this paper, we develop models for sparse networks that combine structure elucidation with predictive performance. We use a Bayesian nonparametric approach, which allows us to predict interactions with entities outside our training set, and allows the both the latent dimensionality of the model and the number of nodes in the network to grow in expectation as we see more data. We demonstrate that we can capture latent structure while maintaining predictive power, and discuss possible extensions.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7102–7121},
numpages = {20},
keywords = {hierarchical modeling, Bayesian nonparametrics, Gibbs sampling, Dirichlet process, networks}
}

@article{10.5555/2946645.3053483,
author = {Bed\"{o}, Justin and Ong, Cheng Soon},
title = {Multivariate Spearman's ρ for Aggregating Ranks Using Copulas},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We study the problem of rank aggregation: given a set of ranked lists, we want to form a consensus ranking. Furthermore, we consider the case of extreme lists: i.e., only the rank of the best or worst elements are known. We impute missing ranks and generalise Spearman's ρ to extreme ranks. Our main contribution is the derivation of a non-parametric estimator for rank aggregation based on multivariate extensions of Spearman's ρ, which measures correlation between a set of ranked lists. Multivariate Spearman's ρ is defined using copulas, and we show that the geometric mean of normalised ranks maximises multivariate correlation. Motivated by this, we propose a weighted geometric mean approach for learning to rank which has a closed form least squares solution. When only the best (top-k) or worst (bottom-k) elements of a ranked list are known, we impute the missing ranks by the average value, allowing us to apply Spearman's ρ. We discuss an optimistic and pessimistic imputation of missing values, which respectively maximise and minimise correlation, and show its effect on aggregating university rankings. Finally, we demonstrate good performance on the rank aggregation benchmarks MQ2007 and MQ2008.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7072–7101},
numpages = {30}
}

@article{10.5555/2946645.3053482,
author = {Qin, Xiangju and Cunningham, P\'{a}draig and Salter-Townshend, Michael},
title = {Online Trans-Dimensional von Mises-Fisher Mixture Models for User Profiles},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {The proliferation of online communities has attracted much attention to modelling user behaviour in terms of social interaction, language adoption and contribution activity. Nevertheless, when applied to large-scale and cross-platform behavioural data, existing approaches generally suffer from expressiveness, scalability and generality issues. This paper proposes trans-dimensional von Mises-Fisher (TvMF) mixture models for L2 normalised behavioural data, which encapsulate: (1) a Bayesian framework for vMF mixtures that enables prior knowledge and information sharing among clusters, (2) an extended version of reversible jump MCMC algorithm that allows adaptive changes in the number of clusters for vMF mixtures when the model parameters are updated, and (3) an online TvMF mixture model that accommodates the dynamics of clusters for time-varying user behavioural data. We develop efficient collapsed Gibbs sampling techniques for posterior inference, which facilitates parallelism for parameter updates. Empirical results on simulated and real-world data show that the proposed TvMF mixture models can discover more interpretable and intuitive clusters than other widely-used models, such as k-means, non-negative matrix factorization (NMF), Dirichlet process Gaussian mixture models (DP-GMM), and dynamic topic models (DTM). We further evaluate the performance of proposed models in real-world applications, such as the churn prediction task, that shows the usefulness of the features generated.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {7021–7071},
numpages = {51},
keywords = {bayesian nonparametric, mixture models, temporal evolution, user modelling, von mises-fisher}
}

@article{10.5555/2946645.3053481,
author = {Sun, Lei and Nikolaev, Alexander G.},
title = {Mutual Information Based Matching for Causal Inference with Observational Data},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {This paper presents an information theory-driven matching methodology for making causal inference from observational data. The paper adopts a "potential outcomes framework" view on evaluating the strength of cause-effect relationships: the population-wide average effects of binary treatments are estimated by comparing two groups of units - the treated and untreated (control). To reduce the bias in such treatment effect estimation, one has to compose a control group in such a way that across the compared groups of units, treatment is independent of the units' covariates. This requirement gives rise to a subset selection / matching problem. This paper presents the models and algorithms that solve the matching problem by minimizing the mutual information (MI) between the covariates and the treatment variable. Such a formulation becomes tractable thanks to the derived optimality conditions that tackle the non-linearity of the sample-based MI function. Computational experiments with mixed integer-programming formulations and four matching algorithms demonstrate the utility of MI based matching for causal inference studies. The algorithmic developments culminate in a matching heuristic that allows for balancing the compared groups in polynomial (close to linear) time, thus allowing for treatment effect estimation with large data sets.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6990–7020},
numpages = {31},
keywords = {mutual information, subset selection, matching, optimization, observational causal inference}
}

@article{10.5555/2946645.3053480,
author = {Elisha, Oren and Dekel, Shai},
title = {Wavelet Decompositions of Random Forests: Smoothness Analysis, Sparse Approximation and Applications},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {In this paper we introduce, in the setting of machine learning, a generalization of wavelet analysis which is a popular approach to low dimensional structured signal analysis. The wavelet decomposition of a Random Forest provides a sparse approximation of any regression or classification high dimensional function at various levels of detail, with a concrete ordering of the Random Forest nodes: from 'significant' elements to nodes capturing only 'insignificant' noise. Motivated by function space theory, we use the wavelet decomposition to compute numerically a 'weak-type' smoothness index that captures the complexity of the underlying function. As we show through extensive experimentation, this sparse representation facilitates a variety of applications such as improved regression for difficult datasets, a novel approach to feature importance, resilience to noisy or irrelevant features, compression of ensembles, etc.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6952–6989},
numpages = {38},
keywords = {besov spaces, wavelets, random forest, adaptive approximation, feature importance}
}

@article{10.5555/2946645.3053479,
author = {Hummel, Patrick and McAfee, R. Preston},
title = {Machine Learning in an Auction Environment},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We consider a model of repeated online auctions in which an ad with an uncertain click-through rate faces a random distribution of competing bids in each auction and there is discounting of payoffs. We formulate the optimal solution to this explore/exploit problem as a dynamic programming problem and show that efficiency is maximized by making a bid for each advertiser equal to the advertiser's expected value for the advertising opportunity plus a term proportional to the variance in this value divided by the number of impressions the advertiser has received thus far. We then use this result to illustrate that the value of incorporating active exploration in an auction environment is exceedingly small.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6915–6951},
numpages = {37},
keywords = {machine learning, online advertising, auctions, explore/exploit}
}

@article{10.5555/2946645.3053478,
author = {Zhao, Shiwen and Gao, Chuan and Mukherjee, Sayan and Engelhardt, Barbara E.},
title = {Bayesian Group Factor Analysis with Structured Sparsity},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Latent factor models are the canonical statistical tool for exploratory analyses of low-dimensional linear structure for a matrix of p features across n samples. We develop a structured Bayesian group factor analysis model that extends the factor model to multiple coupled observation matrices; in the case of two observations, this reduces to a Bayesian model of canonical correlation analysis. Here, we carefully define a structured Bayesian prior that encourages both element-wise and column-wise shrinkage and leads to desirable behavior on high-dimensional data. In particular, our model puts a structured prior on the joint factor loading matrix, regularizing at three levels, which enables element-wise sparsity and unsupervised recovery of latent factors corresponding to structured variance across arbitrary subsets of the observations. In addition, our structured prior allows for both dense and sparse latent factors so that covariation among either all features or only a subset of features can be recovered. We use fast parameter-expanded expectation-maximization for parameter estimation in this model. We validate our method on simulated data with substantial structure. We show results of our method applied to three high-dimensional data sets, comparing results against a number of state-of-the-art approaches. These results illustrate useful properties of our model, including i) recovering sparse signal in the presence of dense effects; ii) the ability to scale naturally to large numbers of observations; iii) flexible observation- and factor-specific regularization to recover factors with a wide variety of sparsity levels and percentage of variance explained; and iv) tractable inference that scales to modern genomic and text data sizes.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6868–6914},
numpages = {47},
keywords = {parameter expansion, sparse and low-rank matrix decomposition, mixture models, canonical correlation analysis, sparse priors, bayesian structured sparsity}
}

@article{10.5555/2946645.3053477,
author = {Menon, Aditya Krishna and Williamson, Robert C.},
title = {Bipartite Ranking: A Risk-Theoretic Perspective},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We present a systematic study of the bipartite ranking problem, with the aim of explicating its connections to the class-probability estimation problem. Our study focuses on the properties of the statistical risk for bipartite ranking with general losses, which is closely related to a generalised notion of the area under the ROC curve: we establish alternate representations of this risk, relate the Bayes-optimal risk to a class of probability divergences, and characterise the set of Bayes-optimal scorers for the risk. We further study properties of a generalised class of bipartite risks, based on the p-norm push of Rudin (2009). Our analysis is based on the rich framework of proper losses, which are the central tool in the study of class-probability estimation. We show how this analytic tool makes transparent the generalisations of several existing results, such as the equivalence of the minimisers for four seemingly disparate risks from bipartite ranking and class-probability estimation. A novel practical implication of our analysis is the design of new families of losses for scenarios where accuracy at the head of ranked list is paramount, with comparable empirical performance to the p-norm push.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6766–6867},
numpages = {102},
keywords = {class-probability estimation, bayes-optimality, proper losses, ranking the best, bipartite ranking}
}

@article{10.5555/2946645.3053476,
author = {Meister, Mona and Steinwart, Ingo},
title = {Optimal Learning Rates for Localized SVMs},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {One of the limiting factors of using support vector machines (SVMs) in large scale applications are their super-linear computational requirements in terms of the number of training samples. To address this issue, several approaches that train SVMs on many small chunks separately have been proposed in the literature. With the exception of random chunks, which is also known as divide-and-conquer kernel ridge regression, however, these approaches have only been empirically investigated. In this work we investigate a spatially oriented method to generate the chunks. For the resulting localized SVM that uses Gaussian kernels and the least squares loss we derive an oracle inequality, which in turn is used to deduce learning rates that are essentially minimax optimal under some standard smoothness assumptions on the regression function. In addition, we derive local learning rates that are based on the local smoothness of the regression function. We further introduce a data-dependent parameter selection method for our local SVM approach and show that this method achieves the same almost optimal learning rates. Finally, we present a few larger scale experiments for our localized SVM showing that it achieves essentially the same test error as a global SVM for a fraction of the computational requirements. In addition, it turns out that the computational requirements for the local SVMs are similar to those of a vanilla random chunk approach, while the achieved test errors are significantly better.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6722–6765},
numpages = {44},
keywords = {least squares regression, localization, support vector machines}
}

@article{10.5555/2946645.3053475,
author = {Khetan, Ashish and Oh, Sewoong},
title = {Data-Driven Rank Breaking for Efficient Rank Aggregation},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Rank aggregation systems collect ordinal preferences from individuals to produce a global ranking that represents the social preference. Rank-breaking is a common practice to reduce the computational complexity of learning the global ranking. The individual preferences are broken into pairwise comparisons and applied to efficient algorithms tailored for independent paired comparisons. However, due to the ignored dependencies in the data, naive rank-breaking approaches can result in inconsistent estimates. The key idea to produce accurate and consistent estimates is to treat the pairwise comparisons unequally, depending on the topology of the collected data. In this paper, we provide the optimal rank-breaking estimator, which not only achieves consistency but also achieves the best error bound. This allows us to characterize the fundamental tradeoff between accuracy and complexity. Further, the analysis identi\'{e}s how the accuracy depends on the spectral gap of a corresponding comparison graph.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6668–6721},
numpages = {54},
keywords = {sample complexity, rank aggregation, Plackett-Luce model}
}

@article{10.5555/2946645.3053474,
author = {Yuan, Kun and Ying, Bicheng and Sayed, Ali H.},
title = {On the Influence of Momentum Acceleration on Online Learning},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {The article examines in some detail the convergence rate and mean-square-error performance of momentum stochastic gradient methods in the constant step-size and slow adaptation regime. The results establish that momentum methods are equivalent to the standard stochastic gradient method with a re-scaled (larger) step-size value. The size of the re-scaling is determined by the value of the momentum parameter. The equivalence result is established for all time instants and not only in steady-state. The analysis is carried out for general strongly convex and smooth risk functions, and is not limited to quadratic risks. One notable conclusion is that the well-known benefits of momentum constructions for deterministic optimization problems do not necessarily carry over to the adaptive online setting when small constant step-sizes are used to enable continuous adaptation and learning in the presence of persistent gradient noise. From simulations, the equivalence between momentum and standard stochastic gradient methods is also observed for nondifferentiable and non-convex problems.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6602–6667},
numpages = {66},
keywords = {Nesterov's method, mean-square-error analysis, convergence rate, momentum acceleration, stochastic gradient, online learning, heavy-ball method}
}

@article{10.5555/2946645.3053473,
author = {Luca, Stijn and Clifton, David A. and Vanrumste, Bart},
title = {One-Class Classification of Point Patterns of Extremes},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Novelty detection or one-class classification starts from a model describing some type of 'normal behaviour' and aims to classify deviations from this model as being either novelties or anomalies.In this paper the problem of novelty detection for point patterns S = {x1,...,xk} ⊂ Rd is treated where examples of anomalies are very sparse, or even absent. The latter complicates the tuning of hyperparameters in models commonly used for novelty detection, such as one-class support vector machines and hidden Markov models.To this end, the use of extreme value statistics is introduced to estimate explicitly a model for the abnormal class by means of extrapolation from a statistical model X for the normal class. We show how multiple types of information obtained from any available extreme instances of S can be combined to reduce the high false-alarm rate that is typically encountered when classes are strongly imbalanced, as often occurs in the one-class setting (whereby 'abnormal' data are often scarce).The approach is illustrated using simulated data and then a real-life application is used as an exemplar, whereby accelerometry data from epileptic seizures are analysed - these are known to be extreme and rare with respect to normal accelerometer data.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6581–6601},
numpages = {21},
keywords = {class imbalance, sequence classification, extreme value theory, novelty detection, asymptotic theory}
}

@article{10.5555/2946645.3053472,
author = {Sutter, Tobias and Ganguly, Arnab and Koeppl, Heinz},
title = {A Variational Approach to Path Estimation and Parameter Inference of Hidden Diffusion Processes},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We consider a hidden Markov model, where the signal process, given by a diffusion, is only indirectly observed through some noisy measurements. The article develops a variational method for approximating the hidden states of the signal process given the full set of observations. This, in particular, leads to systematic approximations of the smoothing densities of the signal process. The paper then demonstrates how an efficient inference scheme, based on this variational approach to the approximation of the hidden states, can be designed to estimate the unknown parameters of stochastic differential equations. Two examples at the end illustrate the efficacy and the accuracy of the presented method.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6544–6580},
numpages = {37},
keywords = {stochastic differential equations, hidden Markov model, diffusion processes, variational inference, optimal control}
}

@article{10.5555/2946645.3053471,
author = {Manukyan, Art\"{u}r and Ceyhan, Elvan},
title = {Classification of Imbalanced Data with a Geometric Digraph Family},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We use a geometric digraph family called class cover catch digraphs (CCCDs) to tackle the class imbalance problem in statistical classification. CCCDs provide graph theoretic solutions to the class cover problem and have been employed in classification. We assess the classification performance of CCCD classifiers by extensive Monte Carlo simulations, comparing them with other classifiers commonly used in the literature. In particular, we show that CCCD classifiers perform relatively well when one class is more frequent than the other in a two-class setting, an example of the class imbalance problem. We also point out the relationship between class imbalance and class overlapping problems, and their inuence on the performance of CCCD classifiers and other classification methods as well as some state-of-the-art algorithms which are robust to class imbalance by construction. Experiments on both simulated and real data sets indicate that CCCD classifiers are robust to the class imbalance problem. CCCDs substantially undersample from the majority class while preserving the information on the discarded points during the undersampling process. Many state-of-the-art methods, however, keep this information by means of ensemble classifiers, but CCCDs yield only a single classifier with the same property, making it both appealing and fast.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6504–6543},
numpages = {40},
keywords = {class overlapping problem, class cover problem, class imbalance problem, prototype selection, graph domination, class cover catch digraphs, support estimation}
}

@article{10.5555/2946645.3053470,
author = {Wu, Chong and Kwon, Sunghoon and Shen, Xiaotong and Pan, Wei},
title = {A New Algorithm and Theory for Penalized Regression-Based Clustering},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Clustering is unsupervised and exploratory in nature. Yet, it can be performed through penalized regression with grouping pursuit, as demonstrated in Pan et al. (2013). In this paper, we develop a more efficient algorithm for scalable computation and a new theory of clustering consistency for the method. This algorithm, called DC-ADMM, combines difference of convex (DC) programming with the alternating direction method of multipliers (ADMM). This algorithm is shown to be more computationally efficient than the quadratic penalty based algorithm of Pan et al. (2013) because of the former's closed-form updating formulas. Numerically, we compare the DC-ADMM algorithm with the quadratic penalty algorithm to demonstrate its utility and scalability. Theoretically, we establish a finite-sample mis-clustering error bound for penalized regression based clustering with the L0 constrained regularization in a general setting. On this ground, we provide conditions for clustering consistency of the penalized clustering method. As an end product, we put R package prclust implementing PRclust with various loss and grouping penalty functions available on GitHub and CRAN.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {647

license: Unlicense

repository: goyalkaraniit/acm-cr

repo_name: goyalkaraniit/acm-cr