text:
oral Differences: A Survey and Comparison},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Policy evaluation is an essential step in most reinforcement learning approaches. It yields a value function, the quality assessment of states for a given policy, which can be used in a policy improvement step. Since the late 1980s, this research area has been dominated by temporal-difference (TD) methods due to their data-efficiency. However, core issues such as stability guarantees in the off-policy scenario, improved sample efficiency and probabilistic treatment of the uncertainty in the estimates have only been tackled recently, which has led to a large number of new approaches.This paper aims at making these new developments accessible in a concise overview, with foci on underlying cost functions, the off-policy scenario as well as on regularization in high dimensional feature spaces. By presenting the first extensive, systematic comparative evaluations comparing TD, LSTD, LSPE, FPKF, the residual-gradient algorithm, Bellman residual minimization, GTD, GTD2 and TDC, we shed light on the strengths and weaknesses of the methods. Moreover, we present alternative versions of LSTD and LSPE with drastically improved off-policy performance.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {809–883},
numpages = {75},
keywords = {temporal differences, value function estimation, reinforcement learning, policy evaluation}
}

@article{10.5555/2627435.2627458,
author = {Zhang, Teng and Lerman, Gilad},
title = {A Novel M-Estimator for Robust PCA},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {We study the basic problem of robust subspace recovery. That is, we assume a data set that some of its points are sampled around a fixed subspace and the rest of them are spread in the whole ambient space, and we aim to recover the fixed underlying subspace. We first estimate "robust inverse sample covariance" by solving a convex minimization procedure; we then recover the subspace by the bottom eigenvectors of this matrix (their number correspond to the number of eigenvalues close to 0). We guarantee exact subspace recovery under some conditions on the underlying data. Furthermore, we propose a fast iterative algorithm, which linearly converges to the matrix minimizing the convex problem. We also quantify the effect of noise and regularization and discuss many other practical and theoretical issues for improving the subspace recovery in various settings. When replacing the sum of terms in the convex energy function (that we minimize) with the sum of squares of terms, we obtain that the new minimizer is a scaled version of the inverse sample covariance (when exists). We thus interpret our minimizer and its subspace (spanned by its bottom eigenvectors) as robust versions of the empirical inverse covariance and the PCA subspace respectively. We compare our method with many other algorithms for robust PCA on synthetic and real data sets and demonstrate state-of-the-art speed and accuracy.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {749–808},
numpages = {60},
keywords = {iteratively re-weighted least squares, robust statistics, principal components analysis, convex relaxation, M-estimator}
}

@article{10.5555/2627435.2627457,
author = {Coviello, Emanuele and Chan, Antoni B. and Lanckriet, Gert R. G.},
title = {Clustering Hidden Markov Models with Variational HEM},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {The hidden Markov model (HMM) is a widely-used generative model that copes with sequential data, assuming that each observation is conditioned on the state of a hidden Markov chain. In this paper, we derive a novel algorithm to cluster HMMs based on the hierarchical EM (HEM) algorithm. The proposed algorithm i) clusters a given collection of HMMs into groups of HMMs that are similar, in terms of the distributions they represent, and ii) characterizes each group by a "cluster center", that is, a novel HMM that is representative for the group, in a manner that is consistent with the underlying generative model of the HMM. To cope with intractable inference in the E-step, the HEM algorithm is formulated as a variational optimization problem, and efficiently solved for the HMM case by leveraging an appropriate variational approximation. The benefits of the proposed algorithm, which we call variational HEM (VHEM), are demonstrated on several tasks involving time-series data, such as hierarchical clustering of motion capture sequences, and automatic annotation and retrieval of music and of online hand-writing data, showing improvements over current methods. In particular, our variational HEM algorithm effectively leverages large amounts of data when learning annotation models by using an efficient hierarchical estimation procedure, which reduces learning times and memory requirements, while improving model robustness through better regularization.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {697–747},
numpages = {51},
keywords = {clustering, time-series classification, hierarchical EM algorithm, variational approximation, hidden Markov model, hidden Markov mixture model}
}

@article{10.5555/2627435.2627456,
author = {Moore, Brett L. and Pyeatt, Larry D. and Kulkarni, Vivekanand and Panousis, Periklis and Padrez, Kevin and Doufas, Anthony G.},
title = {Reinforcement Learning for Closed-Loop Propofol Anesthesia: A Study in Human Volunteers},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Clinical research has demonstrated the efficacy of closed-loop control of anesthesia using the bispectral index of the electroencephalogram as the controlled variable. These controllers have evolved to yield patient-specific anesthesia, which is associated with improved patient outcomes. Despite progress, the problem of patient-specific anesthesia remains unsolved. A variety of factors confound good control, including variations in human physiology, imperfect measures of drug effect, and delayed, hysteretic response to drug delivery. Reinforcement learning (RL) appears to be uniquely equipped to overcome these challenges; however, the literature offers no precedent for RL in anesthesia. To begin exploring the role RL might play in improving anesthetic care, we investigated the method's application in the delivery of patient-specific, propofol-induced hypnosis in human volunteers. When compared to performance metrics reported in the anesthesia literature, RL demonstrated patient-specific control marked by improved accuracy and stability. Furthermore, these results suggest that RL may be considered a viable alternative for solving other difficult closed-loop control problems in medicine. More rigorous clinical study, beyond the confines of controlled human volunteer studies, is needed to substantiate these findings.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {655–696},
numpages = {42},
keywords = {anesthesia, propofol, bispectral index, closed-loop control, reinforcement learning, hypnosis}
}

@article{10.5555/2627435.2627455,
author = {Shah, Rajen Dinesh and Meinshausen, Nicolai},
title = {Random Intersection Trees},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Finding interactions between variables in large and high-dimensional data sets is often a serious computational challenge. Most approaches build up interaction sets incrementally, adding variables in a greedy fashion. The drawback is that potentially informative high-order interactions may be overlooked. Here, we propose an alternative approach for classification problems with binary predictor variables, called Random Intersection Trees. It works by starting with a maximal interaction that includes all variables, and then gradually removing variables if they fail to appear in randomly chosen observations of a class of interest. We show that informative interactions are retained with high probability, and the computational complexity of our procedure is of order pκ, where p is the number of predictor variables. The value of κ can reach values as low as 1 for very sparse data; in many more general settings, it will still beat the exponent s obtained when using a brute force search constrained to order s interactions. In addition, by using some new ideas based on min-wise hash schemes, we are able to further reduce the computational cost. Interactions found by our algorithm can be used for predictive modelling in various forms, but they are also often of interest in their own right as useful characterisations of what distinguishes a certain class from others.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {629–654},
numpages = {26},
keywords = {high-dimensional classification, sparse data, interactions, min-wise hashing}
}

@article{10.5555/2627435.2627454,
author = {Bach, Francis},
title = {Adaptivity of Averaged Stochastic Gradient Descent to Local Strong Convexity for Logistic Regression},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {In this paper, we consider supervised learning problems such as logistic regression and study the stochastic gradient method with averaging, in the usual stochastic approximation setting where observations are used only once. We show that after N iterations, with a constant step-size proportional to 1/R2√N where N is the number of observations and R is the maximum norm of the observations, the convergence rate is always of order O(1/√N), and improves to O(R2/µN) where µ is the lowest eigenvalue of the Hessian at the global optimum (when this eigenvalue is greater than R2/√N. Since µ does not need to be known in advance, this shows that averaged stochastic gradient is adaptive to unknown local strong convexity of the objective function. Our proof relies on the generalized self-concordance properties of the logistic loss and thus extends to all generalized linear models with uniformly bounded features.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {595–627},
numpages = {33},
keywords = {logistic regression, self-concordance, stochastic approximation}
}

@article{10.5555/2627435.2627453,
author = {Richard, Emile and Ga\"{\i}ffas, St\'{e}phane and Vayatis, Nicolas},
title = {Link Prediction in Graphs with Autoregressive Features},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {In the paper, we consider the problem of link prediction in time-evolving graphs. We assume that certain graph features, such as the node degree, follow a vector autoregressive (VAR) model and we propose to use this information to improve the accuracy of prediction. Our strategy involves a joint optimization procedure over the space of adjacency matrices and VAR matrices. On the adjacency matrix it takes into account both sparsity and low rank properties and on the VAR it encodes the sparsity. The analysis involves oracle inequalities that illustrate the trade-offs in the choice of smoothing parameters when modeling the joint effect of sparsity and low rank. The estimate is computed efficiently using proximal methods, and evaluated through numerical experiments.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {565–593},
numpages = {29},
keywords = {graphs, low-rank, link prediction, sparsity, autoregression}
}

@article{10.5555/2627435.2627452,
author = {Cuturi, Marco and Avis, David},
title = {Ground Metric Learning},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Optimal transport distances have been used for more than a decade in machine learning to compare histograms of features. They have one parameter: the ground metric, which can be any metric between the features themselves. As is the case for all parameterized distances, optimal transport distances can only prove useful in practice when this parameter is carefully chosen. To date, the only option available to practitioners to set the ground metric parameter was to rely on a priori knowledge of the features, which limited considerably the scope of application of optimal transport distances. We propose to lift this limitation and consider instead algorithms that can learn the ground metric using only a training set of labeled histograms. We call this approach ground metric learning. We formulate the problem of learning the ground metric as the minimization of the difference of two convex polyhedral functions over a convex set of metric matrices. We follow the presentation of our algorithms with promising experimental results which show that this approach is useful both for retrieval and binary/multiclass classification tasks.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {533–564},
numpages = {32},
keywords = {metric nearness, optimal transport distance, earth mover's distance, metric learning}
}

@article{10.5555/2627435.2627451,
author = {Lowd, Daniel and Davis, Jesse},
title = {Improving Markov Network Structure Learning Using Decision Trees},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Most existing algorithms for learning Markov network structure either are limited to learning interactions among few variables or are very slow, due to the large space of possible structures. In this paper, we propose three new methods for using decision trees to learn Markov network structures. The advantage of using decision trees is that they are very fast to learn and can represent complex interactions among many variables. The first method, DTSL, learns a decision tree to predict each variable and converts each tree into a set of conjunctive features that define the Markov network structure. The second, DT-BLM, builds on DTSL by using it to initialize a search-based Markov network learning algorithm recently proposed by Davis and Domingos (2010). The third, DT+L1, combines the features learned by DTSL with those learned by an L1-regularized logistic regression method (L1) proposed by Ravikumar et al. (2009). In an extensive empirical evaluation on 20 data sets, DTSL is comparable to L1 and significantly faster and more accurate than two other baselines. DT-BLM is slower than DTSL, but obtains slightly higher accuracy. DT+L1 combines the strengths of DTSL and L1 to perform significantly better than either of them with only a modest increase in training time.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {501–532},
numpages = {32},
keywords = {structure learning, probabilistic methods, decision trees, Markov networks}
}

@article{10.5555/2627435.2627450,
author = {Hoi, Steven C. H. and Wang, Jialei and Zhao, Peilin},
title = {LIBOL: A Library for Online Learning Algorithms},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {LIBOL is an open-source library for large-scale online learning, which consists of a large family of efficient and scalable state-of-the-art online learning algorithms for large-scale online classification tasks. We have offered easy-to-use command-line tools and examples for users and developers, and also have made comprehensive documents available for both beginners and advanced users. LIBOL is not only a machine learning toolbox, but also a comprehensive experimental platform for conducting online learning research.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {495–499},
numpages = {5},
keywords = {online learning, massive-scale classification, big data analytics}
}

@article{10.5555/2627435.2627449,
author = {Pang, Haotian and Liu, Han and Vanderbei, Robert},
title = {The Fastclime Package for Linear Programming and Large-Scale Precision Matrix Estimation in R},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {We develop an R package FASTCLIME for solving a family of regularized linear programming (LP) problems. Our package efficiently implements the parametric simplex algorithm, which provides a scalable and sophisticated tool for solving large-scale linear programs. As an illustrative example, one use of our LP solver is to implement an important sparse precision matrix estimation method called CLIME (Constrained L1 Minimization Estimator). Compared with existing packages for this problem such as CLIME and FLARE, our package has three advantages: (1) it efficiently calculates the full piecewise-linear regularization path; (2) it provides an accurate dual certificate as stopping criterion; (3) it is completely coded in C and is highly portable. This package is designed to be useful to statisticians and machine learning researchers for solving a wide range of problems.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {489–493},
numpages = {5},
keywords = {linear programming, undirected graphical model, sparse precision matrix, parametric simplex method, high dimensional data}
}

@article{10.5555/2627435.2627448,
author = {Mohan, Karthik and London, Palma and Fazel, Maryam and Witten, Daniela and Lee, Su-In},
title = {Node-Based Learning of Multiple Gaussian Graphical Models},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {We consider the problem of estimating high-dimensional Gaussian graphical models corresponding to a single set of variables under several distinct conditions. This problem is motivated by the task of recovering transcriptional regulatory networks on the basis of gene expression data containing heterogeneous samples, such as different disease states, multiple species, or different developmental stages. We assume that most aspects of the conditional dependence networks are shared, but that there are some structured differences between them. Rather than assuming that similarities and differences between networks are driven by individual edges, we take a node-based approach, which in many cases provides a more intuitive interpretation of the network differences. We consider estimation under two distinct assumptions: (1) differences between the K networks are due to individual nodes that are perturbed across conditions, or (2) similarities among the K networks are due to the presence of common hub nodes that are shared across all K networks. Using a row-column overlap norm penalty function, we formulate two convex optimization problems that correspond to these two assumptions. We solve these problems using an alternating direction method of multipliers algorithm, and we derive a set of necessary and sufficient conditions that allows us to decompose the problem into independent subproblems so that our algorithm can be scaled to high-dimensional settings. Our proposal is illustrated on synthetic data, a webpage data set, and a brain cancer gene expression data set.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {445–488},
numpages = {44},
keywords = {structured sparsity, lasso, alternating direction method of multipliers, gene regulatory network, graphical model, multivariate normal}
}

@article{10.5555/2627435.2627447,
author = {Fox-Roberts, Patrick and Rosten, Edward},
title = {Unbiased Generative Semi-Supervised Learning},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Reliable semi-supervised learning, where a small amount of labelled data is complemented by a large body of unlabelled data, has been a long-standing goal of the machine learning community. However, while it seems intuitively obvious that unlabelled data can aid the learning process, in practise its performance has often been disappointing. We investigate this by examining generative maximum likelihood semi-supervised learning and derive novel upper and lower bounds on the degree of bias introduced by the unlabelled data. These bounds improve upon those provided in previous work, and are specifically applicable to the challenging case where the model is unable to exactly fit to the underlying distribution a situation which is common in practise, but for which fewer guarantees of semi-supervised performance have been found. Inspired by this new framework for analysing bounds, we propose a new, simple reweighing scheme which provides a provably unbiased estimator for arbitrary model/distribution pairs--an unusual property for a semi-supervised algorithm. This reweighing introduces no additional computational complexity and can be applied to very many models. Additionally, we provide specific conditions demonstrating the circumstance under which the unlabelled data will lower the estimator variance, thereby improving convergence.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {367–443},
numpages = {77},
keywords = {bias, Kullback-Leibler, asymptotic bounds, generative model, semi-supervised}
}

@article{10.5555/2627435.2627446,
author = {Raskutti, Garvesh and Wainwright, Martin J. and Yu, Bin},
title = {Early Stopping and Non-Parametric Regression: An Optimal Data-Dependent Stopping Rule},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Early stopping is a form of regularization based on choosing when to stop running an iterative algorithm. Focusing on non-parametric regression in a reproducing kernel Hilbert space, we analyze the early stopping strategy for a form of gradient-descent applied to the least-squares loss function. We propose a data-dependent stopping rule that does not involve hold-out or cross-validation data, and we prove upper bounds on the squared error of the resulting function estimate, measured in either the L2(P) and L2(Pn) norm. These upper bounds lead to minimax-optimal rates for various kernel classes, including Sobolev smoothness classes and other forms of reproducing kernel Hilbert spaces. We show through simulation that our stopping rule compares favorably to two other stopping rules, one based on hold-out data and the other based on Stein's unbiased risk estimate. We also establish a tight connection between our early stopping strategy and the solution path of a kernel ridge regression estimator.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {335–366},
numpages = {32},
keywords = {kernel ridge regression, stopping rule, empirical processes, early stopping, reproducing kernel hilbert space, rademacher complexity, non-parametric regression}
}

@article{10.5555/2627435.2627445,
author = {Geist, Matthieu and Scherrer, Bruno},
title = {Off-Policy Learning with Eligibility Traces: A Survey},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {In the framework of Markov Decision Processes, we consider linear off-policy learning, that is the problem of learning a linear approximation of the value function of some fixed policy from one trajectory possibly generated by some other policy. We briefly review on-policy learning algorithms of the literature (gradient-based and least-squares-based), adopting a unified algorithmic view. Then, we highlight a systematic approach for adapting them to off-policy learning with eligibility traces. This leads to some known algorithms-- off-policy LSTD(λ), LSPE(λ), TD(λ), TDC/GQ(λ)--and suggests new extensions--off-policy FPKF(λ), BRM(λ), gBRM(λ), GTD2(λ). We describe a comprehensive algorithmic derivation of all algorithms in a recursive and memory-efficent form, discuss their known convergence properties and illustrate their relative empirical behavior on Garnet problems. Our experiments suggest that the most standard algorithms on and off-policy LSTD(λ)/LSPE(λ)--and TD(λ) if the feature space dimension is too large for a least-squares approach--perform the best.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {289–333},
numpages = {45},
keywords = {eligibility traces, reinforcement learning, value function estimation, off-policy learning}
}

@article{10.5555/2627435.2627444,
author = {Szab\'{o}, Zolt\'{a}n},
title = {Information Theoretical Estimators Toolbox},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {We present ITE (information theoretical estimators) a free and open source, multi-platform, Matlab/Octave toolbox that is capable of estimating many different variants of entropy, mutual information, divergence, association measures, cross quantities, and kernels on distributions. Thanks to its highly modular design, ITE supports additionally (i) the combinations of the estimation techniques, (ii) the easy construction and embedding of novel information theoretical estimators, and (iii) their immediate application in information theoretical optimization problems. ITE also includes a prototype application in a central problem class of signal processing, independent subspace analysis and its extensions.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {283–287},
numpages = {5},
keywords = {divergence, multi-platform, independent subspace analysis and its extensions, modularity, Matlab/Octave, distribution kernel estimation, GNU GPLv3 (≥), association, mutual information, entropy}
}

@article{10.5555/2627435.2627443,
author = {Wilson, Aaron and Fern, Alan and Tadepalli, Prasad},
title = {Using Trajectory Data to Improve Bayesian Optimization for Reinforcement Learning},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Recently, Bayesian Optimization (BO) has been used to successfully optimize parametric policies in several challenging Reinforcement Learning (RL) applications. BO is attractive for this problem because it exploits Bayesian prior information about the expected return and exploits this knowledge to select new policies to execute. Effectively, the BO framework for policy search addresses the exploration-exploitation tradeoff. In this work, we show how to more effectively apply BO to RL by exploiting the sequential trajectory information generated by RL agents. Our contributions can be broken into two distinct, but mutually beneficial, parts. The first is a new Gaussian process (GP) kernel for measuring the similarity between policies using trajectory data generated from policy executions. This kernel can be used in order to improve posterior estimates of the expected return thereby improving the quality of exploration. The second contribution, is a new GP mean function which uses learned transition and reward functions to approximate the surface of the objective. We show that the model-based approach we develop can recover from model inaccuracies when good transition and reward models cannot be learned. We give empirical results in a standard set of RL benchmarks showing that both our model-based and model-free approaches can speed up learning compared to competing methods. Further, we show that our contributions can be combined to yield synergistic improvement in some domains.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {253–282},
numpages = {30},
keywords = {Bayesian, MDP, policy search, reinforcement learning, Markov decision process, optimization}
}

@article{10.5555/2627435.2627442,
author = {Aravkin, Aleksandr and Burke, James V. and Chiuso, Alessandro and Pillonetto, Gianluigi},
title = {Convex vs Non-Convex Estimators for Regression and Sparse Estimation: The Mean Squared Error Properties of ARD and GLasso},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {We study a simple linear regression problem for grouped variables; we are interested in methods which jointly perform estimation and variable selection, that is, that automatically set to zero groups of variables in the regression vector. The Group Lasso (GLasso), a well known approach used to tackle this problem which is also a special case of Multiple Kernel Learning (MKL), boils down to solving convex optimization problems. On the other hand, a Bayesian approach commonly known as Sparse Bayesian Learning (SBL), a version of which is the well known Automatic Relevance Determination (ARD), lead to nonconvex problems. In this paper we discuss the relation between ARD (and a penalized version which we call PARD) and Glasso, and study their asymptotic properties in terms of the Mean Squared Error in estimating the unknown parameter. The theoretical arguments developed here are independent of the correctness of the prior models and clarify the advantages of PARD over GLasso.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {217–252},
numpages = {36},
keywords = {group Lasso, marginal likelihood, multiple kernel learning, Bayesian regularization, Lasso}
}

@article{10.5555/2627435.2627441,
author = {Van Laarhoven, Twan and Marchiori, Elena},
title = {Axioms for Graph Clustering Quality Functions},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {We investigate properties that intuitively ought to be satisfied by graph clustering quality functions, that is, functions that assign a score to a clustering of a graph. Graph clustering, also known as network community detection, is often performed by optimizing such a function. Two axioms tailored for graph clustering quality functions are introduced, and the four axioms introduced in previous work on distance based clustering are reformulated and generalized for the graph setting. We show that modularity, a standard quality function for graph clustering, does not satisfy all of these six properties. This motivates the derivation of a new family of quality functions, adaptive scale modularity, which does satisfy the proposed axioms. Adaptive scale modularity has two parameters, which give greater flexibility in the kinds of clusterings that can be found. Standard graph clustering quality functions, such as normalized cut and unnormalized cut, are obtained as special cases of adaptive scale modularity.In general, the results of our investigation indicate that the considered axiomatic framework covers existing 'good' quality functions for graph clustering, and can be used to derive an interesting new family of quality functions.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {193–215},
numpages = {23},
keywords = {modularity, axiomatic framework, graph clustering}
}

@article{10.5555/2627435.2627440,
author = {Vats, Divyanshu and Nowak, Robert D.},
title = {A Junction Tree Framework for Undirected Graphical Model Selection},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {An undirected graphical model is a joint probability distribution defined on an undirected graph G*, where the vertices in the graph index a collection of random variables and the edges encode conditional independence relationships among random variables. The undirected graphical model selection (UGMS) problem is to estimate the graph G* given observations drawn from the undirected graphical model. This paper proposes a framework for decomposing the UGMS problem into multiple subproblems over clusters and subsets of the separators in a junction tree. The junction tree is constructed using a graph that contains a superset of the edges in G*. We highlight three main properties of using junction trees for UGMS. First, different regularization parameters or different UGMS algorithms can be used to learn different parts of the graph. This is possible since the subproblems we identify can be solved independently of each other. Second, under certain conditions, a junction tree based UGMS algorithm can produce consistent results with fewer observations than the usual requirements of existing algorithms. Third, both our theoretical and experimental results show that the junction tree framework does a significantly better job at finding the weakest edges in a graph than existing methods. This property is a consequence of both the first and second properties. Finally, we note that our framework is independent of the choice of the UGMS algorithm and can be used as a wrapper around standard UGMS algorithms for more accurate graph estimation.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {147–191},
numpages = {45},
keywords = {junction trees, high-dimensional statistics, graph decomposition, model selection, graphical models, graphical model selection, Markov random fields}
}

@article{10.5555/2627435.2627439,
author = {Claesen, Marc and De Smet, Frank and Suykens, Johan A. K. and De Moor, Bart},
title = {EnsembleSVM: A Library for Ensemble Learning Using Support Vector Machines},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {EnsembleSVM is a free software package containing efficient routines to perform ensemble learning with support vector machine (SVM) base models. It currently offers ensemble methods based on binary SVM models. Our implementation avoids duplicate storage and evaluation of support vectors which are shared between constituent models. Experimental results show that using ensemble approaches can drastically reduce training complexity while maintaining high predictive accuracy. The EnsembleSVM software package is freely available online at http://esat.kuleuven.be/stadius/ensemblesvm.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {141–145},
numpages = {5},
keywords = {bagging, ensemble learning, support vector machine, classification}
}

@article{10.5555/2627435.2627438,
author = {Oentaryo, Richard and Lim, Ee-Peng and Finegold, Michael and Lo, David and Zhu, Feida and Phua, Clifton and Cheu, Eng-Yeow and Yap, Ghim-Eng and Sim, Kelvin and Nguyen, Minh Nhut and Perera, Kasun and Neupane, Bijay and Faisal, Mustafa and Aung, Zeyar and Woon, Wei Lee and Chen, Wei and Patel, Dhaval and Berrar, Daniel},
title = {Detecting Click Fraud in Online Advertising: A Data Mining Approach},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Click fraud-the deliberate clicking on advertisements with no real interest on the product or service offered-is one of the most daunting problems in online advertising. Building an effective fraud detection method is thus pivotal for online advertising businesses. We organized a Fraud Detection in Mobile Advertising (FDMA) 2012 Competition, opening the opportunity for participants to work on real-world fraud data from BuzzCity Pte. Ltd., a global mobile advertising company based in Singapore. In particular, the task is to identify fraudulent publishers who generate illegitimate clicks, and distinguish them from normal publishers. The competition was held from September 1 to September 30, 2012, attracting 127 teams from more than 15 countries. The mobile advertising data are unique and complex, involving heterogeneous information, noisy patterns with missing values, and highly imbalanced class distribution. The competition results provide a comprehensive study on the usability of data mining-based fraud detection approaches in practical setting. Our principal findings are that features derived from fine-grained time-series analysis are crucial for accurate fraud detection, and that ensemble methods offer promising solutions to highly-imbalanced nonlinear classification tasks with mixed variable types and noisy/missing patterns. The competition data remain available for further studies at http://palanteer.sis.smu.edu.sg/fdma2012/.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {99–140},
numpages = {42},
keywords = {ensemble learning, fraud detection, imbalanced classification, feature engineering}
}

@article{10.5555/2627435.2627437,
author = {Nandan, Manu and Khargonekar, Pramod P. and Talathi, Sachin S.},
title = {Fast SVM Training Using Approximate Extreme Points},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Applications of non-linear kernel support vector machines (SVMs) to large data sets is seriously hampered by its excessive training time. We propose a modification, called the approximate extreme points support vector machine (AESVM), that is aimed at overcoming this burden. Our approach relies on conducting the SVM optimization over a carefully selected subset, called the representative set, of the training data set. We present analytical results that indicate the similarity of AESVM and SVM solutions. A linear time algorithm based on convex hulls and extreme points is used to compute the representative set in kernel space. Extensive computational experiments on nine data sets compared AESVM to LIBSVM (Chang and Lin, 2011), CVM (Tsang et al., 2005), BVM (Tsang et al., 2007), LASVM (Bordes et al., 2005), SVMperf (Joachims and Yu, 2009), and the random features method (Rahimi and Recht, 2007). Our AESVM implementation was found to train much faster than the other methods, while its classification accuracy was similar to that of LIBSVM in all cases. In particular, for a seizure detection data set, AESVM training was almost 500 times faster than LIBSVM and LASVM and 20 times faster than CVM and BVM. Additionally, AESVM also gave competitively fast classification times.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {59–98},
numpages = {40},
keywords = {support vector machines, non-linear kernels, convex hulls, large scale classification, extreme points}
}

@article{10.5555/2627435.2627436,
author = {Lember, J\"{u}ri and Koloydenko, Alexey A.},
title = {Bridging Viterbi and Posterior Decoding: A Generalized Risk Approach to Hidden Path Inference Based on Hidden Markov Models},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Motivated by the unceasing interest in hidden Markov models (HMMs), this paper reexamines hidden path inference in these models, using primarily a risk-based framework. While the most common maximum a posteriori (MAP), or Viterbi, path estimator and the minimum error, or Posterior Decoder (PD) have long been around, other path estimators, or decoders, have been either only hinted at or applied more recently and in dedicated applications generally unfamiliar to the statistical learning community. Over a decade ago, however, a family of algorithmically defined decoders aiming to hybridize the two standard ones was proposed elsewhere. The present paper gives a careful analysis of this hybridization approach, identifies several problems and issues with it and other previously proposed approaches, and proposes practical resolutions of those. Furthermore, simple modifications of the classical criteria for hidden path recognition are shown to lead to a new class of decoders. Dynamic programming algorithms to compute these decoders in the usual forward-backward manner are presented. A particularly interesting subclass of such estimators can be also viewed as hybrids of the MAP and PD estimators. Similar to previously proposed MAP-PD hybrids, the new class is parameterized by a small number of tunable parameters. Unlike their algorithmic predecessors, the new risk-based decoders are more clearly interpretable, and, most importantly, work "out-of-the box" in practice, which is demonstrated on some real bioinformatics tasks and data. Some further generalizations and applications are discussed in the conclusion.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1–58},
numpages = {58},
keywords = {hybrid, risk, power transform, segmental classification, decoder, optimal accuracy, minimum error, posterior decoding, interpolation, HMM, symbol-by-symbol, Viterbi algorithm, MAP sequence, admissible path}
}

@article{10.5555/2567709.2627679,
author = {Djuric, Nemanja and Lan, Liang and Vucetic, Slobodan and Wang, Zhuang},
title = {BudgetedSVM: A Toolbox for Scalable SVM Approximations},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {We present BudgetedSVM, an open-source C++ toolbox comprising highly-optimized implementations of recently proposed algorithms for scalable training of Support Vector Machine (SVM) approximators: Adaptive Multi-hyperplane Machines, Low-rank Linearization SVM, and Budgeted Stochastic Gradient Descent. BudgetedSVM trains models with accuracy comparable to LibSVM in time comparable to LibLinear, solving non-linear problems with millions of high-dimensional examples within minutes on a regular computer. We provide command-line and Matlab interfaces to BudgetedSVM, an efficient API for handling large-scale, high-dimensional data sets, as well as detailed documentation to help developers use and further extend the toolbox.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {3813–3817},
numpages = {5},
keywords = {non-linear classification, machine learning toolbox, large-scale learning, SVM}
}

@article{10.5555/2567709.2627678,
author = {Shankar, Karthik H. and Howard, Marc W.},
title = {Optimally Fuzzy Temporal Memory},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Any learner with the ability to predict the future of a structured time-varying signal must maintain a memory of the recent past. If the signal has a characteristic timescale relevant to future prediction, the memory can be a simple shift register--a moving window extending into the past, requiring storage resources that linearly grows with the timescale to be represented. However, an independent general purpose learner cannot a priori know the characteristic prediction-relevant timescale of the signal. Moreover, many naturally occurring signals show scale-free long range correlations implying that the natural prediction-relevant timescale is essentially unbounded. Hence the learner should maintain information from the longest possible timescale allowed by resource availability. Here we construct a fuzzy memory system that optimally sacrifices the temporal accuracy of information in a scale-free fashion in order to represent prediction-relevant information from exponentially long timescales. Using several illustrative examples, we demonstrate the advantage of the fuzzy memory system over a shift register in time series forecasting of natural signals. When the available storage resources are limited, we suggest that a general purpose learner would be better off committing to such a fuzzy memory system.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {3785–3812},
numpages = {28},
keywords = {temporal information compression, forecasting long range correlated time series}
}

@article{10.5555/2567709.2627677,
author = {Fukumizu, Kenji and Song, Le and Gretton, Arthur},
title = {Kernel Bayes' Rule: Bayesian Inference with Positive Definite Kernels},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {A kernel method for realizing Bayes' rule is proposed, based on representations of probabilities in reproducing kernel Hilbert spaces. Probabilities are uniquely characterized by the mean of the canonical map to the RKHS. The prior and conditional probabilities are expressed in terms of RKHS functions of an empirical sample: no explicit parametric model is needed for these quantities. The posterior is likewise an RKHS mean of a weighted sample. The estimator for the expectation of a function of the posterior is derived, and rates of consistency are shown. Some representative applications of the kernel Bayes' rule are presented, including Bayesian computation without likelihood and filtering with a nonparametric state-space model.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {3753–3783},
numpages = {31},
keywords = {kernel method, Bayes' rule, reproducing kernel Hilbert space}
}

@article{10.5555/2567709.2627676,
author = {Culp, Mark Vere and Ryan, Kenneth Joseph},
title = {Joint Harmonic Functions and Their Supervised Connections},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {The cluster assumption had a significant impact on the reasoning behind semi-supervised classification methods in graph-based learning. The literature includes numerous applications where harmonic functions provided estimates that conformed to data satisfying this well-known assumption, but the relationship between this assumption and harmonic functions is not as well-understood theoretically. We investigate these matters from the perspective of supervised kernel classification and provide concrete answers to two fundamental questions. (i) Under what conditions do semi-supervised harmonic approaches satisfy this assumption? (ii) If such an assumption is satisfied then why precisely would an observation sacrifice its own supervised estimate in favor of the cluster? First, a harmonic function is guaranteed to assign labels to data in harmony with the cluster assumption if a specific condition on the boundary of the harmonic function is satisfied. Second, it is shown that any harmonic function estimate within the interior is a probability weighted average of supervised estimates, where the weight is focused on supervised kernel estimates near labeled cases. We demonstrate that the uniqueness criterion for harmonic estimators is sensitive when the graph is sparse or the size of the boundary is relatively small. This sets the stage for a third contribution, a new regularized joint harmonic function for semi-supervised learning based on a joint optimization criterion. Mathematical properties of this estimator, such as its uniqueness even when the graph is sparse or the size of the boundary is relatively small, are proven. A main selling point is its ability to operate in circumstances where the cluster assumption may not be fully satisfied on real data by compromising between the purely harmonic and purely supervised estimators. The competitive stature of the new regularized joint harmonic approach is established.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {3721–3752},
numpages = {32},
keywords = {harmonic function, cluster assumption, joint training, semi-supervised learning}
}

@article{10.5555/2567709.2627675,
author = {Escalante-B., Alberto N. and Wiskott, Laurenz},
title = {How to Solve Classification and Regression Problems on High-Dimensional Data with a Supervised Extension of Slow Feature Analysis},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Supervised learning from high-dimensional data, for example, multimedia data, is a challenging task. We propose an extension of slow feature analysis (SFA) for supervised dimensionality reduction called graph-based SFA (GSFA). The algorithm extracts a label-predictive low-dimensional set of features that can be post-processed by typical supervised algorithms to generate the final label or class estimation. GSFA is trained with a so-called training graph, in which the vertices are the samples and the edges represent similarities of the corresponding labels. A new weighted SFA optimization problem is introduced, generalizing the notion of slowness from sequences of samples to such training graphs. We show that GSFA computes an optimal solution to this problem in the considered function space and propose several types of training graphs. For classification, the most straightforward graph yields features equivalent to those of (nonlinear) Fisher discriminant analysis. Emphasis is on regression, where four different graphs were evaluated experimentally with a subproblem of face detection on photographs. The method proposed is promising particularly when linear models are insufficient as well as when feature selection is difficult.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {3683–3719},
numpages = {37},
keywords = {training graphs, image analysis, implicitly supervised, classification, pattern recognition, feature extraction, nonlinear dimensionality reduction, regression, high-dimensional data, slow feature analysis, supervised learning}
}

@article{10.5555/2567709.2627674,
author = {Ahlgren, John and Yuen, Shiu Yin},
title = {Efficient Program Synthesis Using Constraint Satisfaction in Inductive Logic Programming},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {We present NrSample, a framework for program synthesis in inductive logic programming. NrSample uses propositional logic constraints to exclude undesirable candidates from the search. This is achieved by representing constraints as propositional formulae and solving the associated constraint satisfaction problem. We present a variety of such constraints: pruning, input-output, functional (arithmetic), and variable splitting. NrSample is also capable of detecting search space exhaustion, leading to further speedups in clause induction and optimality. We benchmark NrSample against enumeration search (Aleph's default) and Progol's A* search in the context of program synthesis. The results show that, on large program synthesis problems, NrSample induces between 1 and 1358 times faster than enumeration (236 times faster on average), always with similar or better accuracy. Compared to Progol A*, NrSample is 18 times faster on average with similar or better accuracy except for two problems: one in which Progol A* substantially sacrificed accuracy to induce faster, and one in which Progol A* was a clear winner. Functional constraints provide a speedup of up to 53 times (21 times on average) with similar or better accuracy. We also benchmark using a few concept learning (non-program synthesis) problems. The results indicate that without strong constraints, the overhead of solving constraints is not compensated for.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {3649–3682},
numpages = {34},
keywords = {inductive logic programming, program synthesis, constraint satisfaction, Boolean satisfiability problem, theory induction}
}

@article{10.5555/2567709.2627673,
author = {Cai, Tony and Zhou, Wen-Xin},
title = {A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {We consider in this paper the problem of noisy 1-bit matrix completion under a general non-uniform sampling distribution using the max-norm as a convex relaxation for the rank. A max-norm constrained maximum likelihood estimate is introduced and studied. The rate of convergence for the estimate is obtained. Information-theoretical methods are used to establish a minimax lower bound under the general sampling model. The minimax upper and lower bounds together yield the optimal rate of convergence for the Frobenius norm loss. Computational algorithms and numerical performance are also discussed.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {3619–3647},
numpages = {29},
keywords = {optimal rate of convergence, maximum likelihood estimate, low-rank matrix, max-norm, constrained optimization, 1-bit matrix completion, trace-norm}
}

@article{10.5555/2567709.2627672,
author = {Gilad-Bachrach, Ran and Burges, Christopher J. C.},
title = {Classifier Selection Using the Predicate Depth},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Typically, one approaches a supervised machine learning problem by writing down an objective function and finding a hypothesis that minimizes it. This is equivalent to finding the Maximum A Posteriori (MAP) hypothesis for a Boltzmann distribution. However, MAP is not a robust statistic. We present an alternative approach by defining a median of the distribution, which we show is both more robust, and has good generalization guarantees. We present algorithms to approximate this median.One contribution of this work is an efficient method for approximating the Tukey median. The Tukey median, which is often used for data visualization and outlier detection, is a special case of the family of medians we define: however, computing it exactly is exponentially slow in the dimension. Our algorithm approximates such medians in polynomial time while making weaker assumptions than those required by previous work.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {3591–3618},
numpages = {28},
keywords = {estimation, classification, median, Tukey depth}
}

@article{10.5555/2567709.2627671,
author = {Parrish, Nathan and Anderson, Hyrum S. and Gupta, Maya R. and Hsiao, Dun Yu},
title = {Classifying with Confidence from Incomplete Information},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {We consider the problem of classifying a test sample given incomplete information. This problem arises naturally when data about a test sample is collected over time, or when costs must be incurred to compute the classification features. For example, in a distributed sensor network only a fraction of the sensors may have reported measurements at a certain time, and additional time, power, and bandwidth is needed to collect the complete data to classify. A practical goal is to assign a class label as soon as enough data is available to make a good decision. We formalize this goal through the notion of reliability--the probability that a label assigned given incomplete data would be the same as the label assigned given the complete data, and we propose a method to classify incomplete data only if some reliability threshold is met. Our approach models the complete data as a random variable whose distribution is dependent on the current incomplete data and the (complete) training data. The method differs from standard imputation strategies in that our focus is on determining the reliability of the classification decision, rather than just the class label. We show that the method provides useful reliability estimates of the correctness of the imputed class labels on a set of experiments on time-series data sets, where the goal is to classify the time-series as early as possible while still guaranteeing that the reliability threshold is met.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {3561–3589},
numpages = {29},
keywords = {signals, sensor networks, classification, reliability}
}

@article{10.5555/2567709.2627670,
author = {Clark, Alexander},
title = {Learning Trees from Strings: A Strong Learning Algorithm for Some Context-Free Grammars},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Standard models of language learning are concerned with weak learning: the learner, receiving as input only information about the strings in the language, must learn to generalise and to generate the correct, potentially infinite, set of strings generated by some target grammar. Here we define the corresponding notion of strong learning: the learner, again only receiving strings as input, must learn a grammar that generates the correct set of structures or parse trees. We formalise this using a modification of Gold's identification in the limit model, requiring convergence to a grammar that is isomorphic to the target grammar. We take as our starting point a simple learning algorithm for substitutable context-free languages, based on principles of distributional learning, and modify it so that it will converge to a canonical grammar for each language. We prove a corresponding strong learning result for a subclass of context-free grammars.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {3537–3559},
numpages = {23},
keywords = {structure learning, grammatical inference, identification in the limit, context-free grammars}
}

@article{10.5555/2567709.2627669,
author = {Jethava, Vinay and Martinsson, Anders and Bhattacharyya, Chiranjib and Dubhashi, Devdatt},
title = {Lov\'{a}Sz ϑ Function, SVMs and Finding Dense Subgraphs},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {In this paper we establish that the Lov\'{a}sz ϑ function on a graph can be restated as a kernel learning problem. We introduce the notion of SVM-ϑ graphs, on which Lov\'{a}sz ϑ function can be approximated well by a Support vector machine (SVM). We show that Erd\"{o}s-R\'{e}nyi random G(n, p) graphs are SVM-ϑ graphs for log4 n/n ≤ p < 1. Even if we embed a large clique of size Θ(√np/1-p) in a G(n, p) graph the resultant graph still remains a SVM-ϑ graph. This immediately suggests an SVM based algorithm for recovering a large planted clique in random graphs. Associated with the ϑ function is the notion of orthogonal labellings. We introduce common orthogonal labellings which extends the idea of orthogonal labellings to multiple graphs. This allows us to propose a Multiple Kernel learning (MKL) based solution which is capable of identifying a large common dense subgraph in multiple graphs. Both in the planted clique case and common subgraph detection problem the proposed solutions beat the state of the art by an order of magnitude.},
journal = {J. Mach. Learn. Res.},
month = dec,
pages = {3495–3536},
numpages = {42},
keywords = {common dense subgraph, planted cliques, orthogonal labellings of graphs, random graphs}
}

@article{10.5555/2567709.2502626,
author = {Neuvial, Pierre},
title = {Asymptotic Results on Adaptive False Discovery Rate Controlling Procedures Based on Kernel Estimators},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {The False Discovery Rate (FDR) is a commonly used type I error rate in multiple testing problems. It is defined as the expected False Discovery Proportion (FDP), that is, the expected fraction of false positives among rejected hypotheses. When the hypotheses are independent, the Benjamini-Hochberg procedure achieves FDR control at any pre-specified level. By construction, FDR control offers no guarantee in terms of power, or type II error. A number of alternative procedures have been developed, including plug-in procedures that aim at gaining power by incorporating an estimate of the proportion of true null hypotheses.In this paper, we study the asymptotic behavior of a class of plug-in procedures based on kernel estimators of the density of the p-values, as the number m of tested hypotheses grows to infinity. In a setting where the hypotheses tested are independent, we prove that these procedures are asymptotically more powerful in two respects: (i) a tighter asymptotic FDR control for any target FDR level and (ii) a broader range of target levels yielding positive asymptotic power. We also show that this increased asymptotic power comes at the price of slower, non-parametric convergence rates for the FDP. These rates are of the form m-k/(2k+1), where k is determined by the regularity of the density of the p-value distribution, or, equivalently, of the test statistics distribution. These results are applied to one- and two-sided tests statistics for Gaussian and Laplace location models, and for the Student model.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {1423–1459},
numpages = {37},
keywords = {test statistics distribution, convergence rates, criticality, false discovery rate, plug-in procedures, Benjamini Hochberg's procedure, kernel estimators, adaptive control, power, multiple testing}
}

@article{10.5555/2567709.2502625,
author = {Picard, David and Thome, Nicolas and Cord, Matthieu},
title = {JKernelMachines: A Simple Framework for Kernel Machine},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {JKernelMachines is a Java library for learning with kernels. It is primarily designed to deal with custom kernels that are not easily found in standard libraries, such as kernels on structured data. These types of kernels are often used in computer vision or bioinformatics applications. We provide several kernels leading to state of the art classification performances in computer vision, as well as various kernels on sets. The main focus of the library is to be easily extended with new kernels. Standard SVM optimization algorithms are available, but also more sophisticated learning-based kernel combination methods such as Multiple Kernel Learning (MKL), and a recently published algorithm to learn powered products of similarities (Product Kernel Learning).},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {1417–1421},
numpages = {5},
keywords = {support vector machines, kernel, computer vision, classification}
}

@article{10.5555/2567709.2502624,
author = {Parviainen, Pekka and Koivisto, Mikko},
title = {Finding Optimal Bayesian Networks Using Precedence Constraints},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {We consider the problem of finding a directed acyclic graph (DAG) that optimizes a decomposable Bayesian network score. While in a favorable case an optimal DAG can be found in polynomial time, in the worst case the fastest known algorithms rely on dynamic programming across the node subsets, taking time and space 2n, to within a factor polynomial in the number of nodes n. In practice, these algorithms are feasible to networks of at most around 30 nodes, mainly due to the large space requirement. Here, we generalize the dynamic programming approach to enhance its feasibility in three dimensions: first, the user may trade space against time; second, the proposed algorithms easily and efficiently parallelize onto thousands of processors; third, the algorithms can exploit any prior knowledge about the precedence relation on the nodes. Underlying all these results is the key observation that, given a partial order P on the nodes, an optimal DAG compatible with P can be found in time and space roughly proportional to the number of ideals of P, which can be significantly less than 2n. Considering sufficiently many carefully chosen partial orders guarantees that a globally optimal DAG will be found. Aside from the generic scheme, we present and analyze concrete tradeoff schemes based on parallel bucket orders.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {1387–1415},
numpages = {29},
keywords = {structure learning, parallelization, space-time tradeoff, partial order, exact algorithm}
}

@article{10.5555/2567709.2502623,
author = {Zhang, Chong and Liu, Yufeng},
title = {Multicategory Large-Margin Unified Machines},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Hard and soft classifiers are two important groups of techniques for classification problems. Logistic regression and Support Vector Machines are typical examples of soft and hard classifiers respectively. The essential difference between these two groups is whether one needs to estimate the class conditional probability for the classification task or not. In particular, soft classifiers predict the label based on the obtained class conditional probabilities, while hard classifiers bypass the estimation of probabilities and focus on the decision boundary. In practice, for the goal of accurate classification, it is unclear which one to use in a given situation. To tackle this problem, the Large-margin Unified Machine (LUM) was recently proposed as a unified family to embrace both groups. The LUM family enables one to study the behavior change from soft to hard binary classifiers. For multicategory cases, however, the concept of soft and hard classification becomes less clear. In that case, class probability estimation becomes more involved as it requires estimation of a probability vector. In this paper, we propose a new Multicategory LUM (MLUM) framework to investigate the behavior of soft versus hard classification under multicategory settings. Our theoretical and numerical results help to shed some light on the nature of multicategory classification and its transition behavior from soft to hard classifiers. The numerical results suggest that the proposed tuned MLUM yields very competitive performance.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {1349–1386},
numpages = {38},
keywords = {soft classification, large-margin, support vector machine, hard classification}
}

@article{10.5555/2567709.2502622,
author = {Hoffman, Matthew D. and Blei, David M. and Wang, Chong and Paisley, John},
title = {Stochastic Variational Inference},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {We develop stochastic variational inference, a scalable algorithm for approximating posterior distributions. We develop this technique for a large class of probabilistic models and we demonstrate it with two probabilistic topic models, latent Dirichlet allocation and the hierarchical Dirichlet process topic model. Using stochastic variational inference, we analyze several large collections of documents: 300K articles from Nature, 1.8M articles from The New York Times, and 3.8M articles from Wikipedia. Stochastic inference can easily handle data sets of this size and outperforms traditional variational inference, which can only handle a smaller subset. (We also show that the Bayesian nonparametric topic model outperforms its parametric counterpart.) Stochastic variational inference lets us apply complex Bayesian models to massive data sets.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {1303–1347},
numpages = {45},
keywords = {Bayesian nonparametrics, stochastic optimization, variational inference, Bayesian inference, topic models}
}

@article{10.5555/2567709.2502621,
author = {Gerber, Samuel and Whitaker, Ross},
title = {Regularization-Free Principal Curve Estimation},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Principal curves and manifolds provide a framework to formulate manifold learning within a statistical context. Principal curves define the notion of a curve passing through the middle of a distribution. While the intuition is clear, the formal definition leads to some technical and practical difficulties. In particular, principal curves are saddle points of the mean-squared projection distance, which poses severe challenges for estimation and model selection. This paper demonstrates that the difficulties in model selection associated with the saddle point property of principal curves are intrinsically tied to the minimization of the mean-squared projection distance. We introduce a new objective function, facilitated through a modification of the principal curve estimation approach, for which all critical points are principal curves and minima. Thus, the new formulation removes the fundamental issue for model selection in principal curve estimation. A gradient-descent-based estimator demonstrates the effectiveness of the new formulation for controlling model complexity on numerical experiments with synthetic and real data.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {1285–1302},
numpages = {18},
keywords = {principal curve, manifold estimation, model selection, unsupervised learning, model complexity}
}

@article{10.5555/2567709.2502620,
author = {Cesa-Bianchi, Nicol\`{o} and Gentile, Claudio and Vitale, Fabio and Zappella, Giovanni},
title = {Random Spanning Trees and the Prediction Ofweighted Graphs},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {We investigate the problem of sequentially predicting the binary labels on the nodes of an arbitrary weighted graph. We show that, under a suitable parametrization of the problem, the optimal number of prediction mistakes can be characterized (up to logarithmic factors) by the cutsize of a random spanning tree of the graph. The cutsize is induced by the unknown adversarial labeling of the graph nodes. In deriving our characterization, we obtain a simple randomized algorithm achieving in expectation the optimal mistake bound on any polynomially connected weighted graph. Our algorithm draws a random spanning tree of the original graph and then predicts the nodes of this tree in constant expected amortized time and linear space. Experiments on real-world data sets show that our method compares well to both global (Perceptron) and local (label propagation) methods, while being generally faster in practice.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {1251–1284},
numpages = {34},
keywords = {learning on graphs, graph prediction, online learning, random spanning trees}
}

@article{10.5555/2567709.2502619,
author = {Niyogi, Partha},
title = {Manifold Regularization and Semi-Supervised Learning: Some Theoretical Analyses},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Manifold regularization (Belkin et al., 2006) is a geometrically motivated framework for machine learning within which several semi-supervised algorithms have been constructed. Here we try to provide some theoretical understanding of this approach. Our main result is to expose the natural structure of a class of problems on which manifold regularization methods are helpful. We show that for such problems, no supervised learner can learn effectively. On the other hand, a manifold based learner (that knows the manifold or "learns" it from unlabeled examples) can learn with relatively few labeled examples. Our analysis follows a minimax style with an emphasis on finite sample results (in terms of n: the number of labeled examples). These results allow us to properly interpret manifold regularization and related spectral and geometric algorithms in terms of their potential use in semi-supervised learning.},
journal = {J. Mach. Learn. Res.},
month = may,
pages = {1229–1250},
numpages = {22},
keywords = {manifold regularization, minimax rates, graph Laplacian, semi-supervised learning}
}

@article{10.5555/2567709.2502618,
author = {Scherrer, Bruno},
title = {Performance Bounds for λ Policy Iteration and Application to the Game of Tetris},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {We consider the discrete-time infinite-horizon optimal control problem formalized by Markov decision processes (Puterman, 1994; Bertsekas and Tsitsiklis, 1996). We revisit the work of Bertsekas and Ioffe (1996), that introduced λ policy iteration--a family of algorithms parametrized by a parameter λ--that generalizes the standard algorithms value and policy iteration, and has some deep connections with the temporal-difference algorithms described by Sutton and Barto (1998). We deepen the original theory developed by the authors by providing convergence rate bounds which generalize standard bounds for value iteration described for instance by Puterman (1994). Then, the main contribution of this paper is to develop the theory of this algorithm when it is used in an approximate form. We extend and unify the separate analyzes developed by Munos for approximate value iteration (Munos, 2007) and approximate policy iteration (Munos, 2003), and provide performance bounds in the discounted and the undiscounted situations. Finally, we revisit the use of this algorithm in the training of a Tetris playing controller as originally done by Bertsekas and Ioffe (1996). Our empirical results are different from those of Bertsekas and Ioffe (which were originally qualified as "paradoxical" and "intriguing"). We track down the reason to be a minor implementation error of the algorithm, which suggests that, in practice, l policy iteration may be more stable than previously thought.},
journal = {J. Mach. Learn. Res.},
month = apr,
pages = {1181–1227},
numpages = {47},
keywords = {reinforcement learning, stochastic optimal control, Markov decision processes, analysis of algorithms}
}

@article{10.5555/2567709.2502617,
author = {Vanhatalo, Jarno and Riihim\"{a}ki, Jaakko and Hartikainen, Jouni and Jyl\"{a}nki, Pasi and Tolvanen, Ville and Vehtari, Aki},
title = {GPstuff: Bayesian Modeling with Gaussian Processes},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {The GPstuff toolbox is a versatile collection of Gaussian process models and computational tools required for Bayesian inference. The tools include, among others, various inference methods, sparse approximations and model assessment methods.},
journal = {J. Mach. Learn. Res.},
month = apr,
pages = {1175–1179},
numpages = {5},
keywords = {Bayesian hierarchical model, nonparametric Bayes, Gaussian process}
}

@article{10.5555/2567709.2502616,
author = {Chen, Lisha and Buja, Andreas},
title = {Stress Functions for Nonlinear Dimension Reduction, Proximity Analysis, and Graph Drawing},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Multidimensional scaling (MDS) is the art of reconstructing pointsets (embeddings) from pairwise distance data, and as such it is at the basis of several approaches to nonlinear dimension reduction and manifold learning. At present, MDS lacks a unifying methodology as it consists of a discrete collection of proposals that differ in their optimization criteria, called "stress functions". To correct this situation we propose (1) to embed many of the extant stress functions in a parametric family of stress functions, and (2) to replace the ad hoc choice among discrete proposals with a principled parameter selection method. This methodology yields the following benefits and problem solutions: (a) It provides guidance in tailoring stress functions to a given data situation, responding to the fact that no single stress function dominates all others across all data situations; (b) the methodology enriches the supply of available stress functions; (c) it helps our understanding of stress functions by replacing the comparison of discrete proposals with a characterization of the effect of parameters on embeddings; (d) it builds a bridge to graph drawing, which is the related but not identical art of constructing embeddings from graphs.},
journal = {J. Mach. Learn. Res.},
month = apr,
pages = {1145–1173},
numpages = {29},
keywords = {force-directed layout, Box-Cox transformations, clustering strength, unsupervised learning, cluster analysis, multidimensional scaling}
}

@article{10.5555/2567709.2502615,
author = {Thom, Markus and Palm, G\"{u}nther},
title = {Sparse Activity and Sparse Connectivity in Supervised Learning},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Sparseness is a useful regularizer for learning in a wide range of applications, in particular in neural networks. This paper proposes a model targeted at classification tasks, where sparse activity and sparse connectivity are used to enhance classification capabilities. The tool for achieving this is a sparseness-enforcing projection operator which finds the closest vector with a pre-defined sparseness for any given vector. In the theoretical part of this paper, a comprehensive theory for such a projection is developed. In conclusion, it is shown that the projection is differentiable almost everywhere and can thus be implemented as a smooth neuronal transfer function. The entire model can hence be tuned end-to-end using gradient-based methods. Experiments on the MNIST database of handwritten digits show that classification performance can be boosted by sparse activity or sparse connectivity. With a combination of both, performance can be significantly better compared to classical non-sparse approaches.},
journal = {J. Mach. Learn. Res.},
month = apr,
pages = {1091–1143},
numpages = {53},
keywords = {sparseness projection, sparse connectivity, supervised learning, sparse activity}
}

@article{10.5555/2567709.2502614,
author = {Zhao, Ming-Jie and Edakunni, Narayanan and Pocock, Adam and Brown, Gavin},
title = {Beyond Fano's Inequality: Bounds on the Optimal F-Score, BER, and Cost-Sensitive Risk and Their Implications},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Fano's inequality lower bounds the probability of transmission error through a communication channel. Applied to classification problems, it provides a lower bound on the Bayes error rate and motivates the widely used Infomax principle. In modern machine learning, we are often interested in more than just the error rate. In medical diagnosis, different errors incur different cost; hence, the overall risk is cost-sensitive. Two other popular criteria are balanced error rate (BER) and F-score. In this work, we focus on the two-class problem and use a general definition of conditional entropy (including Shannon's as a special case) to derive upper/lower bounds on the optimal F-score, BER and cost-sensitive risk, extending Fano's result. As a consequence, we show that Infomax is not suitable for optimizing F-score or cost-sensitive risk, in that it can potentially lead to low F-score and high risk. For cost-sensitive risk, we propose a new conditional entropy formulation which avoids this inconsistency. In addition, we consider the common practice of using a threshold on the posterior probability to tune performance of a classifier. As is widely known, a threshold of 0.5, where the posteriors cross, minimizes error rate--we derive similar optimal thresholds for F-score and BER.},
journal = {J. Mach. Learn. Res.},
month = apr,
pages = {1033–1090},
numpages = {58},
keywords = {F-score (Fβ-measure), cost-sensitive risk, lower/upper bound, conditional entropy, balanced error rate}
}

@article{10.5555/2567709.2502613,
author = {Wang, Chong and Blei, David M.},
title = {Variational Inference in Nonconjugate Models},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Mean-field variational methods are widely used for approximate posterior inference in many probabilistic models. In a typical application, mean-field methods approximately compute the posterior with a coordinate-ascent optimization algorithm. When the model is conditionally conjugate, the coordinate updates are easily derived and in closed form. However, many models of interest--like the correlated topic model and Bayesian logistic regression--are nonconjugate. In these models, mean-field methods cannot be directly applied and practitioners have had to develop variational algorithms on a case-by-case basis. In this paper, we develop two generic methods for nonconjugate models, Laplace variational inference and delta method variational inference. Our methods have several advantages: they allow for easily derived variational algorithms with a wide class of nonconjugate models; they extend and unify some of the existing algorithms that have been derived for specific models; and they work well on real-world data sets. We studied our methods on the correlated topic model, Bayesian logistic regression, and hierarchical Bayesian logistic regression.},
journal = {J. Mach. Learn. Res.},
month = apr,
pages = {1005–1031},
numpages = {27},
keywords = {nonconjugate models, the multivariate delta method, variational inference, Laplace approximations}
}

@article{10.5555/2567709.2502612,
author = {Klami, Arto and Virtanen, Seppo and Kaski, Samuel},
title = {Bayesian Canonical Correlation Analysis},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Canonical correlation analysis (CCA) is a classical method for seeking correlations between two multivariate data sets. During the last ten years, it has received more and more attention in the machine learning community in the form of novel computational formulations and a plethora of applications. We review recent developments in Bayesian models and inference methods for CCA which are attractive for their potential in hierarchical extensions and for coping with the combination of large dimensionalities and small sample sizes. The existing methods have not been particularly successful in fulfilling the promise yet; we introduce a novel efficient solution that imposes group-wise sparsity to estimate the posterior of an extended model which not only extracts the statistical dependencies (correlations) between data sets but also decomposes the data into shared and data set-specific components. In statistics literature the model is known as inter-battery factor analysis (IBFA), for which we now provide a Bayesian treatment.},
journal = {J. Mach. Learn. Res.},
month = apr,
pages = {965–1003},
numpages = {39},
keywords = {Bayesian modeling, inter-battery factor analysis, group-wise sparsity, variational Bayesian approximation, canonical correlation analysis}
}

@article{10.5555/2567709.2502611,
author = {Niehren, Joachim and Champav\`{e}re, J\'{e}r\^{o}me and Lemay, Aur\'{e}lien and Gilleron, R\'{e}mi},
title = {Query Induction with Schema-Guided Pruning Strategies},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Inference algorithms for tree automata that define node selecting queries in unranked trees rely on tree pruning strategies. These impose additional assumptions on node selection that are needed to compensate for small numbers of annotated examples. Pruning-based heuristics in query learning algorithms for Web information extraction often boost the learning quality and speed up the learning process. We will distinguish the class of regular queries that are stable under a given schemaguided pruning strategy, and show that this class is learnable with polynomial time and data. Our learning algorithm is obtained by adding pruning heuristics to the traditional learning algorithm for tree automata from positive and negative examples. While justified by a formal learning model, our learning algorithm for stable queries also performs very well in practice of XML information extraction.},
journal = {J. Mach. Learn. Res.},
month = apr,
pages = {927–964},
numpages = {38},
keywords = {interactive learning, XML schemas, grammatical inference, XML information extraction, tree automata}
}

@article{10.5555/2567709.2502610,
author = {Yuan, Xiao-Tong and Zhang, Tong},
title = {Truncated Power Method for Sparse Eigenvalue Problems},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {This paper considers the sparse eigenvalue problem, which is to extract dominant (largest) sparse eigenvectors with at most k non-zero components. We propose a simple yet effective solution called truncated power method that can approximately solve the underlying nonconvex optimization problem. A strong sparse recovery result is proved for the truncated power method, and this theory is our key motivation for developing the new algorithm. The proposed method is tested on applications such as sparse principal component analysis and the densest k-subgraph problem. Extensive experiments on several synthetic and real-world data sets demonstrate the competitive empirical performance of our method.},
journal = {J. Mach. Learn. Res.},
month = apr,
pages = {899–925},
numpages = {27},
keywords = {power method, sparse eigenvalue, sparse principal component analysis, densest k-subgraph}
}

@article{10.5555/2567709.2502609,
author = {Watanabe, Sumio},
title = {A Widely Applicable Bayesian Information Criterion},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {A statistical model or a learning machine is called regular if the map taking a parameter to a probability distribution is one-to-one and if its Fisher information matrix is always positive definite. If otherwise, it is called singular. In regular statistical models, the Bayes free energy, which is defined by the minus logarithm of Bayes marginal likelihood, can be asymptotically approximated by the Schwarz Bayes information criterion (BIC), whereas in singular models such approximation does not hold.Recently, it was proved that the Bayes free energy of a singular model is asymptotically given by a generalized formula using a birational invariant, the real log canonical threshold (RLCT), instead of half the number of parameters in BIC. Theoretical values of RLCTs in several statistical models are now being discovered based on algebraic geometrical methodology. However, it has been difficult to estimate the Bayes free energy using only training samples, because an RLCT depends on an unknown true distribution.In the present paper, we define a widely applicable Bayesian information criterion (WBIC) by the average log likelihood function over the posterior distribution with the inverse temperature 1/log n, where n is the number of training samples. We mathematically prove that WBIC has the same asymptotic expansion as the Bayes free energy, even if a statistical model is singular for or unrealizable by a statistical model. Since WBIC can be numerically calculated without any information about a true distribution, it is a generalized version of BIC onto singular statistical models.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {867–897},
numpages = {31},
keywords = {Bayes marginal likelihood, widely applicable Bayes information criterion}
}

@article{10.5555/2567709.2502608,
author = {Hennig, Philipp and Kiefel, Martin},
title = {Quasi-Newton Methods: A New Direction},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Four decades after their invention, quasi-Newton methods are still state of the art in unconstrained numerical optimization. Although not usually interpreted thus, these are learning algorithms that fit a local quadratic approximation to the objective function. We show that many, including the most popular, quasi-Newton methods can be interpreted as approximations of Bayesian linear regression under varying prior assumptions. This new notion elucidates some shortcomings of classical algorithms, and lights the way to a novel nonparametric quasi-Newton method, which is able to make more efficient use of available information at computational cost similar to its predecessors.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {843–865},
numpages = {23},
keywords = {optimization, numerical analysis, probability, Gaussian processes}
}

@article{10.5555/2567709.2502607,
author = {Bahmani, Sohail and Raj, Bhiksha and Boufounos, Petros T.},
title = {Greedy Sparsity-Constrained Optimization},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Sparsity-constrained optimization has wide applicability in machine learning, statistics, and signal processing problems such as feature selection and Compressed Sensing. A vast body of work has studied the sparsity-constrained optimization from theoretical, algorithmic, and application aspects in the context of sparse estimation in linear models where the fidelity of the estimate is measured by the squared error. In contrast, relatively less effort has been made in the study of sparsity-constrained optimization in cases where nonlinear models are involved or the cost function is not quadratic. In this paper we propose a greedy algorithm, Gradient Support Pursuit (GraSP), to approximate sparse minima of cost functions of arbitrary form. Should a cost function have a Stable Restricted Hessian (SRH) or a Stable Restricted Linearization (SRL), both of which are introduced in this paper, our algorithm is guaranteed to produce a sparse vector within a bounded distance from the true sparse optimum. Our approach generalizes known results for quadratic cost functions that arise in sparse linear regression and Compressed Sensing. We also evaluate the performance of GraSP through numerical simulations on synthetic and real data, where the algorithm is employed for sparse logistic regression with and without l2-regularization.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {807–841},
numpages = {35},
keywords = {greedy algorithm, optimization, compressed sensing, sparsity}
}

@article{10.5555/2567709.2502606,
author = {Curtin, Ryan R. and Cline, James R. and Slagle, N. P. and March, William B. and Ram, Parikshit and Mehta, Nishant A. and Gray, Alexander G.},
title = {MLPACK: A Scalable C++ Machine Learning Library},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {MLPACK is a state-of-the-art, scalable, multi-platform C++ machine learning library released in late 2011 offering both a simple, consistent API accessible to novice users and high performance and flexibility to expert users by leveraging modern features of C++. MLPACK provides cutting-edge algorithms whose benchmarks exhibit far better performance than other leading machine learning libraries. MLPACK version 1.0.3, licensed under the LGPL, is available at http://www.mlpack.org.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {801–805},
numpages = {5},
keywords = {largescale learning, dual-tree algorithms, machine learning software, open source software, c++}
}

@article{10.5555/2567709.2502605,
author = {Wang, Jun and Jebara, Tony and Chang, Shih-Fu},
title = {Semi-Supervised Learning Using Greedy Max-Cut},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Graph-based semi-supervised learning (SSL) methods play an increasingly important role in practical machine learning systems, particularly in agnostic settings when no parametric information or other prior knowledge is available about the data distribution. Given the constructed graph represented by a weight matrix, transductive inference is used to propagate known labels to predict the values of all unlabeled vertices. Designing a robust label diffusion algorithm for such graphs is a widely studied problem and various methods have recently been suggested. Many of these can be formalized as regularized function estimation through the minimization of a quadratic cost. However, most existing label diffusion methods minimize a univariate cost with the classification function as the only variable of interest. Since the observed labels seed the diffusion process, such univariate frameworks are extremely sensitive to the initial label choice and any label noise. To alleviate the dependency on the initial observed labels, this article proposes a bivariate formulation for graph-based SSL, where both the binary label information and a continuous classification function are arguments of the optimization. This bivariate formulation is shown to be equivalent to a linearly constrained Max-Cut problem. Finally an efficient solution via greedy gradient Max-Cut (GGMC) is derived which gradually assigns unlabeled vertices to each class with minimum connectivity. Once convergence guarantees are established, this greedy Max-Cut based SSL is applied on both artificial and standard benchmark data sets where it obtains superior classification accuracy compared to existing state-of-the-art SSL methods. Moreover, GGMC shows robustness with respect to the graph construction method and maintains high accuracy over extensive experiments with various edge linking and weighting schemes.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {771–800},
numpages = {30},
keywords = {semi-supervised learning, graph transduction, bivariate formulation, mixed integer programming, greedy max-cut}
}

@article{10.5555/2567709.2502604,
author = {Gerchinovitz, S\'{e}bastien},
title = {Sparsity Regret Bounds for Individual Sequences in Online Linear Regression},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {We consider the problem of online linear regression on arbitrary deterministic sequences when the ambient dimension d can be much larger than the number of time rounds T. We introduce the notion of sparsity regret bound, which is a deterministic online counterpart of recent risk bounds derived in the stochastic setting under a sparsity scenario. We prove such regret bounds for an online-learning algorithm called SeqSEW and based on exponential weighting and data-driven truncation. In a second part we apply a parameter-free version of this algorithm to the stochastic setting (regression model with random design). This yields risk bounds of the same flavor as in Dalalyan and Tsybakov (2012a) but which solve two questions left open therein. In particular our risk bounds are adaptive (up to a logarithmic factor) to the unknown variance of the noise if the latter is Gaussian. We also address the regression model with fixed design.},
journal = {J. Mach. Learn. Res.},
month = mar,
pages = {729–769},
numpages = {41},
keywords = {adaptive regret bounds, online linear regression, individual sequences, sparsity}
}

@article{10.5555/2567709.2502603,
author = {Hall, Rob and Rinaldo, Alessandro and Wasserman, Larry},
title = {Differential Privacy for Functions and Functional Data},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Differential privacy is a rigorous cryptographically-motivated characterization of data privacy which may be applied when releasing summaries of a database. Previous work has focused mainly on methods for which the output is a finite dimensional vector, or an element of some discrete set. We develop methods for releasing functions while preserving differential privacy. Specifically, we show that adding an appropriate Gaussian process to the function of interest yields differential privacy. When the functions lie in the reproducing kernel Hilbert space (RKHS) generated by the covariance kernel of the Gaussian process, then the correct noise level is established by measuring the "sensitivity" of the function in the RKHS norm. As examples we consider kernel density estimation, kernel support vector machines, and functions in RKHSs.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {703–727},
numpages = {25},
keywords = {density estimation, Gaussian processes, differential privacy, reproducing kernel Hilbert space}
}

@article{10.5555/2567709.2502602,
author = {Johnson, Matthew J. and Willsky, Alan S.},
title = {Bayesian Nonparametric Hidden Semi-Markov Models},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {There is much interest in the Hierarchical Dirichlet Process Hidden Markov Model (HDP-HMM) as a natural Bayesian nonparametric extension of the ubiquitous Hidden Markov Model for learning from sequential and time-series data. However, in many settings the HDP-HMM's strict Markovian constraints are undesirable, particularly if we wish to learn or encode non-geometric state durations. We can extend the HDP-HMM to capture such structure by drawing upon explicit-duration semi-Markov modeling, which has been developed mainly in the parametric non-Bayesian setting, to allow construction of highly interpretable models that admit natural prior information on state durations.In this paper we introduce the explicit-duration Hierarchical Dirichlet Process Hidden semi-Markov Model (HDP-HSMM) and develop sampling algorithms for efficient posterior inference. The methods we introduce also provide new methods for sampling inference in the finite Bayesian HSMM. Our modular Gibbs sampling methods can be embedded in samplers for larger hierarchical Bayesian models, adding semi-Markov chain modeling as another tool in the Bayesian inference toolbox. We demonstrate the utility of the HDP-HSMM and our inference methods on both synthetic and real experiments.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {673–701},
numpages = {29},
keywords = {Bayesian nonparametrics, sampling algorithms, time series, hierarchical dirichlet process hidden markov model, semi-Markov}
}

@article{10.5555/2567709.2502601,
author = {Han, Fang and Zhao, Tuo and Liu, Han},
title = {CODA: High Dimensional Copula Discriminant Analysis},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {We propose a high dimensional classification method, named the Copula Discriminant Analysis (CODA). The CODA generalizes the normal-based linear discriminant analysis to the larger Gaussian Copula models (or the nonparanormal) as proposed by Liu et al. (2009). To simultaneously achieve estimation efficiency and robustness, the nonparametric rank-based methods including the Spearman's rho and Kendall's tau are exploited in estimating the covariance matrix. In high dimensional settings, we prove that the sparsity pattern of the discriminant features can be consistently recovered with the parametric rate, and the expected misclassification error is consistent to the Bayes risk. Our theory is backed up by careful numerical experiments, which show that the extra flexibility gained by the CODA method incurs little efficiency loss even when the data are truly Gaussian. These results suggest that the CODA method can be an alternative choice besides the normal-based high dimensional linear discriminant analysis.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {629–671},
numpages = {43},
keywords = {rank-based statistics, high dimensional statistics, Gaussian copula, sparse nonlinear discriminant analysis, nonparanormal distribution}
}

@article{10.5555/2567709.2502600,
author = {Frezza-Buet, Herv\'{e} and Geist, Matthieu},
title = {A C++ Template-Based Reinforcement Learning Library: Fitting the Code to the Mathematics},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {This paper introduces the rllib as an original C++ template-based library oriented toward value function estimation. Generic programming is promoted here as a way of having a good fit between the mathematics of reinforcement learning and their implementation in a library. The main concepts of rllib are presented, as well as a short example.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {625–628},
numpages = {4},
keywords = {generic programming, C++, reinforcement learning}
}

@article{10.5555/2567709.2502599,
author = {Bubeck, S\'{e}bastien and Ernst, Damien and Garivier, Aur\'{e}lien},
title = {Optimal Discovery with Probabilistic Expert Advice: Finite Time Analysis and Macroscopic Optimality},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {We consider an original problem that arises from the issue of security analysis of a power system and that we name optimal discovery with probabilistic expert advice. We address it with an algorithm based on the optimistic paradigm and on the Good-Turing missing mass estimator. We prove two different regret bounds on the performance of this algorithm under weak assumptions on the probabilistic experts. Under more restrictive hypotheses, we also prove a macroscopic optimality result, comparing the algorithm both with an oracle strategy and with uniform sampling. Finally, we provide numerical experiments illustrating these theoretical findings.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {601–623},
numpages = {23},
keywords = {optimistic algorithm, probabilistic experts, good-turing estimator, optimal discovery, UCB}
}

@article{10.5555/2567709.2502598,
author = {Shalev-Shwartz, Shai and Zhang, Tong},
title = {Stochastic Dual Coordinate Ascent Methods for Regularized Loss},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Stochastic Gradient Descent (SGD) has become popular for solving large scale supervised machine learning optimization problems such as SVM, due to their strong theoretical guarantees. While the closely related Dual Coordinate Ascent (DCA) method has been implemented in various software packages, it has so far lacked good convergence analysis. This paper presents a new analysis of Stochastic Dual Coordinate Ascent (SDCA) showing that this class of methods enjoy strong theoretical guarantees that are comparable or better than SGD. This analysis justifies the effectiveness of SDCA for practical applications.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {567–599},
numpages = {33},
keywords = {logistic regression, stochastic dual coordinate ascent, optimization, ridge regression, regularized loss minimization, computational complexity, support vector machines}
}

@article{10.5555/2567709.2502597,
author = {Statnikov, Alexander and Lemeir, Jan and Aliferis, Constantin F.},
title = {Algorithms for Discovery of Multiple Markov Boundaries},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Algorithms for Markov boundary discovery from data constitute an important recent development in machine learning, primarily because they offer a principled solution to the variable/feature selection problem and give insight on local causal structure. Over the last decade many sound algorithms have been proposed to identify a single Markov boundary of the response variable. Even though faithful distributions and, more broadly, distributions that satisfy the intersection property always have a single Markov boundary, other distributions/data sets may have multipleMarkov boundaries of the response variable. The latter distributions/data sets are common in practical data-analytic applications, and there are several reasons why it is important to induce multiple Markov boundaries from such data. However, there are currently no sound and efficient algorithms that can accomplish this task. This paper describes a family of algorithms TIE* that can discover all Markov boundaries in a distribution. The broad applicability as well as efficiency of the new algorithmic family is demonstrated in an extensive benchmarking study that involved comparison with 26 state-of-the-art algorithms/variants in 15 data sets from a diversity of application domains.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {499–566},
numpages = {68},
keywords = {information equivalence, variable/feature selection, violations of faithfulness, Markov boundary discovery}
}

@article{10.5555/2567709.2502596,
author = {Mukherjee, Indraneel and Schapire, Robert E.},
title = {A Theory of Multiclass Boosting},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Boosting combines weak classifiers to form highly accurate predictors. Although the case of binary classification is well understood, in the multiclass setting, the "correct" requirements on the weak classifier, or the notion of the most efficient boosting algorithms are missing. In this paper, we create a broad and general framework, within which we make precise and identify the optimal requirements on the weak-classifier, as well as design the most effective, in a certain sense, boosting algorithms that assume such requirements.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {437–497},
numpages = {61},
keywords = {drifting games, boosting, weak learning condition, multiclass}
}

@article{10.5555/2567709.2502595,
author = {Slivkins, Aleksandrs and Radlinski, Filip and Gollapudi, Sreenivas},
title = {Ranked Bandits in Metric Spaces: Learning Diverse Rankings over Large Document Collections},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Most learning to rank research has assumed that the utility of different documents is independent, which results in learned ranking functions that return redundant results. The few approaches that avoid this have rather unsatisfyingly lacked theoretical foundations, or do not scale. We present a learning-to-rank formulation that optimizes the fraction of satisfied users, with several scalable algorithms that explicitly takes document similarity and ranking context into account. Our formulation is a non-trivial common generalization of two multi-armed bandit models from the literature: ranked bandits (Radlinski et al., 2008) and Lipschitz bandits (Kleinberg et al., 2008b). We present theoretical justifications for this approach, as well as a near-optimal algorithm. Our evaluation adds optimizations that improve empirical performance, and shows that our algorithms learn orders of magnitude more quickly than previous approaches.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {399–436},
numpages = {38},
keywords = {contextual bandits, metric spaces, online learning, clickthrough data, diversity, multi-armed bandits, regret}
}

@article{10.5555/2567709.2502594,
author = {Hu, Ting and Fan, Jun and Wu, Qiang and Zhou, Ding-Xuan},
title = {Learning Theory Approach to Minimum Error Entropy Criterion},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {We consider the minimum error entropy (MEE) criterion and an empirical risk minimization learning algorithm when an approximation of R\'{e}nyi's entropy (of order 2) by Parzen windowing is minimized. This learning algorithm involves a Parzen windowing scaling parameter. We present a learning theory approach for this MEE algorithm in a regression setting when the scaling parameter is large. Consistency and explicit convergence rates are provided in terms of the approximation ability and capacity of the involved hypothesis space. Novel analysis is carried out for the generalization error associated with R\'{e}nyi's entropy and a Parzen windowing function, to overcome technical difficulties arising from the essential differences between the classical least squares problems and the MEE setting. An involved symmetrized least squares error is introduced and analyzed, which is related to some ranking algorithms.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {377–397},
numpages = {21},
keywords = {empirical risk minimization, minimum error entropy, R\'{e}nyi's entropy, approximation error, learning theory}
}

@article{10.5555/2567709.2502593,
author = {Zhang, Chao and Tao, Dacheng},
title = {Risk Bounds of Learning Processes for L\'{e}vy Processes},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {L\'{e}evy processes refer to a class of stochastic processes, for example, Poisson processes and Brownian motions, and play an important role in stochastic processes and machine learning. Therefore, it is essential to study risk bounds of the learning process for time-dependent samples drawn from a L\'{e}evy process (or briefly called learning process for L\'{e}evy process). It is noteworthy that samples in this learning process are not independently and identically distributed (i.i.d.). Therefore, results in traditional statistical learning theory are not applicable (or at least cannot be applied directly), because they are obtained under the sample-i.i.d. assumption. In this paper, we study risk bounds of the learning process for time-dependent samples drawn from a L\'{e}evy process, and then analyze the asymptotical behavior of the learning process. In particular, we first develop the deviation inequalities and the symmetrization inequality for the learning process. By using the resultant inequalities, we then obtain the risk bounds based on the covering number. Finally, based on the resulting risk bounds, we study the asymptotic convergence and the rate of convergence of the learning process for L\'{e}evy process. Meanwhile, we also give a comparison to the related results under the sample-i.i.d. assumption.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {351–376},
numpages = {26},
keywords = {statistical learning theory, deviation inequality, symmetrization inequality, risk bound, time-dependent, L\'{e}evy process}
}

@article{10.5555/2567709.2502592,
author = {Chalupka, Krzysztof and Williams, Christopher K. I. and Murray, Iain},
title = {A Framework for Evaluating Approximation Methods for Gaussian Process Regression},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Gaussian process (GP) predictors are an important component of many Bayesian approaches to machine learning. However, even a straightforward implementation of Gaussian process regression (GPR) requires O(n2) space and O(n3) time for a data set of n examples. Several approximation methods have been proposed, but there is a lack of understanding of the relative merits of the different approximations, and in what situations they are most useful. We recommend assessing the quality of the predictions obtained as a function of the compute time taken, and comparing to standard baselines (e.g., Subset of Data and FITC). We empirically investigate four different approximation algorithms on four different prediction problems, and make our code available to encourage future comparisons.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {333–350},
numpages = {18},
keywords = {local GP, FITC, subset of data, Gaussian process regression}
}

@article{10.5555/2567709.2502591,
author = {Valsalam, Vinod K. and Miikkulainen, Risto},
title = {Using Symmetry and Evolutionary Search to Minimize Sorting Networks},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Sorting networks are an interesting class of parallel sorting algorithms with applications in multiprocessor computers and switching networks. They are built by cascading a series of comparison-exchange units called comparators. Minimizing the number of comparators for a given number of inputs is a challenging optimization problem. This paper presents a two-pronged approach called Symmetry and Evolution based Network Sort Optimization (SENSO) that makes it possible to scale the solutions to networks with a larger number of inputs than previously possible. First, it uses the symmetry of the problem to decompose the minimization goal into subgoals that are easier to solve. Second, it minimizes the resulting greedy solutions further by using an evolutionary algorithm to learn the statistical distribution of comparators in minimal networks. The final solutions improve upon half-century of results published in patents, books, and peer-reviewed literature, demonstrating the potential of the SENSO approach for solving difficult combinatorial problems.},
journal = {J. Mach. Learn. Res.},
month = feb,
pages = {303–331},
numpages = {29},
keywords = {combinatorial optimization, sorting networks, evolution, symmetry, estimation of distribution algorithms}
}

@article{10.5555/2567709.2567774,
author = {Forghani, Yahya and Sadoghi, Hadi},
title = {Comment on "Robustness and Regularization of Support Vector Machines" by H. Xu et al. (Journal of Machine Learning Research, Vol. 10, Pp. 1485-1510, 2009)},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {This paper comments on the published work dealing with robustness and regularization of support vector machines (Journal of Machine Learning Research, Vol. 10, pp. 1485-1510, 2009) by H. Xu et al. They proposed a theorem to show that it is possible to relate robustness in the feature space and robustness in the sample space directly. In this paper, we propose a counter example that rejects their theorem.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3493–3494},
numpages = {2},
keywords = {support vector machine, kernel, robustness}
}

@article{10.5555/2567709.2567773,
author = {Rudin, Cynthia and Letham, Benjamin and Madigan, David},
title = {Learning Theory Analysis for Association Rules and Sequential Event Prediction},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {We present a theoretical analysis for prediction algorithms based on association rules. As part of this analysis, we introduce a problem for which rules are particularly natural, called "sequential event prediction." In sequential event prediction, events in a sequence are revealed one by one, and the goal is to determine which event will next be revealed. The training set is a collection of past sequences of events. An example application is to predict which item will next be placed into a customer's online shopping cart, given his/her past purchases. In the context of this problem, algorithms based on association rules have distinct advantages over classical statistical and machine learning methods: they look at correlations based on subsets of co-occurring past events (items a and b imply item c), they can be applied to the sequential event prediction problem in a natural way, they can potentially handle the "cold start" problem where the training set is small, and they yield interpretable predictions. In this work, we present two algorithms that incorporate association rules. These algorithms can be used both for sequential event prediction and for supervised classification, and they are simple enough that they can possibly be understood by users, customers, patients, managers, etc. We provide generalization guarantees on these algorithms based on algorithmic stability analysis from statistical learning theory. We include a discussion of the strict minimum support threshold often used in association rule mining, and introduce an "adjusted confidence" measure that provides a weaker minimum support condition that has advantages over the strict minimum support. The paper brings together ideas from statistical learning theory, association rule mining and Bayesian analysis.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3441–3492},
numpages = {52},
keywords = {algorithmic stability, associative classification, association rules, statistical learning theory, sequence prediction}
}

@article{10.5555/2567709.2567772,
author = {Sun, Wei and Wang, Junhui and Fang, Yixin},
title = {Consistent Selection of Tuning Parameters via Variable Selection Stability},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Penalized regression models are popularly used in high-dimensional data analysis to conduct variable selection and model fitting simultaneously. Whereas success has been widely reported in literature, their performances largely depend on the tuning parameters that balance the trade-off between model fitting and model sparsity. Existing tuning criteria mainly follow the route of minimizing the estimated prediction error or maximizing the posterior model probability, such as cross validation, AIC and BIC. This article introduces a general tuning parameter selection criterion based on variable selection stability. The key idea is to select the tuning parameters so that the resultant penalized regression model is stable in variable selection. The asymptotic selection consistency is established for both fixed and diverging dimensions. Its effectiveness is also demonstrated in a variety of simulated examples as well as an application to the prostate cancer data.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3419–3440},
numpages = {22},
keywords = {stability, kappa coefficient, tuning, selection consistency, penalized regression}
}

@article{10.5555/2567709.2567771,
author = {Sun, Tingni and Zhang, Cun-Hui},
title = {Sparse Matrix Inversion with Scaled Lasso},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {We propose a new method of learning a sparse nonnegative-definite target matrix. Our primary example of the target matrix is the inverse of a population covariance or correlation matrix. The algorithm first estimates each column of the target matrix by the scaled Lasso and then adjusts the matrix estimator to be symmetric. The penalty level of the scaled Lasso for each column is completely determined by data via convex minimization, without using cross-validation.We prove that this scaled Lasso method guarantees the fastest proven rate of convergence in the spectrum norm under conditions of weaker form than those in the existing analyses of other l1 regularized algorithms, and has faster guaranteed rate of convergence when the ratio of the l1 and spectrum norms of the target inverse matrix diverges to infinity. A simulation study demonstrates the computational feasibility and superb performance of the proposed method.Our analysis also provides new performance bounds for the Lasso and scaled Lasso to guarantee higher concentration of the error at a smaller threshold level than previous analyses, and to allow the use of the union bound in column-by-column applications of the scaled Lasso without an adjustment of the penalty level. In addition, the least squares estimation after the scaled Lasso selection is considered and proven to guarantee performance bounds similar to that of the scaled Lasso.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3385–3418},
numpages = {34},
keywords = {concentration matrix, precision matrix, spectrum norm, inverse matrix, linear regression, scaled Lasso, graphical model}
}

@article{10.5555/2567709.2567770,
author = {Harris, Naftali and Drton, Mathias},
title = {PC Algorithm for Nonparanormal Graphical Models},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {The PC algorithm uses conditional independence tests for model selection in graphical modeling with acyclic directed graphs. In Gaussian models, tests of conditional independence are typically based on Pearson correlations, and high-dimensional consistency results have been obtained for the PC algorithm in this setting. Analyzing the error propagation from marginal to partial correlations, we prove that high-dimensional consistency carries over to a broader class of Gaussian copula or nonparanormal models when using rank-based measures of correlation. For graph sequences with bounded degree, our consistency result is as strong as prior Gaussian results. In simulations, the 'Rank PC' algorithm works as well as the 'Pearson PC' algorithm for normal data and considerably better for non-normal data, all the while incurring a negligible increase of computation time. While our interest is in the PC algorithm, the presented analysis of error propagation could be applied to other algorithms that test the vanishing of low-order partial correlations.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3365–3383},
numpages = {19},
keywords = {nonparanormal distribution, multivariate normal distribution, graphical model, model selection, Gaussian copula}
}

@article{10.5555/2567709.2567769,
author = {Zhang, Yuchen and Duchi, John C. and Wainwright, Martin J.},
title = {Communication-Efficient Algorithms for Statistical Optimization},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {We analyze two communication-efficient algorithms for distributed optimization in statistical settings involving large-scale data sets. The first algorithm is a standard averaging method that distributes the N data samples evenly to m machines, performs separate minimization on each subset, and then averages the estimates. We provide a sharp analysis of this average mixture algorithm, showing that under a reasonable set of conditions, the combined parameter achieves mean-squared error (MSE) that decays as O(N-1 +(N/m)-2). Whenever m ≤ √N, this guarantee matches the best possible rate achievable by a centralized algorithm having access to all N samples. The second algorithm is a novel method, based on an appropriate form of bootstrap subsampling. Requiring only a single round of communication, it has mean-squared error that decays as O(N-1 + (N/m)-3), and so is more robust to the amount of parallelization. In addition, we show that a stochastic gradient-based method attains mean-squared error decaying as O(N-1 + (N/m)-3/2), easing computation at the expense of a potentially slower MSE rate. We also provide an experimental evaluation of our methods, investigating their performance both on simulated data and on a large-scale regression problem from the internet search domain. In particular, we show that our methods can be used to efficiently solve an advertisement prediction problem from the Chinese SoSo Search Engine, which involves logistic regression with N ≈ 2.4\texttimes{}108 samples and d ≈ 740,000 covariates.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3321–3363},
numpages = {43},
keywords = {subsampling, stochastic optimization, distributed learning, averaging}
}

@article{10.5555/2567709.2567768,
author = {Rao, Vinayak and Teh, Yee Whye},
title = {Fast MCMC Sampling for Markov Jump Processes and Extensions},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Markov jump processes (or continuous-time Markov chains) are a simple and important class of continuous-time dynamical systems. In this paper, we tackle the problem of simulating from the posterior distribution over paths in these models, given partial and noisy observations. Our approach is an auxiliary variable Gibbs sampler, and is based on the idea of uniformization. This sets up a Markov chain over paths by alternately sampling a finite set of virtual jump times given the current path, and then sampling a new path given the set of extant and virtual jump times. The first step involves simulating a piecewise-constant inhomogeneous Poisson process, while for the second, we use a standard hidden Markov model forward filtering-backward sampling algorithm. Our method is exact and does not involve approximations like time-discretization. We demonstrate how our sampler extends naturally to MJP-based models like Markov-modulated Poisson processes and continuous-time Bayesian networks, and show significant computational benefits over state-of-the-art MCMC samplers for these models.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3295–3320},
numpages = {26},
keywords = {uniformization, MCMC, Markov jump process, Markov-modulated Poisson process, continuous-time Bayesian network, Gibbs sampler}
}

@article{10.5555/2567709.2567767,
author = {Hannah, Lauren A. and Dunson, David B.},
title = {Multivariate Convex Regression with Adaptive Partitioning},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {We propose a new, nonparametric method for multivariate regression subject to convexity or concavity constraints on the response function. Convexity constraints are common in economics, statistics, operations research, financial engineering and optimization, but there is currently no multivariate method that is stable and computationally feasible for more than a few thousand observations. We introduce convex adaptive partitioning (CAP), which creates a globally convex regression model from locally linear estimates fit on adaptively selected covariate partitions. CAP is a computationally efficient, consistent method for convex regression. We demonstrate empirical performance by comparing the performance of CAP to other shape-constrained and unconstrained regression methods for predicting weekly wages and value function approximation for pricing American basket options.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3261–3294},
numpages = {34},
keywords = {adaptive partitioning, nonparametric regression, treed linear model, convex regression, shape constraint}
}

@article{10.5555/2567709.2567766,
author = {Bottou, L\'{e}on and Peters, Jonas and Qui\~{n}onero-Candela, Joaquin and Charles, Denis X. and Chickering, D. Max and Portugaly, Elon and Ray, Dipankar and Simard, Patrice and Snelson, Ed},
title = {Counterfactual Reasoning and Learning Systems: The Example of Computational Advertising},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {This work shows how to leverage causal inference to understand the behavior of complex learning systems interacting with their environment and predict the consequences of changes to the system. Such predictions allow both humans and algorithms to select the changes that would have improved the system performance. This work is illustrated by experiments on the ad placement system associated with the Bing search engine.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3207–3260},
numpages = {54},
keywords = {counterfactual reasoning, causation, computational advertising}
}

@article{10.5555/2567709.2567765,
author = {Tacchetti, Andrea and Mallapragada, Pavan K. and Santoro, Matteo and Rosasco, Lorenzo},
title = {GURLS: A Least Squares Library for Supervised Learning},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {We present GURLS, a least squares, modular, easy-to-extend software library for efficient supervised learning. GURLS is targeted to machine learning practitioners, as well as non-specialists. It offers a number state-of-the-art training strategies for medium and large-scale learning, and routines for efficient model selection. The library is particularly well suited for multi-output problems (multi-category/multi-label). GURLS is currently available in two independent implementations: Matlab and C++. It takes advantage of the favorable properties of regularized least squares algorithm to exploit advanced tools in linear algebra. Routines to handle computations with very large matrices by means of memory-mapped storage and distributed task execution are available. The package is distributed under the BSD license and is available for download at https://github.com/LCSL/GURLS.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3201–3205},
numpages = {5},
keywords = {regularized least squares, linear algebra, big data}
}

@article{10.5555/2567709.2567764,
author = {Liu, Qiang and Ihler, Alexander},
title = {Variational Algorithms for Marginal MAP},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {The marginal maximum a posteriori probability (MAP) estimation problem, which calculates the mode of the marginal posterior distribution of a subset of variables with the remaining variables marginalized, is an important inference problem in many models, such as those with hidden variables or uncertain parameters. Unfortunately, marginal MAP can be NP-hard even on trees, and has attracted less attention in the literature compared to the joint MAP (maximization) and marginalization problems. We derive a general dual representation for marginal MAP that naturally integrates the marginalization and maximization operations into a joint variational optimization problem, making it possible to easily extend most or all variational-based algorithms to marginal MAP. In particular, we derive a set of "mixed-product" message passing algorithms for marginal MAP, whose form is a hybrid of max-product, sum-product and a novel "argmax-product" message updates. We also derive a class of convergent algorithms based on proximal point methods, including one that transforms the marginal MAP problem into a sequence of standard marginalization problems. Theoretically, we provide guarantees under which our algorithms give globally or locally optimal solutions, and provide novel upper bounds on the optimal objectives. Empirically, we demonstrate that our algorithms significantly outperform the existing approaches, including a state-of-the-art algorithm based on local search methods.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3165–3200},
numpages = {36},
keywords = {belief propagation, message passing, variational methods, graphical models, marginal-MAP, hidden variable models, maximum a posteriori}
}

@article{10.5555/2567709.2567763,
author = {Lewis, Joshua M. and De Sa, Virginia R. and Van Der Maaten, Laurens},
title = {Divvy: Fast and Intuitive Exploratory Data Analysis},
year = {2013},
issue_date = {January 2013},
publisher = {JMLR.org},
volume = {14},
number = {1},
issn = {1532-4435},
abstract = {Divvy is an application for applying unsupervised machine learning techniques (clustering and dimensionality reduction) to the data analysis process. Divvy provides a novel UI that allows researchers to tighten the action-perception loop of changing algorithm parameters and seeing a visualization of the result. Machine learning researchers can use Divvy to publish easy to use reference implementations of their algorithms, which helps themachine learning field have a greater impact on research practices elsewhere.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3159–3163},
numpages = {5},
keywords = {open source software, clustering, data visualization, dimensionality reduction, human computer interaction}
}

license: Unlicense

repository: goyalkaraniit/acm-cr

repo_name: goyalkaraniit/acm-cr