text:
9–6503},
numpages = {25},
keywords = {difference of convex (DC) programming, truncated L1-penalty (TLP), clustering consistency, alternating direction method of multipliers (ADMM)}
}

@article{10.5555/2946645.3053469,
author = {Yang, Zhirong and Corander, Jukka and Oja, Erkki},
title = {Low-Rank Doubly Stochastic Matrix Decomposition for Cluster Analysis},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Cluster analysis by nonnegative low-rank approximations has experienced a remarkable progress in the past decade. However, the majority of such approximation approaches are still restricted to nonnegative matrix factorization (NMF) and suffer from the following two drawbacks: 1) they are unable to produce balanced partitions for large-scale manifold data which are common in real-world clustering tasks; 2) most existing NMF-type clustering methods cannot automatically determine the number of clusters. We propose a new low-rank learning method to address these two problems, which is beyond matrix factorization. Our method approximately decomposes a sparse input similarity in a normalized way and its objective can be used to learn both cluster assignments and the number of clusters. For efficient optimization, we use a relaxed formulation based on Data-Cluster-Data random walk, which is also shown to be equivalent to low-rank factorization of the doubly-stochastically normalized cluster incidence matrix. The probabilistic cluster assignments can thus be learned with a multiplicative majorization-minimization algorithm. Experimental results show that the new method is more accurate both in terms of clustering large-scale manifold data sets and of selecting the number of clusters.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6454–6478},
numpages = {25},
keywords = {cluster analysis, manifold, probabilistic relaxation, multiplicative updates, doubly stochastic matrix}
}

@article{10.5555/2946645.3053468,
author = {Henao, Ricardo and Lu, James T. and Lucas, Joseph E. and Ferranti, Jeffrey and Carin, Lawrence},
title = {Electronic Health Record Analysis via Deep Poisson Factor Models},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Electronic Health Record (EHR) phenotyping utilizes patient data captured through normal medical practice, to identify features that may represent computational medical phenotypes. These features may be used to identify at-risk patients and improve prediction of patient morbidity and mortality. We present a novel deep multi-modality architecture for EHR analysis (applicable to joint analysis of multiple forms of EHR data), based on Poisson Factor Analysis (PFA) modules. Each modality, composed of observed counts, is represented as a Poisson distribution, parameterized in terms of hidden binary units. Information from different modalities is shared via a deep hierarchy of common hidden units. Activation of these binary units occurs with probability characterized as Bernoulli-Poisson link functions, instead of more traditional logistic link functions. In addition, we demonstrate that PFA modules can be adapted to discriminative modalities. To compute model parameters, we derive efficient Markov Chain Monte Carlo (MCMC) inference that scales efficiently, with significant computational gains when compared to related models based on logistic link functions. To explore the utility of these models, we apply them to a subset of patients from the Duke-Durham patient cohort. We identified a cohort of over 16,000 patients with Type 2 Diabetes Mellitus (T2DM) based on diagnosis codes and laboratory tests out of our patient population of over 240,000. Examining the common hidden units uniting the PFA modules, we identify patient features that represent medical concepts. Experiments indicate that our learned features are better able to predict mortality and morbidity than clinical features identified previously in a large-scale clinical trial.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6422–6453},
numpages = {32},
keywords = {multi-modality learning, poisson factor model, phenotyping, electronic health records, deep learning}
}

@article{10.5555/2946645.3053467,
author = {Moghaddass, Ramin and Rudin, Cynthia and Madigan, David},
title = {The Factorized Self-Controlled Case Series Method: An Approach for Estimating the Effects of Many Drugs on Any Outcomes},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We provide a hierarchical Bayesian model for estimating the effects of transient drug exposures on a collection of health outcomes, where the effects of all drugs on all outcomes are estimated simultaneously. The method possesses properties that allow it to handle important challenges of dealing with large-scale longitudinal observational databases. In particular, this model is a generalization of the self-controlled case series (SCCS) method, meaning that certain patient specific baseline rates never need to be estimated. Further, this model is formulated with layers of latent factors, which substantially reduces the number of parameters and helps with interpretability by illuminating latent classes of drugs and outcomes. We believe our work is the first to consider multivariate SCCS (in the sense of multiple outcomes) and is the first to couple latent factor analysis with SCCS. We demonstrate the approach by estimating the effects of various time-sensitive insulin treatments for diabetes.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6398–6421},
numpages = {24},
keywords = {matrix factorization, bayesian analysis, drug safety, effect size estimation, self-controlled case series}
}

@article{10.5555/2946645.3053466,
author = {Bayer, Immanuel},
title = {FastFM: A Library for Factorization Machines},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Factorization Machines (FM) are currently only used in a narrow range of applications and are not yet part of the standard machine learning toolbox, despite their great success in collaborative filtering and click-through rate prediction. However, Factorization Machines are a general model to deal with sparse and high dimensional features. Our Factorization Machine implementation (fastFM) provides easy access to many solvers and supports regression, classification and ranking tasks. Such an implementation simplifies the use of FM for a wide range of applications. Therefore, our implementation has the potential to improve understanding of the FM model and drive new development.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6393–6397},
numpages = {5},
keywords = {python, MCMC, context-aware recommendation, matrix factorization}
}

@article{10.5555/2946645.3053465,
author = {Wang, Yu-Xiang and Lei, Jing and Fienberg, Stephen E.},
title = {Learning with Differential Privacy: Stability, Learnability and the Sufficiency and Necessity of ERM Principle},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {While machine learning has proven to be a powerful data-driven solution to many real-life problems, its use in sensitive domains has been limited due to privacy concerns. A popular approach known as differential privacy offers provable privacy guarantees, but it is often observed in practice that it could substantially hamper learning accuracy. In this paper we study the learnability (whether a problem can be learned by any algorithm) under Vapnik's general learning setting with differential privacy constraint, and reveal some intricate relationships between privacy, stability and learnability. In particular, we show that a problem is privately learnable if an only if there is a private algorithm that asymptotically minimizes the empirical risk (AERM). In contrast, for non-private learning AERM alone is not sufficient for learnability. This result suggests that when searching for private learning algorithms, we can restrict the search to algorithms that are AERM. In light of this, we propose a conceptual procedure that always finds a universally consistent algorithm whenever the problem is learnable under privacy constraint. We also propose a generic and practical algorithm and show that under very general conditions it privately learns a wide class of learning problems. Lastly, we extend some of the results to the more practical (ε, δ)-differential privacy and establish the existence of a phase-transition on the class of problems that are approximately privately learnable with respect to how small δ needs to be.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6353–6392},
numpages = {40},
keywords = {learnability, stability, characterization, differential privacy, privacy-preserving machine learning}
}

@article{10.5555/2946645.3053464,
author = {Lefakis, Leonidas and Fleuret, Fran\c{c}ois},
title = {Jointly Informative Feature Selection Made Tractable by Gaussian Modeling},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We address the problem of selecting groups of jointly informative, continuous, features in the context of classification and propose several novel criteria for performing this selection. The proposed class of methods is based on combining a Gaussian modeling of the feature responses with derived bounds on and approximations to their mutual information with the class label. Furthermore, specific algorithmic implementations of these criteria are presented which reduce the computational complexity of the proposed feature selection algorithms by up to two-orders of magnitude. Consequently we show that feature selection based on the joint mutual information of features and class label is in fact tractable; this runs contrary to prior works that largely depend on marginal quantities. An empirical evaluation using several types of classifiers on multiple data sets show that this class of methods outperforms state-of-the-art baselines, both in terms of speed and classification accuracy.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6314–6352},
numpages = {39},
keywords = {feature selection, mixture of gaussians, mutual information, entropy}
}

@article{10.5555/2946645.3053463,
author = {Trillos, Nicol\'{a}s Garc\'{\i}a and Slep\v{c}ev, Dejan and Von Brecht, James and Laurent, Thomas and Bresson, Xavier},
title = {Consistency of Cheeger and Ratio Graph Cuts},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {This paper establishes the consistency of a family of graph-cut-based algorithms for clustering of data clouds. We consider point clouds obtained as samples of a ground-truth measure. We investigate approaches to clustering based on minimizing objective functionals defined on proximity graphs of the given sample. Our focus is on functionals based on graph cuts like the Cheeger and ratio cuts. We show that minimizers of these cuts converge as the sample size increases to a minimizer of a corresponding continuum cut (which partitions the ground truth measure). Moreover, we obtain sharp conditions on how the connectivity radius can be scaled with respect to the number of sample points for the consistency to hold. We provide results for two-way and for multiway cuts. Furthermore we provide numerical experiments that illustrate the results and explore the optimality of scaling in dimension two.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6268–6313},
numpages = {46},
keywords = {consistency, data clustering, balanced cut, graph partitioning}
}

@article{10.5555/2946645.3053462,
author = {Nishiyama, Yu and Fukumizu, Kenji},
title = {Characteristic Kernels and Infinitely Divisible Distributions},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We connect shift-invariant characteristic kernels to infinitely divisible distributions on Rd. Characteristic kernels play an important role in machine learning applications with their kernel means to distinguish any two probability measures. The contribution of this paper is twofold. First, we show, using the L\'{e}vy-Khintchine formula, that any shift-invariant kernel given by a bounded, continuous, and symmetric probability density function (pdf) of an infinitely divisible distribution on Rd is characteristic. We mention some closure properties of such characteristic kernels under addition, pointwise product, and convolution. Second, in developing various kernel mean algorithms, it is fundamental to compute the following values: (i) kernel mean values mP (x), x ∈ χ, and (ii) kernel mean RKHS inner products 〈mP ;mQ〉H, for probability measures P,Q. If P,Q, and kernel k are Gaussians, then the computation of (i) and (ii) results in Gaussian pdfs that are tractable. We generalize this Gaussian combination to more general cases in the class of infinitely divisible distributions. We then introduce a conjugate kernel and a convolution trick, so that the above (i) and (ii) have the same pdf form, expecting tractable computation at least in some cases. As specific instances, we explore α-stable distributions and a rich class of generalized hyperbolic distributions, where the Laplace, Cauchy, and Student's t distributions are included.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6240–6267},
numpages = {28},
keywords = {conjugate kernel, characteristic kernel, kernel mean, infinitely divisible distribution, convolution trick}
}

@article{10.5555/2946645.3053461,
author = {Lyzinski, Vince and Levin, Keith and Fishkind, Donniell E. and Priebe, Carey E.},
title = {On the Consistency of the Likelihood Maximization Vertex Nomination Scheme: Bridging the Gap between Maximum Likelihood Estimation and Graph Matching},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Given a graph in which a few vertices are deemed interesting a priori, the vertex nomination task is to order the remaining vertices into a nomination list such that there is a concentration of interesting vertices at the top of the list. Previous work has yielded several approaches to this problem, with theoretical results in the setting where the graph is drawn from a stochastic block model (SBM), including a vertex nomination analogue of the Bayes optimal classifier. In this paper, we prove that maximum likelihood (ML)-based vertex nomination is consistent, in the sense that the performance of the ML-based scheme asymptotically matches that of the Bayes optimal scheme. We prove theorems of this form both when model parameters are known and unknown. Additionally, we introduce and prove consistency of a related, more scalable restricted-focus ML vertex nomination scheme. Finally, we incorporate vertex and edge features into ML-based vertex nomination and briey explore the empirical effectiveness of this approach.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6206–6239},
numpages = {34},
keywords = {graph inference, vertex nomination, stochastic block model, graph mining, graph matching}
}

@article{10.5555/2946645.3053460,
author = {Couillet, Romain and Wainrib, Gilles and Sevi, Harry and Ali, Hafiz Tiomoko},
title = {The Asymptotic Performance of Linear Echo State Neural Networks},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {In this article, a study of the mean-square error (MSE) performance of linear echo-state neural networks is performed, both for training and testing tasks. Considering the realistic setting of noise present at the network nodes, we derive deterministic equivalents for the aforementioned MSE in the limit where the number of input data T and network size n both grow large. Specializing then the network connectivity matrix to specific random settings, we further obtain simple formulas that provide new insights on the performance of such networks.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6171–6205},
numpages = {35},
keywords = {random matrix theory, recurrent neural networks, linear networks, echo state networks, mean square error}
}

@article{10.5555/2946645.3053459,
author = {Adamczak, Rados\l{}aw},
title = {A Note on the Sample Complexity of the Er-SpUD Algorithm by Spielman, Wang and Wright for Exact Recovery of Sparsely Used Dictionaries},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We consider the problem of recovering an invertible n\texttimes{}n matrix A and a sparse n\texttimes{}p random matrix X based on the observation of Y = AX (up to a scaling and permutation of columns of A and rows of X). Using only elementary tools from the theory of empirical processes we show that a version of the Er-SpUD algorithm by Spielman, Wang and Wright with high probability recovers A and X exactly, provided that p ≥ Cn log n, which is optimal up to the constant C.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6153–6170},
numpages = {18},
keywords = {l1 minimization, sample complexity, sparse dictionaries, Er-SpUD algorithm, exact recovery}
}

@article{10.5555/2946645.3053458,
author = {Brouard, C\'{e}line and Szafranski, Marie and D'Alch\'{e}-Buc, Florence},
title = {Input Output Kernel Regression: Supervised and Semi-Supervised Structured Output Prediction with Operator-Valued Kernels},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {In this paper, we introduce a novel approach, called Input Output Kernel Regression (IOKR), for learning mappings between structured inputs and structured outputs. The approach belongs to the family of Output Kernel Regression methods devoted to regression in feature space endowed with some output kernel. In order to take into account structure in input data and benefit from kernels in the input space as well, we use the Reproducing Kernel Hilbert Space theory for vector-valued functions. We first recall the ridge solution for supervised learning and then study the regularized hinge loss-based solution used in Maximum Margin Regression. Both models are also developed in the context of semi-supervised setting. In addition we derive an extension of Generalized Cross Validation for model selection in the case of the least-square model. Finally we show the versatility of the IOKR framework on two different problems: link prediction seen as a structured output problem and multi-task regression seen as a multiple and interdependent output problem. Eventually, we present a set of detailed numerical results that shows the relevance of the method on these two tasks.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6105–6152},
numpages = {48},
keywords = {semi-supervised learning, vector-valued RKHS, output kernel regression, structured output prediction, operator-valued kernel}
}

@article{10.5555/2946645.3053457,
author = {De Montjoye, Yves-Alexandre and Rocher, Luc and Pentland, Alex Sandy},
title = {Bandicoot: A Python Toolbox for Mobile Phone Metadata},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {bandicoot is an open-source Python toolbox to extract more than 1442 features from standard mobile phone metadata. bandicoot makes it easy for machine learning researchers and practitioners to load mobile phone data, to analyze and visualize them, and to extract robust features which can be used for various classification and clustering tasks. Emphasis is put on ease of use, consistency, and documentation. bandicoot has no dependencies and is distributed under MIT license.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6100–6104},
numpages = {5},
keywords = {CDR, python, mobile phone metadata, feature engineering, visualization}
}

@article{10.5555/2946645.3053456,
author = {Park, Chiwoo and Huang, Jianhua Z.},
title = {Efficient Computation of Gaussian Process Regression for Large Spatial Data Sets by Patching Local Gaussian Processes},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {This paper develops an efficient computational method for solving a Gaussian process (GP) regression for large spatial data sets using a collection of suitably defined local GP regressions. The conventional local GP approach first partitions a domain into multiple non-overlapping local regions, and then fits an independent GP regression for each local region using the training data belonging to the region. Two key issues with the local GP are (1) the prediction around the boundary of a local region is not as accurate as the prediction at interior of the local region, and (2) two local GP regressions for two neighboring local regions produce different predictions at the boundary of the two regions, creating undesirable discontinuity in the prediction. We address these issues by constraining the predictions of local GP regressions sharing a common boundary to satisfy the same boundary constraints, which in turn are estimated by the data. The boundary constrained local GP regressions are solved by a finite element method. Our approach shows competitive performance when compared with several state-of-the-art methods using two synthetic data sets and three real data sets.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6071–6099},
numpages = {29},
keywords = {kriging, spatial prediction, boundary value problem, local regression, constrained gaussian process regression, variational problem}
}

@article{10.5555/2946645.3053455,
author = {Nie, Jiazhong and Kot\l{}owski, Wojciech and Warmuth, Manfred K.},
title = {Online PCA with Optimal Regret},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We investigate the online version of Principle Component Analysis (PCA), where in each trial t the learning algorithm chooses a k-dimensional subspace, and upon receiving the next instance vector xt, suffers the "compression loss", which is the squared Euclidean distance between this instance and its projection into the chosen subspace. When viewed in the right parameterization, this compression loss is linear, i.e. it can be rewritten as tr(Wtxtxt⊤), where Wt is the parameter of the algorithm and the outer product xtxt⊤ (with ||xt|| ≤ 1) is the instance matrix. In this paper generalize PCA to arbitrary positive definite instance matrices Xt with the linear loss tr(WtXt).We evaluate online algorithms in terms of their worst-case regret, which is a bound on the additional total loss of the online algorithm on all instances matrices over the compression loss of the best k-dimensional subspace (chosen in hindsight). We focus on two popular online algorithms for generalized PCA: the Gradient Descent (GD) and Matrix Exponentiated Gradient (MEG) algorithms. We show that if the regret is expressed as a function of the number of trials, then both algorithms are optimal to within a constant factor on worst-case sequences of positive definite instances matrices with trace norm at most one (which subsumes the original PCA problem with outer products). This is surprising because MEG is believed be suboptimal in this case. We also show that when considering regret bounds as a function of a loss budget, then MEG remains optimal and strictly outperforms GD when the instance matrices are trace norm bounded.Next, we consider online PCA when the adversary is allowed to present the algorithm with positive semidefinite instance matrices whose largest eigenvalue is bounded (rather than their trace which is the sum of their eigenvalues). Again we can show that MEG is optimal and strictly better than GD in this setting.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6022–6070},
numpages = {49},
keywords = {k-sets, gradient descent, regret bounds, matrix exponentiated gradient algorithm, online learning, PCA, expert setting}
}

@article{10.5555/2946645.3053454,
author = {Rohde, David and Wand, Matt P.},
title = {Semiparametric Mean Field Variational Bayes: General Principles and Numerical Issues},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We introduce the term semiparametric mean field variational Bayes to describe the relaxation of mean field variational Bayes in which some density functions in the product density restriction are pre-specified to be members of convenient parametric families. This notion has appeared in various guises in the mean field variational Bayes literature during its history and we endeavor to unify this important topic. We lay down a general framework and explain how previous relevant methodologies fall within this framework. A major contribution is elucidation of numerical issues that impact semiparametric mean field variational Bayes in practice.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5975–6021},
numpages = {47},
keywords = {factor graph, nonlinear conjugate gradient method, fixed-point iteration, fixed-form variational bayes, bayesian computing, non-conjugate variational message passing}
}

@article{10.5555/2946645.3053453,
author = {Kouw, Wouter M. and Van Der Maaten, Laurens J. P. and Krijthe, Jesse H. and Loog, Marco},
title = {Feature-Level Domain Adaptation},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Domain adaptation is the supervised learning setting in which the training and test data are sampled from different distributions: training data is sampled from a source domain, whilst test data is sampled from a target domain. This paper proposes and studies an approach, called feature-level domain adaptation (FLDA), that models the dependence between the two domains by means of a feature-level transfer model that is trained to describe the transfer from source to target domain. Subsequently, we train a domain-adapted classifier by minimizing the expected loss under the resulting transfer model. For linear classifiers and a large family of loss functions and transfer models, this expected loss can be computed or approximated analytically, and minimized efficiently. Our empirical evaluation of FLDA focuses on problems comprising binary and count data in which the transfer can be naturally modeled via a dropout distribution, which allows the classifier to adapt to differences in the marginal probability of features in the source and the target domain. Our experiments on several real-world problems show that FLDA performs on par with state-of-the-art domain-adaptation techniques.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5943–5974},
numpages = {32},
keywords = {risk minimization, domain adaptation, covariate shift, transfer learning}
}

@article{10.5555/2946645.3053452,
author = {Bischl, Bernd and Lang, Michel and Kotthoff, Lars and Schiffner, Julia and Richter, Jakob and Studerus, Erich and Casalicchio, Giuseppe and Jones, Zachary M.},
title = {Mlr: Machine Learning in R},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {The MLR package provides a generic, object-oriented, and extensible framework for classification, regression, survival analysis and clustering for the R language. It provides a unified interface to more than 160 basic learners and includes meta-algorithms and model selection techniques to improve and extend the functionality of basic learners with, e.g., hyperparameter tuning, feature selection, and ensemble construction. Parallel high-performance computing is natively supported. The package targets practitioners who want to quickly apply machine learning algorithms, as well as researchers who want to implement, benchmark, and compare their new methods in a structured environment.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5938–5942},
numpages = {5},
keywords = {feature selection, model selection, R, machine learning, benchmarking, data mining, hyperparameter tuning, visualization}
}

@article{10.5555/2946645.3053451,
author = {Adam, Stavros P. and Magoulas, George D. and Karras, Dimitrios A. and Vrahatis, Michael N.},
title = {Bounding the Search Space for Global Optimization of Neural Networks Learning Error: An Interval Analysis Approach},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Training a multilayer perceptron (MLP) with algorithms employing global search strategies has been an important research direction in the field of neural networks. Despite a number of signifcant results, an important matter concerning the bounds of the search region| typically defined as a box--where a global optimization method has to search for a potential global minimizer seems to be unresolved. The approach presented in this paper builds on interval analysis and attempts to define guaranteed bounds in the search space prior to applying a global search algorithm for training an MLP. These bounds depend on the machine precision and the term "guaranteed" denotes that the region defined surely encloses weight sets that are global minimizers of the neural network's error function. Although the solution set to the bounding problem for an MLP is in general non-convex, the paper presents the theoretical results that help deriving a box which is a convex set. This box is an outer approximation of the algebraic solutions to the interval equations resulting from the function implemented by the network nodes. An experimental study using well known benchmarks is presented in accordance with the theoretical results.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5898–5937},
numpages = {40},
keywords = {bound constrained global optimization, algebraic solution, interval linear equations, interval analysis, neural network training}
}

@article{10.5555/2946645.3053450,
author = {Misra, Navodit and Kuruoglu, Ercan E.},
title = {Stable Graphical Models},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Stable random variables are motivated by the central limit theorem for densities with (potentially) unbounded variance and can be thought of as natural generalizations of the Gaussian distribution to skewed and heavy-tailed phenomenon. In this paper, we introduce α-stable graphical (α-SG) models, a class of multivariate stable densities that can also be represented as Bayesian networks whose edges encode linear dependencies between random variables. One major hurdle to the extensive use of stable distributions is the lack of a closed-form analytical expression for their densities. This makes penalized maximum-likelihood based learning computationally demanding. We establish theoretically that the Bayesian information criterion (BIC) can asymptotically be reduced to the computationally more tractable minimum dispersion criterion (MDC) and develop StabLe, a structure learning algorithm based on MDC. We use simulated datasets for five benchmark network topologies to empirically demonstrate how StabLe improves upon ordinary least squares (OLS) regression. We also apply StabLe to microarray gene expression data for lymphoblastoid cells from 727 individuals belonging to eight global population groups. We establish that StabLe improves test set performance relative to OLS via ten-fold cross-validation. Finally, we develop SGEX, a method for quantifying di_erential expression of genes between di_erent population groups.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5862–5897},
numpages = {36},
keywords = {stable distributions, Bayesian networks, gene expression, differential expression, structure learning, linear regression}
}

@article{10.5555/2946645.3053449,
author = {Wang, Yuanjia and Chen, Tianle and Zeng, Donglin},
title = {Support Vector Hazards Machine: A Counting Process Framework for Learning Risk Scores for Censored Outcomes},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Learning risk scores to predict dichotomous or continuous outcomes using machine learning approaches has been studied extensively. However, how to learn risk scores for time-to-event outcomes subject to right censoring has received little attention until recently. Existing approaches rely on inverse probability weighting or rank-based regression, which may be inefficient. In this paper, we develop a new support vector hazards machine (SVHM) approach to predict censored outcomes. Our method is based on predicting the counting process associated with the time-to-event outcomes among subjects at risk via a series of support vector machines. Introducing counting processes to represent time-to-event data leads to a connection between support vector machines in supervised learning and hazards regression in standard survival analysis. To account for di_erent at risk populations at observed event times, a time-varying offset is used in estimating risk scores. The resulting optimization is a convex quadratic programming problem that can easily incorporate nonlinearity using kernel trick. We demonstrate an interesting link from the profiled empirical risk function of SVHM to the Cox partial likelihood. We then formally show that SVHM is optimal in discriminating covariate-specific hazard function from population average hazard function, and establish the consistency and learning rate of the predicted risk using the estimated risk scores. Simulation studies show improved prediction accuracy of the event times using SVHM compared to existing machine learning methods and standard conventional approaches. Finally, we analyze two real world biomedical study data where we use clinical markers and neuroimaging biomarkers to predict age-at-onset of a disease, and demonstrate superiority of SVHM in distinguishing high risk versus low risk subjects.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5825–5861},
numpages = {37},
keywords = {risk bound, early disease detection, biomarkers, survival analysis, risk prediction, support vector machine, neuroimaging}
}

@article{10.5555/2946645.3053448,
author = {Ma, Jing and Michailidis, George},
title = {Joint Structural Estimation of Multiple Graphical Models},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Gaussian graphical models capture dependence relationships between random variables through the pattern of nonzero elements in the corresponding inverse covariance matrices. To date, there has been a large body of literature on both computational methods and analytical results on the estimation of a single graphical model. However, in many application domains, one has to estimate several related graphical models, a problem that has also received attention in the literature. The available approaches usually assume that all graphical models are globally related. On the other hand, in many settings different relationships between subsets of the node sets exist between different graphical models. We develop methodology that jointly estimates multiple Gaussian graphical models, assuming that there exists prior information on how they are structurally related. For many applications, such information is available from external data sources. The proposed method consists of first applying neighborhood selection with a group lasso penalty to obtain edge sets of the graphs, and a maximum likelihood refit for estimating the nonzero entries in the inverse covariance matrices. We establish consistency of the proposed method for sparse high-dimensional Gaussian graphical models and examine its performance using simulation experiments. Applications to a climate data set and a breast cancer data set are also discussed.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5777–5824},
numpages = {48},
keywords = {structured sparsity, edge set recovery, Gaussian graphical model, group lasso penalty, consistency}
}

@article{10.5555/2946645.3053447,
author = {Shah, Nihar B. and Zhou, Dengyong},
title = {Double or Nothing: Multiplicative Incentive Mechanisms for Crowdsourcing},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Crowdsourcing has gained immense popularity in machine learning applications for obtaining large amounts of labeled data. Crowdsourcing is cheap and fast, but suffers from the problem of low-quality data. To address this fundamental challenge in crowdsourcing, we propose a simple payment mechanism to incentivize workers to answer only the questions that they are sure of and skip the rest. We show that surprisingly, under a mild and natural "no-free-lunch" requirement, this mechanism is the one and only incentive-compatible payment mechanism possible. We also show that among all possible incentive-compatible mechanisms (that may or may not satisfy no-free-lunch), our mechanism makes the smallest possible payment to spammers. We further extend our results to a more general setting in which workers are required to provide a quantized confidence for each question. Interestingly, this unique mechanism takes a "multiplicative" form. The simplicity of the mechanism is an added benefit. In preliminary experiments involving over 900 worker-task pairs, we observe a significant drop in the error rates under this unique mechanism for the same or lower monetary expenditure.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5725–5776},
numpages = {52},
keywords = {mechanism design, high-quality labels, crowdsourcing, supervised learning, proper scoring rules}
}

@article{10.5555/2946645.3053446,
author = {Dai, Wenlin and Tong, Tiejun and Genton, Marc G.},
title = {Optimal Estimation of Derivatives in Nonparametric Regression},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We propose a simple framework for estimating derivatives without _tting the regression function in nonparametric regression. Unlike most existing methods that use the symmetric difference quotients, our method is constructed as a linear combination of observations. It is hence very exible and applicable to both interior and boundary points, including most existing methods as special cases of ours. Within this framework, we define the variance-minimizing estimators for any order derivative of the regression function with a fixed bias-reduction level. For the equidistant design, we derive the asymptotic variance and bias of these estimators. We also show that our new method will, for the first time, achieve the asymptotically optimal convergence rate for difference-based estimators. Finally, we provide an effective criterion for selection of tuning parameters and demonstrate the usefulness of the proposed method through extensive simulation studies of the first-and second-order derivative estimators.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5700–5724},
numpages = {25},
keywords = {nonparametric regression, nonparametric derivative estimation, linear combination, taylor expansion, optimal sequence}
}

@article{10.5555/2946645.3053445,
author = {Zhou, Mingyuan and Cong, Yulai and Chen, Bo},
title = {Augmentable Gamma Belief Networks},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {To infer multilayer deep representations of high-dimensional discrete and nonnegative real vectors, we propose an augmentable gamma belief network (GBN) that factorizes each of its hidden layers into the product of a sparse connection weight matrix and the nonnegative real hidden units of the next layer. The GBN's hidden layers are jointly trained with an upward-downward Gibbs sampler that solves each layer with the same subroutine. The gamma-negative binomial process combined with a layer-wise training strategy allows inferring the width of each layer given a fixed budget on the width of the first layer. Example results illustrate interesting relationships between the width of the first layer and the inferred network structure, and demonstrate that the GBN can add more layers to improve its performance in both unsupervisedly extracting features and predicting heldout data. For exploratory data analysis, we extract trees and subnetworks from the learned deep network to visualize how the very specific factors discovered at the first hidden layer and the increasingly more general factors discovered at deeper hidden layers are related to each other, and we generate synthetic data by propagating random variables through the deep network from the top hidden layer back to the bottom data layer.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5656–5699},
numpages = {44},
keywords = {unsupervised learning, Poisson factor analysis, Bayesian nonparametrics, multilayer representation, topic modeling, deep learning}
}

@article{10.5555/2946645.3053444,
author = {Liu, Ji and Zhu, Xiaojin},
title = {The Teaching Dimension of Linear Learners},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Teaching dimension is a learning theoretic quantity that speci\'{e}s the minimum training set size to teach a target model to a learner. Previous studies on teaching dimension focused on version-space learners which maintain all hypotheses consistent with the training data, and cannot be applied to modern machine learners which select a specific hypothesis via optimization. This paper presents the first known teaching dimension for ridge regression, support vector machines, and logistic regression. We also exhibit optimal training sets that match these teaching dimensions. Our approach generalizes to other linear learners.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5631–5655},
numpages = {25},
keywords = {VC-dimension, optimization based learner, Karush-Kuhn-Tucker conditions}
}

@article{10.5555/2946645.3053443,
author = {Gao, Chao and Lu, Yu and Ma, Zongming and Zhou, Harrison H.},
title = {Optimal Estimation and Completion of Matrices with Biclustering Structures},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Biclustering structures in data matrices were first formalized in a seminal paper by John Hartigan (Hartigan, 1972) where one seeks to cluster cases and variables simultaneously. Such structures are also prevalent in block modeling of networks. In this paper, we develop a theory for the estimation and completion of matrices with biclustering structures, where the data is a partially observed and noise contaminated matrix with a certain underlying biclustering structure. In particular, we show that a constrained least squares estimator achieves minimax rate-optimal performance in several of the most important scenarios. To this end, we derive unified high probability upper bounds for all sub-Gaussian data and also provide matching minimax lower bounds in both Gaussian and binary cases. Due to the close connection of graphon to stochastic block models, an immediate consequence of our general results is a minimax rate-optimal estimator for sparse graphons.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5602–5630},
numpages = {29},
keywords = {graphon, missing data, stochastic block models, sparse network, biclustering, matrix completion}
}

@article{10.5555/2946645.3053442,
author = {Hern\'{a}ndez-Lobato, Jos\'{e} Miguel and Gelbart, Michael A. and Adams, Ryan P. and Hoffman, Matthew W. and Ghahramani, Zoubin},
title = {A General Framework for Constrained Bayesian Optimization Using Information-Based Search},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We present an information-theoretic framework for solving global black-box optimization problems that also have black-box constraints. Of particular interest to us is to efficiently solve problems with decoupled constraints, in which subsets of the objective and constraint functions may be evaluated independently. For example, when the objective is evaluated on a CPU and the constraints are evaluated independently on a GPU. These problems require an acquisition function that can be separated into the contributions of the individual function evaluations. We develop one such acquisition function and call it Predictive Entropy Search with Constraints (PESC). PESC is an approximation to the expected information gain criterion and it compares favorably to alternative approaches based on improvement in several synthetic and real-world problems. In addition to this, we consider problems with a mix of functions that are fast and slow to evaluate. These problems require balancing the amount of time spent in the meta-computation of PESC and in the actual evaluation of the target objective. We take a bounded rationality approach and develop a partial update for PESC which trades o_ accuracy against speed. We then propose a method for adaptively switching between the partial and full updates for PESC. This allows us to interpolate between versions of PESC that are efficient in terms of function evaluations and those that are efficient in terms of wall-clock time. Overall, we demonstrate that PESC is an effective algorithm that provides a promising direction towards a unified solution for constrained Bayesian optimization.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5549–5601},
numpages = {53},
keywords = {constraints, Bayesian optimization, predictive entropy search}
}

@article{10.5555/2946645.3053441,
author = {Vollmer, Sebastian J. and Zygalakis, Konstantinos C. and Teh, Yee Whye},
title = {Exploration of the (Non-)Asymptotic Bias and Variance of Stochastic Gradient Langevin Dynamics},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Applying standard Markov chain Monte Carlo (MCMC) algorithms to large data sets is computationally infeasible. The recently proposed stochastic gradient Langevin dynamics (SGLD) method circumvents this problem in three ways: it generates proposed moves using only a subset of the data, it skips the Metropolis-Hastings accept-reject step, and it uses sequences of decreasing step sizes. In Teh et al. (2014), we provided the mathematical foundations for the decreasing step size SGLD, including consistency and a central limit theorem. However, in practice the SGLD is run for a relatively small number of iterations, and its step size is not decreased to zero. The present article investigates the behaviour of the SGLD with fixed step size. In particular we characterise the asymptotic bias explicitly, along with its dependence on the step size and the variance of the stochastic gradient. On that basis a modified SGLD which removes the asymptotic bias due to the variance of the stochastic gradients up to first order in the step size is derived. Moreover, we are able to obtain bounds on the finite-time bias, variance and mean squared error (MSE). The theory is illustrated with a Gaussian toy model for which the bias and the MSE for the estimation of moments can be obtained explicitly. For this toy model we study the gain of the SGLD over the standard Euler method in the limit of large data sets.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5504–5548},
numpages = {45},
keywords = {big data, fixed step size, langevin dynamics, Markov Chain Monte Carlo}
}

@article{10.5555/2946645.3053440,
author = {Odense, Simon and Edwards, Roderick},
title = {Universal Approximation Results for the Temporal Restricted Boltzmann Machine and the Recurrent Temporal Restricted Boltzmann Machine},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {The Restricted Boltzmann Machine (RBM) has proved to be a powerful tool in machine learning, both on its own and as the building block for Deep Belief Networks (multi-layer generative graphical models). The RBM and Deep Belief Network have been shown to be universal approximators for probability distributions on binary vectors. In this paper we prove several similar universal approximation results for two variations of the Restricted Boltzmann Machine with time dependence, the Temporal Restricted Boltzmann Machine (TRBM) and the Recurrent Temporal Restricted Boltzmann Machine (RTRBM). We show that the TRBM is a universal approximator for Markov chains and generalize the theorem to sequences with longer time dependence. We then prove that the RTRBM is a universal approximator for stochastic processes with _nite time dependence. We conclude with a discussion on efficiency and how the constructions developed could explain some previous experimental results.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5483–5503},
numpages = {21},
keywords = {universal approximation, TRBM, machine learning, RTRBM}
}

@article{10.5555/2946645.3053439,
author = {Escalante-B., Alberto N. and Wiskott, Laurenz},
title = {Theoretical Analysis of the Optimal Free Responses of Graph-Based SFA for the Design of Training Graphs},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Slow feature analysis (SFA) is an unsupervised learning algorithm that extracts slowly varying features from a multi-dimensional time series. Graph-based SFA (GSFA) is an extension to SFA for supervised learning that can be used to successfully solve regression problems if combined with a simple supervised post-processing step on a small number of slow features. The objective function of GSFA minimizes the squared output differences between pairs of samples speci\'{e}d by the edges of a structure called training graph. The edges of current training graphs, however, are derived only from the relative order of the labels. Exploiting the exact numerical value of the labels enables further improvements in label estimation accuracy.In this article, we propose the exact label learning (ELL) method to create a more precise training graph that encodes the desired labels explicitly and allows GSFA to extract a normalized version of them directly (i.e., without supervised post-processing). The ELL method is used for three tasks: (1) We estimate gender from artificial images of human faces (regression) and show the advantage of coding additional labels, particularly skin color. (2) We analyze two existing graphs for regression. (3) We extract compact discriminative features to classify traffic sign images. When the number of output features is limited, such compact features provide a higher classification rate compared to a graph that generates features equivalent to those of nonlinear Fisher discriminant analysis. The method is versatile, directly supports multiple labels, and provides higher accuracy compared to current graphs for the problems considered.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5447–5482},
numpages = {36},
keywords = {nonlinear regression, many classes, image analysis, pattern recognition, slow feature analysis}
}

@article{10.5555/2946645.3053438,
author = {Pavlidis, Nicos G. and Hofmeyr, David P. and Tasoulis, Sotiris K.},
title = {Minimum Density Hyperplanes},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Associating distinct groups of objects (clusters) with contiguous regions of high probability density (high-density clusters), is central to many statistical and machine learning approaches to the classification of unlabelled data. We propose a novel hyperplane classifier for clustering and semi-supervised classification which is motivated by this objective. The proposed minimum density hyperplane minimises the integral of the empirical probability density function along it, thereby avoiding intersection with high density clusters. We show that the minimum density and the maximum margin hyperplanes are asymptotically equivalent, thus linking this approach to maximum margin clustering and semi-supervised support vector classifiers. We propose a projection pursuit formulation of the associated optimisation problem which allows us to _nd minimum density hyperplanes efficiently in practice, and evaluate its performance on a range of benchmark data sets. The proposed approach is found to be very competitive with state of the art methods for clustering and semi-supervised classification.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5414–5446},
numpages = {33},
keywords = {projection pursuit, clustering, semi-supervised classification, high-density clusters, low-density separation}
}

@article{10.5555/2946645.3053437,
author = {McDonald, Andrew M. and Pontil, Massimiliano and Stamos, Dimitris},
title = {New Perspectives on K-Support and Cluster Norms},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We study a regularizer which is defined as a parameterized in_mum of quadratics, and which we call the box-norm. We show that the k-support norm, a regularizer proposed by Argyriou et al. (2012) for sparse vector prediction problems, belongs to this family, and the box-norm can be generated as a perturbation of the former. We derive an improved algorithm to compute the proximity operator of the squared box-norm, and we provide a method to compute the norm. We extend the norms to matrices, introducing the spectral k-support norm and spectral box-norm. We note that the spectral box-norm is essentially equivalent to the cluster norm, a multitask learning regularizer introduced by Jacob et al. (2009a), and which in turn can be interpreted as a perturbation of the spectral k-support norm. Centering the norm is important for multitask learning and we also provide a method to use centered versions of the norms as regularizers. Numerical experiments indicate that the spectral k-support and box-norms and their centered variants provide state of the art performance in matrix completion and multitask learning problems respectively.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5376–5413},
numpages = {38},
keywords = {convex optimization, spectral regularization, matrix completion, structured sparsity., multitask learning}
}

@article{10.5555/2946645.3053436,
author = {Neu, Gergely and Bart\'{o}k, G\'{a}bor},
title = {Importance Weighting without Importance Weights: An Efficient Algorithm for Combinatorial Semi-Bandits},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We propose a sample-efficient alternative for importance weighting for situations where one only has sample access to the probability distribution that generates the observations. Our new method, called Geometric Resampling (GR), is described and analyzed in the context of online combinatorial optimization under semi-bandit feedback, where a learner sequentially selects its actions from a combinatorial decision set so as to minimize its cumulative loss. In particular, we show that the well-known Follow-the-Perturbed-Leader (FPL) prediction method coupled with Geometric Resampling yields the _rst computationally efficient reduction from o_ine to online optimization in this setting. We provide a thorough theoretical analysis for the resulting algorithm, showing that its performance is on par with previous, inefficient solutions. Our main contribution is showing that, despite the relatively large variance induced by the GR procedure, our performance guarantees hold with high probability rather than only in expectation. As a side result, we also improve the best known regret bounds for FPL in online combinatorial optimization with full feedback, closing the perceived performance gap between FPL and exponential weights in this setting.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5355–5375},
numpages = {21},
keywords = {follow the perturbed leader, online learning, importance weighting, semi-bandit feedback, bandit problems, combinatorial optimization}
}

@article{10.5555/2946645.3053435,
author = {Su, Weijie and Boyd, Stephen and Cand\`{e}s, Emmanuel J.},
title = {A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We derive a second-order ordinary differential equation (ODE) which is the limit of Nesterov's accelerated gradient method. This ODE exhibits approximate equivalence to Nesterov's scheme and thus can serve as a tool for analysis. We show that the continuous time ODE allows for a better understanding of Nesterov's scheme. As a byproduct, we obtain a family of schemes with similar convergence rates. The ODE interpretation also suggests restarting Nesterov's scheme leading to an algorithm, which can be rigorously proven to converge at a linear rate whenever the objective is strongly convex.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5312–5354},
numpages = {43},
keywords = {Nesterov's accelerated scheme, differential equation, convex optimization, first-order methods, restarting}
}

@article{10.5555/2946645.3053434,
author = {Szab\'{o}, Zolt\'{a}n and Sriperumbudur, Bharath K. and P\'{o}czos, Barnab\'{a}s and Gretton, Arthur},
title = {Learning Theory for Distribution Regression},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We focus on the distribution regression problem: regressing to vector-valued outputs from probability measures. Many important machine learning and statistical tasks fit into this framework, including multi-instance learning and point estimation problems without analytical solution (such as hyperparameter or entropy estimation). Despite the large number of available heuristics in the literature, the inherent two-stage sampled nature of the problem makes the theoretical analysis quite challenging, since in practice only samples from sampled distributions are observable, and the estimates have to rely on similarities computed between sets of points. To the best of our knowledge, the only existing technique with consistency guarantees for distribution regression requires kernel density estimation as an intermediate step (which often performs poorly in practice), and the domain of the distributions to be compact Euclidean. In this paper, we study a simple, analytically computable, ridge regression-based alternative to distribution regression, where we embed the distributions to a reproducing kernel Hilbert space, and learn the regressor from the embeddings to the outputs. Our main contribution is to prove that this scheme is consistent in the two-stage sampled setup under mild conditions (on separable topological domains enriched with kernels): we present an exact computational-statistical efficiency trade-off analysis showing that our estimator is able to match the one-stage sampled minimax optimal rate (Caponnetto and De Vito, 2007; Steinwart et al., 2009). This result answers a 17-year-old open question, establishing the consistency of the classical set kernel (Haussler, 1999; G\"{a}rtner et al., 2002) in regression. We also cover consistency for more recent kernels on distributions, including those due to Christmann and Steinwart (2010).},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5272–5311},
numpages = {40},
keywords = {multi-instance learning, two-Stage sampled distribution regression, minimax optimality, mean embedding, Kernel ridge regression}
}

@article{10.5555/2946645.3053433,
author = {Lemeire, Jan},
title = {Conditional Independencies under the Algorithmic Independence of Conditionals},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {In this paper we analyze the relationship between faithfulness and the more recent condition of algorithmic Independence of Conditionals (IC) with respect to the Conditional Independencies (CIs) they allow. Both conditions have been extensively used for causal inference by refuting factorizations for which the condition does not hold. Violation of faithfulness happens when there are CIs that do not follow from the Markov condition. For those CIs, non-trivial constraints among some parameters of the Conditional Probability Distributions (CPDs) must hold. When such a constraint is defined over parameters of different CPDs, we prove that IC is also violated unless the parameters have a simple description. To understand which non-Markovian CIs are permitted we define a new condition closely related to IC: the Independence from Product Constraints (IPC). The condition reflects that CIs might be the result of specific parameterizations of individual CPDs but not from constraints on parameters of different CPDs. In that sense it is more restrictive than IC: parameters may have a simple description. On the other hand, IC also excludes other forms of algorithmic dependencies between CPDs. Finally, we prove that on top of the CIs permitted by the Markov condition (faithfulness), IPC allows non-minimality, deterministic relations and what we called proportional CPDs. These are the only cases in which a CI follows from a specific parameterization of a single CPD.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5252–5271},
numpages = {20},
keywords = {independence of conditionals, faithfulness, causality, Kolmogorov complexity}
}

@article{10.5555/2946645.3053432,
author = {Shen, Dan and Shen, Haipeng and Marron, J. S.},
title = {A General Framework for Consistency of Principal Component Analysis},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {A general asymptotic framework is developed for studying consistency properties of principal component analysis (PCA). Our framework includes several previously studied domains of asymptotics as special cases and allows one to investigate interesting connections and transitions among the various domains. More importantly, it enables us to investigate asymptotic scenarios that have not been considered before, and gain new insights into the consistency, subspace consistency and strong inconsistency regions of PCA and the boundaries among them. We also establish the corresponding convergence rate within each region. Under general spike covariance models, the dimension (or number of variables) discourages the consistency of PCA, while the sample size and spike information (the relative size of the population eigenvalues) encourage PCA consistency. Our framework nicely illustrates the relationship among these three types of information in terms of dimension, sample size and spike size, and rigorously characterizes how their relationships a\'{e}ct PCA consistency.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5218–5251},
numpages = {34},
keywords = {random matrix, PCA, high dimension low sample size, spike model}
}

@article{10.5555/2946645.3053431,
author = {Qian, Wei and Yang, Yuhong},
title = {Kernel Estimation and Model Combination in a Bandit Problem with Covariates},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Multi-armed bandit problem is an important optimization game that requires an exploration-exploitation tradeoff to achieve optimal total reward. Motivated from industrial applications such as online advertising and clinical research, we consider a setting where the rewards of bandit machines are associated with covariates, and the accurate estimation of the corresponding mean reward functions plays an important role in the performance of allocation rules. Under a exible problem setup, we establish asymptotic strong consistency and perform a finite-time regret analysis for a sequential randomized allocation strategy based on kernel estimation. In addition, since many nonparametric and parametric methods in supervised learning may be applied to estimating the mean reward functions but guidance on how to choose among them is generally unavailable, we propose a model combining allocation strategy for adaptive performance. Simulations and a real data evaluation are conducted to illustrate the performance of the proposed allocation strategy.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5181–5217},
numpages = {37},
keywords = {upper confidence bound, exploration-exploitation tradeoff, nonparametric regression, contextual bandit problem, regret bound}
}

@article{10.5555/2946645.3007101,
author = {McQueen, James and Meil\u{a}, Marina and VanderPlas, Jacob and Zhang, Zhongyue},
title = {Megaman: Scalable Manifold Learning in Python},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Manifold Learning (ML) is a class of algorithms seeking a low-dimensional non-linear representation of high-dimensional data. Thus, ML algorithms are most applicable to high-dimensional data and require large sample sizes to accurately estimate the manifold. Despite this, most existing manifold learning implementations are not particularly scalable. Here we present a Python package that implements a variety of manifold learning algorithms in a modular and scalable fashion, using fast approximate neighbors searches and fast sparse eigendecompositions. The package incorporates theoretical advances in manifold learning, such as the unbiased Laplacian estimator introduced by Coifman and Lafon (2006) and the estimation of the embedding distortion by the Riemannian metric method introduced by Perrault-Joncas and Meila (2013). In benchmarks, even on a single-core desktop computer, our code embeds millions of data points in minutes, and takes just 200 minutes to embed the main sample of galaxy spectra from the Sloan Digital Sky Survey-- consisting of 0.6 million samples in 3750-dimensions--a task which has not previously been possible.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5176–5180},
numpages = {5},
keywords = {python, Riemannian metric, graph embedding, manifold learning, scalable methods, dimension reduction}
}

@article{10.5555/2946645.3007100,
author = {Van Laarhoven, Twan and Marchiori, Elena},
title = {Local Network Community Detection with Continuous Optimization of Conductance and Weighted Kernel K-Means},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Local network community detection is the task of finding a single community of nodes concentrated around few given seed nodes in a localized way. Conductance is a popular objective function used in many algorithms for local community detection. This paper studies a continuous relaxation of conductance. We show that continuous optimization of this objective still leads to discrete communities. We investigate the relation of conductance with weighted kernel k-means for a single community, which leads to the introduction of a new objective function, σ-conductance. Conductance is obtained by setting σ to 0. Two algorithms, EMc and PGDc, are proposed to locally optimize σ-conductance and automatically tune the parameter σ. They are based on expectation maximization and projected gradient descent, respectively. We prove locality and give performance guarantees for EMc and PGDc for a class of dense and well separated communities centered around the seeds. Experiments are conducted on networks with ground-truth communities, comparing to state-of-the-art graph diffusion algorithms for conductance optimization. On large graphs, results indicate that EMc and PGDc stay localized and produce communities most similar to the ground, while graph diffusion algorithms generate large communities of lower quality.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5148–5175},
numpages = {28},
keywords = {k-means, conductance, community detection}
}

@article{10.5555/2946645.3007099,
author = {Lin, Jiahe and Basu, Sumanta and Banerjee, Moulinath and Michailidis, George},
title = {Penalized Maximum Likelihood Estimation of Multi-Layered Gaussian Graphical Models},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Analyzing multi-layered graphical models provides insight into understanding the conditional relationships among nodes within layers after adjusting for and quantifying the effects of nodes from other layers. We obtain the penalized maximum likelihood estimator for Gaussian multi-layered graphical models, based on a computational approach involving screening of variables, iterative estimation of the directed edges between layers and undirected edges within layers and a final refitting and stability selection step that provides improved performance in finite sample settings. We establish the consistency of the estimator in a high-dimensional setting. To obtain this result, we develop a strategy that leverages the biconvexity of the likelihood function to ensure convergence of the developed iterative algorithm to a stationary point, as well as careful uniform error control of the estimates over iterations. The performance of the maximum likelihood estimator is illustrated on synthetic data.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5097–5147},
numpages = {51},
keywords = {penalized likelihood, consistency, block coordinate descent, graphical models, convergence}
}

@article{10.5555/2946645.3007098,
author = {Van Seijen, Harm and Mahmood, A. Rupam and Pilarski, Patrick M. and Machado, Marlos C. and Sutton, Richard S.},
title = {True Online Temporal-Difference Learning},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {The temporal-difference methods TD(λ) and Sarsa(λ) form a core part of modern reinforcement learning. Their appeal comes from their good performance, low computational cost, and their simple interpretation, given by their forward view. Recently, new versions of these methods were introduced, called true online TD(λ) and true online Sarsa(λ), respectively (van Seijen & Sutton, 2014). Algorithmically, these true online methods only make two small changes to the update rules of the regular methods, and the extra computational cost is negligible in most cases. However, they follow the ideas underlying the forward view much more closely. In particular, they maintain an exact equivalence with the forward view at all times, whereas the traditional versions only approximate it for small step-sizes. We hypothesize that these true online methods not only have better theoretical properties, but also dominate the regular methods empirically. In this article, we put this hypothesis to the test by performing an extensive empirical comparison. Specifically, we compare the performance of true online TD(λ)/Sarsa(λ) with regular TD(λ)/Sarsa(λ) on random MRPs, a real-world myoelectric prosthetic arm, and a domain from the Arcade Learning Environment. We use linear function approximation with tabular, binary, and non-binary features. Our results suggest that the true online methods indeed dominate the regular methods. Across all domains/representations the learning speed of the true online methods are often better, but never worse than that of the regular methods. An additional advantage is that no choice between traces has to be made for the true online methods. Besides the empirical results, we provide an in-dept analysis of the theory behind true online temporal-difference learning. In addition, we show that new true online temporal-difference methods can be derived by making changes to the online forward view and then rewriting the update equations.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5057–5096},
numpages = {40},
keywords = {eligibility traces, forward-view equivalence, temporal-difference learning}
}

@article{10.5555/2946645.3007097,
author = {Barber, Rina Foygel and Sidky, Emil Y.},
title = {MOCCA: Mirrored Convex/Concave Optimization for Nonconvex Composite Functions},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Many optimization problems arising in high-dimensional statistics decompose naturally into a sum of several terms, where the individual terms are relatively simple but the composite objective function can only be optimized with iterative algorithms. In this paper, we are interested in optimization problems of the form F(Kx) + G(x), where K is a fixed linear transformation, while F and G are functions that may be nonconvex and/or nondifferentiable. In particular, if either of the terms are nonconvex, existing alternating minimization techniques may fail to converge; other types of existing approaches may instead be unable to handle nondifferentiability. We propose the mocca (mirrored convex/concave) algorithm, a primal/dual optimization approach that takes a local convex approximation to each term at every iteration. Inspired by optimization problems arising in computed tomography (CT) imaging, this algorithm can handle a range of nonconvex composite optimization problems, and offers theoretical guarantees for convergence when the overall problem is approximately convex (that is, any concavity in one term is balanced out by convexity in the other term). Empirical results show fast convergence for several structured signal recovery problems.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5006–5056},
numpages = {51},
keywords = {total variation, MOCCA, penalized likelihood, nonconvex, ADMM, computed tomography}
}

@article{10.5555/2946645.3007096,
author = {Ieva, Francesca and Paganoni, Anna Maria and Tarabelloni, Nicholas},
title = {Covariance-Based Clustering in Multivariate and Functional Data Analysis},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {In this paper we propose a new algorithm to perform clustering of multivariate and functional data. We study the case of two populations different in their covariances, rather than in their means. The algorithm relies on a proper quantification of distance between the estimated covariance operators of the populations, and subdivides data in two groups maximising the distance between their induced covariances. The naive implementation of such an algorithm is computationally forbidding, so we propose a heuristic formulation with a much lighter complexity and we study its convergence properties, along with its computational cost. We also propose to use an enhanced estimator for the estimation of discrete covariances of functional data, namely a linear shrinkage estimator, in order to improve the precision of the clustering. We establish the effectiveness of our algorithm through applications to both synthetic data and a real data set coming from a biomedical context, showing also how the use of shrinkage estimation may lead to substantially better results.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4985–5005},
numpages = {21},
keywords = {clustering, operator distance, covariance operator, functional data analysis, shrinkage estimation}
}

@article{10.5555/2946645.3007095,
author = {Hoffman, Judy and Pathak, Deepak and Tzeng, Eric and Long, Jonathan and Guadarrama, Sergio and Darrell, Trevor and Saenko, Kate},
title = {Large Scale Visual Recognition through Adaptation Using Joint Representation and Multiple Instance Learning},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {A major barrier towards scaling visual recognition systems is the difficulty of obtaining labeled images for large numbers of categories. Recently, deep convolutional neural networks (CNNs) trained used 1.2M+ labeled images have emerged as clear winners on object classification benchmarks. Unfortunately, only a small fraction of those labels are available with bounding box localization for training the detection task and even fewer pixel level annotations are available for semantic segmentation. It is much cheaper and easier to collect large quantities of image-level labels from search engines than it is to collect scene-centric images with precisely localized labels. We develop methods for learning large scale recognition models which exploit joint training over both weak (image-level) and strong (bounding box) labels and which transfer learned perceptual representations from strongly-labeled auxiliary tasks. We provide a novel formulation of a joint multiple instance learning method that includes examples from object-centric data with image-level labels when available, and also performs domain transfer learning to improve the underlying detector representation. We then show how to use our large scale detectors to produce pixel level annotations. Using our method, we produce a >7.6K category detector and release code and models at lsda.berkeleyvision.org.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4954–4984},
numpages = {31},
keywords = {large scale learning, computer vision, transfer learning, deep learning}
}

@article{10.5555/2946645.3007094,
author = {Deshpande, Yash and Montanari, Andrea},
title = {Sparse PCA via Covariance Thresholding},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {In sparse principal component analysis we are given noisy observations of a low-rank matrix of dimension n \texttimes{} p and seek to reconstruct it under additional sparsity assumptions. In particular, we assume here each of the principal components v1, . . . , vr has at most s0 non-zero entries. We are particularly interested in the high dimensional regime wherein p is comparable to, or even much larger than n.In an in uential paper, Johnstone and Lu (2004) introduced a simple algorithm that estimates the support of the principal vectors v1, . . . , vr by the largest entries in the diagonal of the empirical covariance. This method can be shown to identify the correct support with high probability if s0 ≤ K1√n/log p, and to fail with high probability if s0 ≥ K2n/log p for two constants 0 < K1; K2 < ∞. Despite a considerable amount of work over the last ten years, no practical algorithm exists with provably better support recovery guarantees.Here we analyze a covariance thresholding algorithm that was recently proposed by Krauthgamer, Nadler, Vilenchik, et al. (2015). On the basis of numerical simulations (for the rank-one case), these authors conjectured that covariance thresholding correctly recover the support with high probability for s0 K √n (assuming n of the same order as p). We prove this conjecture, and in fact establish a more general guarantee including higher-rank as well as n much smaller than p. Recent lower bounds (Berthet and Rigollet, 2013; Ma and Wigderson, 2015) suggest that no polynomial time algorithm can do significantly better.The key technical component of our analysis develops new bounds on the norm of kernel random matrices, in regimes that were not considered before. Using these, we also derive sharp bounds for estimating the population covariance, and the principal component (with l2-loss).},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4913–4953},
numpages = {41}
}

@article{10.5555/2946645.3007093,
author = {Tai, Cheng and Weinan, E.},
title = {Multiscale Adaptive Representation of Signals: I. the Basic Framework},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We introduce a framework for designing multi-scale, adaptive, shift-invariant frames and bi-frames for representing signals. The new framework, called AdaFrame, improves over dictionary learning-based techniques in terms of computational efficiency at inference time. It improves classical multi-scale basis such as wavelet frames in terms of coding efficiency. It provides an attractive alternative to dictionary learning-based techniques for low level signal processing tasks, such as compression and denoising, as well as high level tasks, such as feature extraction for object recognition. Connections with deep convolutional networks are also discussed. In particular, the proposed framework reveals a drawback in the commonly used approach for visualizing the activations of the intermediate layers in convolutional networks, and suggests a natural alternative.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4875–4912},
numpages = {38},
keywords = {dictionary learning, AdaFrame, wavelet frames/Bi-frames}
}

@article{10.5555/2946645.3007092,
author = {Farahmand, Amir-massoud and Ghavamzadeh, Mohammad and Szepesv\'{a}ri, Csaba and Mannor, Shie},
title = {Regularized Policy Iteration with Nonparametric Function Spaces},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We study two regularization-based approximate policy iteration algorithms, namely REG-LSPI and REG-BRM, to solve reinforcement learning and planning problems in discounted Markov Decision Processes with large state and finite action spaces. The core of these algorithms are the regularized extensions of the Least-Squares Temporal Difference (LSTD) learning and Bellman Residual Minimization (BRM), which are used in the algorithms' policy evaluation steps. Regularization provides a convenient way to control the complexity of the function space to which the estimated value function belongs and as a result enables us to work with rich nonparametric function spaces. We derive efficient implementations of our methods when the function space is a reproducing kernel Hilbert space. We analyze the statistical properties of REG-LSPI and provide an upper bound on the policy evaluation error and the performance loss of the policy returned by this method. Our bound shows the dependence of the loss on the number of samples, the capacity of the function space, and some intrinsic properties of the underlying Markov Decision Process. The dependence of the policy evaluation bound on the number of samples is minimax optimal. This is the first work that provides such a strong guarantee for a nonparametric approximate policy iteration algorithm.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4809–4874},
numpages = {66},
keywords = {regularization, finite-sample analysis, reinforcement learning, approximate policy iteration, nonparametric method}
}

@article{10.5555/2946645.3007091,
author = {Mansinghka, Vikash and Shafto, Patrick and Jonas, Eric and Petschulat, Cap and Gasner, Max and Tenenbaum, Joshua B.},
title = {CrossCat: A Fully Bayesian Nonparametric Method for Analyzing Heterogeneous, High Dimensional Data},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {There is a widespread need for statistical methods that can analyze high-dimensional datasets without imposing restrictive or opaque modeling assumptions. This paper describes a domain-general data analysis method called CrossCat. CrossCat infers multiple non-overlapping views of the data, each consisting of a subset of the variables, and uses a separate nonparametric mixture to model each view. CrossCat is based on approximately Bayesian inference in a hierarchical, nonparametric model for data tables. This model consists of a Dirichlet process mixture over the columns of a data table in which each mixture component is itself an independent Dirichlet process mixture over the rows; the inner mixture components are simple parametric models whose form depends on the types of data in the table. CrossCat combines strengths of mixture modeling and Bayesian network structure learning. Like mixture modeling, CrossCat can model a broad class of distributions by positing latent variables, and produces representations that can be efficiently conditioned and sampled from for prediction. Like Bayesian networks, CrossCat represents the dependencies and independencies between variables, and thus remains accurate when there are multiple statistical signals. Inference is done via a scalable Gibbs sampling scheme; this paper shows that it works well in practice. This paper also includes empirical results on heterogeneous tabular data of up to 10 million cells, such as hospital cost and quality measures, voting records, unemployment rates, gene expression measurements, and images of handwritten digits. CrossCat infers structure that is consistent with accepted findings and common-sense knowledge in multiple domains and yields predictive accuracy competitive with generative, discriminative, and model-free alternatives.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4760–4808},
numpages = {49},
keywords = {structure learning, unsupervised learning, dirichlet processes, multivariate analysis, semi-supervised learning, Bayesian nonparametrics, Markov Chain Monte Carlo}
}

@article{10.5555/2946645.3007090,
author = {Townsend, James and Koep, Niklas and Weichwald, Sebastian},
title = {Pymanopt: A Python Toolbox for Optimization on Manifolds Using Automatic Differentiation},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Optimization on manifolds is a class of methods for optimization of an objective function, subject to constraints which are smooth, in the sense that the set of points which satisfy the constraints admits the structure of a differentiable manifold. While many optimization problems are of the described form, technicalities of differential geometry and the laborious calculation of derivatives pose a significant barrier for experimenting with these methods.We introduce PYMANOPT (available at pymanopt.github.io), a toolbox for optimization on manifolds, implemented in Python, that--similarly to the Manopt1 Matlab toolbox--implements several manifold geometries and optimization algorithms. Moreover, we lower the barriers to users further by using automated differentiation for calculating derivative information, saving users time and saving them from potential calculation and implementation errors.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4755–4759},
numpages = {5},
keywords = {non-convex optimization, manifold optimization, projection matrices, Riemannian optimization, positive definite matrices, symmetric matrices, rotation matrices}
}

@article{10.5555/2946645.3007089,
author = {Vapnik, Vladimir and Izmailov, Rauf},
title = {Synergy of Monotonic Rules},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {This article describes a method for constructing a special rule (we call it synergy rule) that uses as its input information the outputs (scores) of several monotonic rules which solve the same pattern recognition problem. As an example of scores of such monotonic rules we consider here scores of SVM classifiers.In order to construct the optimal synergy rule, we estimate the conditional probability function based on the direct problem setting, which requires solving a Fredholm integral equation. Generally, solving a Fredholm equation is an ill-posed problem. However, in our model, we look for the solution of the equation in the set of monotonic and bounded functions, which makes the problem well-posed. This allows us to solve the equation accurately even with training data sets of limited size.In order to construct a monotonic solution, we use the set of functions that belong to Reproducing Kernel Hilbert Space (RKHS) associated with the INK-spline kernel (splines with Infinite Numbers of Knots) of degree zero. The paper provides details of the methods for finding multidimensional conditional probability in a set of monotonic functions to obtain the corresponding synergy rules. We demonstrate effectiveness of such rules for 1) solving standard pattern recognition problems, 2) constructing multi-class classification rules, 3) constructing a method for knowledge transfer from multiple intelligent teachers in the LUPI paradigm.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4722–4754},
numpages = {33},
keywords = {support vector machines, knowledge transfer, classification, ensemble learning, intelligent teacher, learning theory, synergy, privileged information, kernel functions, regression, SVM+, conditional probability}
}

@article{10.5555/2946645.3007088,
author = {Hanneke, Steve},
title = {Refined Error Bounds for Several Learning Algorithms},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {This article studies the achievable guarantees on the error rates of certain learning algorithms, with particular focus on refining logarithmic factors. Many of the results are based on a general technique for obtaining bounds on the error rates of sample-consistent classifiers with monotonic error regions, in the realizable case. We prove bounds of this type expressed in terms of either the VC dimension or the sample compression size. This general technique also enables us to derive several new bounds on the error rates of general sample-consistent learning algorithms, as well as refined bounds on the label complexity of the CAL active learning algorithm. Additionally, we establish a simple necessary and sufficient condition for the existence of a distribution-free bound on the error rates of all sample-consistent learning rules, converging at a rate inversely proportional to the sample size. We also study learning in the presence of classification noise, deriving a new excess error rate guarantee for general VC classes under Tsybakov's noise condition, and establishing a simple and general necessary and sufficient condition for the minimax excess risk under bounded noise to converge at a rate inversely proportional to the sample size.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4667–4721},
numpages = {55},
keywords = {sample complexity, statistical learning theory, PAC learning, active learning, minimax analysis}
}

@article{10.5555/2946645.3007087,
author = {Romano, Simone and Vinh, Nguyen Xuan and Bailey, James and Verspoor, Karin},
title = {Adjusting for Chance Clustering Comparison Measures},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Adjusted for chance measures are widely used to compare partitions/clusterings of the same data set. In particular, the Adjusted Rand Index (ARI) based on pair-counting, and the Adjusted Mutual Information (AMI) based on Shannon information theory are very popular in the clustering community. Nonetheless it is an open problem as to what are the best application scenarios for each measure and guidelines in the literature for their usage are sparse, with the result that users often resort to using both. Generalized Information Theoretic (IT) measures based on the Tsallis entropy have been shown to link pair-counting and Shannon IT measures. In this paper, we aim to bridge the gap between adjustment of measures based on pair-counting and measures based on information theory. We solve the key technical challenge of analytically computing the expected value and variance of generalized IT measures. This allows us to propose adjustments of generalized IT measures, which reduce to well known adjusted clustering comparison measures as special cases. Using the theory of generalized IT measures, we are able to propose the following guidelines for using ARI and AMI as external validation indices: ARI should be used when the reference clustering has large equal sized clusters; AMI should be used when the reference clustering is unbalanced and there exist small clusters.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4635–4666},
numpages = {32},
keywords = {pair-counting measures, adjustment for chance, clustering comparison, generalized information theoretic measures, clustering validation}
}

@article{10.5555/2946645.3007086,
author = {Elibol, Huseyin Melih and Nguyen, Vincent and Linderman, Scott and Johnson, Matthew and Hashmi, Amna and Doshi-Velez, Finale},
title = {Cross-Corpora Unsupervised Learning of Trajectories in Autism Spectrum Disorders},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Patients with developmental disorders, such as autism spectrum disorder (ASD), present with symptoms that change with time even if the named diagnosis remains fixed. For example, language impairments may present as delayed speech in a toddler and difficulty reading in a school-age child. Characterizing these trajectories is important for early treatment. However, deriving these trajectories from observational sources is challenging: electronic health records only reflect observations of patients at irregular intervals and only record what factors are clinically relevant at the time of observation. Meanwhile, caretakers discuss daily developments and concerns on social media.In this work, we present a fully unsupervised approach for learning disease trajectories from incomplete medical records and social media posts, including cases in which we have only a single observation of each patient. In particular, we use a dynamic topic model approach which embeds each disease trajectory as a path in RD. A P\'{o}lya-gamma augmentation scheme is used to efficiently perform inference as well as incorporate multiple data sources. We learn disease trajectories from the electronic health records of 13,435 patients with ASD and the forum posts of 13,743 caretakers of children with ASD, deriving interesting clinical insights as well as good predictions.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4597–4634},
numpages = {38},
keywords = {disease progression model, dynamic topic model}
}

@article{10.5555/2946645.3007085,
author = {Wallace, Byron C. and Kuiper, Jo\"{e}l and Sharma, Aakash and Zhu, Mingxi and Marshall, Iain J.},
title = {Extracting PICO Sentences from Clinical Trial Reports Using Supervised Distant Supervision},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Systematic reviews underpin Evidence Based Medicine (EBM) by addressing precise clinical questions via comprehensive synthesis of all relevant published evidence. Authors of systematic reviews typically define a Population/Problem, Intervention, Comparator, and Outcome (a PICO criteria) of interest, and then retrieve, appraise and synthesize results from all reports of clinical trials that meet these criteria. Identifying PICO elements in the full-texts of trial reports is thus a critical yet time-consuming step in the systematic review process. We seek to expedite evidence synthesis by developing machine learning models to automatically extract sentences from articles relevant to PICO elements. Collecting a large corpus of training data for this task would be prohibitively expensive. Therefore, we derive distant supervision (DS) with which to train models using previously conducted reviews. DS entails heuristically deriving 'soft' labels from an available structured resource. However, we have access only to unstructured, free-text summaries of PICO elements for corresponding articles; we must derive from these the desired sentence-level annotations. To this end, we propose a novel method - supervised distant supervision (SDS) - that uses a small amount of direct supervision to better exploit a large corpus of distantly labeled instances by learning to pseudo-annotate articles using the available DS. We show that this approach tends to outperform existing methods with respect to automated PICO extraction.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4572–4596},
numpages = {25},
keywords = {data extraction, evidence-based medicine, distant supervision, natural language processing, text mining}
}

@article{10.5555/2946645.3007084,
author = {Samo, Yves-Laurent Kom and Roberts, Stephen J.},
title = {String and Membrane Gaussian Processes},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {In this paper we introduce a novel framework for making exact nonparametric Bayesian inference on latent functions that is particularly suitable for Big Data tasks. Firstly, we introduce a class of stochastic processes we refer to as string Gaussian processes (string GPs which are not to be mistaken for Gaussian processes operating on text). We construct string GPs so that their finite-dimensional marginals exhibit suitable local conditional independence structures, which allow for scalable, distributed, and flexible nonparametric Bayesian inference, without resorting to approximations, and while ensuring some mild global regularity constraints. Furthermore, string GP priors naturally cope with heterogeneous input data, and the gradient of the learned latent function is readily available for explanatory analysis. Secondly, we provide some theoretical results relating our approach to the standard GP paradigm. In particular, we prove that some string GPs are Gaussian processes, which provides a complementary global perspective on our framework. Finally, we derive a scalable and distributed MCMC scheme for supervised learning tasks under string GP priors. The proposed MCMC scheme has computational time complexity O(N) and memory requirement O(dN), where N is the data size and d the dimension of the input space. We illustrate the efficacy of the proposed approach on several synthetic and real-world data sets, including a data set with 6 millions input points and 8 attributes.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4485–4571},
numpages = {87},
keywords = {string Gaussian processes, scalable Bayesian nonparametrics, point process priors, Gaussian processes, reversible-jump MCMC, nonstationary kernels}
}

@article{10.5555/2946645.3007083,
author = {Maurya, Ashwini},
title = {A Well-Conditioned and Sparse Estimation of Covariance and Inverse Covariance Matrices Using a Joint Penalty},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We develop a method for estimating well-conditioned and sparse covariance and inverse covariance matrices from a sample of vectors drawn from a sub-Gaussian distribution in high dimensional setting. The proposed estimators are obtained by minimizing the quadratic loss function and joint penalty of l1 norm and variance of its eigenvalues. In contrast to some of the existing methods of covariance and inverse covariance matrix estimation, where often the interest is to estimate a sparse matrix, the proposed method is flexible in estimating both a sparse and well-conditioned covariance matrix simultaneously. The proposed estimators are optimal in the sense that they achieve the mini-max rate of estimation in operator norm for the underlying class of covariance and inverse covariance matrices. We give a very fast algorithm for computation of these covariance and inverse covariance matrices which is easily scalable to large scale data analysis problems. The simulation study for varying sample sizes and variables shows that the proposed estimators performs better than several other estimators for various choices of structured covariance and inverse covariance matrices. We also use our proposed estimator for tumor tissues classification using gene expression data and compare its performance with some other classification methods.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4457–4484},
numpages = {28},
keywords = {sparsity, eigenvalue penalty, penalized estimation}
}

@article{10.5555/2946645.3007082,
author = {Shimkin, Nahum},
title = {An Online Convex Optimization Approach to Blackwell's Approachability},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {The problem of approachability in repeated games with vector payoffs was introduced by Blackwell in the 1950s, along with geometric conditions and corresponding approachability strategies that rely on computing a sequence of direction vectors in the payoff space. For convex target sets, these vectors are obtained as projections from the current average payoff vector to the set. A recent paper by Abernethy, Batlett and Hazan (2011) proposed a class of approachability algorithms that rely on Online Linear Programming for obtaining alternative sequences of direction vectors. This is first implemented for target sets that are convex cones, and then generalized to any convex set by embedding it in a higher-dimensional convex cone. In this paper we present a more direct formulation that relies on general Online Convex Optimization (OCO) algorithms, along with basic properties of the support function of convex sets. This leads to a general class of approachability algorithms, depending on the choice of the OCO algorithm and the used norms. Blackwell's original algorithm and its convergence are recovered when Follow The Leader (or a regularized version thereof) is used for the OCO algorithm.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4434–4456},
numpages = {23},
keywords = {online convex optimization, repeated games with vector payoffs, approachability}
}

@article{10.5555/2946645.3007081,
author = {Doran, Gary and Ray, Soumya},
title = {Multiple-Instance Learning from Distributions},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We propose a new theoretical framework for analyzing the multiple-instance learning (MIL) setting. In MIL, training examples are provided to a learning algorithm in the form of labeled sets, or "bags," of instances. Applications of MIL include 3-D quantitative structure-activity relationship prediction for drug discovery and content-based image retrieval for web search. The goal of an algorithm is to learn a function that correctly labels new bags or a function that correctly labels new instances. We propose that bags should be treated as latent distributions from which samples are observed. We show that it is possible to learn accurate instance - and bag-labeling functions in this setting as well as functions that correctly rank bags or instances under weak assumptions. Additionally, our theoretical results suggest that it is possible to learn to rank efficiently using traditional, well-studied "supervised" learning approaches. We perform an extensive empirical evaluation that supports the theoretical predictions entailed by the new framework. The proposed theoretical framework leads to a better understanding of the relationship between the MI and standard supervised learning settings, and it provides new methods for learning from MI data that are more accurate, more efficient, and have better understood theoretical properties than existing MI-specific algorithms.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4384–4433},
numpages = {50},
keywords = {ranking, learning theory, classification, multiple-instance learning}
}

@article{10.5555/2946645.3007080,
author = {Klenske, Edgar D. and Hennig, Philipp},
title = {Dual Control for Approximate Bayesian Reinforcement Learning},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Control of non-episodic, finite-horizon dynamical systems with uncertain dynamics poses a tough and elementary case of the exploration-exploitation trade-off. Bayesian reinforcement learning, reasoning about the effect of actions and future observations, offers a principled solution, but is intractable. We review, then extend an old approximate approach from control theory--where the problem is known as dual control--in the context of modern regression methods, specifically generalized linear regression. Experiments on simulated systems show that this framework offers a useful approximation to the intractable aspects of Bayesian RL, producing structured exploration strategies that differ from standard RL approaches. We provide simple examples for the use of this framework in (approximate) Gaussian process regression and feedforward neural networks for the control of exploration.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4354–4383},
numpages = {30},
keywords = {control, reinforcement learning, Bayesian inference, Gaussian processes filtering}
}

@article{10.5555/2946645.3007079,
author = {Arjevani, Yossi and Shalev-Shwartz, Shai and Shamir, Ohad},
title = {On Lower and Upper Bounds in Smooth and Strongly Convex Optimization},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We develop a novel framework to study smooth and strongly convex optimization algorithms. Focusing on quadratic functions we are able to examine optimization algorithms as a recursive application of linear operators. This, in turn, reveals a powerful connection between a class of optimization algorithms and the analytic theory of polynomials whereby new lower and upper bounds are derived. Whereas existing lower bounds for this setting are only valid when the dimensionality scales with the number of iterations, our lower bound holds in the natural regime where the dimensionality is fixed. Lastly, expressing it as an optimal solution for the corresponding optimization problem over polynomials, as formulated by our framework, we present a novel systematic derivation of Nesterov's well-known Accelerated Gradient Descent method. This rather natural interpretation of AGD contrasts with earlier ones which lacked a simple, yet solid, motivation.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4303–4353},
numpages = {51},
keywords = {full gradient descent, smooth and strongly convex optimization, heavy ball method, accelerated gradient descent}
}

@article{10.5555/2946645.3007078,
author = {Gutmann, Michael U. and Corander, Jukka},
title = {Bayesian Optimization for Likelihood-Free Inference of Simulator-Based Statistical Models},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Our paper deals with inferring simulator-based statistical models given some observed data. A simulator-based model is a parametrized mechanism which specifies how data are generated. It is thus also referred to as generative model. We assume that only a finite number of parameters are of interest and allow the generative process to be very general; it may be a noisy nonlinear dynamical system with an unrestricted number of hidden variables. This weak assumption is useful for devising realistic models but it renders statistical inference very difficult. The main challenge is the intractability of the likelihood function. Several likelihood-free inference methods have been proposed which share the basic idea of identifying the parameters by finding values for which the discrepancy between simulated and observed data is small. A major obstacle to using these methods is their computational cost. The cost is largely due to the need to repeatedly simulate data sets and the lack of knowledge about how the parameters affect the discrepancy. We propose a strategy which combines probabilistic modeling of the discrepancy with optimization to facilitate likelihood-free inference. The strategy is implemented using Bayesian optimization and is shown to accelerate the inference through a reduction in the number of required simulations by several orders of magnitude.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4256–4302},
numpages = {47},
keywords = {latent variables, intractable likelihood, approximate Bayesian computation, computational efficiency, Bayesian inference}
}

@article{10.5555/2946645.3007077,
author = {Josse, Julie and Wager, Stefan},
title = {Bootstrap-Based Regularization for Low-Rank Matrix Estimation},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We develop a flexible framework for low-rank matrix estimation that allows us to transform noise models into regularization schemes via a simple bootstrap algorithm. Effectively, our procedure seeks an autoencoding basis for the observed matrix that is stable with respect to the specified noise model; we call the resulting procedure a stable autoencoder. In the simplest case, with an isotropic noise model, our method is equivalent to a classical singular value shrinkage estimator. For non-isotropic noise models--e.g., Poisson noise-- the method does not reduce to singular value shrinkage, and instead yields new estimators that perform well in experiments. Moreover, by iterating our stable autoencoding scheme, we can automatically generate low-rank estimates without specifying the target rank as a tuning parameter.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4227–4255},
numpages = {29},
keywords = {correspondence analysis, L\'{e}vy bootstrap, singular-value decomposition, empirical Bayes}
}

@article{10.5555/2946645.3007076,
author = {Kong, Yinfei and Zheng, Zemin and Lv, Jinchi},
title = {The Constrained Dantzig Selector with Enhanced Consistency},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {The Dantzig selector has received popularity for many applications such as compressed sensing and sparse modeling, thanks to its computational efficiency as a linear programming problem and its nice sampling properties. Existing results show that it can recover sparse signals mimicking the accuracy of the ideal procedure, up to a logarithmic factor of the dimensionality. Such a factor has been shown to hold for many regularization methods. An important question is whether this factor can be reduced to a logarithmic factor of the sample size in ultra-high dimensions under mild regularity conditions. To provide an affirmative answer, in this paper we suggest the constrained Dantzig selector, which has more flexible constraints and parameter space. We prove that the suggested method can achieve convergence rates within a logarithmic factor of the sample size of the oracle rates and improved sparsity, under a fairly weak assumption on the signal strength. Such improvement is significant in ultra-high dimensions. This method can be implemented efficiently through sequential linear programming. Numerical studies confirm that the sample size needed for a certain level of accuracy in these problems can be much reduced.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4205–4226},
numpages = {22},
keywords = {sparse modeling, compressed sensing, dantzig selector, finite sample, ultra-high dimensionality, regularization methods}
}

@article{10.5555/2946645.3007075,
author = {Gillberg, Jussi and Marttinen, Pekka and Pirinen, Matti and Kangas, Antti J. and Soininen, Pasi and Ali, Mehreen and Havulinna, Aki S. and J\"{a}rvelin, Marjo-Riitta and Ala-Korpela, Mika and Kaski, Samuel},
title = {Multiple Output Regression with Latent Noise},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {In high-dimensional data, structured noise caused by observed and unobserved factors affecting multiple target variables simultaneously, imposes a serious challenge for modeling, by masking the often weak signal. Therefore, (1) explaining away the structured noise in multiple-output regression is of paramount importance. Additionally, (2) assumptions about the correlation structure of the regression weights are needed. We note that both can be formulated in a natural way in a latent variable model, in which both the interesting signal and the noise are mediated through the same latent factors. Under this assumption, the signal model then borrows strength from the noise model by encouraging similar effects on correlated targets. We introduce a hyperparameter for the latent signal-to-noise ratio which turns out to be important for modelling weak signals, and an ordered infinite-dimensional shrinkage prior that resolves the rotational unidentifiability in reduced-rank regression models. Simulations and prediction experiments with metabolite, gene expression, FMRI measurement, and macroeconomic time series data show that our model equals or exceeds the state-of-the-art performance and, in particular, outperforms the standard approach of assuming independent noise and signal models.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4170–4204},
numpages = {35},
keywords = {multiple-output regression, latent variable models, nonparametric Bayes, latent signal-to-noise ratio, Bayesian reduced-rank regression, weak effects, structured noise, shrinkage priors}
}

@article{10.5555/2946645.3007074,
author = {Zhao, Jing and Sun, Shiliang},
title = {Variational Dependent Multi-Output Gaussian Process Dynamical Systems},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {This paper presents a dependent multi-output Gaussian process (GP) for modeling complex dynamical systems. The outputs are dependent in this model, which is largely different from previous GP dynamical systems. We adopt convolved multi-output GPs to model the outputs, which are provided with a flexible multi-output covariance function. We adapt the variational inference method with inducing points for learning the model. Conjugate gradient based optimization is used to solve parameters involved by maximizing the variational lower bound of the marginal likelihood. The proposed model has superiority on modeling dynamical systems under the more reasonable assumption and the fully Bayesian learning framework. Further, it can be flexibly extended to handle regression problems. We evaluate the model on both synthetic and real-world data including motion capture data, traffic flow data and robot inverse dynamics data. Various evaluation methods are taken on the experiments to demonstrate the effectiveness of our model, and encouraging results are observed.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4134–4169},
numpages = {36},
keywords = {dynamical system, multi-output modeling, Gaussian process, variational inference}
}

@article{10.5555/2946645.3007073,
author = {Avron, Haim and Sindhwani, Vikas and Yang, Jiyan and Mahoney, Michael W.},
title = {Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We consider the problem of improving the efficiency of randomized Fourier feature maps to accelerate training and testing speed of kernel methods on large data sets. These approximate feature maps arise as Monte Carlo approximations to integral representations of shift-invariant kernel functions (e.g., Gaussian kernel). In this paper, we propose to use Quasi-Monte Carlo (QMC) approximations instead, where the relevant integrands are evaluated on a low-discrepancy sequence of points as opposed to random point sets as in the Monte Carlo approach. We derive a new discrepancy measure called box discrepancy based on theoretical characterizations of the integration error with respect to a given sequence. We then propose to learn QMC sequences adapted to our setting based on explicit box discrepancy minimization. Our theoretical analyses are complemented with empirical results that demonstrate the effectiveness of classical and adaptive QMC techniques for this problem.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4096–4133},
numpages = {38}
}

@article{10.5555/2946645.3007072,
author = {Hazan, Elad and Karnin, Zohar},
title = {Volumetric Spanners: An Efficient Exploration Basis for Learning},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Numerous learning problems that contain exploration, such as experiment design, multiarm bandits, online routing, search result aggregation and many more, have been studied extensively in isolation. In this paper we consider a generic and efficiently computable method for action space exploration based on convex geometry.We define a novel geometric notion of an exploration mechanism with low variance called volumetric spanners, and give efficient algorithms to construct such spanners. We describe applications of this mechanism to the problem of optimal experiment design and the general framework for decision making under uncertainty of bandit linear optimization. For the latter we give efficient and near-optimal regret algorithm over general convex sets. Previously such results were known only for specific convex sets, or under special conditions such as the existence of an efficient self-concordant barrier for the underlying set.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4062–4095},
numpages = {34},
keywords = {volumetric spanner, linear bandits, hard margin linear regression, barycentric spanner}
}

@article{10.5555/2946645.3007071,
author = {Su, Chengwei and Borsuk, Mark E.},
title = {Improving Structure MCMC for Bayesian Networks through Markov Blanket Resampling},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Algorithms for inferring the structure of Bayesian networks from data have become an increasingly popular method for uncovering the direct and indirect influences among variables in complex systems. A Bayesian approach to structure learning uses posterior probabilities to quantify the strength with which the data and prior knowledge jointly support each possible graph feature. Existing Markov Chain Monte Carlo (MCMC) algorithms for estimating these posterior probabilities are slow in mixing and convergence, especially for large networks. We present a novel Markov blanket resampling (MBR) scheme that intermittently reconstructs the Markov blanket of nodes, thus allowing the sampler to more effectively traverse low-probability regions between local maxima. As we can derive the complementary forward and backward directions of the MBR proposal distribution, the Metropolis-Hastings algorithm can be used to account for any asymmetries in these proposals. Experiments across a range of network sizes show that the MBR scheme outperforms other state-of-the-art algorithms, both in terms of learning performance and convergence rate. In particular, MBR achieves better learning performance than the other algorithms when the number of observations is relatively small and faster convergence when the number of variables in the network is large.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4042–4061},
numpages = {20},
keywords = {probabilistic graphical models, directed acyclic graph, Markov chain Monte Carlo, Bayesian inference}
}

@article{10.5555/2946645.3007070,
author = {Gittens, Alex and Mahoney, Michael W.},
title = {Revisiting the Nystr\"{o}m Method for Improved Large-Scale Machine Learning},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We reconsider randomized algorithms for the low-rank approximation of symmetric positive semi-definite (SPSD) matrices such as Laplacian and kernel matrices that arise in data analysis and machine learning applications. Our main results consist of an empirical evaluation of the performance quality and running time of sampling and projection methods on a diverse suite of SPSD matrices. Our results highlight complementary aspects of sampling versus projection methods; they characterize the effects of common data preprocessing steps on the performance of these algorithms; and they point to important differences between uniform sampling and nonuniform sampling methods based on leverage scores. In addition, our empirical results illustrate that existing theory is so weak that it does not provide even a qualitative guide to practice. Thus, we complement our empirical results with a suite of worst-case theoretical bounds for both random sampling and random projection methods. These bounds are qualitatively superior to existing bounds--e.g., improved additive-error bounds for spectral and Frobenius norm error and relative-error bounds for trace norm error--and they point to future directions to make these algorithms useful in even larger-scale machine learning applications.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3977–4041},
numpages = {65},
keywords = {kernel methods, Nystr\"{o}m approximation, numerical linear algebra, low-rank approximation, randomized algorithms}
}

@article{10.5555/2946645.3007069,
author = {Elser, Veit},
title = {A Network That Learns Strassen Multiplication},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We study neural networks whose only non-linear components are multipliers, to test a new training rule in a context where the precise representation of data is paramount. These networks are challenged to discover the rules of matrix multiplication, given many examples. By limiting the number of multipliers, the network is forced to discover the Strassen multiplication rules. This is the mathematical equivalent of finding low rank decompositions of the n \texttimes{} n matrix multiplication tensor, Mn. We train these networks with the conservative learning rule, which makes minimal changes to the weights so as to give the correct output for each input at the time the input-output pair is received. Conservative learning needs a few thousand examples to find the rank 7 decomposition of M2, and 105 for the rank 23 decomposition of M3 (the lowest known). High precision is critical, especially for M3, to discriminate between true decompositions and "border approximations".},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3964–3976},
numpages = {13},
keywords = {sum-product networks, tensor decomposition, Strassen multiplication}
}

@article{10.5555/2946645.3007068,
author = {Sojoudi, Somayeh},
title = {Equivalence of Graphical Lasso and Thresholding for Sparse Graphs},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {This paper is concerned with the problem of finding a sparse graph capturing the conditional dependence between the entries of a Gaussian random vector, where the only available information is a sample correlation matrix. A popular approach to address this problem is the graphical lasso technique, which employs a sparsity-promoting regularization term. This paper derives a simple condition under which the computationally-expensive graphical lasso behaves the same as the simple heuristic method of thresholding. This condition depends only on the solution of graphical lasso and makes no direct use of the sample correlation matrix or the regularization coefficient. It is proved that this condition is always satisfied if the solution of graphical lasso is close to its first-order Taylor approximation or equivalently the regularization term is relatively large. This condition is tested on several random problems, and it is shown that graphical lasso and the thresholding method lead to highly similar results in the case where a sparse graph is sought. We also conduct two case studies on brain connectivity networks of twenty subjects based on fMRI data and the topology identification of electrical circuits to support the findings of this work on the similarity of graphical lasso and thresholding.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3943–3963},
numpages = {21},
keywords = {brain connectivity networks, graphical models, electrical circuits, sparse graphs, graphical lasso}
}

@article{10.5555/2946645.3007067,
author = {Lapuschkin, Sebastian and Binder, Alexander and Montavon, Gr\'{e}goire and M\"{u}ller, Klaus-Robert and Samek, Wojciech},
title = {The LRP Toolbox for Artificial Neural Networks},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {The Layer-wise Relevance Propagation (LRP) algorithm explains a classifier's prediction specific to a given data point by attributing relevance scores to important components of the input by using the topology of the learned model itself. With the LRP Toolbox we provide platform-agnostic implementations for explaining the predictions of pretrained state of the art Caffe networks and stand-alone implementations for fully connected Neural Network models. The implementations for Matlab and python shall serve as a playing field to familiarize oneself with the LRP algorithm and are implemented with readability and transparency in mind. Models and data can be imported and exported using raw text formats, Matlab's .mat files and the .npy format for numpy or plain text.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3938–3942},
numpages = {5},
keywords = {deep learning, artificial neural networks, explaining classifiers, computer vision, layer-wise relevance propagation}
}

@article{10.5555/2946645.3007066,
author = {Tang, Lu and Song, Peter X .K.},
title = {Fused Lasso Approach in Regression Coefficients Clustering: Learning Parameter Heterogeneity in Data Integration},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {As data sets of related studies become more easily accessible, combining data sets of similar studies is often undertaken in practice to achieve a larger sample size and higher power. A major challenge arising from data integration pertains to data heterogeneity in terms of study population, study design, or study coordination. Ignoring such heterogeneity in data analysis may result in biased estimation and misleading inference. Traditional techniques of remedy to data heterogeneity include the use of interactions and random effects, which are inferior to achieving desirable statistical power or providing a meaningful interpretation, especially when a large number of smaller data sets are combined. In this paper, we propose a regularized fusion method that allows us to identify and merge inter-study homogeneous parameter clusters in regression analysis, without the use of hypothesis testing approach. Using the fused lasso, we establish a computationally efficient procedure to deal with large-scale integrated data. Incorporating the estimated parameter ordering in the fused lasso facilitates computing speed with no loss of statistical power. We conduct extensive simulation studies and provide an application example to demonstrate the performance of the new method with a comparison to the conventional methods.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3915–3937},
numpages = {23},
keywords = {fused lasso, data integration, extended BIC, generalized linear models}
}

@article{10.5555/2946645.3007065,
author = {Ahmed, Bilal and Thesen, Thomas and Blackmon, Karen E. and Kuzniekcy, Ruben and Devinsky, Orrin and Brodley, Carla E.},
title = {Decrypting "Cryptogenic" Epilepsy: Semi-Supervised Hierarchical Conditional Random Fields for Detecting Cortical Lesions in MRI-Negative Patients},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Focal cortical dysplasia (FCD) is the most common cause of pediatric epilepsy and the third most common cause in adults with treatment-resistant epilepsy. Surgical resection of the lesion is the most effective treatment to stop seizures. Technical advances in MRI have revolutionized the diagnosis of FCD, leading to high success rates for resective surgery. However, 45% of histologically confirmed FCD patients have normal MRIs (MRI-negative). Without a visible lesion, the success rate of surgery drops from 66% to 29%. In this work, we cast the problem of detecting potential FCD lesions using MRI scans of MRI-negative patients in an image segmentation framework based on hierarchical conditional random fields (HCRF). We use surface based morphometry to model the cortical surface as a two-dimensional surface which is then segmented at multiple scales to extract superpixels of different sizes. Each superpixel is assigned an outlier score by comparing it to a control population. The lesion is detected by fusing the outlier probabilities across multiple scales using a tree-structured HCRF. The proposed method achieves a higher detection rate, with superior recall and precision on a sample of twenty MRI-negative FCD patients as compared to a baseline across four morphological features and their combinations.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3885–3914},
numpages = {30},
keywords = {epilepsy, LOF, conditional random fields, focal cortical dysplasia}
}

@article{10.5555/2946645.3007064,
author = {De Castro, Yohann and Gassiat, \'{E}lisabeth and Lacour, Claire},
title = {Minimax Adaptive Estimation of Nonparametric Hidden Markov Models},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We consider stationary hidden Markov models with finite state space and nonparametric modeling of the emission distributions. It has remained unknown until very recently that such models are identifiable. In this paper, we propose a new penalized least-squares estimator for the emission distributions which is statistically optimal and practically tractable. We prove a non asymptotic oracle inequality for our nonparametric estimator of the emission distributions. A consequence is that this new estimator is rate minimax adaptive up to a logarithmic term. Our methodology is based on projections of the emission distributions onto nested subspaces of increasing complexity. The popular spectral estimators are unable to achieve the optimal rate but may be used as initial points in our procedure. Simulations are given that show the improvement obtained when applying the least-squares minimization consecutively to the spectral estimation.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3842–3884},
numpages = {43},
keywords = {penalized least-squares, minimax adaptive estimation, oracle inequality, hidden Markov models, nonparametric estimation}
}

@article{10.5555/2946645.3007063,
author = {Wainberg, Michael and Alipanahi, Babak and Frey, Brendan J.},
title = {Are Random Forests Truly the Best Classifiers?},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {The JMLR study Do we need hundreds of classifiers to solve real world classification problems? benchmarks 179 classifiers in 17 families on 121 data sets from the UCI repository and claims that "the random forest is clearly the best family of classifier". In this response, we show that the study's results are biased by the lack of a held-out test set and the exclusion of trials with errors. Further, the study's own statistical tests indicate that random forests do not have significantly higher percent accuracy than support vector machines and neural networks, calling into question the conclusion that random forests are the best classifiers.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3837–3841},
numpages = {5},
keywords = {classification, random forests, neural networks, support vector machines, benchmarking}
}

@article{10.5555/2946645.3007062,
author = {Gupta, Maya and Cotter, Andrew and Pfeifer, Jan and Voevodski, Konstantin and Canini, Kevin and Mangylov, Alexander and Moczydlowski, Wojciech and Van Esbroeck, Alexander},
title = {Monotonic Calibrated Interpolated Look-up Tables},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Real-world machine learning applications may have requirements beyond accuracy, such as fast evaluation times and

license_type: permissive

branch_name: refs/heads/main

extension: bib