text:
, Ioannis},
title = {Constraint-Based Causal Discovery from Multiple Interventions over Overlapping Variable Sets},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {Scientific practice typically involves repeatedly studying a system, each time trying to unravel a different perspective. In each study, the scientist may take measurements under different experimental conditions (interventions, manipulations, perturbations) and measure different sets of quantities (variables). The result is a collection of heterogeneous data sets coming from different data distributions. In this work, we present algorithm COmbINE, which accepts a collection of data sets over overlapping variable sets under different experimental conditions; COmbINE then outputs a summary of all causal models indicating the invariant and variant structural characteristics of all models that simultaneously fit all of the input data sets. COmbINE converts estimated dependencies and independencies in the data into path constraints on the data-generating causal model and encodes them as a SAT instance. The algorithm is sound and complete in the sample limit. To account for conflicting constraints arising from statistical errors, we introduce a general method for sorting constraints in order of confidence, computed as a function of their corresponding p-values. In our empirical evaluation, COmbINE outperforms in terms of efficiency the only pre-existing similar algorithm; the latter additionally admits feedback cycles, but does not admit conflicting constraints which hinders the applicability on real data. As a proof-of-concept, COmbINE is employed to co-analyze 4 real, mass-cytometry data sets measuring phosphorylated protein concentrations of overlapping protein sets under 3 different interventions.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2147–2205},
numpages = {59},
keywords = {randomized experiments, semi-Markov causal models, maximal ancestral graphs, causal discovery, latent variables, graphical models, causality}
}

@article{10.5555/2789272.2886818,
author = {Zhang, Jian and Liu, Chao},
title = {On Linearly Constrained Minimum Variance Beamforming},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {Beamforming is a widely used technique for source localization in signal processing and neuroimaging. A number of vector-beamformers have been introduced to localize neuronal activity by using magnetoencephalography (MEG) data in the literature. However, the existing theoretical analyses on these beamformers have been limited to simple cases, where no more than two sources are allowed in the associated model and the theoretical sensor covariance is also assumed known. The information about the effects of the MEG spatial and temporal dimensions on the consistency of vector-beamforming is incomplete. In the present study, we consider a class of vector-beamformers defined by thresholding the sensor covariance matrix, which include the standard vector-beamformer as a special case. A general asymptotic theory is developed for these vector-beamformers, which shows the extent of effects to which the MEG spatial and temporal dimensions on estimating the neuronal activity index. The performances of the proposed beamformers are assessed by simulation studies. Superior performances of the proposed beamformers are obtained when the signal-to-noise ratio is low. We apply the proposed procedure to real MEG data sets derived from five sessions of a human face-perception experiment, finding several highly active areas in the brain. A good agreement between these findings and the known neurophysiology of the MEG response to human face perception is shown.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2099–2145},
numpages = {47},
keywords = {vector-beamforming, source localization and reconstruction, MEG neuroimaging, sparse covariance estimation}
}

@article{10.5555/2789272.2886817,
author = {Hermans, Michiel and Soriano, Miguel C. and Dambre, Joni and Bienstman, Peter and Fischer, Ingo},
title = {Photonic Delay Systems as Machine Learning Implementations},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {Nonlinear photonic delay systems present interesting implementation platforms for machine learning models. They can be extremely fast, offer great degrees of parallelism and potentially consume far less power than digital processors. So far they have been successfully employed for signal processing using the Reservoir Computing paradigm. In this paper we show that their range of applicability can be greatly extended if we use gradient descent with backpropagation through time on a model of the system to optimize the input encoding of such systems. We perform physical experiments that demonstrate that the obtained input encodings work well in reality, and we show that optimized systems perform significantly better than the common Reservoir Computing approach. The results presented here demonstrate that common gradient descent techniques from machine learning may well be applicable on physical neuro-inspired analog computers.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2081–2097},
numpages = {17},
keywords = {machine learning models, optical computing, recurrent neural networks}
}

@article{10.5555/2789272.2886816,
author = {Gammerman, Alex and Vovk, Vladimir},
title = {Alexey Chervonenkis's Bibliography},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2067–2080},
numpages = {14}
}

@article{10.5555/2789272.2886815,
author = {Gammerman, Alex and Vovk, Vladimir},
title = {Alexey Chervonenkis's Bibliography: Introductory Comments},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2051–2066},
numpages = {16}
}

@article{10.5555/2789272.2886814,
author = {Vapnik, Vladimir and Izmailov, Rauf},
title = {Learning Using Privileged Information: Similarity Control and Knowledge Transfer},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {This paper describes a new paradigm of machine learning, in which Intelligent Teacher is involved. During training stage, Intelligent Teacher provides Student with information that contains, along with classification of each example, additional privileged information (for example, explanation) of this example. The paper describes two mechanisms that can be used for significantly accelerating the speed of Student's learning using privileged information: (1) correction of Student's concepts of similarity between examples, and (2) direct Teacher-Student knowledge transfer.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2023–2049},
numpages = {27},
keywords = {similarity control, privileged information, SVM+, learning theory, kernel functions, intelligent teacher, similarity functions, frames, classification, regression, knowledge representation, support vector machines, knowledge transfer}
}

@article{10.5555/2789272.2886813,
author = {Herbster, Mark and Pasteris, Stephen and Pontil, Massimiliano},
title = {Predicting a Switching Sequence of Graph Labelings},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {We study the problem of predicting online the labeling of a graph. We consider a novel setting for this problem in which, in addition to observing vertices and labels on the graph, we also observe a sequence of just vertices on a second graph. A latent labeling of the second graph selects one of K labelings to be active on the first graph. We propose a polynomial time algorithm for online prediction in this setting and derive a mistake bound for the algorithm. The bound is controlled by the geometric cut of the observed and latent labelings, as well as the resistance diameters of the graphs. When specialized to multitask prediction and online switching problems the bound gives new and sharper results under certain conditions.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2003–2022},
numpages = {20},
keywords = {matrix winnow, switching, online learning over graphs, kernel methods}
}

@article{10.5555/2789272.2886812,
author = {Thomann, Philipp and Steinwart, Ingo and Schmid, Nico},
title = {Towards an Axiomatic Approach to Hierarchical Clustering of Measures},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {We propose some axioms for hierarchical clustering of probability measures and investigate their ramifications. The basic idea is to let the user stipulate the clusters for some elementary measures. This is done without the need of any notion of metric, similarity or dissimilarity. Our main results then show that for each suitable choice of user-defined clustering on elementary measures we obtain a unique notion of clustering on a large set of distributions satisfying a set of additivity and continuity axioms. We illustrate the developed theory by numerous examples including some with and some without a density.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1949–2002},
numpages = {54},
keywords = {mixed Hausdorff-dimensions, hierarchical clustering, infinite samples clustering, density level set clustering, axiomatic clustering}
}

@article{10.5555/2789272.2886811,
author = {Janzing, Dominik and Sch\"{o}lkopf, Bernhard},
title = {Semi-Supervised Interpolation in an Anticausal Learning Scenario},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {According to a recently stated 'independence postulate', the distribution Pcause contains no information about the conditional Peffect|cause while Peffect may contain information about Pcause|effect. Since semi-supervised learning (SSL) attempts to exploit information from PX to assist in predicting Y from X, it should only work in anticausal direction, i.e., when Y is the cause and X is the effect. In causal direction, when X is the cause and Y the effect, unlabelled x-values should be useless. To shed light on this asymmetry, we study a deterministic causal relation Y = f(X) as recently assayed in Information-Geometric Causal Inference (IGCI). Within this model, we discuss two options to formalize the independence of PX and f as an orthogonality of vectors in appropriate inner product spaces. We prove that unlabelled data help for the problem of interpolating a monotonically increasing function if and only if the orthogonality conditions are violated - which we only expect for the anticausal direction. Here, performance of SSL and its supervised baseline analogue is measured in terms of two different loss functions: first, the mean squared error and second the surprise in a Bayesian prediction scenario.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1923–1948},
numpages = {26},
keywords = {information geometry, independence of cause and mechanism, anticausal learning, causality, semi-supervised learning}
}

@article{10.5555/2789272.2886810,
author = {Addario-Berry, Louigi and Bhamidi, Shankar and Bubeck, S\'{e}bastien and Devroye, Luc and Lugosi, G\'{a}bor and Oliveira, Roberto Imbuzeiro},
title = {Exceptional Rotations of Random Graphs: A VC Theory},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {In this paper we explore maximal deviations of large random structures from their typical behavior. We introduce a model for a high-dimensional random graph process and ask analogous questions to those of Vapnik and Chervonenkis for deviations of averages: how "rich" does the process have to be so that one sees atypical behavior.In particular, we study a natural process of Erd\"{o}s-R\'{e}nyi random graphs indexed by unit vectors in Rd. We investigate the deviations of the process with respect to three fundamental properties: clique number, chromatic number, and connectivity. In all cases we establish upper and lower bounds for the minimal dimension d that guarantees the existence of "exceptional directions" in which the random graph behaves atypically with respect to the property. For each of the three properties, four theorems are established, to describe upper and lower bounds for the threshold dimension in the subcritical and supercritical regimes.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1893–1922},
numpages = {30},
keywords = {VC theory, clique number, chromatic number, random graphs, connectivity}
}

@article{10.5555/2789272.2886809,
author = {Bellec, Pierre C. and Tsybakov, Alexandre B.},
title = {Sharp Oracle Bounds for Monotone and Convex Regression through Aggregation},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {We derive oracle inequalities for the problems of isotonic and convex regression using the combination of Q-aggregation procedure and sparsity pattern aggregation. This improves upon the previous results including the oracle inequalities for the constrained least squares estimator. One of the improvements is that our oracle inequalities are sharp, i.e., with leading constant 1. It allows us to obtain bounds for the minimax regret thus accounting for model misspecification, which was not possible based on the previous results. Another improvement is that we obtain oracle inequalities both with high probability and in expectation.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1879–1892},
numpages = {14},
keywords = {shape constraints, sharp oracle inequalities, convex regression, isotonic regression, aggregation, minimax regret, model misspecification}
}

@article{10.5555/2789272.2886808,
author = {Gy\"{o}rfi, L\'{a}szl\'{o} and Walk, Harro},
title = {On the Asymptotic Normality of an Estimate of a Regression Functional},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {An estimate of the second moment of the regression function is introduced. Its asymptotic normality is proved such that the asymptotic variance depends neither on the dimension of the observation vector, nor on the smoothness properties of the regression function. The asymptotic variance is given explicitly.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1863–1877},
numpages = {15},
keywords = {regression functional, nonparametric estimation, partitioning estimate, central limit theorem}
}

@article{10.5555/2789272.2886807,
author = {Van Erven, Tim and Gr\"{u}nwald, Peter D. and Mehta, Nishant A. and Reid, Mark D. and Williamson, Robert C.},
title = {Fast Rates in Statistical and Online Learning},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {The speed with which a learning algorithm converges as it is presented with more data is a central problem in machine learning -- a fast rate of convergence means less data is needed for the same level of performance. The pursuit of fast rates in online and statistical learning has led to the discovery of many conditions in learning theory under which fast learning is possible. We show that most of these conditions are special cases of a single, unifying condition, that comes in two forms: the central condition for 'proper' learning algorithms that always output a hypothesis in the given model, and stochastic mixability for online algorithms that may make predictions outside of the model. We show that under surprisingly weak assumptions both conditions are, in a certain sense, equivalent. The central condition has a re-interpretation in terms of convexity of a set of pseudoprobabilities, linking it to density estimation under misspecification. For bounded losses, we show how the central condition enables a direct proof of fast rates and we prove its equivalence to the Bernstein condition, itself a generalization of the Tsybakov margin condition, both of which have played a central role in obtaining fast rates in statistical learning. Yet, while the Bernstein condition is two-sided, the central condition is one-sided, making it more suitable to deal with unbounded losses. In its stochastic mixability form, our condition generalizes both a stochastic exp-concavity condition identified by Juditsky, Rigollet and Tsybakov and Vovk's notion of mixability. Our unifying conditions thus provide a substantial step towards a characterization of fast rates in statistical learning, similar to how classical mixability characterizes constant regret in the sequential prediction with expert advice setting.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1793–1861},
numpages = {69},
keywords = {statistical learning theory, fast rates, exp-concavity, mixability, Tsybakov margin condition}
}

@article{10.5555/2789272.2886806,
author = {Koltchinskii, Vladimir and Xia, Dong},
title = {Optimal Estimation of Low Rank Density Matrices},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {The density matrices are positively semi-definite Hermitian matrices of unit trace that describe the state of a quantum system. The goal of the paper is to develop minimax lower bounds on error rates of estimation of low rank density matrices in trace regression models used in quantum state tomography (in particular, in the case of Pauli measurements) with explicit dependence of the bounds on the rank and other complexity parameters. Such bounds are established for several statistically relevant distances, including quantum versions of Kullback-Leibler divergence (relative entropy distance) and of Hellinger distance (so called Bures distance), and Schatten p-norm distances. Sharp upper bounds and oracle inequalities for least squares estimator with von Neumann entropy penalization are obtained showing that minimax lower bounds are attained (up to logarithmic factors) for these distances.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1757–1792},
numpages = {36},
keywords = {quantum state tomography, minimax lower bounds, low rank density matrix}
}

@article{10.5555/2789272.2886805,
author = {Swaminathan, Adith and Joachims, Thorsten},
title = {Batch Learning from Logged Bandit Feedback through Counterfactual Risk Minimization},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {We develop a learning principle and an efficient algorithm for batch learning from logged bandit feedback. This learning setting is ubiquitous in online systems (e.g., ad placement, web search, recommendation), where an algorithm makes a prediction (e.g., ad ranking) for a given input (e.g., query) and observes bandit feedback (e.g., user clicks on presented ads). We first address the counterfactual nature of the learning problem (Bottou et al., 2013) through propensity scoring. Next, we prove generalization error bounds that account for the variance of the propensity-weighted empirical risk estimator. In analogy to the Structural Risk Minimization principle of Wapnik and Tscherwonenkis (1979), these constructive bounds give rise to the Counterfactual Risk Minimization (CRM) principle. We show how CRM can be used to derive a new learning method--called Policy Optimizer for Exponential Models (POEM)--for learning stochastic linear rules for structured output prediction. We present a decomposition of the POEM objective that enables efficient stochastic gradient optimization. The effectiveness and efficiency of POEM is evaluated on several simulated multi-label classification problems, as well as on a real-world information retrieval problem. The empirical results show that the CRM objective implemented in POEM provides improved robustness and generalization performance compared to the state-of-the-art.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1731–1755},
numpages = {25},
keywords = {structured prediction, bandit feedback, importance sampling, empirical risk minimization, propensity score matching}
}

@article{10.5555/2789272.2886804,
author = {Vapnik, Vladimir and Izmailov, Rauf},
title = {V-Matrix Method of Solving Statistical Inference Problems},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {This paper presents direct settings and rigorous solutions of the main Statistical Inference problems. It shows that rigorous solutions require solving multidimensional Fredholm integral equations of the first kind in the situation where not only the right-hand side of the equation is an approximation, but the operator in the equation is also defined approximately. Using Stefanuyk-Vapnik theory for solving such ill-posed operator equations, constructive methods of empirical inference are introduced. These methods are based on a new concept called V-matrix. This matrix captures geometric properties of the observation data that are ignored by classical statistical methods.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1683–1730},
numpages = {48},
keywords = {mutual information, regression, conditional probability, data adaptation, interpolation function, reproducing kernel Hilbert space, support vector machines, data balancing, density ratio, conditional density, function estimation, ill-posed problem}
}

@article{10.5555/2789272.2886803,
author = {Gammerman, Alex and Vovk, Vladimir},
title = {Preface to This Special Issue},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1677–1681},
numpages = {5}
}

@article{10.5555/2789272.2886802,
author = {Scherrer, Bruno and Ghavamzadeh, Mohammad and Gabillon, Victor and Lesner, Boris and Geist, Matthieu},
title = {Approximate Modified Policy Iteration and Its Application to the Game of Tetris},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {Modified policy iteration (MPI) is a dynamic programming (DP) algorithm that contains the two celebrated policy and value iteration methods. Despite its generality, MPI has not been thoroughly studied, especially its approximation form which is used when the state and/or action spaces are large or infinite. In this paper, we propose three implementations of approximate MPI (AMPI) that are extensions of the well-known approximate DP algorithms: fitted-value iteration, fitted-Q iteration, and classification-based policy iteration. We provide error propagation analysis that unify those for approximate policy and value iteration. We develop the finite-sample analysis of these algorithms, which highlights the influence of their parameters. In the classification-based version of the algorithm (CBMPI), the analysis shows that MPI's main parameter controls the balance between the estimation error of the classifier and the overall value function approximation. We illustrate and evaluate the behavior of these new algorithms in the Mountain Car and Tetris problems. Remarkably, in Tetris, CBMPI outperforms the existing DP approaches by a large margin, and competes with the current state-of-the-art methods while using fewer samples.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1629–1676},
numpages = {48},
keywords = {approximate dynamic programming, Markov decision processes, game of tetris, reinforcement learning, finite-sample analysis, performance bounds}
}

@article{10.5555/2789272.2886801,
author = {Moreno, Pablo G. and Art\'{e}s-Rodr\'{\i}guez, Antonio and Teh, Yee Whye and Perez-Cruz, Fernando},
title = {Bayesian Nonparametric Crowdsourcing},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {Crowdsourcing has been proven to be an effective and efficient tool to annotate large data-sets. User annotations are often noisy, so methods to combine the annotations to produce reliable estimates of the ground truth are necessary. We claim that considering the existence of clusters of users in this combination step can improve the performance. This is especially important in early stages of crowdsourcing implementations, where the number of annotations is low. At this stage there is not enough information to accurately estimate the bias introduced by each annotator separately, so we have to resort to models that consider the statistical links among them. In addition, finding these clusters is interesting in itself as knowing the behavior of the pool of annotators allows implementing efficient active learning strategies. Based on this, we propose in this paper two new fully unsupervised models based on a Chinese restaurant process (CRP) prior and a hierarchical structure that allows inferring these groups jointly with the ground truth and the properties of the users. Efficient inference algorithms based on Gibbs sampling with auxiliary variables are proposed. Finally, we perform experiments, both on synthetic and real databases, to show the advantages of our models over state-of-the-art algorithms.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1607–1627},
numpages = {21},
keywords = {Bayesian nonparametrics, multiple annotators, Gibbs sampling, hierarchical clustering, Dirichlet process}
}

@article{10.5555/2789272.2886800,
author = {Liu, Han and Wang, Lie and Zhaoy, Tuo},
title = {Calibrated Multivariate Regression with Application to Neural Semantic Basis Discovery},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {We propose a calibrated multivariate regression method named CMR for fitting high dimensional multivariate regression models. Compared with existing methods, CMR calibrates regularization for each regression task with respect to its noise level so that it simultaneously attains improved finite-sample performance and tuning insensitiveness. Theoretically, we provide sufficient conditions under which CMR achieves the optimal rate of convergence in parameter estimation. Computationally, we propose an efficient smoothed proximal gradient algorithm with a worst-case numerical rate of convergence O(1/ε), where ε is a pre-specified accuracy of the objective function value. We conduct thorough numerical simulations to illustrate that CMR consistently outperforms other high dimensional multivariate regression methods. We also apply CMR to solve a brain activity prediction problem and find that it is as competitive as a handcrafted model created by human experts. The R package camel implementing the proposed method is available on the Comprehensive R Archive Network http://cran.r-project.org/web/packages/camel/.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1579–1606},
numpages = {28},
keywords = {multivariate regression, sparsity, high dimension, low rank, calibration, brain activity prediction}
}

@article{10.5555/2789272.2886799,
author = {Geramifard, Alborz and Dann, Christoph and Klein, Robert H. and Dabney, William and How, Jonathan P.},
title = {RLPy: A Value-Function-Based Reinforcement Learning Framework for Education and Research},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {RLPy is an object-oriented reinforcement learning software package with a focus on value-function-based methods using linear function approximation and discrete actions. The framework was designed for both educational and research purposes. It provides a rich library of fine-grained, easily exchangeable components for learning agents (e.g., policies or representations of value functions), facilitating recently increased specialization in reinforcement learning. RLPy is written in Python to allow fast prototyping, but is also suitable for large-scale experiments through its built-in support for optimized numerical libraries and parallelization. Code profiling, domain visualizations, and data analysis are integrated in a self-contained package available under the Modified BSD License at http://github.com/rlpy/rlpy. All of these properties allow users to compare various reinforcement learning algorithms with little effort.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1573–1578},
numpages = {6},
keywords = {open source, reinforcement learning, empirical evaluation, value-function}
}

@article{10.5555/2789272.2886798,
author = {Qiao, Xingye and Zhang, Lingsong},
title = {Flexible High-Dimensional Classification Machines and Their Asymptotic Properties},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {Classification is an important topic in statistics and machine learning with great potential in many real applications. In this paper, we investigate two popular large-margin classification methods, Support Vector Machine (SVM) and Distance Weighted Discrimination (DWD), under two contexts: the high-dimensional, low-sample size data and the imbalanced data. A unified family of classification machines, the FLexible Assortment MachinE (FLAME) is proposed, within which DWD and SVM are special cases. The FLAME family helps to identify the similarities and differences between SVM and DWD. It is well known that many classifiers overfit the data in the high-dimensional setting; and others are sensitive to the imbalanced data, that is, the class with a larger sample size overly influences the classifier and pushes the decision boundary towards the minority class. SVM is resistant to the imbalanced data issue, but it overfits high-dimensional data sets by showing the undesired data-piling phenomenon. The DWD method was proposed to improve SVM in the high-dimensional setting, but its decision boundary is sensitive to the imbalanced ratio of sample sizes. Our FLAME family helps to understand an intrinsic connection between SVM and DWD, and provides a trade-off between sensitivity to the imbalanced data and overfitting the high-dimensional data. Several asymptotic properties of the FLAME classifiers are studied. Simulations and real data applications are investigated to illustrate theoretical findings.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1547–1572},
numpages = {26},
keywords = {support vector machine, classification, imbalanced data, Fisher consistency, high-dimensional low-sample size asymptotics}
}

@article{10.5555/2789272.2886797,
author = {Berend, Daniel and Kontorovich, Aryeh},
title = {A Finite Sample Analysis of the Naive Bayes Classifier},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {We revisit, from a statistical learning perspective, the classical decision-theoretic problem of weighted expert voting. In particular, we examine the consistency (both asymptotic and finitary) of the optimal Naive Bayes weighted majority and related rules. In the case of known expert competence levels, we give sharp error estimates for the optimal rule. We derive optimality results for our estimates and also establish some structural characterizations. When the competence levels are unknown, they must be empirically estimated. We provide frequentist and Bayesian analyses for this situation. Some of our proof techniques are non-standard and may be of independent interest. Several challenging open problems are posed, and experimental results are provided to illustrate the theory.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1519–1545},
numpages = {27},
keywords = {Chernoff-Stein lemma, hypothesis testing, measure concentration, Neyman-Pearson lemma, experts, naive Bayes}
}

@article{10.5555/2789272.2886796,
author = {Moroshko, Edward and Vaits, Nina and Crammer, Koby},
title = {Second-Order Non-Stationary Online Learning for Regression},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {The goal of a learner in standard online learning, is to have the cumulative loss not much larger compared with the best-performing function from some fixed class. Numerous algorithms were shown to have this gap arbitrarily close to zero, compared with the best function that is chosen off-line. Nevertheless, many real-world applications, such as adaptive filtering, are non-stationary in nature, and the best prediction function may drift over time. We introduce two novel algorithms for online regression, designed to work well in non-stationary environment. Our first algorithm performs adaptive resets to forget the history, while the second is last-step min-max optimal in context of a drift. We analyze both algorithms in the worst-case regret framework and show that they maintain an average loss close to that of the best slowly changing sequence of linear functions, as long as the cumulative drift is sublinear. In addition, in the stationary case, when no drift occurs, our algorithms suffer logarithmic regret, as for previous algorithms. Our bounds improve over existing ones, and simulations demonstrate the usefulness of these algorithms compared with other state-of-the-art approaches.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1481–1517},
numpages = {37},
keywords = {non-stationary input, regret bounds, online learning}
}

@article{10.5555/2789272.2886795,
author = {Garc\'{\i}a, Javier and Fern\'{a}ndez, Fernando},
title = {A Comprehensive Survey on Safe Reinforcement Learning},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {Safe Reinforcement Learning can be defined as the process of learning policies that maximize the expectation of the return in problems in which it is important to ensure reasonable system performance and/or respect safety constraints during the learning and/or deployment processes. We categorize and analyze two approaches of Safe Reinforcement Learning. The first is based on the modification of the optimality criterion, the classic discounted finite/infinite horizon, with a safety factor. The second is based on the modification of the exploration process through the incorporation of external knowledge or the guidance of a risk metric. We use the proposed classification to survey the existing literature, as well as suggesting future directions for Safe Reinforcement Learning.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1437–1480},
numpages = {44},
keywords = {teacher advice, reinforcement learning, safe exploration, risk sensitivity}
}

@article{10.5555/2789272.2886794,
author = {Kir\'{a}ly, Franz J. and Theran, Louis and Tomioka, Ryota},
title = {The Algebraic Combinatorial Approach for Low-Rank Matrix Completion},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {We present a novel algebraic combinatorial view on low-rank matrix completion based on studying relations between a few entries with tools from algebraic geometry and matroid theory. The intrinsic locality of the approach allows for the treatment of single entries in a closed theoretical and practical framework. More specifically, apart from introducing an algebraic combinatorial theory of low-rank matrix completion, we present probability-one algorithms to decide whether a particular entry of the matrix can be completed. We also describe methods to complete that entry from a few others, and to estimate the error which is incurred by any method completing that entry. Furthermore, we show how known results on matrix completion and their sampling assumptions can be related to our new perspective and interpreted in terms of a completability phase transition.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1391–1436},
numpages = {46},
keywords = {entry-wise completion, algebraic combinatorics, matrix reconstruction, low-rank matrix completion}
}

@article{10.5555/2789272.2886793,
author = {Sunehag, Peter and Hutter, Marcus},
title = {Rationality, Optimism and Guarantees in General Reinforcement Learning},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {In this article, we present a top-down theoretical study of general reinforcement learning agents. We begin with rational agents with unlimited resources and then move to a setting where an agent can only maintain a limited number of hypotheses and optimizes plans over a horizon much shorter than what the agent designer actually wants. We axiomatize what is rational in such a setting in a manner that enables optimism, which is important to achieve systematic explorative behavior. Then, within the class of agents deemed rational, we achieve convergence and finite-error bounds. Such results are desirable since they imply that the agent learns well from its experiences, but the bounds do not directly guarantee good performance and can be achieved by agents doing things one should obviously not. Good performance cannot in fact be guaranteed for any agent in fully general settings. Our approach is to design agents that learn well from experience and act rationally. We introduce a framework for general reinforcement learning agents based on rationality axioms for a decision function and an hypothesis-generating function designed so as to achieve guarantees on the number errors. We will consistently use an optimistic decision function but the hypothesis-generating function needs to change depending on what is known/assumed. We investigate a number of natural situations having either a frequentist or Bayesian flavor, deterministic or stochastic environments and either finite or countable hypothesis class. Further, to achieve sufficiently good bounds as to hold promise for practical success we introduce a notion of a class of environments being generated by a set of laws. None of the above has previously been done for fully general reinforcement learning environments.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1345–1390},
numpages = {46},
keywords = {error bounds, optimality, optimism, rationality, reinforcement learning}
}

@article{10.5555/2789272.2886792,
author = {Fearnley, John and Gairing, Martin and Goldberg, Paul W. and Savani, Rahul},
title = {Learning Equilibria of Games via Payoff Queries},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {A recent body of experimental literature has studied empirical game-theoretical analysis, in which we have partial knowledge of a game, consisting of observations of a subset of the pure-strategy profiles and their associated payoffs to players. The aim is to find an exact or approximate Nash equilibrium of the game, based on these observations. It is usually assumed that the strategy profiles may be chosen in an on-line manner by the algorithm. We study a corresponding computational learning model, and the query complexity of learning equilibria for various classes of games. We give basic results for exact equilibria of bimatrix and graphical games. We then study the query complexity of approximate equilibria in bimatrix games. Finally, we study the query complexity of exact equilibria in symmetric network congestion games. For directed acyclic networks, we can learn the cost functions (and hence compute an equilibrium) while querying just a small fraction of pure-strategy profiles. For the special case of parallel links, we have the stronger result that an equilibrium can be identified while only learning a small fraction of the cost values.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1305–1344},
numpages = {40},
keywords = {congestion game, bimatrix game, query complexity, equilibrium computation, approximate Nash equilibrium}
}

@article{10.5555/2789272.2886791,
author = {Sabato, Sivan and Shalev-Shwartz, Shai and Srebro, Nathan and Hsu, Daniel and Zhang, Tong},
title = {Learning Sparse Low-Threshold Linear Classifiers},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {We consider the problem of learning a non-negative linear classifier with a l1-norm of at most k, and a fixed threshold, under the hinge-loss. This problem generalizes the problem of learning a k-monotone disjunction. We prove that we can learn efficiently in this setting, at a rate which is linear in both k and the size of the threshold, and that this is the best possible rate. We provide an efficient online learning algorithm that achieves the optimal rate, and show that in the batch case, empirical risk minimization achieves this rate as well. The rates we show are tighter than the uniform convergence rate, which grows with k2.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1275–1304},
numpages = {30},
keywords = {online learning, uniform convergence, empirical risk minimization, linear classifiers, monotone disjunctions}
}

@article{10.5555/2789272.2886790,
author = {Ravanbakhsh, Siamak and Greiner, Russell},
title = {Perturbed Message Passing for Constraint Satisfaction Problems},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {We introduce an efficient message passing scheme for solving Constraint Satisfaction Problems (CSPs), which uses stochastic perturbation of Belief Propagation (BP) and Survey Propagation (SP) messages to bypass decimation and directly produce a single satisfying assignment. Our first CSP solver, called Perturbed Belief Propagation, smoothly interpolates two well-known inference procedures; it starts as BP and ends as a Gibbs sampler, which produces a single sample from the set of solutions. Moreover we apply a similar perturbation scheme to SP to produce another CSP solver, Perturbed Survey Propagation. Experimental results on random and real-world CSPs show that Perturbed BP is often more successful and at the same time tens to hundreds of times more efficient than standard BP guided decimation. Perturbed BP also compares favorably with state-of-the-art SP-guided decimation, which has a computational complexity that generally scales exponentially worse than our method (w.r.t. the cardinality of variable domains and constraints). Furthermore, our experiments with random satisfiability and coloring problems demonstrate that Perturbed SP can outperform SP-guided decimation, making it the best incomplete random CSP-solver in difficult regimes.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1249–1274},
numpages = {26},
keywords = {belief propagation, survey propagation, message passing, decimation, Gibbs sampling, constraint satisfaction problem}
}

@article{10.5555/2789272.2886789,
author = {Heaton, Jeff},
title = {Encog: Library of Interchangeable Machine Learning Models for Java and C#},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {This paper introduces the Encog library for Java and C#, a scalable, adaptable, multiplatform machine learning framework that was first released in 2008. Encog allows a variety of machine learning models to be applied to data sets using regression, classification, and clustering. Various supported machine learning models can be used interchangeably with minimal recoding. Encog uses efficient multithreaded code to reduce training time by exploiting modern multicore processors. The current version of Encog can be downloaded from http://www.encog.org.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1243–1247},
numpages = {5},
keywords = {neural network, Java, open source software, support vector machine, C#}
}

@article{10.5555/2789272.2886788,
author = {Schnass, Karin},
title = {Local Identification of Overcomplete Dictionaries},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {This paper presents the first theoretical results showing that stable identification of overcomplete µ-coherent dictionaries Φ ε Rd\texttimes{}K is locally possible from training signals with sparsity levels S up to the order O(µ-2) and signal to noise ratios up to O(√d). In particular the dictionary is recoverable as the local maximum of a new maximization criterion that generalizes the K-means criterion. For this maximization criterion results for asymptotic exact recovery for sparsity levels up to O(µ-1) and stable recovery for sparsity levels up to O(µ-2) as well as signal to noise ratios up to O(√d) are provided. These asymptotic results translate to finite sample size recovery results with high probability as long as the sample size N scales as O(K3dsε-2), where the recovery precision ε can go down to the asymptotically achievable precision. Further, to actually and the local maxima of the new criterion, a very simple Iterative Thresholding and K (signed) Means algorithm (ITKM), which has complexity O(dKN) in each iteration, is presented and its local efficiency is demonstrated in several experiments.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1211–1242},
numpages = {32},
keywords = {maximization criterion, sparse representation, sample complexity, vector quantization, sparse coding, sparse component analysis, K-means, dictionary identification, dictionary learning, finite sample size}
}

@article{10.5555/2789272.2886787,
author = {Honorio, Jean and Ortiz, Luis},
title = {Learning the Structure and Parameters of Large-Population Graphical Games from Behavioral Data},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {We consider learning, from strictly behavioral data, the structure and parameters of linear in uence games (LIGs), a class of parametric graphical games introduced by Irfan and Ortiz (2014). LIGs facilitate causal strategic inference (CSI): Making inferences from causal interventions on stable behavior in strategic settings. Applications include the identification of the most in uential individuals in large (social) networks. Such tasks can also support policy-making analysis. Motivated by the computational work on LIGs, we cast the learning problem as maximum-likelihood estimation (MLE) of a generative model defined by pure-strategy Nash equilibria (PSNE). Our simple formulation uncovers the fundamental interplay between goodness-of-fit and model complexity: good models capture equilibrium behavior within the data while controlling the true number of equilibria, including those unobserved. We provide a generalization bound establishing the sample complexity for MLE in our framework. We propose several algorithms including convex loss minimization (CLM) and sigmoidal approximations. We prove that the number of exact PSNE in LIGs is small, with high probability; thus, CLM is sound. We illustrate our approach on synthetic data and real-world U.S. congressional voting records. We briefly discuss our learning framework's generality and potential applicability to general graphical games.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1157–1210},
numpages = {54},
keywords = {graphical games, structure and parameter learning, linear influence games, behavioral data in strategic settings}
}

@article{10.5555/2789272.2886786,
author = {Krueger, Tammo and Panknin, Danny and Braun, Mikio},
title = {Fast Cross-Validation via Sequential Testing},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {With the increasing size of today's data sets, nding the right parameter configuration in model selection via cross-validation can be an extremely time-consuming task. In this paper we propose an improved cross-validation procedure which uses nonparametric testing coupled with sequential analysis to determine the best parameter set on linearly increasing subsets of the data. By eliminating underperforming candidates quickly and keeping promising candidates as long as possible, the method speeds up the computation while preserving the power of the full cross-validation. Theoretical considerations underline the statistical power of our procedure. The experimental evaluation shows that our method reduces the computation time by a factor of up to 120 compared to a full cross-validation with a negligible impact on the accuracy.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1103–1155},
numpages = {53},
keywords = {cross-validation, statistical testing, nonparametric methods}
}

@article{10.5555/2789272.2886785,
author = {Wang, Jie and Wonka, Peter and Ye, Jieping},
title = {Lasso Screening Rules via Dual Polytope Projection},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {Lasso is a widely used regression technique to find sparse representations. When the dimension of the feature space and the number of samples are extremely large, solving the Lasso problem remains challenging. To improve the efficiency of solving large-scale Lasso problems, El Ghaoui and his colleagues have proposed the SAFE rules which are able to quickly identify the inactive predictors, i.e., predictors that have 0 components in the solution vector. Then, the inactive predictors or features can be removed from the optimization problem to reduce its scale. By transforming the standard Lasso to its dual form, it can be shown that the inactive predictors include the set of inactive constraints on the optimal dual solution. In this paper, we propose an efficient and effective screening rule via Dual Polytope Projections (DPP), which is mainly based on the uniqueness and nonexpansiveness of the optimal dual solution due to the fact that the feasible set in the dual space is a convex and closed polytope. Moreover, we show that our screening rule can be extended to identify inactive groups in group Lasso. To the best of our knowledge, there is currently no exact screening rule for group Lasso. We have evaluated our screening rule using synthetic and real data sets. Results show that our rule is more effective in identifying inactive predictors than existing state-of-the-art screening rules for Lasso.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1063–1101},
numpages = {39},
keywords = {polytope projection, large-scale optimization, lasso, dual formulation, sparse regularization, safe screening}
}

@article{10.5555/2789272.2886784,
author = {Lee, Wonyul and Liu, Yufeng},
title = {Joint Estimation of Multiple Precision Matrices with Common Structures},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {Estimation of inverse covariance matrices, known as precision matrices, is important in various areas of statistical analysis. In this article, we consider estimation of multiple precision matrices sharing some common structures. In this setting, estimating each precision matrix separately can be suboptimal as it ignores potential common structures. This article proposes a new approach to parameterize each precision matrix as a sum of common and unique components and estimate multiple precision matrices in a constrained l1 minimization framework. We establish both estimation and selection consistency of the proposed estimator in the high dimensional setting. The proposed estimator achieves a faster convergence rate for the common structure in certain cases. Our numerical examples demonstrate that our new estimator can perform better than several existing methods in terms of the entropy loss and Frobenius loss. An application to a glioblastoma cancer data set reveals some interesting gene networks across multiple cancer subtypes.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1035–1062},
numpages = {28},
keywords = {covariance matrix, joint estimation, precision matrix, high dimension, graphical model}
}

@article{10.5555/2789272.2886783,
author = {Feng, Yunlong and Huang, Xiaolin and Shi, Lei and Yang, Yuning and Suykens, Johan A. K.},
title = {Learning with the Maximum Correntropy Criterion Induced Losses for Regression},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {Within the statistical learning framework, this paper studies the regression model associated with the correntropy induced losses. The correntropy, as a similarity measure, has been frequently employed in signal processing and pattern recognition. Motivated by its empirical successes, this paper aims at presenting some theoretical understanding towards the maximum correntropy criterion in regression problems. Our focus in this paper is two-fold: first, we are concerned with the connections between the regression model associated with the correntropy induced loss and the least squares regression model. Second, we study its convergence property. A learning theory analysis which is centered around the above two aspects is conducted. From our analysis, we see that the scale parameter in the loss function balances the convergence rates of the regression model and its robustness. We then make some efforts to sketch a general view on robust loss functions when being applied into the learning for regression problems. Numerical experiments are also implemented to verify the effectiveness of the model.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {993–1034},
numpages = {42},
keywords = {the maximum correntropy criterion, statistical learning theory, robust regression, least squares regression, correntropy, robust loss function}
}

@article{10.5555/2789272.2886782,
author = {Pokarowski, Piotr and Mielniczuk, Jan},
title = {Combined l<sub>1</sub> and Greedy l<sub>0</sub> Penalized Least Squares for Linear Model Selection},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {We introduce a computationally effective algorithm for a linear model selection consisting of three steps: screening-ordering-selection (SOS). Screening of predictors is based on the thresholded Lasso that is l1 penalized least squares. The screened predictors are then fitted using least squares (LS) and ordered with respect to their |t| statistics. Finally, a model is selected using greedy generalized information criterion (GIC) that is l0 penalized LS in a nested family induced by the ordering. We give non-asymptotic upper bounds on error probability of each step of the SOS algorithm in terms of both penalties. Then we obtain selection consistency for different (n, p) scenarios under conditions which are needed for screening consistency of the Lasso. Our error bounds and numerical experiments show that SOS is worth considering alternative for multi-stage convex relaxation, the latest quasiconvex penalized LS. For the traditional setting (n > p) we give Sanov-type bounds on the error probabilities of the ordering-selection algorithm. It is surprising consequence of our bounds that the selection error of greedy GIC is asymptotically not larger than of exhaustive GIC.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {961–992},
numpages = {32},
keywords = {generalized information criterion, greedy search, lasso, linear model selection, multi-stage convex relaxation, penalized least squares}
}

@article{10.5555/2789272.2831142,
author = {Mackey, Lester and Talwalkar, Ameet and Jordan, Michael I.},
title = {Distributed Matrix Completion and Robust Factorization},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {If learning methods are to scale to the massive sizes of modern data sets, it is essential for the field of machine learning to embrace parallel and distributed computing. Inspired by the recent development of matrix factorization methods with rich theory but poor computational complexity and by the relative ease of mapping matrices onto distributed architectures, we introduce a scalable divide-and-conquer framework for noisy matrix factorization. We present a thorough theoretical analysis of this framework in which we characterize the statistical errors introduced by the "divide" step and control their magnitude in the "conquer" step, so that the overall algorithm enjoys high-probability estimation guarantees comparable to those of its base algorithm. We also present experiments in collaborative filtering and video background modeling that demonstrate the near-linear to superlinear speed-ups attainable with this approach.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {913–960},
numpages = {48},
keywords = {video surveillance, collaborative filtering, matrix factorization, parallel and distributed algorithms, randomized algorithms, divide-and-conquer, robust matrix factorization, matrix completion}
}

@article{10.5555/2789272.2831141,
author = {Ma, Ping and Mahoney, Michael W. and Yu, Bin},
title = {A Statistical Perspective on Algorithmic Leveraging},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {One popular method for dealing with large-scale data sets is sampling. For example, by using the empirical statistical leverage scores as an importance sampling distribution, the method of algorithmic leveraging samples and rescales rows/columns of data matrices to reduce the data size before performing computations on the subproblem. This method has been successful in improving computational efficiency of algorithms for matrix problems such as least-squares approximation, least absolute deviations approximation, and low-rank matrix approximation. Existing work has focused on algorithmic issues such as worst-case running times and numerical issues associated with providing high-quality implementations, but none of it addresses statistical aspects of this method.In this paper, we provide a simple yet effective framework to evaluate the statistical properties of algorithmic leveraging in the context of estimating parameters in a linear regression model with a fixed number of predictors. In particular, for several versions of leverage-based sampling, we derive results for the bias and variance, both conditional and unconditional on the observed data. We show that from the statistical perspective of bias and variance, neither leverage-based sampling nor uniform sampling dominates the other. This result is particularly striking, given the well-known result that, from the algorithmic perspective of worst-case analysis, leverage-based sampling provides uniformly superior worst-case algorithmic results, when compared with uniform sampling.Based on these theoretical results, we propose and analyze two new leveraging algorithms: one constructs a smaller least-squares problem with "shrinkage" leverage scores (SLEV), and the other solves a smaller and unweighted (or biased) least-squares problem (LEVUNW). A detailed empirical evaluation of existing leverage-based methods as well as these two new methods is carried out on both synthetic and real data sets. The empirical results indicate that our theory is a good predictor of practical performance of existing and new leverage-based algorithms and that the new algorithms achieve improved performance. For example, with the same computation reduction as in the original algorithmic leveraging approach, our proposed SLEV typically leads to improved biases and variances both unconditionally and conditionally (on the observed data), and our proposed LEVUNW typically yields improved unconditional biases and variances.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {861–911},
numpages = {51},
keywords = {least squares, randomized algorithm, linear regression, subsampling, leverage scores}
}

@article{10.5555/2789272.2831140,
author = {Germain, Pascal and Lacasse, Alexandre and Laviolette, Fran\c{c}ois and Marchand, Mario and Roy, Jean-Francis},
title = {Risk Bounds for the Majority Vote: From a PAC-Bayesian Analysis to a Learning Algorithm},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {We propose an extensive analysis of the behavior of majority votes in binary classification. In particular, we introduce a risk bound for majority votes, called the C-bound, that takes into account the average quality of the voters and their average disagreement. We also propose an extensive PAC-Bayesian analysis that shows how the C-bound can be estimated from various observations contained in the training data. The analysis intends to be self-contained and can be used as introductory material to PAC-Bayesian statistical learning theory. It starts from a general PAC-Bayesian perspective and ends with uncommon PAC-Bayesian bounds. Some of these bounds contain no Kullback-Leibler divergence and others allow kernel functions to be used as voters (via the sample compression setting). Finally, out of the analysis, we propose the MinCq learning algorithm that basically minimizes the C-bound. MinCq reduces to a simple quadratic program. Aside from being theoretically grounded, MinCq achieves state-of-the-art performance, as shown in our extensive empirical comparison with both AdaBoost and the Support Vector Machine.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {787–860},
numpages = {74},
keywords = {majority vote, sample compression, ensemble methods, learning theory, PAC-Bayesian theory}
}

@article{10.5555/2789272.2831139,
author = {Nikulin, Vladimir},
title = {Strong Consistency of the Prototype Based Clustering in Probabilistic Space},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {In this paper we formulate in general terms an approach to prove strong consistency of the Empirical Risk Minimisation inductive principle applied to the prototype or distance based clustering. This approach was motivated by the Divisive Information-Theoretic Feature Clustering model in probabilistic space with Kullback-Leibler divergence, which may be regarded as a special case within the Clustering Minimisation framework.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {775–785},
numpages = {11},
keywords = {probabilistic space, consistency, clustering}
}

@article{10.5555/2789272.2831138,
author = {Bernstein, Andrey and Shimkin, Nahum},
title = {Response-Based Approachability with Applications to Generalized No-Regret Problems},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {Blackwell's theory of approachability provides fundamental results for repeated games with vector-valued payoffs, which have been usefully applied in the theory of learning in games, and in devising online learning algorithms in the adversarial setup. A target set S is approachable by a player (the agent) in such a game if he can ensure that the average payoff vector converges to S, no matter what the opponent does. Blackwell provided two equivalent conditions for a convex set to be approachable. Standard approachability algorithms rely on the primal condition, which is a geometric separation condition, and essentially require to compute at each stage a projection direction from a certain point to S. Here we introduce an approachability algorithm that relies on Blackwell's dual condition, which requires the agent to have a feasible response to each mixed action of the opponent, namely a mixed action such that the expected payoff vector belongs to S. Thus, rather than projections, the proposed algorithm relies on computing the response to a certain action of the opponent at each stage. We demonstrate the utility of the proposed approach by applying it to certain generalizations of the classical regret minimization problem, which incorporate side constraints, reward-to-cost criteria, and so-called global cost functions. In these extensions, computation of the projection is generally complex while the response is readily obtainable.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {747–773},
numpages = {27},
keywords = {no-regret algorithms, approachability}
}

@article{10.5555/2789272.2831137,
author = {Wiener, Yair and Hanneke, Steve and El-Yaniv, Ran},
title = {A Compression Technique for Analyzing Disagreement-Based Active Learning},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {We introduce a new and improved characterization of the label complexity of disagreement-based active learning, in which the leading quantity is the version space compression set size. This quantity is defined as the size of the smallest subset of the training data that induces the same version space. We show various applications of the new characterization, including a tight analysis of CAL and refined label complexity bounds for linear separators under mixtures of Gaussians and axis-aligned rectangles under product densities. The version space compression set size, as well as the new characterization of the label complexity, can be naturally extended to agnostic learning problems, for which we show new speedup results for two well known active learning algorithms.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {713–745},
numpages = {33},
keywords = {sample complexity, selective prediction, selective sampling, PAC learning, active learning, statistical learning theory, sequential design}
}

@article{10.5555/2789272.2831136,
author = {Da Silva, Cleomar Pereira and Dias, Douglas Mota and Bentes, Cristiana and Pacheco, Marco Aur\'{e}lio Cavalcanti and Cupertino, Leandro Fontoura},
title = {Evolving GPU Machine Code},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {Parallel Graphics Processing Unit (GPU) implementations of GP have appeared in the literature using three main methodologies: (i) compilation, which generates the individuals in GPU code and requires compilation; (ii) pseudo-assembly, which generates the individuals in an intermediary assembly code and also requires compilation; and (iii) interpretation, which interprets the codes. This paper proposes a new methodology that uses the concepts of quantum computing and directly handles the GPU machine code instructions. Our methodology utilizes a probabilistic representation of an individual to improve the global search capability. In addition, the evolution in machine code eliminates both the overhead of compiling the code and the cost of parsing the program during evaluation. We obtained up to 2.74 trillion GP operations per second for the 20-bit Boolean Multiplexer benchmark. We also compared our approach with the other three GPU-based acceleration methodologies implemented for quantum-inspired linear GP. Significant gains in performance were obtained.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {673–712},
numpages = {40},
keywords = {graphics processing units, genetic programming, machine code}
}

@article{10.5555/2789272.2831135,
author = {Mont\'{u}far, Guido and Morton, Jason},
title = {Discrete Restricted Boltzmann Machines},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {We describe discrete restricted Boltzmann machines: probabilistic graphical models with bipartite interactions between visible and hidden discrete variables. Examples are binary restricted Boltzmann machines and discrete na\"{\i}ve Bayes models. We detail the inference functions and distributed representations arising in these models in terms of configurations of projected products of simplices and normal fans of products of simplices. We bound the number of hidden variables, depending on the cardinalities of their state spaces, for which these models can approximate any probability distribution on their visible states to any given accuracy. In addition, we use algebraic methods and coding theory to compute their dimension.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {653–672},
numpages = {20},
keywords = {expected dimension, na\"{\i}ve Bayes model, restricted Boltzmann machine, representational power, distributed representation}
}

@article{10.5555/2789272.2789292,
author = {Jawanpuria, Pratik and Nath, Jagarlapudi Saketha and Ramakrishnan, Ganesh},
title = {Generalized Hierarchical Kernel Learning},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {This paper generalizes the framework of Hierarchical Kernel Learning (HKL) and illustrates its utility in the domain of rule learning. HKL involves Multiple Kernel Learning over a set of given base kernels assumed to be embedded on a directed acyclic graph. This paper proposes a two-fold generalization of HKL: the first is employing a generic l1/lp block-norm regularizer (ρ ∈ (1, 2]) that alleviates a key limitation of the HKL formulation. The second is a generalization to the case of multi-class, multi-label and more generally, multi-task applications. The main technical contribution of this work is the derivation of a highly specialized partial dual of the proposed generalized HKL formulation and an efficient mirror descent based active set algorithm for solving it. Importantly, the generic regularizer enables the proposed formulation to be employed in the Rule Ensemble Learning (REL) where the goal is to construct an ensemble of conjunctive propositional rules. Experiments on benchmark REL data sets illustrate the efficacy of the proposed generalizations.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {617–652},
numpages = {36},
keywords = {mixed-norm regularization, rule ensemble learning, active set method, multi-task learning, multiple kernel learning}
}

@article{10.5555/2789272.2789291,
author = {Loh, Po-Ling and Wainwright, Martin J.},
title = {Regularized M-Estimators with Nonconvexity: Statistical and Algorithmic Theory for Local Optima},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {We provide novel theoretical results regarding local optima of regularized M-estimators, allowing for nonconvexity in both loss and penalty functions. Under restricted strong convexity on the loss and suitable regularity conditions on the penalty, we prove that any stationary point of the composite objective function will lie within statistical precision of the underlying parameter vector. Our theory covers many nonconvex objective functions of interest, including the corrected Lasso for errors-in-variables linear models; regression for generalized linear models with nonconvex penalties such as SCAD, MCP, and capped-l 1; and high-dimensional graphical model estimation. We quantify statistical accuracy by providing bounds on the l1-, l2-, and prediction error between stationary points and the population-level optimum. We also propose a simple modification of composite gradient descent that may be used to obtain a near-global optimum within statistical precision εstat in log(1/εstat) steps, which is the fastest possible rate of any first-order method. We provide simulation studies illustrating the sharpness of our theoretical results.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {559–616},
numpages = {58},
keywords = {nonconvex regularization, M-estimation, high-dimensional statistics, model selection, nonconvex optimization}
}

@article{10.5555/2789272.2789290,
author = {Li, Xingguo and Zhao, Tuo and Yuan, Xiaoming and Liu, Han},
title = {The Flare Package for High Dimensional Linear Regression and Precision Matrix Estimation in R},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {This paper describes an R package named flare, which implements a family of new high dimensional regression methods (LAD Lasso, SQRT Lasso, lq Lasso, and Dantzig selector) and their extensions to sparse precision matrix estimation (TIGER and CLIME). These methods exploit different nonsmooth loss functions to gain modeling flexibility, estimation robustness, and tuning insensitiveness. The developed solver is based on the alternating direction method of multipliers (ADMM). The package flare is coded in double precision C, and called from R by a user-friendly interface. The memory usage is optimized by using the sparse matrix output. The experiments show that flare is efficient and can scale up to large problems.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {553–557},
numpages = {5},
keywords = {tuning insensitiveness, sparse linear regression, robustness, sparse precision matrix estimation, alternating direction method of multipliers}
}

@article{10.5555/2789272.2789289,
author = {Weninger, Felix and Bergmann, Johannes and Schuller, Bj\"{o}rn},
title = {Introducing CURRENNT: The Munich Open-Source CUDA Recurrent Neural Network Toolkit},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {In this article, we introduce CURRENNT, an open-source parallel implementation of deep recurrent neural networks (RNNs) supporting graphics processing units (GPUs) through NVIDIA's Computed Unified Device Architecture (CUDA). CURRENNT supports uni- and bidirectional RNNs with Long Short-Term Memory (LSTM) memory cells which overcome the vanishing gradient problem. To our knowledge, CURRENNT is the first publicly available parallel implementation of deep LSTM-RNNs. Benchmarks are given on a noisy speech recognition task from the 2013 2nd CHiME Speech Separation and Recognition Challenge, where LSTM-RNNs have been shown to deliver best performance. In the result, double digit speedups in bidirectional LSTM training are achieved with respect to a reference single-threaded CPU implementation. CURRENNT is available under the GNU General Public License from http://sourceforge.net/p/currennt.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {547–551},
numpages = {5},
keywords = {parallel computing, long short-term memory, deep neural networks, recurrent neural networks}
}

@article{10.5555/2789272.2789288,
author = {Martins, Andr\'{e} F. T. and Figueiredo, M\'{a}rio A. T. and Aguiar, Pedro M. Q. and Smith, Noah A. and Xing, Eric P.},
title = {AD<sup>3</sup>: Alternating Directions Dual Decomposition for MAP Inference in Graphical Models},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {We present AD3, a new algorithm for approximate maximum a posteriori (MAP) inference on factor graphs, based on the alternating directions method of multipliers. Like other dual decomposition algorithms, AD3 has a modular architecture, where local subproblems are solved independently, and their solutions are gathered to compute a global update. The key characteristic of AD3 is that each local subproblem has a quadratic regularizer, leading to faster convergence, both theoretically and in practice. We provide closed-form solutions for these AD3 subproblems for binary pairwise factors and factors imposing first-order logic constraints. For arbitrary factors (large or combinatorial), we introduce an active set method which requires only an oracle for computing a local MAP configuration, making AD3 applicable to a wide range of problems. Experiments on synthetic and real-world problems show that AD3 compares favorably with the state-of-the-art.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {495–545},
numpages = {51},
keywords = {graphical models, dual decomposition, alternating directions method of multipliers, MAP inference}
}

@article{10.5555/2789272.2789287,
author = {Cano, Alberto and Luna, Jos\'{e} Mar\'{\i}a and Zafra, Amelia and Ventura, Sebasti\'{a}n},
title = {A Classification Module for Genetic Programming Algorithms in JCLEC},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {JCLEC-Classification is a usable and extensible open source library for genetic programming classification algorithms. It houses implementations of rule-based methods for classification based on genetic programming, supporting multiple model representations and providing to users the tools to implement any classifier easily. The software is written in Java and it is available from http://jclec.sourceforge.net/classification under the GPL license.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {491–494},
numpages = {4},
keywords = {evolutionary algorithms, classification, genetic programming, JCLEC}
}

@article{10.5555/2789272.2789286,
author = {Ailon, Nir and Chen, Yudong and Xu, Huan},
title = {Iterative and Active Graph Clustering Using Trace Norm Minimization without Cluster Size Constraints},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {This paper investigates graph clustering under the planted partition model in the presence of small clusters. Traditional results dictate that for an algorithm to provably correctly recover the underlying clusters, all clusters must be sufficiently large--in particular, the cluster sizes need to be Ω(√n), where n is the number of nodes of the graph. We show that this is not really a restriction: by a refined analysis of a convex-optimization-based recovery approach, we prove that small clusters, under certain mild assumptions, do not hinder recovery of large ones. Based on this result, we further devise an iterative algorithm to provably recover almost all clusters via a "peeling strategy": we recover large clusters first, leading to a reduced problem, and repeat this procedure. These results are extended to the partial observation setting, in which only a (chosen) part of the graph is observed. The peeling strategy gives rise to an active learning algorithm, in which edges adjacent to smaller clusters are queried more often after large clusters are learned (and removed). We expect that the idea of iterative peeling--that is, sequentially identifying a subset of the clusters and reducing the problem to a smaller one|is useful more broadly beyond the specific implementations (based on convex optimization) used in this paper.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {455–490},
numpages = {36},
keywords = {planted partition model, convex optimization, graph clustering, stochastic block model, community detection, active clustering}
}

@article{10.5555/2789272.2789285,
author = {Basu, Sumanta and Shojaie, Ali and Michailidis, George},
title = {Network Granger Causality with Inherent Grouping Structure},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {The problem of estimating high-dimensional network models arises naturally in the analysis of many biological and socio-economic systems. In this work, we aim to learn a network structure from temporal panel data, employing the framework of Granger causal models under the assumptions of sparsity of its edges and inherent grouping structure among its nodes. To that end, we introduce a group lasso regression regularization framework, and also examine a thresholded variant to address the issue of group misspecification. Further, the norm consistency and variable selection consistency of the estimates are established, the latter under the novel concept of direction consistency. The performance of the proposed methodology is assessed through an extensive set of simulation studies and comparisons with existing techniques. The study is illustrated on two motivating examples coming from functional genomics and financial econometrics.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {417–453},
numpages = {37},
keywords = {Granger causality, thresholding, panel vector autoregression model, high dimensional networks, group lasso}
}

@article{10.5555/2789272.2789284,
author = {Tran-Dinh, Quoc and Kyrillidis, Anastasios and Cevher, Volkan},
title = {Composite Self-Concordant Minimization},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {We propose a variable metric framework for minimizing the sum of a self-concordant function and a possibly non-smooth convex function, endowed with an easily computable proximal operator. We theoretically establish the convergence of our framework without relying on the usual Lipschitz gradient assumption on the smooth part. An important highlight of our work is a new set of analytic step-size selection and correction procedures based on the structure of the problem. We describe concrete algorithmic instances of our framework for several interesting applications and demonstrate them numerically on both synthetic and real data.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {371–416},
numpages = {46},
keywords = {sparse convex optimization, graph learning, composite minimization, self-concordance, proximal-gradient/Newton method}
}

@article{10.5555/2789272.2789283,
author = {Barbero, \`{A}lvaro and Takeda, Akiko and L\'{o}pez, Jorge},
title = {Geometric Intuition and Algorithms for Ev-SVM},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {In this work we address the Ev-SVM model proposed by P\'{e}rez-Cruz et al. as an extension of the traditional v support vector classification model (v-SVM). Through an enhancement of the range of admissible values for the regularization parameter v, the Ev-SVM has been shown to be able to produce a wider variety of decision functions, giving rise to a better adaptability to the data. However, while a clear and intuitive geometric interpretation can be given for the v-SVM model as a nearest-point problem in reduced convex hulls (RCH-NPP), no previous work has been made in developing such intuition for the Ev-SVM model. In this paper we show how Ev-SVM can be reformulated as a geometrical problem that generalizes RCH-NPP, providing new insights into this model. Under this novel point of view, we propose the RapMinos algorithm, able to solve Ev-SVM more efficiently than the current methods. Furthermore, we show how RapMinos is able to address the Ev-SVM model for any choice of regularization norm lp ≥1 seamlessly, which further extends the SVM model flexibility beyond the usual Ev-SVM models.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {323–369},
numpages = {47},
keywords = {SVM, classification, Ev-SVM, reduced convex hulls, nearest point problem}
}

@article{10.5555/2789272.2789282,
author = {Liu, Ji and Wright, Stephen J. and R\'{e}, Christopher and Bittorf, Victor and Sridhar, Srikrishna},
title = {An Asynchronous Parallel Stochastic Coordinate Descent Algorithm},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {We describe an asynchronous parallel stochastic coordinate descent algorithm for minimizing smooth unconstrained or separably constrained functions. The method achieves a linear convergence rate on functions that satisfy an essential strong convexity property and a sublinear rate (1/K) on general convex functions. Near-linear speedup on a multicore system can be expected if the number of processors is O(n1/2) in unconstrained optimization and O(n1/4) in the separable-constrained case, where n is the number of variables. We describe results from implementation on 40-core processors.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {285–322},
numpages = {38},
keywords = {asynchronous parallel optimization, stochastic coordinate descent}
}

@article{10.5555/2789272.2789281,
author = {Pitsikalis, Vassilis and Katsamanis, Athanasios and Theodorakis, Stavros and Maragos, Petros},
title = {Multimodal Gesture Recognition via Multiple Hypotheses Rescoring},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {We present a new framework for multimodal gesture recognition that is based on a multiple hypotheses rescoring fusion scheme. We specifically deal with a demanding Kinect-based multimodal data set, introduced in a recent gesture recognition challenge (ChaLearn 2013), where multiple subjects freely perform multimodal gestures. We employ multiple modalities, that is, visual cues, such as skeleton data, color and depth images, as well as audio, and we extract feature descriptors of the hands' movement, handshape, and audio spectral properties. Using a common hidden Markov model framework we build single-stream gesture models based on which we can generate multiple single stream-based hypotheses for an unknown gesture sequence. By multimodally rescoring these hypotheses via constrained decoding and a weighted combination scheme, we end up with a multimodally-selected best hypothesis. This is further refined by means of parallel fusion of the monomodal gesture models applied at a segmental level. In this setup, accurate gesture modeling is proven to be critical and is facilitated by an activity detection system that is also presented. The overall approach achieves 93.3% gesture recognition accuracy in the ChaLearn Kinect-based multimodal data set, significantly outperforming all recently published approaches on the same challenging multimodal gesture recognition task, providing a relative error rate reduction of at least 47.6%.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {255–284},
numpages = {30},
keywords = {multimodal gesture recognition, speech recognition, HMMs, activity detection, multimodal fusion}
}

@article{10.5555/2789272.2789280,
author = {Jiang, Feng and Zhang, Shengping and Wu, Shen and Gao, Yang and Zhao, Debin},
title = {Multi-Layered Gesture Recognition with Kinect},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {This paper proposes a novel multi-layered gesture recognition method with Kinect. We explore the essential linguistic characters of gestures: the components concurrent character and the sequential organization character, in a multi-layered framework, which extracts features from both the segmented semantic units and the whole gesture sequence and then sequentially classifies the motion, location and shape components. In the first layer, an improved principle motion is applied to model the motion component. In the second layer, a particle-based descriptor and a weighted dynamic time warping are proposed for the location component classification. In the last layer, the spatial path warping is further proposed to classify the shape component represented by unclosed shape context. The proposed method can obtain relatively high performance for one-shot learning gesture recognition on the ChaLearn Gesture Dataset comprising more than 50, 000 gesture sequences recorded with Kinect.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {227–254},
numpages = {28},
keywords = {multi-layered classification, gesture recognition, Kinect, principle motion, linguistic characters, dynamic time warping}
}

@article{10.5555/2789272.2789279,
author = {Qiu, Qiang and Sapiro, Guillermo},
title = {Learning Transformations for Clustering and Classification},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {A low-rank transformation learning framework for subspace clustering and classification is proposed here. Many high-dimensional data, such as face images and motion sequences, approximately lie in a union of low-dimensional subspaces. The corresponding subspace clustering problem has been extensively studied in the literature to partition such high-dimensional data into clusters corresponding to their underlying low-dimensional subspaces. Low-dimensional intrinsic structures are often violated for real-world observations, as they can be corrupted by errors or deviate from ideal models. We propose to address this by learning a linear transformation on subspaces using nuclear norm as the modeling and optimization criteria. The learned linear transformation restores a low-rank structure for data from the same subspace, and, at the same time, forces a maximally separated structure for data from different subspaces. In this way, we reduce variations within the subspaces, and increase separation between the subspaces for a more robust subspace clustering. This proposed learned robust subspace clustering framework significantly enhances the performance of existing subspace clustering methods. Basic theoretical results presented here help to further support the underlying framework. To exploit the low-rank structures of the transformed subspaces, we further introduce a fast subspace clustering technique, which efficiently combines robust PCA with sparse modeling. When class labels are present at the training stage, we show this low-rank transformation framework also significantly enhances classification performance. Extensive experiments using public data sets are presented, showing that the proposed approach significantly outperforms state-of-the-art methods for subspace clustering and classification. The learned low cost transform is also applicable to other classification frameworks.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {187–225},
numpages = {39},
keywords = {feature learning, low-rank transformation, classification, nuclear norm, subspace clustering}
}

@article{10.5555/2789272.2789278,
author = {Rakhlin, Alexander and Sridharan, Karthik and Tewari, Ambuj},
title = {Online Learning via Sequential Complexities},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {We consider the problem of sequential prediction and provide tools to study the minimax value of the associated game. Classical statistical learning theory provides several useful complexity measures to study learning with i.i.d. data. Our proposed sequential complexities can be seen as extensions of these measures to the sequential setting. The developed theory is shown to yield precise learning guarantees for the problem of sequential prediction. In particular, we show necessary and sufficient conditions for online learnability in the setting of supervised learning. Several examples show the utility of our framework: we can establish learnability without having to exhibit an explicit online learning algorithm.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {155–186},
numpages = {32},
keywords = {sequential complexities, regret minimization, online learning}
}

@article{10.5555/2789272.2789277,
author = {De Francisci Morales, Gianmarco and Bifet, Albert},
title = {SAMOA: Scalable Advanced Massive Online Analysis},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {SAMOA (SCALABLE ADVANCED MASSIVE ONLINE ANALYSIS) is a platform for mining big data streams. It provides a collection of distributed streaming algorithms for the most common data mining and machine learning tasks such as classification, clustering, and regression, as well as programming abstractions to develop new algorithms. It features a pluggable architecture that allows it to run on several distributed stream processing engines such as Storm, S4, and Samza. samoa is written in Java, is open source, and is available at http://samoa-project.net under the Apache Software License version 2.0.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {149–153},
numpages = {5},
keywords = {distributed systems, regression, clustering, data streams, toolbox, classification, machine learning}
}

@article{10.5555/2789272.2789276,
author = {Thon, Michael and Jaeger, Herbert},
title = {Links between Multiplicity Automata, Observable Operator Models and Predictive State Representations: A Unified Learning Framework},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {Stochastic multiplicity automata (SMA) are weighted finite automata that generalize probabilistic automata. They have been used in the context of probabilistic grammatical inference. Observable operator models (OOMs) are a generalization of hidden Markov models, which in turn are models for discrete-valued stochastic processes and are used ubiquitously in the context of speech recognition and bio-sequence modeling. Predictive state representations (PSRs) extend OOMs to stochastic input-output systems and are employed in the context of agent modeling and planning.We present SMA, OOMs, and PSRs under the common framework of sequential systems, which are an algebraic characterization of multiplicity automata, and examine the precise relationships between them. Furthermore, we establish a unified approach to learning such models from data. Many of the learning algorithms that have been proposed can be understood as variations of this basic learning scheme, and several turn out to be closely related to each other, or even equivalent.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {103–147},
numpages = {45},
keywords = {multiplicity automata, observable operator models, hidden Markov models, spectral learning algorithms, predictive state representations}
}

@article{10.5555/2789272.2789275,
author = {Bubenik, Peter},
title = {Statistical Topological Data Analysis Using Persistence Landscapes},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {We define a new topological summary for data that we call the persistence landscape. Since this summary lies in a vector space, it is easy to combine with tools from statistics and machine learning, in contrast to the standard topological summaries. Viewed as a random variable with values in a Banach space, this summary obeys a strong law of large numbers and a central limit theorem. We show how a number of standard statistical tests can be used for statistical inference using this summary. We also prove that this summary is stable and that it can be used to provide lower bounds for the bottleneck and Wasserstein distances.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {77–102},
numpages = {26},
keywords = {topological data analysis, statistical topology, persistent homology, persistence landscape, topological summary}
}

@article{10.5555/2789272.2789274,
author = {Yan, Qi and Ye, Jieping and Shen, Xiaotong},
title = {Simultaneous Pursuit of Sparseness and Rank Structures for Matrix Decomposition},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {In multi-response regression, pursuit of two different types of structures is essential to battle the curse of dimensionality. In this paper, we seek a sparsest decomposition representation of a parameter matrix in terms of a sum of sparse and low rank matrices, among many overcomplete decompositions. On this basis, we propose a constrained method subject to two nonconvex constraints, respectively for sparseness and low-rank properties. Computationally, obtaining an exact global optimizer is rather challenging. To overcome the difficulty, we use an alternating directions method solving a low-rank subproblem and a sparseness subproblem alternatively, where we derive an exact solution to the low-rank subproblem, as well as an exact solution in a special case and an approximated solution generally through a surrogate of the L0-constraint and difference convex programming, for the sparse subproblem. Theoretically, we establish convergence rates of a global minimizer in the Hellinger-distance, providing an insight into why pursuit of two different types of decomposed structures is expected to deliver higher estimation accuracy than its counterparts based on either sparseness alone or low-rank approximation alone. Numerical examples are given to illustrate these aspects, in addition to an application to facial imagine recognition and multiple time series analysis.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {47–75},
numpages = {29},
keywords = {structure pursuit, nonconvex minimization, matrix decomposition, blockwise decent}
}

@article{10.5555/2789272.2789273,
author = {Chen, Xi and Lin, Qihang and Zhou, Dengyong},
title = {Statistical Decision Making for Optimal Budget Allocation in Crowd Labeling},
year = {2015},
issue_date = {January 2015},
publisher = {JMLR.org},
volume = {16},
number = {1},
issn = {1532-4435},
abstract = {It has become increasingly popular to obtain machine learning labels through commercial crowdsourcing services. The crowdsourcing workers or annotators are paid for each label they provide, but the task requester usually has only a limited amount of the budget. Since the data instances have different levels of labeling difficulty and the workers have different reliability for the labeling task, it is desirable to wisely allocate the budget among all the instances and workers such that the overall labeling quality is maximized. In this paper, we formulate the budget allocation problem as a Bayesian Markov decision process (MDP), which simultaneously conducts learning and decision making. The optimal allocation policy can be obtained by using the dynamic programming (DP) recurrence. However, DP quickly becomes computationally intractable when the size of the problem increases. To solve this challenge, we propose a computationally eficient approximate policy which is called optimistic knowledge gradient. Our method applies to both pull crowdsourcing marketplaces with homogeneous workers and push marketplaces with heterogeneous workers. It can also incorporate the contextual information of instances when they are available. The experiments on both simulated and real data show that our policy achieves a higher labeling quality than other existing policies at the same budget level.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1–46},
numpages = {46},
keywords = {crowdsourcing, optimistic knowledge gradient, Markov decision process, budget allocation, dynamic programming}
}

@article{10.5555/2627435.2750369,
author = {Judah, Kshitij and Fern, Alan P. and Dietterich, Thomas G. and adepalli, Prasad},
title = {Active Lmitation Learning: Formal and Practical Reductions to I.I.D. Learning},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {In standard passive imitation learning, the goal is to learn a policy that performs as well as a target policy by passively observing full execution trajectories of it. Unfortunately, generating such trajectories can require substantial expert effort and be impractical in some cases. In this paper, we consider active imitation learning with the goal of reducing this effort by querying the expert about the desired action at individual states, which are selected based on answers to past queries and the learner's interactions with an environment simulator. We introduce a new approach based on reducing active imitation learning to active i.i.d. learning, which can leverage progress in the i.i.d. setting. Our first contribution is to analyze reductions for both non-stationary and stationary policies, showing for the first time that the label complexity (number of queries) of active imitation learning can be less than that of passive learning. Our second contribution is to introduce a practical algorithm inspired by the reductions, which is shown to be highly effective in five test domains compared to a number of alternatives.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3925–3963},
numpages = {39},
keywords = {imitation learning, active learning, active imitation learning, reductions}
}

@article{10.5555/2627435.2750368,
author = {Desautels, Thomas and Krause, Andreas and Burdick, Joel W.},
title = {Parallelizing Exploration-Exploitation Tradeoffs in Gaussian Process Bandit Optimization},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {How can we take advantage of opportunities for experimental parallelization in exploration-exploitation tradeoffs? In many experimental scenarios, it is often desirable to execute experiments simultaneously or in batches, rather than only performing one at a time. Additionally, observations may be both noisy and expensive. We introduce Gaussian Process Batch Upper Confidence Bound (GP-BUCB), an upper confidence bound-based algorithm, which models the reward function as a sample from a Gaussian process and which can select batches of experiments to run in parallel. We prove a general regret bound for GP-BUCB, as well as the surprising result that for some common kernels, the asymptotic average regret can be made independent of the batch size. The GP-BUCB algorithm is also applicable in the related case of a delay between initiation of an experiment and observation of its results, for which the same regret bounds hold. We also introduce Gaussian Process Adaptive Upper Confidence Bound (GP-AUCB), a variant of GP-BUCB which can exploit parallelism in an adaptive manner. We evaluate GP-BUCB and GP-AUCB on several simulated and real data sets. These experiments show that GP-BUCB and GP-AUCB are competitive with state-of-the-art heuristics.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3873–3923},
numpages = {51},
keywords = {regret bound, Gaussian process, batch, upper confidence bound, active learning}
}

@article{10.5555/2627435.2750367,
author = {Balcan, Maria-Florina and Liang, Yingyu and Gupta, Pramod},
title = {Robust Hierarchical Clustering},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {One of the most widely used techniques for data clustering is agglomerative clustering. Such algorithms have been long used across many different fields ranging from computational biology to social sciences to computer vision in part because their output is easy to interpret. Unfortunately, it is well known, however, that many of the classic agglomerative clustering algorithms are not robust to noise. In this paper we propose and analyze a new robust algorithm for bottom-up agglomerative clustering. We show that our algorithm can be used to cluster accurately in cases where the data satisfies a number of natural properties and where the traditional agglomerative algorithms fail. We also show how to adapt our algorithm to the inductive setting where our given data is only a small random sample of the entire data set. Experimental evaluations on synthetic and real world data sets show that our algorithm achieves better performance than other hierarchical algorithms in the presence of noise.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3831–3871},
numpages = {41},
keywords = {clustering, robustness, agglomerative algorithms, unsupervised learning}
}

@article{10.5555/2627435.2750366,
author = {Lu, Tyler and Boutilier, Craig},
title = {Effective Sampling and Learning for Mallows Models with Pairwise-Preference Data},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Learning preference distributions is a critical problem in many areas (e.g., recommender systems, IR, social choice). However, many existing learning and inference methods impose restrictive assumptions on the form of user preferences that can be admitted as evidence. We relax these restrictions by considering as data arbitrary pairwise comparisons of alternatives, which represent the fundamental building blocks of ordinal rankings. We develop the first algorithms for learning Mallows models (and mixtures thereof) from pairwise comparison data. At the heart of our technique is a new algorithm, the generalized repeated insertion model (GRIM), which allows sampling from arbitrary ranking distributions, and conditional Mallows models in particular. While we show that sampling from a Mallows model with pairwise evidence is computationally difficult in general, we develop approximate samplers that are exact for many important special cases|and have provable bounds with pairwise evidence--and derive algorithms for evaluating log-likelihood, learning Mallows mixtures, and non-parametric estimation. Experiments on real-world data sets demonstrate the effectiveness of our approach.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3783–3829},
numpages = {47},
keywords = {incomplete data, ranking, mixture models, preference learning, Mallows models}
}

@article{10.5555/2627435.2750365,
author = {Colombo, Diego and Maathuis, Marloes H.},
title = {Order-Independent Constraint-Based Causal Structure Learning},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {We consider constraint-based methods for causal structure learning, such as the PC-, FCI-, RFCI- and CCD- algorithms (Spirtes et al., 1993, 2000; Richardson, 1996; Colombo et al., 2012; Claassen et al., 2013). The first step of all these algorithms consists of the adjacency search of the PC-algorithm. The PC-algorithm is known to be order-dependent, in the sense that the output can depend on the order in which the variables are given. This order-dependence is a minor issue in low-dimensional settings. We show, however, that it can be very pronounced in high-dimensional settings, where it can lead to highly variable results. We propose several modifications of the PC-algorithm (and hence also of the other algorithms) that remove part or all of this order-dependence. All proposed modifications are consistent in high-dimensional settings under the same conditions as their original counterparts. We compare the PC-, FCI-, and RFCI-algorithms and their modifications in simulation studies and on a yeast gene expression data set. We show that our modifications yield similar performance in low-dimensional settings and improved performance in high-dimensional settings. All software is implemented in the R-package pcalg.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3741–3782},
numpages = {42},
keywords = {order-dependence, directed acyclic graph, FCI-algorithm, high-dimensional data, PC-algorithm, CCD-algorithm, consistency}
}

@article{10.5555/2627435.2750364,
author = {Martinez-Cantin, Ruben},
title = {BayesOpt: A Bayesian Optimization Library for Nonlinear Optimization, Experimental Design and Bandits},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {BayesOpt is a library with state-of-the-art Bayesian optimization methods to solve nonlinear optimization, stochastic bandits or sequential experimental design problems. Bayesian optimization characterized for being sample efficient as it builds a posterior distribution to capture the evidence and prior knowledge of the target function. Built in standard C++, the library is extremely efficient while being portable and flexible. It includes a common interface for C, C++, Python, Matlab and Octave.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3735–3739},
numpages = {5},
keywords = {Gaussian processes, sequential model-based optimization, sequential experimental design, Bayesian optimization, efficient global optimization}
}

@article{10.5555/2627435.2750363,
author = {Hansen, Toke J. and Mahoney, Michael W.},
title = {Semi-Supervised Eigenvectors for Large-Scale Locally-Biased Learning},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {In many applications, one has side information, e.g., labels that are provided in a semi-supervised manner, about a specific target region of a large data set, and one wants to perform machine learning and data analysis tasks "nearby" that prespecified target region. For example, one might be interested in the clustering structure of a data graph near a prespecified "seed set" of nodes, or one might be interested in finding partitions in an image that are near a prespecified "ground truth" set of pixels. Locally-biased problems of this sort are particularly challenging for popular eigenvector-based machine learning and data analysis tools. At root, the reason is that eigenvectors are inherently global quantities, thus limiting the applicability of eigenvector-based methods in situations where one is interested in very local properties of the data.In this paper, we address this issue by providing a methodology to construct semisupervised eigenvectors of a graph Laplacian, and we illustrate how these locally-biased eigenvectors can be used to perform locally-biased machine learning. These semi-supervised eigenvectors capture successively-orthogonalized directions of maximum variance, conditioned on being well-correlated with an input seed set of nodes that is assumed to be provided in a semi-supervised manner. We show that these semi-supervised eigenvectors can be computed quickly as the solution to a system of linear equations; and we also describe several variants of our basic method that have improved scaling properties. We provide several empirical examples demonstrating how these semi-supervised eigenvectors can be used to perform locally-biased learning; and we discuss the relationship between our results and recent machine learning algorithms that use global eigenvectors of the graph Laplacian.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3691–3734},
numpages = {44},
keywords = {spectral clustering, large-scale machine learning, local spectral methods, locally-biased learning, kernel methods, semi-supervised learning}
}

@article{10.5555/2627435.2750362,
author = {Goussies, Norberto A. and Ubalde, Sebasti\'{a}n and Mejail, Marta},
title = {Transfer Learning Decision Forests for Gesture Recognition},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Decision forests are an increasingly popular tool in computer vision problems. Their advantages include high computational efficiency, state-of-the-art accuracy and multi-class support. In this paper, we present a novel method for transfer learning which uses decision forests, and we apply it to recognize gestures and characters. We introduce two mechanisms into the decision forest framework in order to transfer knowledge from the source tasks to a given target task. The first one is mixed information gain, which is a databased regularizer. The second one is label propagation, which infers the manifold structure of the feature space. We show that both of them are important to achieve higher accuracy. Our experiments demonstrate improvements over traditional decision forests in the ChaLearn Gesture Challenge and MNIST data set. They also compare favorably against other state-of-the-art classifiers.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3667–3690},
numpages = {24},
keywords = {decision forests, transfer learning, gesture recognition}
}

@article{10.5555/2627435.2750361,
author = {Jackson, Jeffrey C. and Wimmer, Karl},
title = {New Results for Random Walk Learning},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {In a very strong positive result for passive learning algorithms, Bshouty et al. showed that DNF expressions are efficiently learnable in the uniform random walk model. It is natural to ask whether the more expressive class of thresholds of parities (TOP) can also be learned efficiently in this model, since both DNF and TOP are efficiently uniform-learnable from queries. However, the time bounds of the algorithms of Bshouty et al. are exponential for TOP. We present a new approach to weak parity learning that leads to quasi-efficient uniform random walk learnability of TOP. We also introduce a more general random walk model and give two positive results in this new model: DNF is efficiently learnable and juntas are efficiently agnostically learnable.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3635–3666},
numpages = {32},
keywords = {TOP learning, random walks, Fourier analysis of Boolean functions, DNF learning, computational learning theory}
}

@article{10.5555/2627435.2750360,
author = {Wipf, David and Zhang, Haichao},
title = {Revisiting Bayesian Blind Deconvolution},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Blind deconvolution involves the estimation of a sharp signal or image given only a blurry observation. Because this problem is fundamentally ill-posed, strong priors on both the sharp image and blur kernel are required to regularize the solution space. While this naturally leads to a standard MAP estimation framework, performance is compromised by unknown trade-off parameter settings, optimization heuristics, and convergence issues stemming from non-convexity and/or poor prior selections. To mitigate some of these problems, a number of authors have recently proposed substituting a variational Bayesian (VB) strategy that marginalizes over the high-dimensional image space leading to better estimates of the blur kernel. However, the underlying cost function now involves both integrals with no closed-form solution and complex, function-valued arguments, thus losing the transparency of MAP. Beyond standard Bayesian-inspired intuitions, it thus remains unclear by exactly what mechanism these methods are able to operate, rendering understanding, improvements and extensions more difficult. To elucidate these issues, we demonstrate that the VB methodology can be recast as an unconventional MAP problem with a very particular penalty/prior that conjoins the image, blur kernel, and noise level in a principled way. This unique penalty has a number of useful characteristics pertaining to relative concavity, local minima avoidance, normalization, and scale-invariance that allow us to rigorously explain the success of VB including its existing implementational heuristics and approximations. It also provides strict criteria for learning the noise level and choosing the optimal image prior that, perhaps counter-intuitively, need not reflect the statistics of natural scenes. In so doing we challenge the prevailing notion of why VB is successful for blind deconvolution while providing a transparent platform for introducing enhancements and extensions. Moreover, the underlying insights carry over to a wide variety of other bilinear models common in the machine learning literature such as independent component analysis, dictionary learning/sparse coding, and non-negative matrix factorization.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3595–3634},
numpages = {40},
keywords = {sparse estimation, sparse priors, variational Bayes, blind deconvolution, blind image deblurring}
}

@article{10.5555/2627435.2750359,
author = {Alain, Guillaume and Bengio, Yoshua},
title = {What Regularized Auto-Encoders Learn from the Data-Generating Distribution},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {What do auto-encoders learn about the underlying data-generating distribution? Recent work suggests that some auto-encoder variants do a good job of capturing the local manifold structure of data. This paper clarifies some of these previous observations by showing that minimizing a particular form of regularized reconstruction error yields a reconstruction function that locally characterizes the shape of the data-generating density. We show that the auto-encoder captures the score (derivative of the log-density with respect to the input). It contradicts previous interpretations of reconstruction error as an energy function. Unlike previous results, the theorems provided here are completely generic and do not depend on the parameterization of the auto-encoder: they show what the auto-encoder would tend to if given enough capacity and examples. These results are for a contractive training criterion we show to be similar to the denoising auto-encoder training criterion with small corruption noise, but with contraction applied on the whole reconstruction function rather than just encoder. Similarly to score matching, one can consider the proposed training criterion as a convenient alternative to maximum likelihood because it does not involve a partition function. Finally, we show how an approximate Metropolis-Hastings MCMC can be setup to recover samples from the estimated distribution, and this is confirmed in sampling experiments.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3563–3593},
numpages = {31},
keywords = {score matching, auto-encoders, manifold learning, denoising auto-encoders, Markov chains, generative models, unsupervised representation learning}
}

@article{10.5555/2627435.2750358,
author = {Yamazaki, Keisuke},
title = {Asymptotic Accuracy of Distribution-Based Estimation of Latent Variables},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Hierarchical statistical models are widely employed in information science and data engineering. The models consist of two types of variables: observable variables that represent the given data and latent variables for the unobservable labels. An asymptotic analysis of the models plays an important role in evaluating the learning process; the result of the analysis is applied not only to theoretical but also to practical situations, such as optimal model selection and active learning. There are many studies of generalization errors, which measure the prediction accuracy of the observable variables. However, the accuracy of estimating the latent variables has not yet been elucidated. For a quantitative evaluation of this, the present paper formulates distribution-based functions for the errors in the estimation of the latent variables. The asymptotic behavior is analyzed for both the maximum likelihood and the Bayes methods.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3541–3562},
numpages = {22},
keywords = {hierarchical parametric models, unsupervised learning, latent variable, Bayes method, maximum likelihood method}
}

@article{10.5555/2627435.2750357,
author = {Lyzinski, Vince and Fishkind, Donniell E. and Priebe, Carey E.},
title = {Seeded Graph Matching for Correlated Erd\"{o}s-R\'{e}Nyi Graphs},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Graph matching is an important problem in machine learning and pattern recognition. Herein, we present theoretical and practical results on the consistency of graph matching for estimating a latent alignment function between the vertex sets of two graphs, as well as subsequent algorithmic implications when the latent alignment is partially observed. In the correlated Erdos-R\'{e}nyi graph setting, we prove that graph matching provides a strongly consistent estimate of the latent alignment in the presence of even modest correlation. We then investigate a tractable, restricted-focus version of graph matching, which is only concerned with adjacency involving vertices in a partial observation of the latent alignment; we prove that a logarithmic number of vertices whose alignment is known is sufficient for this restricted-focus version of graph matching to yield a strongly consistent estimate of the latent alignment of the remaining vertices. We show how Frank-Wolfe methodology for approximate graph matching, when there is a partially observed latent alignment, inherently incorporates this restricted-focus graph matching. Lastly, we illustrate the relationship between seeded graph matching and restricted-focus graph matching by means of an illuminating example from human connectomics.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3513–3540},
numpages = {28},
keywords = {seeded vertices, graph matching, consistency, estimation, Frank-Wolfe, assignment problem, Erdos-R\'{e}nyi graph}
}

@article{10.5555/2627435.2750356,
author = {Van Moffaert, Kristof and Now\'{e}, Ann},
title = {Multi-Objective Reinforcement Learning Using Sets of Pareto Dominating Policies},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Many real-world problems involve the optimization of multiple, possibly conflicting objectives. Multi-objective reinforcement learning (MORL) is a generalization of standard reinforcement learning where the scalar reward signal is extended to multiple feedback signals, in essence, one for each objective. MORL is the process of learning policies that optimize multiple criteria simultaneously. In this paper, we present a novel temporal difference learning algorithm that integrates the Pareto dominance relation into a reinforcement learning approach. This algorithm is a multi-policy algorithm that learns a set of Pareto dominating policies in a single run. We name this algorithm Pareto Q-learning and it is applicable in episodic environments with deterministic as well as stochastic transition functions. A crucial aspect of Pareto Q-learning is the updating mechanism that bootstraps sets of Q-vectors. One of our main contributions in this paper is a mechanism that separates the expected immediate reward vector from the set of expected future discounted reward vectors. This decomposition allows us to update the sets and to exploit the learned policies consistently throughout the state space. To balance exploration and exploitation during learning, we also propose three set evaluation mechanisms. These three mechanisms evaluate the sets of vectors to accommodate for standard action selection strategies, such as ε-greedy. More precisely, these mechanisms use multi-objective evaluation principles such as the hypervolume measure, the cardinality indicator and the Pareto dominance relation to select the most promising actions. We experimentally validate the algorithm on multiple environments with two and three objectives and we demonstrate that Pareto Q-learning outperforms current state-of-the-art MORL algorithms with respect to the hypervolume of the obtained policies. We note that (1) Pareto Q-learning is able to learn the entire Pareto front under the usual assumption that each state-action pair is sufficiently sampled, while (2) not being biased by the shape of the Pareto front. Furthermore, (3) the set evaluation mechanisms provide indicative measures for local action selection and (4) the learned policies can be retrieved throughout the state and action space.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3483–3512},
numpages = {30},
keywords = {hypervolume, multiple criteria analysis, reinforcement learning, Pareto sets, multi-objective}
}

@article{10.5555/2627435.2750355,
author = {Feldman, Sergey and Gupta, Maya R. and Frigyik, Bela A.},
title = {Revisiting Stein's Paradox: Multi-Task Averaging},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {We present a multi-task learning approach to jointly estimate the means of multiple independent distributions from samples. The proposed multi-task averaging (MTA) algorithm results in a convex combination of the individual task's sample averages. We derive the optimal amount of regularization for the two task case for the minimum risk estimator and a minimax estimator, and show that the optimal amount of regularization can be practically estimated without cross-validation. We extend the practical estimators to an arbitrary number of tasks. Simulations and real data experiments demonstrate the advantage of the proposed MTA estimators over standard averaging and James-Stein estimation.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3441–3482},
numpages = {42},
keywords = {James-Stein, multi-task learning, Stein's paradox}
}

@article{10.5555/2627435.2750354,
author = {Hamilton, William and Fard, Mahdi Milani and Pineau, Joelle},
title = {Efficient Learning and Planning with Compressed Predictive States},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {Predictive state representations (PSRs) offer an expressive framework for modelling partially observable systems. By compactly representing systems as functions of observable quantities, the PSR learning approach avoids using local-minima prone expectation-maximization and instead employs a globally optimal moment-based algorithm. Moreover, since PSRs do not require a predetermined latent state structure as an input, they offer an attractive framework for model-based reinforcement learning when agents must plan without a priori access to a system model. Unfortunately, the expressiveness of PSRs comes with significant computational cost, and this cost is a major factor inhibiting the use of PSRs in applications. In order to alleviate this shortcoming, we introduce the notion of compressed PSRs (CPSRs). The CPSR learning approach combines recent advancements in dimensionality reduction, incremental matrix decomposition, and compressed sensing. We show how this approach provides a principled avenue for learning accurate approximations of PSRs, drastically reducing the computational costs associated with learning while also providing effective regularization. Going further, we propose a planning framework which exploits these learned models. And we show that this approach facilitates model-learning and planning in large complex partially observable domains, a task that is infeasible without the principled use of compression.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3395–3439},
numpages = {45},
keywords = {dimensionality reduction, predictive state representation, random projections, reinforcement learning}
}

@article{10.5555/2627435.2750353,
author = {Fournier-Viger, Philippe and Gomariz, Antonio and Gueniche, Ted and Soltani, Azadeh and Wu, Cheng-Wei and Tseng, Vincent S.},
title = {SPMF: A Java Open-Source Pattern Mining Library},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {We present SPMF, an open-source data mining library offering implementations of more than 55 data mining algorithms. SPMF is a cross-platform library implemented in Java, specialized for discovering patterns in transaction and sequence databases such as frequent itemsets, association rules and sequential patterns. The source code can be integrated in other Java programs. Moreover, SPMF offers a command line interface and a simple graphical interface for quick testing. The source code is available under the GNU General Public License, version 3. The website of the project offers several resources such as documentation with examples of how to run each algorithm, a developer's guide, performance comparisons of algorithms, data sets, an active forum, a FAQ and a mailing list.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3389–3393},
numpages = {5},
keywords = {transaction database, library, data mining, sequence database, frequent pattern mining, open-source}
}

@article{10.5555/2627435.2750352,
author = {Waegeman, Willem and Dembczy\'{n}ki, Krzysztof and Jachnik, Arkadiusz and Cheng, Weiwei and H\"{u}llermeier, Eyke},
title = {On the Bayes-Optimality of F-Measure Maximizers},
year = {2014},
issue_date = {January 2014},
publisher = {JMLR.org},
volume = {15},
number = {1},
issn = {1532-4435},
abstract = {The F-measure, which has originally been introduced in information retrieval, is nowadays routinely used as a performance metric for problems such as binary classification, multi-label classification, and structured output prediction. Optimizing this measure is a statistically and computationally challenging problem, since no closed-form solution exists. Adopting a decision-theoretic perspective, this article provides a formal and experimental analysis of different approaches for maximizing the F-measure. We start with a Bayes-risk analysis of related loss functions, such as Hamming loss and subset zero-one loss, showing that optimizing such losses as a surrogate of the F-measure leads to a high worst-case regret. Subsequently, we perform a similar type of analysis for F-measure maximizing algorithms, showing that such algorithms are approximate, while relying on additional assumptions regarding the statistical distribution of the binary response variables. Furthermore, we present a new algorithm which is not only computationally efficient but also Bayes-optimal, regardless of the underlying distribution. To this end, the algorithm requires only a quadratic (with respect to the number of binary responses) number of parameters of the joint distribution. We illustrate the practical performance of all analyzed methods by means of experiments with multi-label classification problems.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3333–3388},
numpages = {56},
keywords = {bayes-optimal predictions, structured output prediction, F-measure, multi-label classification, statistical decision theory, regret}
}

@article{10.5555/2627435.2697077,
author = {Couprie, Camille and Farabet, Cl\'{e}ment and Najman, Laurent and LeCun, Yann},
title = {Convolutional Nets and Watershed Cuts for Real-Time Semantic Labeling of RGBD Videos},
year = {2014},
issue_date = {January 2014},
publisher

license: Unlicense

repository: goyalkaraniit/acm-cr

repo_name: goyalkaraniit/acm-cr