text:
1532-4435},
abstract = {We provide theoretical and empirical evidence for a type of asymmetry between causes and effects that is present when these are related via linear models contaminated with additive non-Gaussian noise. Assuming that the causes and the effects have the same distribution, we show that the distribution of the residuals of a linear fit in the anti-causal direction is closer to a Gaussian than the distribution of the residuals in the causal direction. This Gaussianization effect is characterized by reduction of the magnitude of the high-order cumulants and by an increment of the differential entropy of the residuals. The problem of non-linear causal inference is addressed by performing an embedding in an expanded feature space, in which the relation between causes and effects can be assumed to be linear. The effectiveness of a method to discriminate between causes and effects based on this type of asymmetry is illustrated in a variety of experiments using different measures of Gaussianity. The proposed method is shown to be competitive with state-of-the-art techniques for causal inference.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {939–977},
numpages = {39},
keywords = {cause-effect pairs, Gaussianity of the residuals, causal inference}
}

@article{10.5555/2946645.2946672,
author = {Chen, Yudong and Xu, Jiaming},
title = {Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We consider two closely related problems: planted clustering and submatrix localization. In the planted clustering problem, a random graph is generated based on an underlying cluster structure of the nodes; the task is to recover these clusters given the graph. The submatrix localization problem concerns locating hidden submatrices with elevated means inside a large real-valued random matrix. Of particular interest is the setting where the number of clusters/submatrices is allowed to grow unbounded with the problem size. These formulations cover several classical models such as planted clique, planted densest subgraph, planted partition, planted coloring, and the stochastic block model, which are widely used for studying community detection, graph clustering and bi-clustering.For both problems, we show that the space of the model parameters (cluster/submatrix size, edge probabilities and the mean of the submatrices) can be partitioned into four disjoint regions corresponding to decreasing statistical and computational complexities: (1) the impossible regime, where all algorithms fail; (2) the hard regime, where the computationally expensive Maximum Likelihood Estimator (MLE) succeeds; (3) the easy regime, where the polynomial-time convexified MLE succeeds; (4) the simple regime, where a local counting/thresholding procedure succeeds. Moreover, we show that each of these algorithms provably fails in the harder regimes.Our results establish the minimax recovery limits, which are tight up to universal constants and hold even with a growing number of clusters/submatrices, and provide order-wise stronger performance guarantees for polynomial-time algorithms than previously known. Our study demonstrates the tradeoffs between statistical and computational considerations, and suggests that the minimax limits may not be achievable by polynomial-time algorithms.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {882–938},
numpages = {57},
keywords = {minimax recovery, graph clustering, bi-clustering, planted coloring, planted clique, submatrix localization, convex relaxation, computational hardness, planted partition}
}

@article{10.5555/2946645.2946671,
author = {Mentch, Lucas and Hooker, Giles},
title = {Quantifying Uncertainty in Random Forests via Confidence Intervals and Hypothesis Tests},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {This work develops formal statistical inference procedures for predictions generated by supervised learning ensembles. Ensemble methods based on bootstrapping, such as bagging and random forests, have improved the predictive accuracy of individual trees, but fail to provide a framework in which distributional results can be easily determined. Instead of aggregating full bootstrap samples, we consider predicting by averaging over trees built on subsamples of the training set and demonstrate that the resulting estimator takes the form of a U-statistic. As such, predictions for individual feature vectors are asymptotically normal, allowing for confidence intervals to accompany predictions. In practice, a subset of subsamples is used for computational speed; here our estimators take the form of incomplete U-statistics and equivalent results are derived. We further demonstrate that this setup provides a framework for testing the significance of features. Moreover, the internal estimation method we develop allows us to estimate the variance parameters and perform these inference procedures at no additional computational cost. Simulations and illustrations on a real data set are provided.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {841–881},
numpages = {41},
keywords = {random forests, bagging, u-statistics, trees, subbagging}
}

@article{10.5555/2946645.2946670,
author = {Minh, H\`{a} Quang and Bazzani, Loris and Murino, Vittorio},
title = {A Unifying Framework in Vector-Valued Reproducing Kernel Hilbert Spaces for Manifold Regularization and Co-Regularized Multi-View Learning},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {This paper presents a general vector-valued reproducing kernel Hilbert spaces (RKHS) framework for the problem of learning an unknown functional dependency between a structured input space and a structured output space. Our formulation encompasses both Vector-valued Manifold Regularization and Co-regularized Multi-view Learning, providing in particular a unifying framework linking these two important learning approaches. In the case of the least square loss function, we provide a closed form solution, which is obtained by solving a system of linear equations. In the case of Support Vector Machine (SVM) classification, our formulation generalizes in particular both the binary Laplacian SVM to the multi-class, multi-view settings and the multi-class Simplex Cone SVM to the semi-supervised, multi-view settings. The solution is obtained by solving a single quadratic optimization problem, as in standard SVM, via the Sequential Minimal Optimization (SMO) approach. Empirical results obtained on the task of object recognition, using several challenging data sets, demonstrate the competitiveness of our algorithms compared with other state-of-the-art methods.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {769–840},
numpages = {72},
keywords = {multi-view learning, multi-kernel learning, multi-modality learning, multi-class classification, vector-valued RKHS, manifold regularization, kernel methods}
}

@article{10.5555/2946645.2946669,
author = {Valenzuela, Michael L. and Rozenblit, Jerzy W.},
title = {Learning Using Anti-Training with Sacrificial Data},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Traditionally the machine-learning community has viewed the No Free Lunch (NFL) theorems for search and optimization as a limitation. We review, analyze, and unify the NFL theorem with the perspectives of "blind" search and meta-learning to arrive at necessary conditions for improving black-box optimization. We survey meta-learning literature to determine when and how meta-learning can benefit machine learning. Then, we generalize meta-learning in the context of the NFL theorems, to arrive at a novel technique called anti-training with sacrificial data (ATSD). Our technique applies at the meta level to arrive at domain specific algorithms. We also show how to generate sacrificial data. An extensive case study is presented along with simulated annealing results to demonstrate the efficacy of the ATSD method.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {727–768},
numpages = {42},
keywords = {anti-training, machine learning, sacrificial data, meta optimization, no free lunch, optimization}
}

@article{10.5555/2946645.2946668,
author = {Adamskiy, Dmitry and Koolen, Wouter M. and Chernov, Alexey and Vovk, Vladimir},
title = {A Closer Look at Adaptive Regret},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {For the prediction with expert advice setting, we consider methods to construct algorithms that have low adaptive regret. The adaptive regret of an algorithm on a time interval [t1, t2] is the loss of the algorithm minus the loss of the best expert over that interval. Adaptive regret measures how well the algorithm approximates the best expert locally, and so is different from, although closely related to, both the classical regret, measured over an initial time interval [1, t], and the tracking regret, where the algorithm is compared to a good sequence of experts over [1, t].We investigate two existing intuitive methods for deriving algorithms with low adaptive regret, one based on specialist experts and the other based on restarts. Quite surprisingly, we show that both methods lead to the same algorithm, namely Fixed Share, which is known for its tracking regret. We provide a thorough analysis of the adaptive regret of Fixed Share. We obtain the exact worst-case adaptive regret for Fixed Share, from which the classical tracking bounds follow. We prove that Fixed Share is optimal for adaptive regret: the worst-case adaptive regret of any algorithm is at least that of an instance of Fixed Share.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {706–726},
numpages = {21},
keywords = {specialist experts, online learning, fixed share, adaptive regret}
}

@article{10.5555/2946645.2946667,
author = {Kpotufe, Samory and Boularias, Abdeslam and Schultz, Thomas and Kim, Kyoungok},
title = {Gradients Weights Improve Regression and Classification},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {In regression problems over Rd, the unknown function f often varies more in some coordinates than in others. We show that weighting each coordinate i according to an estimate of the variation of f along coordinate i - e.g. the L1 norm of the ith-directional derivative of f - is an efficient way to significantly improve the performance of distance-based regressors such as kernel and k- NN regressors. The approach, termed Gradient Weighting (GW), consists of a first pass regression estimate fn which serves to evaluate the directional derivatives of f, and a second-pass regression estimate on the re-weighted data. The GW approach can be instantiated for both regression and classification, and is grounded in strong theoretical principles having to do with the way regression bias and variance are affected by a generic feature-weighting scheme. These theoretical principles provide further technical foundation for some existing feature-weighting heuristics that have proved successful in practice.We propose a simple estimator of these derivative norms and prove its consistency. The proposed estimator computes efficiently and easily extends to run online. We then derive a classification version of the GW approach which evaluates on real-worlds datasets with as much success as its regression counterpart.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {672–705},
numpages = {34},
keywords = {metric learning, nonparametric learning, feature weighting, feature selection, nonparametric sparsity}
}

@article{10.5555/2946645.2946666,
author = {Read, Jesse and Reutemann, Peter and Pfahringer, Bernhard and Holmes, Geoff},
title = {Meka: A Multi-Label/Multi-Target Extension to Weka},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Multi-label classification has rapidly attracted interest in the machine learning literature, and there are now a large number and considerable variety of methods for this type of learning. We present MEKA: an open-source Java framework based on the well-known WEKA library. MEKA provides interfaces to facilitate practical application, and a wealth of multi-label classifiers, evaluation metrics, and tools for multi-label experiments and development. It supports multi-label and multi-target data, including in incremental and semi-supervised contexts.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {667–671},
numpages = {5},
keywords = {classification, multi-label, learning, incremental, multi-target}
}

@article{10.5555/2946645.2946665,
author = {Kadri, Hachem and Duflos, Emmanuel and Preux, Philippe and Canu, St\'{e}phane and Rakotomamonjy, Alain and Audiffren, Julien},
title = {Operator-Valued Kernels for Learning from Functional Response Data},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {In this paper we consider the problems of supervised classification and regression in the case where attributes and labels are functions: a data is represented by a set of functions, and the label is also a function. We focus on the use of reproducing kernel Hilbert space theory to learn from such functional data. Basic concepts and properties of kernel-based learning are extended to include the estimation of function-valued functions. In this setting, the representer theorem is restated, a set of rigorously defined infinite-dimensional operator-valued kernels that can be valuably applied when the data are functions is described, and a learning algorithm for nonlinear functional data analysis is introduced. The methodology is illustrated through speech and audio signal processing experiments.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {613–666},
numpages = {54},
keywords = {function-valued reproducing kernel Hilbert spaces, operator-valued kernels, audio signal processing, nonlinear functional data analysis}
}

@article{10.5555/2946645.2946664,
author = {Lazaric, Alessandro and Ghavamzadeh, Mohammad and Munos, R\'{e}mi},
title = {Analysis of Classification-Based Policy Iteration Algorithms},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We introduce a variant of the classification-based approach to policy iteration which uses a cost-sensitive loss function weighting each classification mistake by its actual regret, that is, the difference between the action-value of the greedy action and of the action chosen by the classifier. For this algorithm, we provide a full finite-sample analysis. Our results state a performance bound in terms of the number of policy improvement steps, the number of rollouts used in each iteration, the capacity of the considered policy space (classifier), and a capacity measure which indicates how well the policy space can approximate policies that are greedy with respect to any of its members. The analysis reveals a tradeoff between the estimation and approximation errors in this classification-based policy iteration setting. Furthermore it confirms the intuition that classification-based policy iteration algorithms could be favorably compared to value-based approaches when the policies can be approximated more easily than their corresponding value functions. We also study the consistency of the algorithm when there exists a sequence of policy spaces with increasing capacity.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {583–612},
numpages = {30},
keywords = {reinforcement learning, finite-sample analysis, policy iteration, classification-based approach to policy iteration}
}

@article{10.5555/2946645.2946663,
author = {Hsu, Daniel and Sabato, Sivan},
title = {Loss Minimization and Parameter Estimation with Heavy Tails},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {This work studies applications and generalizations of a simple estimation technique that provides exponential concentration under heavy-tailed distributions, assuming only bounded low-order moments. We show that the technique can be used for approximate minimization of smooth and strongly convex losses, and specifically for least squares linear regression. For instance, our d-dimensional estimator requires just O(d log(1/δ)) random samples to obtain a constant factor approximation to the optimal least squares loss with probability 1-δ, without requiring the covariates or noise to be bounded or subgaussian. We provide further applications to sparse linear regression and low-rank covariance matrix estimation with similar allowances on the noise and covariate distributions. The core technique is a generalization of the median-of-means estimator to arbitrary metric spaces.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {543–582},
numpages = {40},
keywords = {least squares, heavy-tailed distributions, unbounded losses, linear regression}
}

@article{10.5555/2946645.2946662,
author = {Kairouz, Peter and Oh, Sewoong and Viswanath, Pramod},
title = {Extremal Mechanisms for Local Differential Privacy},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Local differential privacy has recently surfaced as a strong measure of privacy in contexts where personal information remains private even from data analysts. Working in a setting where both the data providers and data analysts want to maximize the utility of statistical analyses performed on the released data, we study the fundamental trade-off between local differential privacy and utility. This trade-off is formulated as a constrained optimization problem: maximize utility subject to local differential privacy constraints. We introduce a combinatorial family of extremal privatization mechanisms, which we call staircase mechanisms, and show that it contains the optimal privatization mechanisms for a broad class of information theoretic utilities such as mutual information and f-divergences. We further prove that for any utility function and any privacy level, solving the privacy-utility maximization problem is equivalent to solving a finite-dimensional linear program, the outcome of which is the optimal staircase mechanism. However, solving this linear program can be computationally expensive since it has a number of variables that is exponential in the size of the alphabet the data lives in. To account for this, we show that two simple privatization mechanisms, the binary and randomized response mechanisms, are universally optimal in the low and high privacy regimes, and well approximate the intermediate regime.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {492–542},
numpages = {51},
keywords = {f-divergences, statistical inference, local differential privacy, information theoretic utilities, estimation, privacy-preserving machine learning algorithms, mutual information, hypothesis testing}
}

@article{10.5555/2946645.2946661,
author = {Zhang, Xiang and Wu, Yichao and Wang, Lan and Li, Runze},
title = {A Consistent Information Criterion for Support Vector Machines in Diverging Model Spaces},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Information criteria have been popularly used in model selection and proved to possess nice theoretical properties. For classification, Claeskens et al. (2008) proposed support vector machine information criterion for feature selection and provided encouraging numerical evidence. Yet no theoretical justification was given there. This work aims to fill the gap and to provide some theoretical justifications for support vector machine information criterion in both fixed and diverging model spaces. We first derive a uniform convergence rate for the support vector machine solution and then show that a modification of the support vector machine information criterion achieves model selection consistency even when the number of features diverges at an exponential rate of the sample size. This consistency result can be further applied to selecting the optimal tuning parameter for various penalized support vector machine methods. Finite-sample performance of the proposed information criterion is investigated using Monte Carlo studies and one real-world gene selection problem.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {466–491},
numpages = {26},
keywords = {diverging model spaces, Bayesian information criterion, support vector machines, feature selection}
}

@article{10.5555/2946645.2946660,
author = {Lee, Joonseok and Kim, Seungyeon and Lebanon, Guy and Singer, Yoram and Bengio, Samy},
title = {LLORMA: Local Low-Rank Matrix Approximation},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Matrix approximation is a common tool in recommendation systems, text mining, and computer vision. A prevalent assumption in constructing matrix approximations is that the partially observed matrix is low-rank. In this paper, we propose, analyze, and experiment with two procedures, one parallel and the other global, for constructing local matrix approximations. The two approaches approximate the observed matrix as a weighted sum of low-rank matrices. These matrices are limited to a local region of the observed matrix. We analyze the accuracy of the proposed local low-rank modeling. Our experiments show improvements in prediction accuracy over classical approaches for recommendation tasks.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {442–465},
numpages = {24},
keywords = {non-parametric methods, collaborative filtering, matrix approximation, kernel smoothing, recommender systems}
}

@article{10.5555/2946645.2946659,
author = {Ramaswamy, Harish G. and Agarwal, Shivani},
title = {Convex Calibration Dimension for Multiclass Loss Matrices},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We study consistency properties of surrogate loss functions for general multiclass learning problems, defined by a general multiclass loss matrix. We extend the notion of classification calibration, which has been studied for binary and multiclass 0-1 classification problems (and for certain other specific learning problems), to the general multiclass setting, and derive necessary and sufficient conditions for a surrogate loss to be calibrated with respect to a loss matrix in this setting. We then introduce the notion of convex calibration dimension of a multiclass loss matrix, which measures the smallest 'size' of a prediction space in which it is possible to design a convex surrogate that is calibrated with respect to the loss matrix. We derive both upper and lower bounds on this quantity, and use these results to analyze various loss matrices. In particular, we apply our framework to study various subset ranking losses, and use the convex calibration dimension as a tool to show both the existence and non-existence of various types of convex calibrated surrogates for these losses. Our results strengthen recent results of Duchi et al. (2010) and Calauz\`{e}nes et al. (2012) on the non-existence of certain types of convex calibrated surrogates in subset ranking. We anticipate the convex calibration dimension may prove to be a useful tool in the study and design of surrogate losses for general multiclass learning problems.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {397–441},
numpages = {45},
keywords = {surrogate loss, loss matrix, convex surrogates, subset ranking, multiclass loss, classification calibration, calibrated surrogates, statistical consistency}
}

@article{10.5555/2946645.2946658,
author = {Tamar, Aviv and Di Castro, Dotan and Mannor, Shie},
title = {Learning the Variance of the Reward-to-Go},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {In Markov decision processes (MDPs), the variance of the reward-to-go is a natural measure of uncertainty about the long term performance of a policy, and is important in domains such as finance, resource allocation, and process control. Currently however, there is no tractable procedure for calculating it in large scale MDPs. This is in contrast to the case of the expected reward-to-go, also known as the value function, for which effective simulation-based algorithms are known, and have been used successfully in various domains. In this paper we extend temporal difference (TD) learning algorithms to estimating the variance of the reward-to-go for a fixed policy. We propose variants of both TD(0) and LSTD(λ) with linear function approximation, prove their convergence, and demonstrate their utility in an option pricing problem. Our results show a dramatic improvement in terms of sample efficiency over standard Monte-Carlo methods, which are currently the state-of-the-art.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {361–396},
numpages = {36},
keywords = {variance estimation, reinforcement learning, Markov decision processes, simulation, temporal differences}
}

@article{10.5555/2946645.2946657,
author = {Wang, Yu-Xiang and Xu, Huan},
title = {Noisy Sparse Subspace Clustering},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {This paper considers the problem of subspace clustering under noise. Specifically, we study the behavior of Sparse Subspace Clustering (SSC) when either adversarial or random noise is added to the unlabeled input data points, which are assumed to be in a union of low-dimensional subspaces. We show that a modified version of SSC is provably effective in correctly identifying the underlying subspaces, even with noisy data. This extends theoretical guarantee of this algorithm to more practical settings and provides justification to the success of SSC in a class of real applications.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {320–360},
numpages = {41},
keywords = {stability, subspace clustering, robustness, sparse, compressive sensing}
}

@article{10.5555/2946645.2946656,
author = {Yuille, Alan and Mottaghi, Roozbeh},
title = {Complexity of Representation and Inference in Compositional Models with Part Sharing},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {This paper performs a complexity analysis of a class of serial and parallel compositional models of multiple objects and shows that they enable efficient representation and rapid inference. Compositional models are generative and represent objects in a hierarchically distributed manner in terms of parts and subparts, which are constructed recursively by part-subpart compositions. Parts are represented more coarsely at higher level of the hierarchy, so that the upper levels give coarse summary descriptions (e.g., there is a horse in the image) while the lower levels represents the details (e.g., the positions of the legs of the horse). This hierarchically distributed representation obeys the executive summary principle, meaning that a high level executive only requires a coarse summary description and can, if necessary, get more details by consulting lower level executives. The parts and subparts are organized in terms of hierarchical dictionaries which enables part sharing between different objects allowing efficient representation of many objects. The first main contribution of this paper is to show that compositional models can be mapped onto a parallel visual architecture similar to that used by bio-inspired visual models such as deep convolutional networks but more explicit in terms of representation, hence enabling part detection as well as object detection, and suitable for complexity analysis. Inference algorithms can be run on this architecture to exploit the gains caused by part sharing and executive summary. Effectively, this compositional architecture enables us to perform exact inference simultaneously over a large class of generative models of objects. The second contribution is an analysis of the complexity of compositional models in terms of computation time (for serial computers) and numbers of nodes (e.g., "neurons") for parallel computers. In particular, we compute the complexity gains by part sharing and executive summary and their dependence on how the dictionary scales with the level of the hierarchy. We explore three regimes of scaling behavior where the dictionary size (i) increases exponentially with the level of the hierarchy, (ii) is determined by an unsupervised compositional learning algorithm applied to real data, (iii) decreases exponentially with scale. This analysis shows that in some regimes the use of shared parts enables algorithms which can perform inference in time linear in the number of levels for an exponential number of objects. In other regimes part sharing has little advantage for serial computers but can enable linear processing on parallel computers.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {292–319},
numpages = {28},
keywords = {hierarchical architectures, object detection, part sharing, compositional models}
}

@article{10.5555/2946645.2946655,
author = {Chen, Yutian and Bornn, Luke and De Freitas, Nando and Eskelin, Mareija and Fang, Jing and Welling, Max},
title = {Herded Gibbs Sampling},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {The Gibbs sampler is one of the most popular algorithms for inference in statistical models. In this paper, we introduce a herding variant of this algorithm, called herded Gibbs, that is entirely deterministic. We prove that herded Gibbs has an O(1/T) convergence rate for models with independent variables and for fully connected probabilistic graphical models. Herded Gibbs is shown to outperform Gibbs in the tasks of image denoising with MRFs and named entity recognition with CRFs. However, the convergence for herded Gibbs for sparsely connected probabilistic graphical models is still an open problem.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {263–291},
numpages = {29},
keywords = {deterministic sampling, Gibbs sampling, herding}
}

@article{10.5555/2946645.2946654,
author = {Rieck, Konrad and Wressnegger, Christian},
title = {Harry: A Tool for Measuring String Similarity},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {Comparing strings and assessing their similarity is a basic operation in many application domains of machine learning, such as in information retrieval, natural language processing and bioinformatics. The practitioner can choose from a large variety of available similarity measures for this task, each emphasizing different aspects of the string data. In this article, we present Harry, a small tool specifically designed for measuring the similarity of strings. Harry implements over 20 similarity measures, including common string distances and string kernels, such as the Levenshtein distance and the Subsequence kernel. The tool has been designed with efficiency in mind and allows for multi-threaded as well as distributed computing, enabling the analysis of large data sets of strings. Harry supports common data formats and thus can interface with analysis environments, such as Matlab, Pylab and Weka.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {258–262},
numpages = {5},
keywords = {string distances, similarity measures for strings, string kernels}
}

@article{10.5555/2946645.2946653,
author = {G\"{u}l\c{c}ehre, \c{C}aundefinedlar and Bengio, Yoshua},
title = {Knowledge Matters: Importance of Prior Information for Optimization},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {We explored the effect of introducing prior knowledge into the intermediate level of deep supervised neural networks on two tasks. On a task we designed, all black-box state-of-the-art machine learning algorithms which we tested, failed to generalize well. We motivate our work from the hypothesis that, there is a training barrier involved in the nature of such tasks, and that humans learn useful intermediate concepts from other individuals by using a form of supervision or guidance using a curriculum. Our results provide a positive evidence in favor of this hypothesis. In our experiments, we trained a two-tiered MLP architecture on a dataset for which each input image contains three sprites, and the binary target class is 1 if all of three shapes belong to the same category and otherwise the class is 0. In terms of generalization, black-box machine learning algorithms could not perform better than chance on this task. Standard deep supervised neural networks also failed to generalize. However, using a particular structure and guiding the learner by providing intermediate targets in the form of intermediate concepts (the presence of each object) allowed us to solve the task efficiently. We obtained much better than chance, but imperfect results by exploring different architectures and optimization variants. This observation might be an indication of optimization diculty when the neural network trained without hints on this task. We hypothesize that the learning difficulty is due to the composition of two highly non-linear tasks. Our findings are also consistent with the hypotheses on cultural learning inspired by the observations of training of neural networks sometimes getting stuck, even though good solutions exist, both in terms of training and generalization error.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {226–257},
numpages = {32},
keywords = {evolution of culture, curriculum learning, neural networks, deep learning, training with hints, optimization}
}

@article{10.5555/2946645.2946652,
author = {Teh, Yee Whye and Thiery, Alexandre H. and Vollmer, Sebastian J.},
title = {Consistency and Fluctuations for 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 expensive. Both the calculation of the acceptance probability and the creation of informed proposals usually require an iteration through the whole data set. The recently proposed stochastic gradient Langevin dynamics (SGLD) method circumvents this problem by generating proposals which are only based on a subset of the data, by skipping the accept-reject step and by using decreasing step-sizes sequence (δm)m≥0.We provide in this article a rigorous mathematical framework for analysing this algorithm. We prove that, under verifiable assumptions, the algorithm is consistent, satisfies a central limit theorem (CLT) and its asymptotic bias-variance decomposition can be characterized by an explicit functional of the step-sizes sequence (δm)m≥0. We leverage this analysis to give practical recommendations for the notoriously difficult tuning of this algorithm: it is asymptotically optimal to use a step-size sequence of the type δm = m-1/3, leading to an algorithm whose mean squared error (MSE) decreases at rate O(m-1/3).},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {193–225},
numpages = {33},
keywords = {Markov chain Monte Carlo, Langevin dynamics, big data}
}

@article{10.5555/2946645.2946651,
author = {Collier, Olivier and Dalalyan, Arnak S.},
title = {Minimax Rates in Permutation Estimation for Feature Matching},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {The problem of matching two sets of features appears in various tasks of computer vision and can be often formalized as a problem of permutation estimation. We address this problem from a statistical point of view and provide a theoretical analysis of the accuracy of several natural estimators. To this end, the minimax rate of separation is investigated and its expression is obtained as a function of the sample size, noise level and dimension of the features. We consider the cases of homoscedastic and heteroscedastic noise and establish, in each case, tight upper bounds on the separation distance of several estimators. These upper bounds are shown to be unimprovable both in the homoscedastic and heteroscedastic settings. Interestingly, these bounds demonstrate that a phase transition occurs when the dimension d of the features is of the order of the logarithm of the number of features n. For d = O(log n), the rate is dimension free and equals σ(log n)1/2, where σ is the noise level. In contrast, when d is larger than c log n for some constant c < 0, the minimax rate increases with d and is of the order of σ(d log n)1/4. We also discuss the computational aspects of the estimators and provide empirical evidence of their consistency on synthetic data. Finally, we show that our results extend to more general matching criteria.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {162–192},
numpages = {31},
keywords = {minimax rate of separation, feature matching, permutation estimation}
}

@article{10.5555/2946645.2946650,
author = {Benavoli, Alessio and Corani, Giorgio and Mangili, Francesca},
title = {Should We Really Use Post-Hoc Tests Based on Mean-Ranks?},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {The statistical comparison of multiple algorithms over multiple data sets is fundamental in machine learning. This is typically carried out by the Friedman test. When the Friedman test rejects the null hypothesis, multiple comparisons are carried out to establish which are the significant differences among algorithms. The multiple comparisons are usually performed using the mean-ranks test. The aim of this technical note is to discuss the inconsistencies of the mean-ranks post-hoc test with the goal of discouraging its use in machine learning as well as in medicine, psychology, etc. We show that the outcome of the mean-ranks test depends on the pool of algorithms originally included in the experiment. In other words, the outcome of the comparison between algorithms A and B depends also on the performance of the other algorithms included in the original experiment. This can lead to paradoxical situations. For instance the difference between A and B could be declared significant if the pool comprises algorithms C, D, E and not significant if the pool comprises algorithms F, G, H. To overcome these issues, we suggest instead to perform the multiple comparison using a test whose outcome only depends on the two algorithms being compared, such as the sign-test or the Wilcoxon signed-rank test.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {152–161},
numpages = {10},
keywords = {statistical comparison, post-hoc test, Friedman test}
}

@article{10.5555/2946645.2946649,
author = {Blaser, Rico and Fryzlewicz, Piotr},
title = {Random Rotation Ensembles},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {In machine learning, ensemble methods combine the predictions of multiple base learners to construct more accurate aggregate predictions. Established supervised learning algorithms inject randomness into the construction of the individual base learners in an effort to promote diversity within the resulting ensembles. An undesirable side effect of this approach is that it generally also reduces the accuracy of the base learners. In this paper, we introduce a method that is simple to implement yet general and effective in improving ensemble diversity with only modest impact on the accuracy of the individual base learners. By randomly rotating the feature space prior to inducing the base learners, we achieve favorable aggregate predictions on standard data sets compared to state of the art ensemble methods, most notably for tree-based ensembles, which are particularly sensitive to rotation.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {126–151},
numpages = {26},
keywords = {feature rotation, ensemble diversity, smooth decision boundary}
}

@article{10.5555/2946645.2946648,
author = {Khaleghi, Azadeh and Ryabko, Daniil and Mary, J\'{e}r\'{e}mie and Preux, Philippe},
title = {Consistent Algorithms for Clustering Time Series},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {The problem of clustering is considered for the case where every point is a time series. The time series are either given in one batch (offline setting), or they are allowed to grow with time and new time series can be added along the way (online setting). We propose a natural notion of consistency for this problem, and show that there are simple, computationally efficient algorithms that are asymptotically consistent under extremely weak assumptions on the distributions that generate the data. The notion of consistency is as follows. A clustering algorithm is called consistent if it places two time series into the same cluster if and only if the distribution that generates them is the same. In the considered framework the time series are allowed to be highly dependent, and the dependence can have arbitrary form. If the number of clusters is known, the only assumption we make is that the (marginal) distribution of each time series is stationary ergodic. No parametric, memory or mixing assumptions are made. When the number of clusters is unknown, stronger assumptions are provably necessary, but it is still possible to devise nonparametric algorithms that are consistent under very general conditions. The theoretical findings of this work are illustrated with experiments on both synthetic and real data.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {94–125},
numpages = {32},
keywords = {clustering, time series, ergodicity, unsupervised learning}
}

@article{10.5555/2946645.2946647,
author = {Maggioni, Mauro and Minsker, Stanislav and Strawn, Nate},
title = {Multiscale Dictionary Learning: Non-Asymptotic Bounds and Robustness},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {High-dimensional datasets are well-approximated by low-dimensional structures. Over the past decade, this empirical observation motivated the investigation of detection, measurement, and modeling techniques to exploit these low-dimensional intrinsic structures, yielding numerous implications for high-dimensional statistics, machine learning, and signal processing. Manifold learning (where the low-dimensional structure is a manifold) and dictionary learning (where the low-dimensional structure is the set of sparse linear combinations of vectors from a finite dictionary) are two prominent theoretical and computational frameworks in this area. Despite their ostensible distinction, the recently-introduced Geometric Multi-Resolution Analysis (GMRA) provides a robust, computationally efficient, multiscale procedure for simultaneously learning manifolds and dictionaries.In this work, we prove non-asymptotic probabilistic bounds on the approximation error of GMRA for a rich class of data-generating statistical models that includes "noisy" manifolds, thereby establishing the theoretical robustness of the procedure and confirming empirical observations. In particular, if a dataset aggregates near a low-dimensional manifold, our results show that the approximation error of the GMRA is completely independent of the ambient dimension. Our work therefore establishes GMRA as a provably fast algorithm for dictionary learning with approximation and sparsity guarantees. We include several numerical experiments confirming these theoretical results, and our theoretical framework provides new tools for assessing the behavior of manifold learning and dictionary learning procedures on a large class of interesting models.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {43–93},
numpages = {51},
keywords = {manifold learning, robustness, sparsity, dictionary learning, multi-resolution analysis}
}

@article{10.5555/2946645.2946646,
author = {Kaufmann, Emilie and Capp\'{e}, Olivier and Garivier, Aur\'{e}lien},
title = {On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models},
year = {2016},
issue_date = {January 2016},
publisher = {JMLR.org},
volume = {17},
number = {1},
issn = {1532-4435},
abstract = {The stochastic multi-armed bandit model is a simple abstraction that has proven useful in many different contexts in statistics and machine learning. Whereas the achievable limit in terms of regret minimization is now well known, our aim is to contribute to a better understanding of the performance in terms of identifying the m best arms. We introduce generic notions of complexity for the two dominant frameworks considered in the literature: fixed-budget and fixed-confidence settings. In the fixed-confidence setting, we provide the first known distribution-dependent lower bound on the complexity that involves information-theoretic quantities and holds when m ≥ 1 under general assumptions. In the specific case of two armed-bandits, we derive refined lower bounds in both the fixedcon fidence and fixed-budget settings, along with matching algorithms for Gaussian and Bernoulli bandit models. These results show in particular that the complexity of the fixed-budget setting may be smaller than the complexity of the fixed-confidence setting, contradicting the familiar behavior observed when testing fully specified alternatives. In addition, we also provide improved sequential stopping rules that have guaranteed error probabilities and shorter average running times. The proofs rely on two technical results that are of independent interest: a deviation lemma for self-normalized sums (Lemma 7) and a novel change of measure inequality for bandit models (Lemma 1).},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1–42},
numpages = {42},
keywords = {sequential testing, multi-armed bandit, information-theoretic divergences, best-arm identification, pure exploration}
}

@article{10.5555/2789272.2912120,
author = {Hothorn, Torsten and Zeileis, Achim},
title = {Partykit: A Modular Toolkit for Recursive Partytioning in R},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {The R package partykit provides a flexible toolkit for learning, representing, summarizing, and visualizing a wide range of tree-structured regression and classification models. The functionality encompasses: (a) basic infrastructure for representing trees (inferred by any algorithm) so that unified print/plot/predict methods are available; (b) dedicated methods for trees with constant fits in the leaves (or terminal nodes) along with suitable coercion functions to create such trees (e.g., by rpart, RWeka, PMML); (c) a reimplementation of conditional inference trees (ctree, originally provided in the party package); (d) an extended reimplementation of model-based recursive partitioning (mob, also originally in party) along with dedicated methods for trees with parametric models in the leaves. Here, a brief overview of the package and its design is given while more detailed discussions of items (a)-(d) are available in vignettes accompanying the package.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3905–3909},
numpages = {5},
keywords = {recursive partitioning, statistical learning, regression trees, classification trees, R}
}

@article{10.5555/2789272.2912119,
author = {Taleghan, Majid Alkaee and Dietterich, Thomas G. and Crowley, Mark and Hall, Kim and Albers, H. Jo},
title = {PAC Optimal MDP Planning with Application to Invasive Species Management},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {In a simulator-defined MDP, the Markovian dynamics and rewards are provided in the form of a simulator from which samples can be drawn. This paper studies MDP planning algorithms that attempt to minimize the number of simulator calls before terminating and outputting a policy that is approximately optimal with high probability. The paper introduces two heuristics for efficient exploration and an improved confidence interval that enables earlier termination with probabilistic guarantees. We prove that the heuristics and the confidence interval are sound and produce with high probability an approximately optimal policy in polynomial time. Experiments on two benchmark problems and two instances of an invasive species management problem show that the improved confidence intervals and the new search heuristics yield reductions of between 8% and 47% in the number of simulator calls required to reach near-optimal policies.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3877–3903},
numpages = {27},
keywords = {invasive species management, Good-Turing estimate, reinforcement learning, Markov decision processes, MDP planning}
}

@article{10.5555/2789272.2912118,
author = {Chen, Minmin and Weinberger, Kilian Q. and Xu, Zhixiang and Sha, Fei},
title = {Marginalizing Stacked Linear Denoising Autoencoders},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {Stacked denoising autoencoders (SDAs) have been successfully used to learn new representations for domain adaptation. They have attained record accuracy on standard benchmark tasks of sentiment analysis across different text domains. SDAs learn robust data representations by reconstruction, recovering original features from data that are artificially corrupted with noise. In this paper, we propose marginalized Stacked Linear Denoising Autoencoder (mSLDA) that addresses two crucial limitations of SDAs: high computational cost and lack of scalability to high-dimensional features. In contrast to SDAs, our approach of mSLDA marginalizes noise and thus does not require stochastic gradient descent or other optimization algorithms to learn parameters -- in fact, the linear formulation gives rise to a closed-form solution. Consequently, mSLDA, which can be implemented in only 20 lines of MATLAB™, is about two orders of magnitude faster than a corresponding SDA. Furthermore, the representations learnt by mSLDA are as effective as the traditional SDAs, attaining almost identical accuracies in benchmark tasks.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3849–3875},
numpages = {27},
keywords = {domain adaption, denoising autoencoders, noise marginalization, fast representation learning}
}

@article{10.5555/2789272.2912117,
author = {Yang, Eunho and Ravikumar, Pradeep and Allen, Genevera I. and Liu, Zhandong},
title = {Graphical Models via Univariate Exponential Family Distributions},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {Undirected graphical models, or Markov networks, are a popular class of statistical models, used in a wide variety of applications. Popular instances of this class include Gaussian graphical models and Ising models. In many settings, however, it might not be clear which subclass of graphical models to use, particularly for non-Gaussian and non-categorical data. In this paper, we consider a general sub-class of graphical models where the node-wise conditional distributions arise from exponential families. This allows us to derive multivariate graphical model distributions from univariate exponential family distributions, such as the Poisson, negative binomial, and exponential distributions. Our key contributions include a class of M-estimators to fit these graphical model distributions; and rigorous statistical analysis showing that these M-estimators recover the true graphical model structure exactly, with high probability. We provide examples of genomic and proteomic networks learned via instances of our class of graphical models derived from Poisson and exponential distributions.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3813–3847},
numpages = {35},
keywords = {sparse estimation, model selection, graphical models}
}

@article{10.5555/2789272.2912116,
author = {Nakajima, Shinichi and Tomioka, Ryota and Sugiyama, Masashi and Babacan, S. Derin},
title = {Condition for Perfect Dimensionality Recovery by Variational Bayesian PCA},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {Having shown its good performance in many applications, variational Bayesian (VB) learning is known to be one of the best tractable approximations to Bayesian learning. However, its performance was not well understood theoretically. In this paper, we clarify the behavior of VB learning in probabilistic PCA (or fully-observed matrix factorization). More specifically, we establish a necessary and sufficient condition for perfect dimensionality (or rank) recovery in the large-scale limit when the matrix size goes to infinity. Our result theoretically guarantees the performance of VB-PCA. At the same time, it also reveals the conservative nature of VB learning--it offers a low false positive rate at the expense of low sensitivity. By contrasting with an alternative dimensionality selection method, we characterize VB learning in PCA. In our analysis, we obtain bounds of the noise variance estimator, and a new and simple analytic-form solution for the other parameters, which themselves are useful for implementation of VB-PCA.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3757–3811},
numpages = {55},
keywords = {automatic relevance determination, principal component analysis, matrix factorization, variational Bayesian learning, perfect dimensionality recovery}
}

@article{10.5555/2789272.2912115,
author = {Honda, Junya and Takemura, Akimichi},
title = {Non-Asymptotic Analysis of a New Bandit Algorithm for Semi-Bounded Rewards},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {In this paper we consider a stochastic multiarmed bandit problem. It is known in this problem that Deterministic Minimum Empirical Divergence (DMED) policy achieves the asymptotic theoretical bound for the model where each reward distribution is supported in a known bounded interval, say [0; 1]. However, the regret bound of DMED is described in an asymptotic form and the performance in finite time has been unknown. We modify this policy and derive a finite-time regret bound for the new policy, Indexed Minimum Empirical Divergence (IMED), by refining large deviation probabilities to a simple nonasymptotic form. Further, the refined analysis reveals that the finite-time regret bound is valid even in the case that the reward is not bounded from below. Therefore, our finite-time result applies to the case that the minimum reward (that is, the maximum loss) is unknown or unbounded. We also present some simulation results which shows that IMED much improves DMED and performs competitively to other state-of-the-art policies.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3721–3756},
numpages = {36},
keywords = {large deviation principle, stochastic bandit, finite-time regret}
}

@article{10.5555/2789272.2912114,
author = {Prasse, Paul and Sawade, Christoph and Landwehr, Niels and Scheffer, Tobias},
title = {Learning to Identify Concise Regular Expressions That Describe Email Campaigns},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {This paper addresses the problem of inferring a regular expression from a given set of strings that resembles, as closely as possible, the regular expression that a human expert would have written to identify the language. This is motivated by our goal of automating the task of postmasters who use regular expressions to describe and blacklist email spam campaigns. Training data contains batches of messages and corresponding regular expressions that an expert postmaster feels confident to blacklist. We model this task as a two-stage learning problem with structured output spaces and appropriate loss functions. We derive decoders and the resulting optimization problems which can be solved using standard cutting plane methods. We report on a case study conducted with an email service provider.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3687–3720},
numpages = {34},
keywords = {learning with structured output spaces, applications of machine learning, supervised learning, email campaigns, regular expressions}
}

@article{10.5555/2789272.2912113,
author = {Lin, Tong and Xue, Hanlin and Wang, Ling and Huang, Bo and Zha, Hongbin},
title = {Supervised Learning via Euler's Elastica Models},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {This paper investigates the Euler's elastica (EE) model for high-dimensional supervised learning problems in a function approximation framework. In 1744 Euler introduced the elastica energy for a 2D curve on modeling torsion-free thin elastic rods. Together with its degenerate form of total variation (TV), Euler's elastica has been successfully applied to low-dimensional data processing such as image denoising and image inpainting in the last two decades. Our motivation is to apply Euler's elastica to high-dimensional supervised learning problems. To this end, a supervised learning problem is modeled as an energy functional minimization under a new geometric regularization scheme, where the energy is composed of a squared loss and an elastica penalty. The elastica penalty aims at regularizing the approximated function by heavily penalizing large gradients and high curvature values on all level curves. We take a computational PDE approach to minimize the energy functional. By using variational principles, the energy minimization problem is transformed into an Euler-Lagrange PDE. However, this PDE is usually high-dimensional and can not be directly handled by common low-dimensional solvers. To circumvent this difficulty, we use radial basis functions (RBF) to approximate the target function, which reduces the optimization problem to finding the linear coefficients of these basis functions. Some theoretical properties of this new model, including the existence and uniqueness of solutions and universal consistency, are analyzed. Extensive experiments have demonstrated the effectiveness of the proposed model for binary classification, multi-class classification, and regression tasks.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3637–3686},
numpages = {50},
keywords = {universal consistency, Euler's elastica, total variation, geometric regularization, supervised learning, Euler-Lagrange PDE, function approximation}
}

@article{10.5555/2789272.2912112,
author = {Chazal, Fr\'{e}d\'{e}ric and Glisse, Marc and Labru\`{e}re, Catherine and Michel, Bertrand},
title = {Convergence Rates for Persistence Diagram Estimation in Topological Data Analysis},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {Computational topology has recently seen an important development toward data analysis, giving birth to the field of topological data analysis. Topological persistence, or persistent homology, appears as a fundamental tool in this field. In this paper, we study topological persistence in general metric spaces, with a statistical approach. We show that the use of persistent homology can be naturally considered in general statistical frameworks and that persistence diagrams can be used as statistics with interesting convergence properties. Some numerical experiments are performed in various contexts to illustrate our results.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3603–3635},
numpages = {33},
keywords = {topological data analysis, convergence rates, persistent homology}
}

@article{10.5555/2789272.2912111,
author = {Hanneke, Steve and Yang, Liu},
title = {Minimax Analysis of Active Learning},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {This work establishes distribution-free upper and lower bounds on the minimax label complexity of active learning with general hypothesis classes, under various noise models. The results reveal a number of surprising facts. In particular, under the noise model of Tsybakov (2004), the minimax label complexity of active learning with a VC class is always asymptotically smaller than that of passive learning, and is typically signi_cantly smaller than the best previously-published upper bounds in the active learning literature. In high-noise regimes, it turns out that all active learning problems of a given VC dimension have roughly the same minimax label complexity, which contrasts with well-known results for bounded noise. In low-noise regimes, we find that the label complexity is well-characterized by a simple combinatorial complexity measure we call the star number. Interestingly, we find that almost all of the complexity measures previously explored in the active learning literature have worst-case values exactly equal to the star number. We also propose new active learning strategies that nearly achieve these minimax label complexities.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3487–3602},
numpages = {116},
keywords = {Tsybakov noise, selective sampling, sequential design, minimax analysis, active learning, sample complexity, statistical learning theory, adaptive sampling, margin condition}
}

@article{10.5555/2789272.2912110,
author = {Shamir, Ohad},
title = {The Sample Complexity of Learning Linear Predictors with the Squared Loss},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {We provide a tight sample complexity bound for learning bounded-norm linear predictors with respect to the squared loss. Our focus is on an agnostic PAC-style setting, where no assumptions are made on the data distribution beyond boundedness. This contrasts with existing results in the literature, which rely on other distributional assumptions, refer to specific parameter settings, or use other performance measures.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3475–3486},
numpages = {12},
keywords = {linear predictors, distribution-free learning, squared loss, sample complexity}
}

@article{10.5555/2789272.2912109,
author = {Plumb, Gregory and Pachauri, Deepti and Kondor, Risi and Singh, Vikas},
title = {S<sub>n</sub>FFT: A Julia Toolkit for Fourier Analysis of Functions over Permutations},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {SnFFT is an easy to use software library written in the Julia language to facilitate Fourier analysis on the symmetric group (set of permutations) of degree n, denoted Sn and make it more easily deployable within statistical machine learning algorithms. Our implementation internally creates the irreducible matrix representations of Sn, and efficiently computes fast Fourier transforms (FFTs) and inverse fast Fourier transforms (iFFTs). Advanced users can achieve scalability and promising practical performance by exploiting various other forms of sparsity. Further, the library also supports the partial inverse Fourier transforms which utilizes the smoothness properties of functions by maintaining only the first few Fourier coefficients. Out of the box, SnFFT currently offers two non-trivial operations for functions defined on Sn, namely convolution and correlation. While the potential applicability of SnFFT is fairly broad, as an example, we show how it can be used for clustering ranked data, where each ranking is modeled as a distribution on Sn.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3469–3473},
numpages = {5},
keywords = {permutations, Fourier analysis, Julia, fast Fourier transform}
}

@article{10.5555/2789272.2912108,
author = {Feldman, Vitaly and Kothari, Pravesh},
title = {Agnostic Learning of Disjunctions on Symmetric Distributions},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {We consider the problem of approximating and learning disjunctions (or equivalently, conjunctions) on symmetric distributions over {0; 1}n. Symmetric distributions are distributions whose PDF is invariant under any permutation of the variables. We prove that for every symmetric distribution D, there exists a set of nO(log (1/ε)) functions S, such that for every disjunction c, there is function p, expressible as a linear combination of functions in S, such that p ε-approximates c in l1 distance on D or Ex-D[|c(x) - p(x)|] ≤ ε. This implies an agnostic learning algorithm for disjunctions on symmetric distributions that runs in time nO(log (1/ε)). The best known previous bound is nO(1/ε4) and follows from approximation of the more general class of halfspaces (Wimmer, 2010). We also show that there exists a symmetric distribution D, such that the minimum degree of a polynomial that 1/3-approximates the disjunction of all n variables in l1 distance on D is Ω(√n). Therefore the learning result above cannot be achieved via l1-regression with a polynomial basis used in most other agnostic learning algorithms.Our technique also gives a simple proof that for any product distribution D and every disjunction c, there exists a polynomial p of degree O(log (1/ε)) such that p ε-approximates c in l1 distance on D. This was first proved by Blais et al. (2008) via a more involved argument.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3455–3467},
numpages = {13},
keywords = {conjunction, polynomial approximation, disjunction, symmetric distribution, DNF, agnostic learning, decision tree, regression}
}

@article{10.5555/2789272.2912107,
author = {Helmbold, David P. and Long, Philip M.},
title = {On the Inductive Bias of Dropout},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {Dropout is a simple but effective technique for learning in neural networks and other settings. A sound theoretical understanding of dropout is needed to determine when dropout should be applied and how to use it most effectively. In this paper we continue the exploration of dropout as a regularizer pioneered by Wager et al. We focus on linear classification where a convex proxy to the misclassification loss (i.e. the logistic loss used in logistic regression) is minimized. We show: • when the dropout-regularized criterion has a unique minimizer, • when the dropout-regularization penalty goes to infinity with the weights, and when it remains bounded, • that the dropout regularization can be non-monotonic as individual weights increase from 0, and • that the dropout regularization penalty may not be convex. This last point is particularly surprising because the combination of dropout regularization with any convex loss proxy is always a convex function.In order to contrast dropout regularization with L2 regularization, we formalize the notion of when different random sources of data are more compatible with different regularizers. We then exhibit distributions that are provably more compatible with dropout regularization than L2 regularization, and vice versa. These sources provide additional insight into how the inductive biases of dropout and L2 regularization differ. We provide some similar results for L1 regularization.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3403–3454},
numpages = {52},
keywords = {learning theory, regularization, dropout, feature noising, inductive bias}
}

@article{10.5555/2789272.2912106,
author = {Hastie, Trevor and Mazumder, Rahul and Lee, Jason D. and Zadeh, Reza},
title = {Matrix Completion and Low-Rank SVD via Fast Alternating Least Squares},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {The matrix-completion problem has attracted a lot of attention, largely as a result of the celebrated Net flix competition. Two popular approaches for solving the problem are nuclear-norm-regularized matrix approximation (Cand\`{e}s and Tao, 2009; Mazumder et al., 2010), and maximum-margin matrix factorization (Srebro et al., 2005). These two procedures are in some cases solving equivalent problems, but with quite different algorithms. In this article we bring the two approaches together, leading to an efficient algorithm for large matrix factorization and completion that outperforms both of these. We develop a software package softImpute in R for implementing our approaches, and a distributed version for very large matrices using the Spark cluster programming environment.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3367–3402},
numpages = {36},
keywords = {matrix completion, nuclear norm, alternating least squares, svd}
}

@article{10.5555/2789272.2912105,
author = {Lin, Junhong and Zhou, Ding-Xuan},
title = {Learning Theory of Randomized Kaczmarz Algorithm},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {A relaxed randomized Kaczmarz algorithm is investigated in a least squares regression setting by a learning theory approach. When the sampling values are accurate and the regression function (conditional means) is linear, such an algorithm has been well studied in the community of non-uniform sampling. In this paper, we are mainly interested in the different case of either noisy random measurements or a nonlinear regression function. In this case, we show that relaxation is needed. A necessary and sufficient condition on the sequence of relaxation parameters or step sizes for the convergence of the algorithm in expectation is presented. Moreover, polynomial rates of convergence, both in expectation and in probability, are provided explicitly. As a result, the almost sure convergence of the algorithm is proved by applying the Borel-Cantelli Lemma.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3341–3365},
numpages = {25},
keywords = {online learning, relaxed randomized Kaczmarz algorithm, almost sure convergence, space of homogeneous linear functions, learning theory}
}

@article{10.5555/2789272.2912104,
author = {Zhang, Yuchen and Duchi, John and Wainwright, Martin},
title = {Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {We study a decomposition-based scalable approach to kernel ridge regression, and show that it achieves minimax optimal convergence rates under relatively mild conditions. The method is simple to describe: it randomly partitions a dataset of size N into m subsets of equal size, computes an independent kernel ridge regression estimator for each subset using a careful choice of the regularization parameter, then averages the local solutions into a global predictor. This partitioning leads to a substantial reduction in computation time versus the standard approach of performing kernel ridge regression on all N samples. Our two main theorems establish that despite the computational speed-up, statistical optimality is retained: as long as m is not too large, the partition-based estimator achieves the statistical minimax rate over all estimators using the set of N samples. As concrete examples, our theory guarantees that the number of subsets m may grow nearly linearly for finite-rank or Gaussian kernels and polynomially in N for Sobolev spaces, which in turn allows for substantial reductions in computational cost. We conclude with experiments on both simulated data and a music-prediction task that complement our theoretical results, exhibiting the computational and statistical benefits of our approach.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3299–3340},
numpages = {42},
keywords = {kernel ridge regression, divide and conquer, computation complexity}
}

@article{10.5555/2789272.2912103,
author = {Curtin, Ryan R. and Lee, Dongryeol and March, William B. and Ram, Parikshit},
title = {Plug-and-Play Dual-Tree Algorithm Runtime Analysis},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {Numerous machine learning algorithms contain pairwise statistical problems at their core-- that is, tasks that require computations over all pairs of input points if implemented naively. Often, tree structures are used to solve these problems efficiently. Dual-tree algorithms can efficiently solve or approximate many of these problems. Using cover trees, rigorous worstcase runtime guarantees have been proven for some of these algorithms. In this paper, we present a problem-independent runtime guarantee for any dual-tree algorithm using the cover tree, separating out the problem-dependent and the problem-independent elements. This allows us to just plug in bounds for the problem-dependent elements to get runtime guarantees for dual-tree algorithms for any pairwise statistical problem without rederiving the entire proof. We demonstrate this plug-and-play procedure for nearest-neighbor search and approximate kernel density estimation to get improved runtime guarantees. Under mild assumptions, we also present the first linear runtime guarantee for dual-tree based range search.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3269–3297},
numpages = {29},
keywords = {adaptive runtime analysis, cover tree, expansion constant, dual-tree algorithms, range search, kernel density estimation, nearest neighbor search}
}

@article{10.5555/2789272.2912102,
author = {Statnikov, Alexander and Ma, Sisi and Henaff, Mikael and Lytkin, Nikita and Efstathiadis, Efstratios and Peskin, Eric R. and Aliferis, Constantin F.},
title = {Ultra-Scalable and Efficient Methods for Hybrid Observational and Experimental Local Causal Pathway Discovery},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {Discovery of causal relations from data is a fundamental objective of several scientific disciplines. Most causal discovery algorithms that use observational data can infer causality only up to a statistical equivalency class, thus leaving many causal relations undetermined. In general, complete identification of causal relations requires experimentation to augment discoveries from observational data. This has led to the recent development of several methods for active learning of causal networks that utilize both observational and experimental data in order to discover causal networks. In this work, we focus on the problem of discovering local causal pathways that contain only direct causes and direct effects of the target variable of interest and propose new discovery methods that aim to minimize the number of required experiments, relax common sufficient discovery assumptions in order to increase discovery accuracy, and scale to high-dimensional data with thousands of variables. We conduct a comprehensive evaluation of new and existing methods with data of dimensionality up to 1,000,000 variables. We use both artificially simulated networks and in-silico gene transcriptional networks that model the characteristics of real gene expression data.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3219–3267},
numpages = {49},
keywords = {observational data, causality, large-scale experimental design, local causal pathway discovery, randomized experiments, experimental data}
}

@article{10.5555/2789272.2912101,
author = {Ryan, Kenneth Joseph and Culp, Mark Vere},
title = {On Semi-Supervised Linear Regression in Covariate Shift Problems},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {Semi-supervised learning approaches are trained using the full training (labeled) data and available testing (unlabeled) data. Demonstrations of the value of training with unlabeled data typically depend on a smoothness assumption relating the conditional expectation to high density regions of the marginal distribution and an inherent missing completely at random assumption for the labeling. So-called covariate shift poses a challenge for many existing semi-supervised or supervised learning techniques. Covariate shift models allow the marginal distributions of the labeled and unlabeled feature data to differ, but the conditional distribution of the response given the feature data is the same. An example of this occurs when a complete labeled data sample and then an unlabeled sample are obtained sequentially, as it would likely follow that the distributions of the feature data are quite different between samples. The value of using unlabeled data during training for the elastic net is justified geometrically in such practical covariate shift problems. The approach works by obtaining adjusted coefficients for unlabeled prediction which recalibrate the supervised elastic net to compromise: (i) maintaining elastic net predictions on the labeled data with (ii) shrinking unlabeled predictions to zero. Our approach is shown to dominate linear supervised alternatives on unlabeled response predictions when the unlabeled feature data are concentrated on a low dimensional manifold away from the labeled data and the true coefficient vector emphasizes directions away from this manifold. Large variance of the supervised predictions on the unlabeled set is reduced more than the increase in squared bias when the unlabeled responses are expected to be small, so an improved compromise within the bias-variance tradeoff is the rationale for this performance improvement. Performance is validated on simulated and real data.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3183–3217},
numpages = {35},
keywords = {joint optimization, usefulness of unlabeled data, semi-supervised regression}
}

@article{10.5555/2789272.2912100,
author = {Mokhtari, Aryan and Ribeiro, Alejandro},
title = {Global Convergence of Online Limited Memory BFGS},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {Global convergence of an online (stochastic) limited memory version of the Broyden-Fletcher-Goldfarb-Shanno (BFGS) quasi-Newton method for solving optimization problems with stochastic objectives that arise in large scale machine learning is established. Lower and upper bounds on the Hessian eigenvalues of the sample functions are shown to suffice to guarantee that the curvature approximation matrices have bounded determinants and traces, which, in turn, permits establishing convergence to optimal arguments with probability 1. Experimental evaluation on a search engine advertising problem showcase reductions in convergence time relative to stochastic gradient descent algorithms.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3151–3181},
numpages = {31},
keywords = {quasi-Newton methods, stochastic optimization, large-scale optimization}
}

@article{10.5555/2789272.2912099,
author = {Han, Fang and Lu, Huanran and Liu, Han},
title = {A Direct Estimation of High Dimensional Stationary Vector Autoregressions},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {The vector autoregressive (VAR) model is a powerful tool in learning complex time series and has been exploited in many fields. The VAR model poses some unique challenges to researchers: On one hand, the dimensionality, introduced by incorporating multiple numbers of time series and adding the order of the vector autoregression, is usually much higher than the time series length; On the other hand, the temporal dependence structure naturally present in the VAR model gives rise to extra difficulties in data analysis. The regular way in cracking the VAR model is via "least squares" and usually involves adding different penalty terms (e.g., ridge or lasso penalty) in handling high dimensionality. In this manuscript, we propose an alternative way in estimating the VAR model. The main idea is, via exploiting the temporal dependence structure, formulating the estimating problem to a linear program. There is instant advantage of the proposed approach over the lasso-type estimators: The estimation equation can be decomposed to multiple sub-equations and accordingly can be solved efficiently using parallel computing. Besides that, we also bring new theoretical insights into the VAR model analysis. So far the theoretical results developed in high dimensions (e.g., Song and Bickel, 2011 and Kock and Callot, 2015) are based on stringent assumptions that are not transparent. Our results, on the other hand, show that the spectral norms of the transition matrices play an important role in estimation accuracy and build estimation and prediction consistency accordingly. Moreover, we provide some experiments on both synthetic and real-world equity data. We show that there are empirical advantages of our method over the lasso-type estimators in parameter estimation and forecasting.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3115–3150},
numpages = {36},
keywords = {double asymptotic framework, multivariate time series, linear program, vector autoregressive model, transition matrix}
}

@article{10.5555/2789272.2912098,
author = {Jorgensen, Palle and Tian, Feng},
title = {Discrete Reproducing Kernel Hilbert Spaces: Sampling and Distribution of Dirac-Masses},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {We study reproducing kernels, and associated reproducing kernel Hilbert spaces (RKHSs) H over infinite, discrete and countable sets V. In this setting we analyze in detail the distributions of the corresponding Dirac point-masses of V. Illustrations include certain models from neural networks: An Extreme Learning Machine (ELM) is a neural network-configuration in which a hidden layer of weights are randomly sampled, and where the object is then to compute resulting output. For RKHSs H of functions defined on a prescribed countable infinite discrete set V, we characterize those which contain the Dirac masses δx for all points x in V. Further examples and applications where this question plays an important role are: (i) discrete Brownian motion-Hilbert spaces, i.e., discrete versions of the Cameron-Martin Hilbert space; (ii) energy-Hilbert spaces corresponding to graph-Laplacians where the set V of vertices is then equipped with a resistance metric; and finally (iii) the study of Gaussian free fields.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3079–3114},
numpages = {36},
keywords = {Gaussian reproducing kernel Hilbert spaces, discrete Green's functions, sampling in discrete systems, graph Laplacians, resistance metric}
}

@article{10.5555/2789272.2912097,
author = {Dhillon, Paramveer S. and Foster, Dean P. and Ungar, Lyle H.},
title = {Eigenwords: Spectral Word Embeddings},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {Spectral learning algorithms have recently become popular in data-rich domains, driven in part by recent advances in large scale randomized SVD, and in spectral estimation of Hidden Markov Models. Extensions of these methods lead to statistical estimation algorithms which are not only fast, scalable, and useful on real data sets, but are also provably correct. Following this line of research, we propose four fast and scalable spectral algorithms for learning word embeddings -- low dimensional real vectors (called Eigenwords) that capture the "meaning" of words from their context. All the proposed algorithms harness the multi-view nature of text data i.e. the left and right context of each word, are fast to train and have strong theoretical properties. Some of the variants also have lower sample complexity and hence higher statistical power for rare words. We provide theory which establishes relationships between these algorithms and optimality criteria for the estimates they provide. We also perform thorough qualitative and quantitative evaluation of Eigenwords showing that simple linear approaches give performance comparable to or superior than the state-of-the-art non-linear deep learning based methods.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3035–3078},
numpages = {44},
keywords = {NLP, CCA, spectral learning, word embeddings}
}

@article{10.5555/2789272.2912096,
author = {Chen, Yudong and Bhojanapalli, Srinadh and Sanghavi, Sujay and Ward, Rachel},
title = {Completing Any Low-Rank Matrix, Provably},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {Matrix completion, i.e., the exact and provable recovery of a low-rank matrix from a small subset of its elements, is currently only known to be possible if the matrix satisfies a restrictive structural constraint--known as incoherence--on its row and column spaces. In these cases, the subset of elements is assumed to be sampled uniformly at random.In this paper, we show that any rank-r n-by-n matrix can be exactly recovered from as few as O(nr log2 n) randomly chosen elements, provided this random choice is made according to a specific biased distribution suitably dependent on the coherence structure of the matrix: the probability of any element being sampled should be at least a constant times the sum of the leverage scores of the corresponding row and column. Moreover, we prove that this specific form of sampling is nearly necessary, in a natural precise sense; this implies that many other perhaps more intuitive sampling schemes fail.We further establish three ways to use the above result for the setting when leverage scores are not known a priori. (a) We describe a provably-correct sampling strategy for the case when only the column space is incoherent and no assumption or knowledge of the row space is required. (b) We propose a two-phase sampling procedure for general matrices that first samples to estimate leverage scores followed by sampling for exact recovery. These two approaches assume control over the sampling procedure. (c) By using our main theorem in a reverse direction, we provide an analysis showing the advantages of the (empirically successful) weighted nuclear/trace-norm minimization approach over the vanilla un-weighted formulation given non-uniformly distributed observed elements. This approach does not require controlled sampling or knowledge of the leverage scores.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2999–3034},
numpages = {36},
keywords = {weighted nuclear norm, nuclear norm, matrix completion, leverage score, coherence}
}

@article{10.5555/2789272.2912095,
author = {Horta, Danilo and Campello, Ricardo J. G. B.},
title = {Comparing Hard and Overlapping Clusterings},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {Similarity measures for comparing clusterings is an important component, e.g., of evaluating clustering algorithms, for consensus clustering, and for clustering stability assessment. These measures have been studied for over 40 years in the domain of exclusive hard clusterings (exhaustive and mutually exclusive object sets). In the past years, the literature has proposed measures to handle more general clusterings (e.g., fuzzy/probabilistic clusterings). This paper provides an overview of these new measures and discusses their drawbacks. We ultimately develop a corrected-for-chance measure (13AGRI) capable of comparing exclusive hard, fuzzy/probabilistic, non-exclusive hard, and possibilistic clusterings. We prove that 13AGRI and the adjusted Rand index (ARI, by Hubert and Arabie) are equivalent in the exclusive hard domain. The reported experiments show that only 13AGRI could provide both a fine-grained evaluation across clusterings with different numbers of clusters and a constant evaluation between random clusterings, showing all the four desirable properties considered here. We identified a high correlation between 13AGRI applied to fuzzy clusterings and ARI applied to hard exclusive clusterings over 14 real data sets from the UCI repository, which corroborates the validity of 13AGRI fuzzy clustering evaluation. 13AGRI also showed good results as a clustering stability statistic for solutions produced by the expectation maximization algorithm for Gaussian mixture. Implementation and supplementary figures can be found at http://sn.im/25a9h8u.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2949–2997},
numpages = {49},
keywords = {overlapping, probabilistic, fuzzy, clustering evaluation}
}

@article{10.5555/2789272.2912094,
author = {Li, Chun-Liang and Su, Yu-Chuan and Lin, Ting-Wei and Tsai, Cheng-Hao and Chang, Wei-Cheng and Huang, Kuan-Hao and Kuo, Tzu-Ming and Lin, Shan-Wei and Lin, Young-San and Lu, Yu-Chen and Yang, Chun-Pai and Chang, Cheng-Xia and Chin, Wei-Sheng and Juan, Yu-Chin and Tung, Hsiao-Yu and Wang, Jui-Pin and Wei, Cheng-Kuang and Wu, Felix and Yin, Tu-Chun and Yu, Tong and Zhuang, Yong and Lin, Shou-De and Lin, Hsuan-Tien and Lin, Chih-Jen},
title = {Combination of Feature Engineering and Ranking Models for Paper-Author Identification in KDD Cup 2013},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {This paper describes the winning solution of team National Taiwan University for track 1 of KDD Cup 2013. The track 1 in KDD Cup 2013 considers the paper-author identification problem, which is to identify whether a paper is truly written by an author. First, we conduct feature engineering to transform the various types of provided text information into 97 features. Second, we train classification and ranking models using these features. Last, we combine our individual models to boost the performance by using results on the internal validation set and the official Valid set. Some effective post-processing techniques have also been proposed. Our solution achieves 0.98259 MAP score and ranks the first place on the private leaderboard of the Test set.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2921–2947},
numpages = {27},
keywords = {paper-author identification, feature generation}
}

@article{10.5555/2789272.2912093,
author = {Kirichenko, Alisa and Van Zanten, Harry},
title = {Optimality of Poisson Processes Intensity Learning with Gaussian Processes},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {In this paper we provide theoretical support for the so-called "Sigmoidal Gaussian Cox Process" approach to learning the intensity of an inhomogeneous Poisson process on a d- dimensional domain. This method was proposed by Adams, Murray and MacKay (ICML, 2009), who developed a tractable computational approach and showed in simulation and real data experiments that it can work quite satisfactorily. The results presented in the present paper provide theoretical underpinning of the method. In particular, we show how to tune the priors on the hyper parameters of the model in order for the procedure to automatically adapt to the degree of smoothness of the unknown intensity, and to achieve optimal convergence rates.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2909–2919},
numpages = {11},
keywords = {Gaussian process prior, optimal rates, Bayesian intensity learning, adaptation to smoothness, inhomogeneous Poisson process}
}

@article{10.5555/2789272.2912092,
author = {Lopez-Paz, David and Muandet, Krikamol and Recht, Benjamin},
title = {The Randomized Causation Coefficient},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {We are interested in learning causal relationships between pairs of random variables, purely from observational data. To effectively address this task, the state-of-the-art relies on strong assumptions on the mechanisms mapping causes to effects, such as invertibility or the existence of additive noise, which only hold in limited situations. On the contrary, this short paper proposes to learn how to perform causal inference directly from data, without the need of feature engineering. In particular, we pose causality as a kernel mean embedding classification problem, where inputs are samples from arbitrary probability distributions on pairs of random variables, and labels are types of causal relationships. We validate the performance of our method on synthetic and real-world data against the state-of-the-art. Moreover, we submitted our algorithm to the ChaLearn's "Fast Causation Coefficient Challenge" competition, with which we won the fastest code prize and ranked third in the overall leaderboard.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2901–2907},
numpages = {7},
keywords = {cause-effect inference, causality, random features, kernel mean embeddings}
}

@article{10.5555/2789272.2912091,
author = {Cunningham, John P. and Ghahramani, Zoubin},
title = {Linear Dimensionality Reduction: Survey, Insights, and Generalizations},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {Linear dimensionality reduction methods are a cornerstone of analyzing high dimensional data, due to their simple geometric interpretations and typically attractive computational properties. These methods capture many data features of interest, such as covariance, dynamical structure, correlation between data sets, input-output relationships, and margin between data classes. Methods have been developed with a variety of names and motivations in many fields, and perhaps as a result the connections between all these methods have not been highlighted. Here we survey methods from this disparate literature as optimization programs over matrix manifolds. We discuss principal component analysis, factor analysis, linear multidimensional scaling, Fisher's linear discriminant analysis, canonical correlations analysis, maximum autocorrelation factors, slow feature analysis, sufficient dimensionality reduction, undercomplete independent component analysis, linear regression, distance metric learning, and more. This optimization framework gives insight to some rarely discussed shortcomings of well-known methods, such as the suboptimality of certain eigenvector solutions. Modern techniques for optimization over matrix manifolds enable a generic linear dimensionality reduction solver, which accepts as input data and an objective to be optimized, and returns, as output, an optimal low-dimensional projection of the data. This simple optimization framework further allows straightforward generalizations and novel variants of classical methods, which we demonstrate here by creating an orthogonal-projection canonical correlations analysis. More broadly, this survey and generic solver suggest that linear dimensionality reduction can move toward becoming a blackbox, objective-agnostic numerical technology.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2859–2900},
numpages = {42},
keywords = {eigenvector problems, matrix manifolds, dimensionality reduction}
}

@article{10.5555/2789272.2912090,
author = {Zhang, Jing and Sheng, Victor S. and Nicholson, Bryce A. and Wu, Xindong},
title = {CEKA: A Tool for Mining the Wisdom of Crowds},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {CEKA is a software package for developers and researchers to mine the wisdom of crowds. It makes the entire knowledge discovery procedure much easier, including analyzing qualities of workers, simulating labeling behaviors, inferring true class labels of instances, filtering and correcting mislabeled instances (noise), building learning models and evaluating them. It integrates a set of state-of-the-art inference algorithms, a set of general noise handling algorithms, and abundant functions for model training and evaluation. CEKA is written in Java with core classes being compatible with the well-known machine learning tool WEKA, which makes the utilization of the functions in WEKA much easier.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2853–2858},
numpages = {6},
keywords = {crowdsourcing, multiple noisy labeling, inference, noise handling, learning from crowds, repeated labeling simulation}
}

@article{10.5555/2789272.2912089,
author = {Pati, Debdeep and Bhattacharya, Anirban and Cheng, Guang},
title = {Optimal Bayesian Estimation in Random Covariate Design with a Rescaled Gaussian Process Prior},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {In Bayesian nonparametric models, Gaussian processes provide a popular prior choice for regression function estimation. Existing literature on the theoretical investigation of the resulting posterior distribution almost exclusively assume a fixed design for covariates. The only random design result we are aware of (van der Vaart and van Zanten, 2011) assumes the assigned Gaussian process to be supported on the smoothness class specified by the true function with probability one. This is a fairly restrictive assumption as it essentially rules out the Gaussian process prior with a squared exponential kernel when modeling rougher functions. In this article, we show that an appropriate rescaling of the above Gaussian process leads to a rate-optimal posterior distribution even when the covariates are independently realized from a known density on a compact set. The proofs are based on deriving sharp concentration inequalities for frequentist kernel estimators; the results might be of independent interest.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2837–2851},
numpages = {15},
keywords = {nonparametric regression, Bayesian, rate-optimal, random design, convergence rate, Gaussian process}
}

@article{10.5555/2789272.2912088,
author = {Huang, Furong and Niranjan, U. N. and Hakeem, Mohammad Umar and Anandkumar, Animashree},
title = {Online Tensor Methods for Learning Latent Variable Models},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {We introduce an online tensor decomposition based approach for two latent variable modeling problems namely, (1) community detection, in which we learn the latent communities that the social actors in social networks belong to, and (2) topic modeling, in which we infer hidden topics of text articles. We consider decomposition of moment tensors using stochastic gradient descent. We conduct optimization of multilinear operations in SGD and avoid directly forming the tensors, to save computational and storage costs. We present optimized algorithm in two platforms. Our GPU-based implementation exploits the parallelism of SIMD architectures to allow for maximum speed-up by a careful optimization of storage and data transfer, whereas our CPU-based implementation uses efficient sparse matrix computations and is suitable for large sparse data sets. For the community detection problem, we demonstrate accuracy and computational efficiency on Facebook, Yelp and DBLP data sets, and for the topic modeling problem, we also demonstrate good performance on the New York Times data set. We compare our results to the state-of-the-art algorithms such as the variational method, and report a gain of accuracy and a gain of several orders of magnitude in the execution time.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2797–2835},
numpages = {39},
keywords = {stochastic gradient descent, mixed membership stochastic blockmodel, topic modeling, large datasets, parallel implementation, tensor method}
}

@article{10.5555/2789272.2912087,
author = {Masnadi-Shirazi, Hamed and Vasconcelos, Nuno},
title = {A View of Margin Losses as Regularizers of Probability Estimates},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {Regularization is commonly used in classifier design, to assure good generalization. Classical regularization enforces a cost on classifier complexity, by constraining parameters. This is usually combined with a margin loss, which favors large-margin decision rules. A novel and unified view of this architecture is proposed, by showing that margin losses act as regularizers of posterior class probabilities, in a way that amplifies classical parameter regularization. The problem of controlling the regularization strength of a margin loss is considered, using a decomposition of the loss in terms of a link and a binding function. The link function is shown to be responsible for the regularization strength of the loss, while the binding function determines its outlier robustness. A large class of losses is then categorized into equivalence classes of identical regularization strength or outlier robustness. It is shown that losses in the same regularization class can be parameterized so as to have tunable regularization strength. This parameterization is finally used to derive boosting algorithms with loss regularization (BoostLR). Three classes of tunable regularization losses are considered in detail. Canonical losses can implement all regularization behaviors but have no flexibility in terms of outlier modeling. Shrinkage losses support equally parameterized link and binding functions, leading to boosting algorithms that implement the popular shrinkage procedure. This offers a new explanation for shrinkage as a special case of loss-based regularization. Finally, α-tunable losses enable the independent parameterization of link and binding functions, leading to boosting algorithms of great exibility. This is illustrated by the derivation of an algorithm that generalizes both AdaBoost and LogitBoost, behaving as either one when that best suits the data to classify. Various experiments provide evidence of the benefits of probability regularization for both classification and estimation of posterior class probabilities.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2751–2795},
numpages = {45},
keywords = {probability elicitation, regularization, binding functions, boosting, classification, generalization, shrinkage, link functions, loss functions, margin losses}
}

@article{10.5555/2789272.2912086,
author = {Varando, Gherardo and Bielza, Concha and Larra\~{n}aga, Pedro},
title = {Decision Boundary for Discrete Bayesian Network Classifiers},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {Bayesian network classifiers are a powerful machine learning tool. In order to evaluate the expressive power of these models, we compute families of polynomials that sign-represent decision functions induced by Bayesian network classifiers. We prove that those families are linear combinations of products of Lagrange basis polynomials. In absence of V-structures in the predictor sub-graph, we are also able to prove that this family of polynomials does indeed characterize the specific classifier considered. We then use this representation to bound the number of decision functions representable by Bayesian network classifiers with a given structure.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2725–2749},
numpages = {25},
keywords = {polynomial threshold function, supervised classification, Bayesian networks, Lagrange basis, decision boundary}
}

@article{10.5555/2789272.2912085,
author = {Pourhabib, Arash and Mallick, Bani K. and Ding, Yu},
title = {Absent Data Generating Classifier for Imbalanced Class Sizes},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {We propose an algorithm for two-class classification problems when the training data are imbalanced. This means the number of training instances in one of the classes is so low that the conventional classification algorithms become ineffective in detecting the minority class. We present a modification of the kernel Fisher discriminant analysis such that the imbalanced nature of the problem is explicitly addressed in the new algorithm formulation. The new algorithm exploits the properties of the existing minority points to learn the effects of other minority data points, had they actually existed. The algorithm proceeds iteratively by employing the learned properties and conditional sampling in such a way that it generates sufficient artificial data points for the minority set, thus enhancing the detection probability of the minority class. Implementing the proposed method on a number of simulated and real data sets, we show that our proposed method performs competitively compared to a set of alternative state-of-the-art imbalanced classification algorithms.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2695–2724},
numpages = {30},
keywords = {two-class classification, imbalanced data, kernel Fisher discriminant analysis}
}

@article{10.5555/2789272.2912084,
author = {Anandkumar, Animashree and Hsu, Daniel and Janzamin, Majid and Kakade, Sham},
title = {When Are Overcomplete Topic Models Identifiable? Uniqueness of Tensor Tucker Decompositions with Structured Sparsity},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {Overcomplete latent representations have been very popular for unsupervised feature learning in recent years. In this paper, we specify which overcomplete models can be identified given observable moments of a certain order. We consider probabilistic admixture or topic models in the overcomplete regime, where the number of latent topics can greatly exceed the size of the observed word vocabulary. While general overcomplete topic models are not identifiable, we establish generic identifiability under a constraint, referred to as topic persistence. Our sufficient conditions for identifiability involve a novel set of "higher order" expansion conditions on the topic-word matrix or the population structure of the model. This set of higher-order expansion conditions allow for overcomplete models, and require the existence of a perfect matching from latent topics to higher order observed words. We establish that random structured topic models are identifiable w.h.p. in the overcomplete regime. Our identifiability results allows for general (non-degenerate) distributions for modeling the topic proportions, and thus, we can handle arbitrarily correlated topics in our framework. Our identifiability results imply uniqueness of a class of tensor decompositions with structured sparsity which is contained in the class of Tucker decompositions, but is more general than the Candecomp/Parafac (CP) decomposition.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2643–2694},
numpages = {52},
keywords = {generic identifiability, tensor decomposition, overcomplete representations, topic models}
}

@article{10.5555/2789272.2912083,
author = {Wang, Wen Wu and Lin, Lu},
title = {Derivative Estimation Based on Difference Sequence via Locally Weighted Least Squares Regression},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {A new method is proposed for estimating derivatives of a nonparametric regression function. By applying Taylor expansion technique to a derived symmetric difference sequence, we obtain a sequence of approximate linear regression representation in which the derivative is just the intercept term. Using locally weighted least squares, we estimate the derivative in the linear regression model. The estimator has less bias in both valleys and peaks of the true derivative function. For the special case of a domain with equispaced design points, the asymptotic bias and variance are derived; consistency and asymptotic normality are established. In simulations our estimators have less bias and mean square error than its main competitors, especially second order derivative estimator.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2617–2641},
numpages = {25},
keywords = {nonparametric derivative estimation, Taylor expansion, symmetric difference sequence, locally weighted least squares, biascorrection}
}

@article{10.5555/2789272.2912082,
author = {Neumann, Marion and Huang, Shan and Marthaler, Daniel E. and Kersting, Kristian},
title = {PyGPs: A Python Library for Gaussian Process Regression and Classification},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {We introduce pyGPs, an object-oriented implementation of Gaussian processes (gps) for machine learning. The library provides a wide range of functionalities reaching from simple gp specification via mean and covariance and gp inference to more complex implementations of hyperparameter optimization, sparse approximations, and graph based learning. Using Python we focus on usability for both "users" and "researchers". Our main goal is to offer a user-friendly and flexible implementation of GPs for machine learning.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2611–2616},
numpages = {6},
keywords = {Gaussian processes, regression and classification, Python}
}

@article{10.5555/2789272.2912081,
author = {He, Yangbo and Jia, Jinzhu and Yu, Bin},
title = {Counting and Exploring Sizes of Markov Equivalence Classes of Directed Acyclic Graphs},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {When learning a directed acyclic graph (DAG) model via observational data, one generally cannot identify the underlying DAG, but can potentially obtain a Markov equivalence class. The size (the number of DAGs) of a Markov equivalence class is crucial to infer causal effects or to learn the exact causal DAG via further interventions. Given a set of Markov equivalence classes, the distribution of their sizes is a key consideration in developing learning methods. However, counting the size of an equivalence class with many vertices is usually computationally infeasible, and the existing literature reports the size distributions only for equivalence classes with ten or fewer vertices.In this paper, we develop a method to compute the size of a Markov equivalence class. We first show that there are five types of Markov equivalence classes whose sizes can be formulated as five functions of the number of vertices respectively. Then we introduce a new concept of a rooted sub-class. The graph representations of rooted subclasses of a Markov equivalence class are used to partition this class recursively until the sizes of all rooted subclasses can be computed via the five functions. The proposed size counting is efficient for Markov equivalence classes of sparse DAGs with hundreds of vertices. Finally, we explore the size and edge distributions of Markov equivalence classes and find experimentally that, in general, (1) most Markov equivalence classes are half completed and their average sizes are small, and (2) the sizes of sparse classes grow approximately exponentially with the numbers of vertices.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2589–2609},
numpages = {21},
keywords = {directed acyclic graphs, causality, Markov equivalence class, size distribution}
}

@article{10.5555/2789272.2912080,
author = {Tibshirani, Ryan J.},
title = {A General Framework for Fast Stagewise Algorithms},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {Forward stagewise regression follows a very simple strategy for constructing a sequence of sparse regression estimates: it starts with all coefficients equal to zero, and iteratively updates the coefficient (by a small amount ε) of the variable that achieves the maximal absolute inner product with the current residual. This procedure has an interesting connection to the lasso: under some conditions, it is known that the sequence of forward stagewise estimates exactly coincides with the lasso path, as the step size ε goes to zero. Furthermore, essentially the same equivalence holds outside of least squares regression, with the minimization of a differentiable convex loss function subject to an l1 norm constraint (the stagewise algorithm now updates the coefficient corresponding to the maximal absolute component of the gradient).Even when they do not match their l1-constrained analogues, stagewise estimates provide a useful approximation, and are computationally appealing. Their success in sparse modeling motivates the question: can a simple, effective strategy like forward stagewise be applied more broadly in other regularization settings, beyond the l1 norm and sparsity? The current paper is an attempt to do just this. We present a general framework for stagewise estimation, which yields fast algorithms for problems such as group-structured learning, matrix completion, image denoising, and more.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2543–2588},
numpages = {46},
keywords = {lasso, forward stagewise regression, regularization paths, ε-boosting}
}

@article{10.5555/2789272.2912079,
author = {Fox, Emily B. and Dunson, David B.},
title = {Bayesian Nonparametric Covariance Regression},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {Capturing predictor-dependent correlations amongst the elements of a multivariate response vector is fundamental to numerous applied domains, including neuroscience, epidemiology, and finance. Although there is a rich literature on methods for allowing the variance in a univariate regression model to vary with predictors, relatively little has been done in the multivariate case. As a motivating example, we consider the Google Flu Trends data set, which provides indirect measurements of influenza incidence at a large set of locations over time (our predictor). To accurately characterize temporally evolving influenza incidence across regions, it is important to develop statistical methods for a time-varying covariance matrix. Importantly, the locations provide a redundant set of measurements and do not yield a sparse nor static spatial dependence structure. We propose to reduce dimensionality and induce a flexible Bayesian nonparametric covariance regression model by relating these location-specific trajectories to a lower-dimensional subspace through a latent factor model with predictor-dependent factor loadings. These loadings are in terms of a collection of basis functions that vary nonparametrically over the predictor space. Such low-rank approximations are in contrast to sparse precision assumptions, and are appropriate in a wide range of applications. Our formulation aims to address three challenges: scaling to large p domains, coping with missing values, and allowing an irregular grid of observations. The model is shown to be highly exible, while leading to a computationally feasible implementation via Gibbs sampling. The ability to scale to large p domains and cope with missing values is fundamental in analyzing the Google Flu Trends data.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2501–2542},
numpages = {42},
keywords = {time series, latent factor model, nonparametric Bayes, covariance regression, dictionary learning, Gaussian process}
}

@article{10.5555/2789272.2912078,
author = {Maru\v{s}ic, Ines and Worrell, James},
title = {Complexity of Equivalence and Learning for Multiplicity Tree Automata},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {We consider the query and computational complexity of learning multiplicity tree automata in Angluin's exact learning model. In this model, there is an oracle, called the Teacher, that can answer membership and equivalence queries posed by the Learner. Motivated by this feature, we first characterise the complexity of the equivalence problem for multiplicity tree automata, showing that it is logspace equivalent to polynomial identity testing.We then move to query complexity, deriving lower bounds on the number of queries needed to learn multiplicity tree automata over both fixed and arbitrary fields. In the latter case, the bound is linear in the size of the target automaton. The best known upper bound on the query complexity over arbitrary fields derives from an algorithm of Habrard and Oncina (2006), in which the number of queries is proportional to the size of the target automaton and the size of a largest counterexample, represented as a tree, that is returned by the Teacher. However, a smallest counterexample tree may already be exponential in the size of the target automaton. Thus the above algorithm has query complexity exponentially larger than our lower bound, and does not run in time polynomial in the size of the target automaton.We give a new learning algorithm for multiplicity tree automata in which counterexamples to equivalence queries are represented as DAGs. The query complexity of this algorithm is quadratic in the target automaton size and linear in the size of a largest counterexample. In particular, if the Teacher always returns DAG counterexamples of minimal size then the query complexity is quadratic in the target automaton size--almost matching the lower bound, and improving the best previously-known algorithm by an exponential factor.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2465–2500},
numpages = {36},
keywords = {query complexity, polynomial identity testing, multiplicity tree automata, Hankel matrices, exact learning, DAG representations of trees}
}

@article{10.5555/2789272.2912077,
author = {Lowd, Daniel and Rooshenas, Amirmohammad},
title = {The Libra Toolkit for Probabilistic Models},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {The Libra Toolkit is a collection of algorithms for learning and inference with discrete probabilistic models, including Bayesian networks, Markov networks, dependency networks, and sum-product networks. Compared to other toolkits, Libra places a greater emphasis on learning the structure of tractable models in which exact inference is efficient. It also includes a variety of algorithms for learning graphical models in which inference is potentially intractable, and for performing exact and approximate inference. Libra is released under a 2-clause BSD license to encourage broad use in academia and industry.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2459–2463},
numpages = {5},
keywords = {probabilistic graphical models, structure learning, inference}
}

@article{10.5555/2789272.2912076,
author = {Bontempi, Gianluca and Flauder, Maxime},
title = {From Dependency to Causality: A Machine Learning Approach},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {The relationship between statistical dependency and causality lies at the heart of all statistical approaches to causal inference. Recent results in the ChaLearn cause-effect pair challenge have shown that causal directionality can be inferred with good accuracy also in Markov indistinguishable configurations thanks to data driven approaches. This paper proposes a supervised machine learning approach to infer the existence of a directed causal link between two variables in multivariate settings with n > 2 variables. The approach relies on the asymmetry of some conditional (in) dependence relations between the members of the Markov blankets of two variables causally connected. Our results show that supervised learning methods may be successfully used to extract causal information on the basis of asymmetric statistical descriptors also for n gt; 2 variate distributions.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2437–2457},
numpages = {21},
keywords = {information theory, machine learning, causal inference}
}

@article{10.5555/2789272.2912075,
author = {Mont\'{u}far, Guido and Ay, Nihat and Ghazi-Zahedi, Keyan},
title = {Geometry and Expressive Power of Conditional Restricted Boltzmann Machines},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {Conditional restricted Boltzmann machines are undirected stochastic neural networks with a layer of input and output units connected bipartitely to a layer of hidden units. These networks define models of conditional probability distributions on the states of the output units given the states of the input units, parameterized by interaction weights and biases. We address the representational power of these models, proving results on their ability to represent conditional Markov random fields and conditional distributions with restricted supports, the minimal size of universal approximators, the maximal model approximation errors, and on the dimension of the set of representable conditional distributions. We contribute new tools for investigating conditional probability models, which allow us to improve the results that can be derived from existing work on restricted Boltzmann machine probability models.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2405–2436},
numpages = {32},
keywords = {conditional restricted Boltzmann machine, Kullback-Leibler approximation error, universal approximation, expected dimension}
}

@article{10.5555/2789272.2912074,
author = {Daniely, Amit and Sabato, Sivan and Ben-David, Shai and Shalev-Shwartz, Shai},
title = {Multiclass Learnability and the ERM Principle},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {We study the sample complexity of multiclass prediction in several learning settings. For the PAC setting our analysis reveals a surprising phenomenon: In sharp contrast to binary classification, we show that there exist multiclass hypothesis classes for which some Empirical Risk Minimizers (ERM learners) have lower sample complexity than others. Furthermore, there are classes that are learnable by some ERM learners, while other ERM learners will fail to learn them. We propose a principle for designing good ERM learners, and use this principle to prove tight bounds on the sample complexity of learning symmetric multiclass hypothesis classes--classes that are invariant under permutations of label names. We further provide a characterization of mistake and regret bounds for multiclass learning in the online setting and the bandit setting, using new generalizations of Littlestone's dimension.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2377–2404},
numpages = {28},
keywords = {ERM, sample complexity, multiclass}
}

@article{10.5555/2789272.2886824,
author = {Watanabe, Kazuho and Roos, Teemu},
title = {Achievability of Asymptotic Minimax Regret by Horizon-Dependent and Horizon-Independent Strategies},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {The normalized maximum likelihood distribution achieves minimax coding (log-loss) regret given a fixed sample size, or horizon, n. It generally requires that n be known in advance. Furthermore, extracting the sequential predictions from the normalized maximum likelihood distribution is computationally infeasible for most statistical models. Several computationally feasible alternative strategies have been devised. We characterize the achievability of asymptotic minimaxity by horizon-dependent and horizon-independent strategies. We prove that no horizon-independent strategy can be asymptotically minimax in the multinomial case. A weaker result is given in the general case subject to a condition on the horizon-dependence of the normalized maximum likelihood. Motivated by these negative results, we demonstrate that an easily implementable Bayes mixture based on a conjugate Dirichlet prior with a simple dependency on n achieves asymptotic minimaxity for all sequences, simplifying earlier similar proposals. Our numerical experiments for the Bernoulli model demonstrate improved finite-sample performance by a number of novel horizon-dependent and horizon-independent algorithms.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2357–2375},
numpages = {19},
keywords = {on-line learning, asymptotic minimax regret, normalized maximum likelihood, bayes mixture, prediction of individual sequences}
}

@article{10.5555/2789272.2886823,
author = {Santhanam, Narayana and Anantharam, Venkat},
title = {Agnostic Insurability of Model Classes},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {Motivated by problems in insurance, our task is to predict finite upper bounds on a future draw from an unknown distribution p over natural numbers. We can only use past observations generated independently and identically distributed according to p. While p is unknown, it is known to belong to a given collection P of probability distributions on the natural numbers.The support of the distributions p ∈ P may be unbounded, and the prediction game goes on for infinitely many draws. We are allowed to make observations without predicting upper bounds for some time. But we must, with probability 1, start and then continue to predict upper bounds after a finite time irrespective of which p ∈ P governs the data.If it is possible, without knowledge of p and for any prescribed confidence however close to 1, to come up with a sequence of upper bounds that is never violated over an infinite time window with confidence at least as big as prescribed, we say the model class P is insurable.We completely characterize the insurability of any class P of distributions over natural numbers by means of a condition on how the neighborhoods of distributions in P should be, one that is both necessary and sufficient.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2329–2355},
numpages = {27},
keywords = {insurance, prediction of quantiles of distributions, l1 topology of probability distributions over countable sets, non-parametric approaches, universal compression}
}

@article{10.5555/2789272.2886822,
author = {Aragam, Bryon and Zhou, Qing},
title = {Concave Penalized Estimation of Sparse Gaussian Bayesian Networks},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {We develop a penalized likelihood estimation framework to learn the structure of Gaussian Bayesian networks from observational data. In contrast to recent methods which accelerate the learning problem by restricting the search space, our main contribution is a fast algorithm for score-based structure learning which does not restrict the search space in any way and works on high-dimensional data sets with thousands of variables. Our use of concave regularization, as opposed to the more popular l0 (e.g. BIC) penalty, is new. Moreover, we provide theoretical guarantees which generalize existing asymptotic results when the underlying distribution is Gaussian. Most notably, our framework does not require the existence of a so-called faithful DAG representation, and as a result, the theory must handle the inherent nonidentifiability of the estimation problem in a novel way. Finally, as a matter of independent interest, we provide a comprehensive comparison of our approach to several standard structure learning methods using open-source packages developed for the R language. Based on these experiments, we show that our algorithm obtains higher sensitivity with comparable false discovery rates for high-dimensional data and scales efficiently as the number of nodes increases. In particular, the total runtime for our method to generate a solution path of 20 estimates for DAGs with 8000 nodes is around one hour.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2273–2328},
numpages = {56},
keywords = {directed acyclic graphs, nonconvex optimization, concave penalization, coordinate descent, bayesian networks}
}

@article{10.5555/2789272.2886821,
author = {Carpentier, Alexandra and Munos, Remi and Antos, Andr\'{a}s},
title = {Adaptive Strategy for Stratified Monte Carlo Sampling},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {We consider the problem of stratified sampling for Monte Carlo integration of a random variable. We model this problem in a K-armed bandit, where the arms represent the K strata. The goal is to estimate the integral mean, that is a weighted average of the mean values of the arms. The learner is allowed to sample the variable n times, but it can decide on-line which stratum to sample next. We propose an UCB-type strategy that samples the arms according to an upper bound on their estimated standard deviations. We compare its performance to an ideal sample allocation that knows the standard deviations of the arms. For sub-Gaussian arm distributions, we provide bounds on the total regret: a distribution-dependent bound of order poly(λmin-1)\~{O}(n-3/2)1 that depends on a measure of the disparity λmin of the per stratum variances and a distribution-free bound poly(K)\~{O}(n-7/6) that does not. We give similar, but somewhat sharper bounds on a proxy of the regret. The problem-independent bound for this proxy matches its recent minimax lower bound in terms of n up to a log n factor.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2231–2271},
numpages = {41},
keywords = {stratied Monte Carlo, minimax strategies, active learning, bandit theory, adaptive sampling}
}

@article{10.5555/2789272.2886820,
author = {Ovcharov, Evgeni Y.},
title = {Existence and Uniqueness of Proper Scoring Rules},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {To discuss the existence and uniqueness of proper scoring rules one needs to extend the associated entropy functions as sublinear functions to the conic hull of the prediction set. In some natural function spaces, such as the Lebesgue Lp-spaces over Rd, the positive cones have empty interior. Entropy functions defined on such cones have directional derivatives only, which typically exist on large subspaces and behave similarly to gradients. Certain entropies may be further extended continuously to open cones in normed spaces containing signed densities. The extended densities are G\^{a}teaux differentiable except on a negligible set and have everywhere continuous subgradients due to the supporting hyperplane theorem. We introduce the necessary framework from analysis and algebra that allows us to give an affirmative answer to the titular question of the paper. As a result of this, we give a formal sense in which entropy functions have uniquely associated proper scoring rules. We illustrate our framework by studying the derivatives and subgradients of the following three prototypical entropies: Shannon entropy, Hyv\"{a}rinen entropy, and quadratic entropy.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2207–2230},
numpages = {24},
keywords = {directional derivative, G\^{a}teaux derivative, sublinear, proper scoring rules, characterisation, uniqueness, quasiinterior, existence, entropy, subgradient, convex analysis}
}

@article{10.5555/2789272.2886819,
author = {Triantafillou, Sofia and Tsamardinos

license_type: permissive

branch_name: refs/heads/main

extension: bib