text:
= {Guedj, Benjamin and Desikan, Bhargav Srinivasa},
title = {Pycobra: A Python Toolbox for Ensemble Learning and Visualisation},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We introduce pycobra, a Python library devoted to ensemble learning (regression and classification) and visualisation. Its main assets are the implementation of several ensemble learning algorithms, a flexible and generic interface to compare and blend any existing machine learning algorithm available in Python libraries (as long as a predict method is given), and visualisation tools such as Voronoi tessellations. pycobra is fully scikit-learn compatible and is released under the MIT open-source license. pycobra can be downloaded from the Python Package Index (PyPi) and Machine Learning Open Source Software (MLOSS). The current version (along with Jupyter notebooks, extensive documentation, and continuous integration tests) is available at https://github.com/bhargavvader/pycobra and official documentation website is https://modal.lille.inria.fr/pycobra.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6988–6992},
numpages = {5},
keywords = {Voronoi tesselation, ensemble methods, machine learning, open source software, python}
}

@article{10.5555/3122009.3242046,
author = {Kusano, Genki and Fukumizu, Kenji and Hiraoka, Yasuaki},
title = {Kernel Method for Persistence Diagrams via Kernel Embedding and Weight Factor},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Topological data analysis (TDA) is an emerging mathematical concept for characterizing shapes in complicated data. In TDA, persistence diagrams are widely recognized as a useful descriptor of data, distinguishing robust and noisy topological properties. This paper introduces a kernel method for persistence diagrams to develop a statistical framework in TDA. The proposed kernel is stable under perturbation of data, enables one to explicitly control the effect of persistence by a weight function, and allows an efficient and accurate approximate computation. The method is applied into practical data on granular systems, oxide glasses and proteins, showing advantages of our method compared to other relevant methods for persistence diagrams.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6947–6987},
numpages = {41},
keywords = {kernel method, topological data analysis, kernel embedding, persistence weighted Gaussian kernel, persistence diagrams}
}

@article{10.5555/3122009.3242045,
author = {Palowitch, John and Bhamidi, Shankar and Nobel, Andrew B.},
title = {Significance-Based Community Detection in Weighted Networks},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Community detection is the process of grouping strongly connected nodes in a network. Many community detection methods for un-weighted networks have a theoretical basis in a null model. Communities discovered by these methods therefore have interpretations in terms of statistical significance. In this paper, we introduce a null for weighted networks called the continuous configuration model. First, we propose a community extraction algorithm for weighted networks which incorporates iterative hypothesis testing under the null. We prove a central limit theorem for edge-weight sums and asymptotic consistency of the algorithm under a weighted stochastic block model. We then incorporate the algorithm in a community detection method called CCME. To benchmark the method, we provide a simulation framework involving the null to plant "background" nodes in weighted networks with communities. We show that the empirical performance of CCME on these simulations is competitive with existing methods, particularly when overlapping communities and background nodes are present. To further validate the method, we present two real-world networks with potential background nodes and analyze them with CCME, yielding results that reveal macro-features of the corresponding systems.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6899–6946},
numpages = {48},
keywords = {weighted networks, multiple testing, unsupervised learning, community detection, network models}
}

@article{10.5555/3122009.3242044,
author = {Hubara, Itay and Courbariaux, Matthieu and Soudry, Daniel and El-Yaniv, Ran and Bengio, Yoshua},
title = {Quantized Neural Networks: Training Neural Networks with Low Precision Weights and Activations},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We introduce a method to train Quantized Neural Networks (QNNs) -- neural networks with extremely low precision (e.g., 1-bit) weights and activations, at run-time. At traintime the quantized weights and activations are used for computing the parameter gradients. During the forward pass, QNNs drastically reduce memory size and accesses, and replace most arithmetic operations with bit-wise operations. As a result, power consumption is expected to be drastically reduced. We trained QNNs over the MNIST, CIFAR-10, SVHN and ImageNet datasets. The resulting QNNs achieve prediction accuracy comparable to their 32-bit counterparts. For example, our quantized version of AlexNet with 1-bit weights and 2-bit activations achieves 51% top-1 accuracy. Moreover, we quantize the parameter gradients to 6-bits as well which enables gradients computation using only bit-wise operation. Quantized recurrent neural networks were tested over the Penn Treebank dataset, and achieved comparable accuracy as their 32-bit counterparts using only 4-bits. Last but not least, we programmed a binary matrix multiplication GPU kernel with which it is possible to run our MNIST QNN 7 times faster than with an unoptimized GPU kernel, without suffering any loss in classification accuracy. The QNN code is available online.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6869–6898},
numpages = {30},
keywords = {neural networks compression, energy efficient neural networks, computer vision, language models, deep learning}
}

@article{10.5555/3122009.3242043,
author = {Hajek, Bruce and Wu, Yihong and Xu, Jiaming},
title = {Submatrix Localization via Message Passing},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {The principal submatrix localization problem deals with recovering a K \texttimes{} K principal submatrix of elevated mean µ in a large n \texttimes{} n symmetric matrix subject to additive standard Gaussian noise, or more generally, mean zero, variance one, subgaussian noise. This problem serves as a prototypical example for community detection, in which the community corresponds to the support of the submatrix. The main result of this paper is that in the regime Ω(√n) ≤ K ≤ o(n), the support of the submatrix can be weakly recovered (with o(K) misclassification errors on average) by an optimized message passing algorithm if λ = µ2K2/n, the signal-to-noise ratio, exceeds 1/e. This extends a result by Deshpande and Montanari previously obtained for K = Θ(√n) and µ = Θ(1): In addition, the algorithm can be combined with a voting procedure to achieve the information-theoretic limit of exact recovery with sharp constants for all K ≥ n/log n (1/8e + o(1)). The total running time of the algorithm is O(n2 log n).Another version of the submatrix localization problem, known as noisy biclustering, aims to recover a K1 \texttimes{} K2 submatrix of elevated mean µ in a large n1 \texttimes{} n2 Gaussian matrix. The optimized message passing algorithm and its analysis are adapted to the bicluster problem assuming Ω(√ni) ≤ Ki ≤ o(ni) and K1 = K2: A sharp information-theoretic condition for the weak recovery of both clusters is also identified.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6817–6868},
numpages = {52},
keywords = {high-dimensional statistics, submatrix localization, message passing, spectral algorithms computational complexity, biclustering}
}

@article{10.5555/3122009.3242042,
author = {Li, Lisha and Jamieson, Kevin and DeSalvo, Giulia and Rostamizadeh, Afshin and Talwalkar, Ameet},
title = {Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Performance of machine learning algorithms depends critically on identifying a good set of hyperparameters. While recent approaches use Bayesian optimization to adaptively select configurations, we focus on speeding up random search through adaptive resource allocation and early-stopping. We formulate hyperparameter optimization as a pure-exploration nonstochastic infinite-armed bandit problem where a predefined resource like iterations, data samples, or features is allocated to randomly sampled configurations. We introduce a novel algorithm, Hyperband, for this framework and analyze its theoretical properties, providing several desirable guarantees. Furthermore, we compare Hyperband with popular Bayesian optimization methods on a suite of hyperparameter optimization problems. We observe that Hyperband can provide over an order-of-magnitude speedup over our competitor set on a variety of deep-learning and kernel-based learning problems.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6765–6816},
numpages = {52},
keywords = {infinite-armed bandits, model selection, hyperparameter optimization, deep learning, online optimization}
}

@article{10.5555/3122009.3242041,
author = {Li, Xingguo and Zhao, Tuo and Arora, Raman and Liu, Han and Hong, Mingyi},
title = {On Faster Convergence of Cyclic Block Coordinate Descent-Type Methods for Strongly Convex Minimization},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {The cyclic block coordinate descent-type (CBCD-type) methods, which perform iterative updates for a few coordinates (a block) simultaneously throughout the procedure, have shown remarkable computational performance for solving strongly convex minimization problems. Typical applications include many popular statistical machine learning methods such as elastic-net regression, ridge penalized logistic regression, and sparse additive regression. Existing optimization literature has shown that for strongly convex minimization, the CBCD-type methods attain iteration complexity of O(p log(1/ε)), where ε is a pre-specified accuracy of the objective value, and p is the number of blocks. However, such iteration complexity explicitly depends on p, and therefore is at least p times worse than the complexity O(log(1/ε)) of gradient descent (GD) methods. To bridge this theoretical gap, we propose an improved convergence analysis for the CBCD-type methods. In particular, we first show that for a family of quadratic minimization problems, the iteration complexity O(log2(p) · log(1/ε)) of the CBCD-type methods matches that of the GD methods in term of dependency on p, up to a log2 p factor. Thus our complexity bounds are sharper than the existing bounds by at least a factor of p/log2(p). We also provide a lower bound to confirm that our improved complexity bounds are tight (up to a log2(p) factor), under the assumption that the largest and smallest eigenvalues of the Hessian matrix do not scale with p. Finally, we generalize our analysis to other strongly convex minimization problems beyond quadratic ones.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6741–6764},
numpages = {24},
keywords = {strongly convex minimization, improved iteration complexity, quadratic minimization, cyclic block coordinate descent, gradient descent}
}

@article{10.5555/3122009.3242040,
author = {Li, Zifan and Tewari, Ambuj},
title = {Beyond the Hazard Rate: More Perturbation Algorithms for Adversarial Multi-Armed Bandits},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Recent work on follow the perturbed leader (FTPL) algorithms for the adversarial multiarmed bandit problem has highlighted the role of the hazard rate of the distribution generating the perturbations. Assuming that the hazard rate is bounded, it is possible to provide regret analyses for a variety of FTPL algorithms for the multi-armed bandit problem. This paper pushes the inquiry into regret bounds for FTPL algorithms beyond the bounded hazard rate condition. There are good reasons to do so: natural distributions such as the uniform and Gaussian violate the condition. We give regret bounds for both bounded support and unbounded support distributions without assuming the hazard rate condition. We also disprove a conjecture that the Gaussian distribution cannot lead to a low-regret algorithm. In fact, it turns out that it leads to near optimal regret, up to logarithmic factors. A key ingredient in our approach is the introduction of a new notion called the generalized hazard rate.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6717–6740},
numpages = {24},
keywords = {follow the perturbed leader, multi-armed bandits, regret, gradient based algorithms, online learning}
}

@article{10.5555/3122009.3242039,
author = {Lian, Heng and Fan, Zengyan},
title = {Divide-and-Conquer for Debiased l1-Norm Support Vector Machine in Ultra-High Dimensions},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {1-norm support vector machine (SVM) generally has competitive performance compared to standard 2-norm support vector machine in classification problems, with the advantage of automatically selecting relevant features. We propose a divide-and-conquer approach in the large sample size and high-dimensional setting by splitting the data set across multiple machines, and then averaging the debiased estimators. Extension of existing theoretical studies to SVM is challenging in estimation of the inverse Hessian matrix that requires approximating the Dirac delta function via smoothing. We show that under appropriate conditions the aggregated estimator can obtain the same convergence rate as the central estimator utilizing all observations.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6691–6716},
numpages = {26},
keywords = {classification, debiased estimator, distributed estimator, divide and conquer, sparsity}
}

@article{10.5555/3122009.3242038,
author = {Probst, Philipp and Boulesteix, Anne-Laure},
title = {To Tune or Not to Tune the Number of Trees in Random Forest},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {The number of trees T in the random forest (RF) algorithm for supervised learning has to be set by the user. It is unclear whether T should simply be set to the largest computationally manageable value or whether a smaller T may be sufficient or in some cases even better. While the principle underlying bagging is that more trees are better, in practice the classification error rate sometimes reaches a minimum before increasing again for increasing number of trees. The goal of this paper is four-fold: (i) providing theoretical results showing that the expected error rate may be a non-monotonous function of the number of trees and explaining under which circumstances this happens; (ii) providing theoretical results showing that such non-monotonous patterns cannot be observed for other performance measures such as the Brier score and the logarithmic loss (for classification) and the mean squared error (for regression); (iii) illustrating the extent of the problem through an application to a large number (n = 306) of datasets from the public database OpenML; (iv) finally arguing in favor of setting T to a computationally feasible large number as long as classical error measures based on average loss are considered.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6673–6690},
numpages = {18},
keywords = {bagging, number of trees, random forest, error rate, out-of-bag}
}

@article{10.5555/3122009.3242037,
author = {Sasaki, Hiroaki and Kanamori, Takafumi and Hyv\"{a}rinen, Aapo and Niu, Gang and Sugiyama, Masashi},
title = {Mode-Seeking Clustering and Density Ridge Estimation via Direct Estimation of Density-Derivative-Ratios},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Modes and ridges of the probability density function behind observed data are useful geometric features. Mode-seeking clustering assigns cluster labels by associating data samples with the nearest modes, and estimation of density ridges enables us to find lower-dimensional structures hidden in data. A key technical challenge both in mode-seeking clustering and density ridge estimation is accurate estimation of the ratios of the first- and second-order density derivatives to the density. A naive approach takes a three-step approach of first estimating the data density, then computing its derivatives, and finally taking their ratios. However, this three-step approach can be unreliable because a good density estimator does not necessarily mean a good density derivative estimator, and division by the estimated density could significantly magnify the estimation error. To cope with these problems, we propose a novel estimator for the density-derivative-ratios. The proposed estimator does not involve density estimation, but rather directly approximates the ratios of density derivatives of any order. Moreover, we establish a convergence rate of the proposed estimator. Based on the proposed estimator, novel methods both for mode-seeking clustering and density ridge estimation are developed, and the respective convergence rates to the mode and ridge of the underlying density are also established. Finally, we experimentally demonstrate that the developed methods significantly outperform existing methods, particularly for relatively high-dimensional data.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6626–6672},
numpages = {47},
keywords = {density ridge estimation, mode-seeking clustering, geometric feature, density derivative}
}

@article{10.5555/3122009.3242036,
author = {Yao, Quanming and Kwok, James T.},
title = {Efficient Learning with a Family of Nonconvex Regularizers by Redistributing Nonconvexity},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {The use of convex regularizers allows for easy optimization, though they often produce biased estimation and inferior prediction performance. Recently, nonconvex regularizers have attracted a lot of attention and outperformed convex ones. However, the resultant optimization problem is much harder. In this paper, a popular subclass of l1-based nonconvex sparsity-inducing and low-rank regularizers is considered. This includes nonconvex variants of lasso, sparse group lasso, tree-structured lasso, nuclear norm and total variation regularizers. We propose to move the nonconvexity from the regularizer to the loss. The nonconvex regularizer is then transformed to a familiar convex one, while the resultant loss function can still be guaranteed to be smooth. Learning with the convexified regularizer can be performed by existing efficient algorithms originally designed for convex regularizers (such as the proximal algorithm, Frank-Wolfe algorithm, alternating direction method of multipliers and stochastic gradient descent). This is further extended to consider cases where the convexified regularizer does not have a closed-form proximal step, and when the loss function is nonconvex nonsmooth. Extensive experiments on a variety of machine learning application scenarios show that optimizing the transformed problem is much faster than running the state-of-the-art on the original problem.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6574–6625},
numpages = {52},
keywords = {nonconvex optimization, matrix completion, proximal algorithm, nonconvex regularization, Frank-Wolfe algorithm}
}

@article{10.5555/3122009.3242035,
author = {Shah, Rajen D. and Meinshausen, Nicolai},
title = {On b-Bit Min-Wise Hashing for Large-Scale Regression and Classification with Sparse Data},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Large-scale regression problems where both the number of variables, p, and the number of observations, n, may be large and in the order of millions or more, are becoming increasingly more common. Typically the data are sparse: only a fraction of a percent of the entries in the design matrix are non-zero. Nevertheless, often the only computationally feasible approach is to perform dimension reduction to obtain a new design matrix with far fewer columns and then work with this compressed data.b-bit min-wise hashing (Li and K\"{o}nig, 2011; Li et al., 2011) is a promising dimension reduction scheme for sparse matrices which produces a set of random features such that regression on the resulting design matrix approximates a kernel regression with the resemblance kernel. In this work, we derive bounds on the prediction error of such regressions. For both linear and logistic models, we show that the average prediction error vanishes asymptotically as long as q||β*||22/n → 0, where q is the average number of non-zero entries in each row of the design matrix and β* is the coefficient of the linear predictor.We also show that ordinary least squares or ridge regression applied to the reduced data can in fact allow us fit more flexible models. We obtain non-asymptotic prediction error bounds for interaction models and for models where an unknown row normalisation must be applied in order for the signal to be linear in the predictors.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6532–6573},
numpages = {42},
keywords = {ridge regression, sparse data, min-wise hashing, large-scale data, resemblance kernel}
}

@article{10.5555/3122009.3242034,
author = {Abbe, Emmanuel},
title = {Community Detection and Stochastic Block Models: Recent Developments},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {The stochastic block model (SBM) is a random graph model with planted clusters. It is widely employed as a canonical model to study clustering and community detection, and provides generally a fertile ground to study the statistical and computational tradeoffs that arise in network and data sciences.This note surveys the recent developments that establish the fundamental limits for community detection in the SBM, both with respect to information-theoretic and computational thresholds, and for various recovery requirements such as exact, partial and weak recovery (a.k.a., detection). The main results discussed are the phase transitions for exact recovery at the Chernoff-Hellinger threshold, the phase transition for weak recovery at the Kesten-Stigum threshold, the optimal distortion-SNR tradeoff for partial recovery, the learning of the SBM parameters and the gap between information-theoretic and computational thresholds.The note also covers some of the algorithms developed in the quest of achieving the limits, in particular two-round algorithms via graph-splitting, semi-definite programming, linearized belief propagation, classical and nonbacktracking spectral methods. A few open problems are also discussed.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6446–6531},
numpages = {86},
keywords = {computational gaps, network data analysis, clustering, unsupervised learning, spectral algorithms, random graphs, community detection, stochastic block models}
}

@article{10.5555/3122009.3242033,
author = {Padilla, Oscar Hernan Madrid and Sharpnack, James and Scott, James G.},
title = {The DFS Fused Lasso: Linear-Time Denoising over General Graphs},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {The fused lasso, also known as (anisotropic) total variation denoising, is widely used for piecewise constant signal estimation with respect to a given undirected graph. The fused lasso estimate is highly nontrivial to compute when the underlying graph is large and has an arbitrary structure. But for a special graph structure, namely, the chain graph, the fused lasso--or simply, 1d fused lasso--can be computed in linear time. In this paper, we revisit a result recently established in the online classification literature (Herbster et al., 2009; Cesa-Bianchi et al., 2013) and show that it has important implications for signal denoising on graphs. The result can be translated to our setting as follows. Given a general graph, if we run the standard depth-first search (DFS) traversal algorithm, then the total variation of any signal over the chain graph induced by DFS is no more than twice its total variation over the original graph.This result leads to several interesting theoretical and computational conclusions. Letting m and n denote the number of edges and nodes, respectively, of the graph in consideration, it implies that for an underlying signal with total variation t over the graph, the fused lasso (properly tuned) achieves a mean squared error rate of t2/3n-2/3. Moreover, precisely the same mean squared error rate is achieved by running the 1d fused lasso on the DFS-induced chain graph. Importantly, the latter estimator is simple and computationally cheap, requiring O(m) operations to construct the DFS-induced chain and O(n) operations to compute the 1d fused lasso solution over this chain. Further, for trees that have bounded maximum degree, the error rate of t2/3n-2/3 cannot be improved, in the sense that it is the minimax rate for signals that have total variation t over the tree. Finally, several related results also hold--for example, the analogous result holds for a roughness measure defined by the l0 norm of differences across edges in place of the total variation metric.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6410–6445},
numpages = {36},
keywords = {total variation denoising, fused lasso, graph denoising, depth-first search}
}

@article{10.5555/3122009.3242032,
author = {Tosh, Christopher and Dasgupta, Sanjoy},
title = {Maximum Likelihood Estimation for Mixtures of Spherical Gaussians is NP-Hard},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {This paper presents NP-hardness and hardness of approximation results for maximum likelihood estimation of mixtures of spherical Gaussians.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6399–6409},
numpages = {11},
keywords = {NP-completeness, mixtures of gaussians, maximum likelihood}
}

@article{10.5555/3122009.3242031,
author = {Nogueira, Sarah and Sechidis, Konstantinos and Brown, Gavin},
title = {On the Stability of Feature Selection Algorithms},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Feature Selection is central to modern data science, from exploratory data analysis to predictive model-building. The "stability" of a feature selection algorithm refers to the robustness of its feature preferences, with respect to data sampling and to its stochastic nature. An algorithm is 'unstable' if a small change in data leads to large changes in the chosen feature subset. Whilst the idea is simple, quantifying this has proven more challenging--we note numerous proposals in the literature, each with different motivation and justification. We present a rigorous statistical treatment for this issue. In particular, with this work we consolidate the literature and provide (1) a deeper understanding of existing work based on a small set of properties, and (2) a clearly justified statistical approach with several novel benefits. This approach serves to identify a stability measure obeying all desirable properties, and (for the first time in the literature) allowing confidence intervals and hypothesis tests on the stability, enabling rigorous experimental comparison of feature selection algorithms.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6345–6398},
numpages = {54},
keywords = {feature selection, stability}
}

@article{10.5555/3122009.3242030,
author = {Freitag, Michael and Amiriparian, Shahin and Pugachevskiy, Sergey and Cummins, Nicholas and Schuller, Bj\"{o}rn},
title = {AuDeep: Unsupervised Learning of Representations from Audio with Deep Recurrent Neural Networks},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {AUDEEP is a Python toolkit for deep unsupervised representation learning from acoustic data. It is based on a recurrent sequence to sequence autoencoder approach which can learn representations of time series data by taking into account their temporal dynamics. We provide an extensive command line interface in addition to a Python API for users and developers, both of which are comprehensively documented and publicly available at https: //github.com/auDeep/auDeep. Experimental results indicate that auDeep features are competitive with state-of-the art audio classification.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6340–6344},
numpages = {5},
keywords = {deep feature learning, sequence to sequence learning, autoencoders, recurrent neural networks, audio processing}
}

@article{10.5555/3122009.3242029,
author = {Du, Jian and Ma, Shaodan and Wu, Yik-Chung and Kar, Soummya and Moura, Jos\'{e} M. F.},
title = {Convergence Analysis of Distributed Inference with Vector-Valued Gaussian Belief Propagation},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {This paper considers inference over distributed linear Gaussian models using factor graphs and Gaussian belief propagation (BP). The distributed inference algorithm involves only local computation of the information matrix and of the mean vector, and message passing between neighbors. Under broad conditions, it is shown that the message information matrix converges to a unique positive definite limit matrix for arbitrary positive semidefinite initialization, and it approaches an arbitrarily small neighborhood of this limit matrix at an exponential rate. A necessary and sufficient convergence condition for the belief mean vector to converge to the optimal centralized estimator is provided under the assumption that the message information matrix is initialized as a positive semidefinite matrix. Further, it is shown that Gaussian BP always converges when the underlying factor graph is given by the union of a forest and a single loop. The proposed convergence condition in the setup of distributed linear Gaussian models is shown to be strictly weaker than other existing convergence conditions and requirements, including the Gaussian Markov random field based walk-summability condition, and applicable to a large class of scenarios.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6302–6339},
numpages = {38},
keywords = {linear gaussian model, walk-summability, graphical model, large-scale networks, Markov random field}
}

@article{10.5555/3122009.3242028,
author = {Lei, Yunwen and Shi, Lei and Guo, Zheng-Chu},
title = {Convergence of Unregularized Online Learning Algorithms},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {In this paper we study the convergence of online gradient descent algorithms in reproducing kernel Hilbert spaces (RKHSs) without regularization. We establish a sufficient condition and a necessary condition for the convergence of excess generalization errors in expectation. A sufficient condition for the almost sure convergence is also given. With high probability, we provide explicit convergence rates of the excess generalization errors for both averaged iterates and the last iterate, which in turn also imply convergence rates with probability one. To our best knowledge, this is the first high-probability convergence rate for the last iterate of online gradient descent algorithms in the general convex setting. Without any boundedness assumptions on iterates, our results are derived by a novel use of two measures of the algorithm's one-step progress, respectively by generalization errors and by distances in RKHSs, where the variances of the involved martingales are cancelled out by the descent property of the algorithm.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6269–6301},
numpages = {33},
keywords = {learning theory, convergence analysis, reproducing kernel Hilbert space, online learning}
}

@article{10.5555/3122009.3242027,
author = {Angiulli, Fabrizio},
title = {On the Behavior of Intrinsically High-Dimensional Spaces: Distances, Direct and Reverse Nearest Neighbors, and Hubness},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Over the years, different characterizations of the curse of dimensionality have been provided, usually stating the conditions under which, in the limit of the infinite dimensionality, distances become indistinguishable. However, these characterizations almost never address the form of associated distributions in the finite, although high-dimensional, case. This work aims to contribute in this respect by investigating the distribution of distances, and of direct and reverse nearest neighbors, in intrinsically high-dimensional spaces. Indeed, we derive a closed form for the distribution of distances from a given point, for the expected distance from a given point to its kth nearest neighbor, and for the expected size of the approximate set of neighbors of a given point in finite high-dimensional spaces. Additionally, the hubness problem is considered, which is related to the form of the function Nk representing the number of points that have a given point as one of their k nearest neighbors, which is also called the number of k-occurrences. Despite the extensive use of this function, the precise characterization of its form is a longstanding problem. We derive a closed form for the number of k-occurrences associated with a given point in finite high-dimensional spaces, together with the associated limiting probability distribution. By investigating the relationships with the hubness phenomenon emerging in network science, we find that the distribution of node (in-)degrees of some real-life, large-scale networks has connections with the distribution of k-occurrences described herein.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6209–6268},
numpages = {60},
keywords = {nearest neighbors, high-dimensional data, distance concentration, reverse nearest neighbors, hubness, distribution of distances}
}

@article{10.5555/3122009.3242026,
author = {Morstatter, Fred and Liu, Huan},
title = {In Search of Coherence and Consensus: Measuring the Interpretability of Statistical Topics},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Topic modeling is an important tool in natural language processing. Topic models provide two forms of output. The first is a predictive model. This type of model has the ability to predict unseen documents (e.g., their categories). When topic models are used in this way, there are ample measures to assess their performance. The second output of these models is the topics themselves. Topics are lists of keywords that describe the top words pertaining to each topic. Often, these lists of keywords are presented to a human subject who then assesses the meaning of the topic, which is ultimately subjective. One of the fundamental problems of topic models lies in assessing the quality of the topics from the perspective of human interpretability. Naturally, human subjects need to be employed to evaluate interpretability of a topic. Lately, crowdsourcing approaches are widely used to serve the role of human subjects in evaluation. In this work we study measures of interpretability and propose to measure topic interpretability from two perspectives: topic coherence and topic consensus. We start with an existing measure for topic coherence--model precision. It evaluates coherence of a topic by introducing an intruded word and measuring how well a human subject or a crowdsourcing approach could identify the intruded word: if it is easy to identify, the topic is coherent. We then investigate how we can measure coherence comprehensively by examining dimensions of topic coherence. For the second perspective of topic interpretability, we suggest topic consensus that measures how well the results of a crowdsourcing approach matches those given categories of topics. Good topics should lead to good categories, thus, high topic consensus. Therefore, if there is low topic consensus in terms of categories, topics could be of low interpretability. We then further discuss how topic coherence and topic consensus assess different aspects of topic interpretability and hope that this work can pave way for comprehensive measures of topic interpretability.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6177–6208},
numpages = {32}
}

@article{10.5555/3122009.3242025,
author = {Wu, Siqi and Yu, Bin},
title = {Local Identifiability of ℓ1-Minimization Dictionary Learning: A Sufficient and Almost Necessary Condition},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We study the theoretical properties of learning a dictionary from N signals xi ∈ ℝK for i = 1,..., N via ℓ1-minimization. We assume that xi's are i.i.d. random linear combinations of the K columns from a complete (i.e., square and invertible) reference dictionary D0 ∈ ℝK\texttimes{}K. Here, the random linear coefficients are generated from either the s-sparse Gaussian model or the Bernoulli-Gaussian model. First, for the population case, we establish a sufficient and almost necessary condition for the reference dictionary D0 to be locally identifiable, i.e., a strict local minimum of the expected ℓ1-norm objective function. Our condition covers both sparse and dense cases of the random linear coefficients and significantly improves the sufficient condition by Gribonval and Schnass (2010). In addition, we show that for a complete µ-coherent reference dictionary, i.e., a dictionary with absolute pairwise column inner-product at most µ ∈ [0; 1), local identifiability holds even when the random linear coefficient vector has up to O(µ-2) nonzero entries. Moreover, our local identifiability results also translate to the finite sample case with high probability provided that the number of signals N scales as O(K log K).},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6121–6176},
numpages = {56},
keywords = {non-convex optimization, local minimum, sparse decomposition, dictionary learning, ℓ1-minimization}
}

@article{10.5555/3122009.3242024,
author = {Chow, Yinlam and Ghavamzadeh, Mohammad and Janson, Lucas and Pavone, Marco},
title = {Risk-Constrained Reinforcement Learning with Percentile Risk Criteria},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {In many sequential decision-making problems one is interested in minimizing an expected cumulative cost while taking into account risk, i.e., increased awareness of events of small probability and high consequences. Accordingly, the objective of this paper is to present efficient reinforcement learning algorithms for risk-constrained Markov decision processes (MDPs), where risk is represented via a chance constraint or a constraint on the conditional value-at-risk (CVaR) of the cumulative cost. We collectively refer to such problems as percentile risk-constrained MDPs. Specifically, we first derive a formula for computing the gradient of the Lagrangian function for percentile risk-constrained MDPs. Then, we devise policy gradient and actor-critic algorithms that (1) estimate such gradient, (2) update the policy in the descent direction, and (3) update the Lagrange multiplier in the ascent direction. For these algorithms we prove convergence to locally optimal policies. Finally, we demonstrate the effectiveness of our algorithms in an optimal stopping problem and an online marketing application.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6070–6120},
numpages = {51},
keywords = {chance-constrained optimization, conditional value-at-risk, reinforcement learning, Markov decision process, actor-critic algorithms, policy gradient algorithms}
}

@article{10.5555/3122009.3242023,
author = {Yuan, Xiao-Tong and Li, Ping and Zhang, Tong},
title = {Gradient Hard Thresholding Pursuit},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Hard Thresholding Pursuit (HTP) is an iterative greedy selection procedure for finding sparse solutions of underdetermined linear systems. This method has been shown to have strong theoretical guarantee and impressive numerical performance. In this article, we generalize HTP from compressed sensing to a generic problem setup of sparsity-constrained convex optimization. The proposed algorithm iterates between a standard gradient descent step and a hard-thresholding step with or without debiasing. We analyze the parameter estimation and sparsity recovery performance of the proposed method. Extensive numerical results confirm our theoretical predictions and demonstrate the superiority of our method to the state-of-the-art greedy selection methods in sparse linear regression, sparse logistic regression and sparse precision matrix estimation problems.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {6027–6069},
numpages = {43},
keywords = {sparsity recovery, greedy selection, hard thresholding pursuit}
}

@article{10.5555/3122009.3242022,
author = {Li, Qianxiao and Chen, Long and Tai, Cheng and Weinan, E.},
title = {Maximum Principle Based Algorithms for Deep Learning},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {The continuous dynamical system approach to deep learning is explored in order to devise alternative frameworks for training algorithms. Training is recast as a control problem and this allows us to formulate necessary optimality conditions in continuous time using the Pontryagin's maximum principle (PMP). A modification of the method of successive approximations is then used to solve the PMP, giving rise to an alternative training algorithm for deep learning. This approach has the advantage that rigorous error estimates and convergence results can be established. We also show that it may avoid some pitfalls of gradient-based methods, such as slow convergence on at landscapes near saddle points. Furthermore, we demonstrate that it obtains favorable initial convergence rate periteration, provided Hamiltonian maximization can be efficiently carried out - a step which is still in need of improvement. Overall, the approach opens up new avenues to attack problems associated with deep learning, such as trapping in slow manifolds and inapplicability of gradient-based methods for discrete trainable variables.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5998–6026},
numpages = {29},
keywords = {pontryagin's maximum principle, deep learning, optimal control, method of successive approximations}
}

@article{10.5555/3122009.3242021,
author = {Schreiber, Jacob},
title = {Pomegranate: Fast and Flexible Probabilistic Modeling in Python},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We present pomegranate, an open source machine learning package for probabilistic modeling in Python. Probabilistic modeling encompasses a wide range of methods that explicitly describe uncertainty using probability distributions. Three widely used probabilistic models implemented in pomegranate are general mixture models, hidden Markov models, and Bayesian networks. A primary focus of pomegranate is to abstract away the complexities of training models from their definition. This allows users to focus on specifying the correct model for their application instead of being limited by their understanding of the underlying algorithms. An aspect of this focus involves the collection of additive sufficient statistics from data sets as a strategy for training models. This approach trivially enables many useful learning strategies, such as out-of-core learning, minibatch learning, and semi-supervised learning, without requiring the user to consider how to partition data or modify the algorithms to handle these tasks themselves. pomegranate is written in Cython to speed up calculations and releases the global interpreter lock to allow for built-in multithreaded parallelism, making it competitive with--or outperform--other implementations of similar algorithms. This paper presents an overview of the design choices in pomegranate, and how they have enabled complex features to be supported by simple code. The code is available at https://github.com/jmschrei/pomegranate.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5992–5997},
numpages = {6},
keywords = {big data, python, probabilistic modeling, cython, machine learning}
}

@article{10.5555/3122009.3242020,
author = {Morningstar, Alan and Melko, Roger G.},
title = {Deep Learning the Ising Model near Criticality},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {It is well established that neural networks with deep architectures perform better than shallow networks for many tasks in machine learning. In statistical physics, while there has been recent interest in representing physical data with generative modelling, the focus has been on shallow neural networks. A natural question to ask is whether deep neural networks hold any advantage over shallow networks in representing such data. We investigate this question by using unsupervised, generative graphical models to learn the probability distribution of a two-dimensional Ising system. Deep Boltzmann machines, deep belief networks, and deep restricted Boltzmann networks are trained on thermal spin configurations from this system, and compared to the shallow architecture of the restricted Boltzmann machine. We benchmark the models, focussing on the accuracy of generating energetic observables near the phase transition, where these quantities are most difficult to approximate. Interestingly, after training the generative networks, we observe that the accuracy essentially depends only on the number of neurons in the first hidden layer of the network, and not on other model details such as network depth or model type. This is evidence that shallow networks are more efficient than deep networks at representing physical probability distributions associated with Ising systems near criticality.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5975–5991},
numpages = {17},
keywords = {restricted Boltzmann machine, deep Boltzmann machine, deep learning, deep belief network}
}

@article{10.5555/3122009.3242019,
author = {George, Clint P. and Doss, Hani},
title = {Principled Selection of Hyperparameters in the Latent Dirichlet Allocation Model},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Latent Dirichlet Allocation (LDA) is a well known topic model that is often used to make inference regarding the properties of collections of text documents. LDA is a hierarchical Bayesian model, and involves a prior distribution on a set of latent topic variables. The prior is indexed by certain hyperparameters, and even though these have a large impact on inference, they are usually chosen either in an ad-hoc manner, or by applying an algorithm whose theoretical basis has not been firmly established. We present a method, based on a combination of Markov chain Monte Carlo and importance sampling, for estimating the maximum likelihood estimate of the hyperparameters. The method may be viewed as a computational scheme for implementation of an empirical Bayes analysis. It comes with theoretical guarantees, and a key feature of our approach is that we provide theoretically-valid error margins for our estimates. Experiments on both synthetic and real data show good performance of our methodology.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5937–5974},
numpages = {38},
keywords = {Markov chain monte carlo, latent dirichlet allocation, empirical bayes inference, topic modelling, model selection}
}

@article{10.5555/3122009.3242018,
author = {Borkar, Vivek S. and Dwaracherla, Vikranth R. and Sahasrabudhe, Neeraja},
title = {Gradient Estimation with Simultaneous Perturbation and Compressive Sensing},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We propose a scheme for finding a "good" estimator for the gradient of a function on a high-dimensional space with few function evaluations, for applications where function evaluations are expensive and the function under consideration is not sensitive in all coordinates locally, making its gradient almost sparse. Exploiting the latter aspect, our method combines ideas from Spall's Simultaneous Perturbation Stochastic Approximation with compressive sensing. We theoretically justify its computational advantages and illustrate them empirically by numerical experiments. In particular, applications to estimating gradient outer product matrix as well as standard optimization problems are illustrated via simulations.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5910–5936},
numpages = {27},
keywords = {gradient descent, compressive sensing, gradient estimation, gradient outer product matrix, sparsity}
}

@article{10.5555/3122009.3242017,
author = {Lucic, Mario and Faulkner, Matthew and Krause, Andreas and Feldman, Dan},
title = {Training Gaussian Mixture Models at Scale via Coresets},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {How can we train a statistical mixture model on a massive data set? In this work we show how to construct coresets for mixtures of Gaussians. A coreset is a weighted subset of the data, which guarantees that models fitting the coreset also provide a good fit for the original data set. We show that, perhaps surprisingly, Gaussian mixtures admit coresets of size polynomial in dimension and the number of mixture components, while being independent of the data set size. Hence, one can harness computationally intensive algorithms to compute a good approximation on a significantly smaller data set. More importantly, such coresets can be efficiently constructed both in distributed and streaming settings and do not impose restrictions on the data generating process. Our results rely on a novel reduction of statistical estimation to problems in computational geometry and new combinatorial complexity results for mixtures of Gaussians. Empirical evaluation on several real-world data sets suggests that our coreset-based approach enables significant reduction in training-time with negligible approximation error.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5885–5909},
numpages = {25},
keywords = {gaussian mixture models, coresets, streaming and distributed computation}
}

@article{10.5555/3122009.3242016,
author = {Chazal, Fr\'{e}d\'{e}ric and Fasy, Brittany and Lecci, Fabrizio and Michel, Bertrand and Rinaldo, Alessandro and Rinaldo, Alessandro and Wasserman, Larry},
title = {Robust Topological Inference: Distance to a Measure and Kernel Distance},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Let P be a distribution with support S. The salient features of S can be quantified with persistent homology, which summarizes topological features of the sublevel sets of the distance function (the distance of any point x to S). Given a sample from P we can infer the persistent homology using an empirical version of the distance function. However, the empirical distance function is highly non-robust to noise and outliers. Even one outlier is deadly. The distance-to-a-measure (DTM), introduced by Chazal et al. (2011), and the kernel distance, introduced by Phillips et al. (2014), are smooth functions that provide useful topological information but are robust to noise and outliers. Chazal et al. (2015) derived concentration bounds for DTM. Building on these results, we derive limiting distributions and confidence sets, and we propose a method for choosing tuning parameters.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5845–5884},
numpages = {40},
keywords = {topological data analysis, RKHS, persistent homology}
}

@article{10.5555/3122009.3242015,
author = {Vitelli, Valeria and S\o{}rensen, \O{}ystein and Crispino, Marta and Frigessi, Arnoldo and Arjas, Elja},
title = {Probabilistic Preference Learning with the Mallows Rank Model},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Ranking and comparing items is crucial for collecting information about preferences in many areas, from marketing to politics. The Mallows rank model is among the most successful approaches to analyze rank data, but its computational complexity has limited its use to a particular form based on Kendall distance. We develop new computationally tractable methods for Bayesian inference in Mallows models that work with any right-invariant distance. Our method performs inference on the consensus ranking of the items, also when based on partial rankings, such as top-k items or pairwise comparisons. We prove that items that none of the assessors has ranked do not inuence the maximum a posteriori consensus ranking, and can therefore be ignored. When assessors are many or heterogeneous, we propose a mixture model for clustering them in homogeneous subgroups, with cluster-specific consensus rankings. We develop approximate stochastic algorithms that allow a fully probabilistic analysis, leading to coherent quantifications of uncertainties. We make probabilistic predictions on the class membership of assessors based on their ranking of just some items, and predict missing individual preferences, as needed in recommendation systems. We test our approach using several experimental and benchmark data sets.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5796–5844},
numpages = {49},
keywords = {pairwise comparisons, preference learning with uncertainty, recommendation systems, incomplete rankings, Markov chain monte carlo}
}

@article{10.5555/3122009.3242014,
author = {Vural, Elif and Guillemot, Christine},
title = {A Study of the Classification of Low-Dimensional Data with Supervised Manifold Learning},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Supervised manifold learning methods learn data representations by preserving the geometric structure of data while enhancing the separation between data samples from different classes. In this work, we propose a theoretical study of supervised manifold learning for classification. We consider nonlinear dimensionality reduction algorithms that yield linearly separable embeddings of training data and present generalization bounds for this type of algorithms. A necessary condition for satisfactory generalization performance is that the embedding allow the construction of a sufficiently regular interpolation function in relation with the separation margin of the embedding. We show that for supervised embeddings satisfying this condition, the classification error decays at an exponential rate with the number of training samples. Finally, we examine the separability of supervised nonlinear embeddings that aim to preserve the low-dimensional geometric structure of data based on graph representations. The proposed analysis is supported by experiments on several real data sets.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5741–5795},
numpages = {55},
keywords = {classification, dimensionality reduction, manifold learning, RBF interpolation, out-of-sample extensions}
}

@article{10.5555/3122009.3242013,
author = {Wang, Yining and Singh, Aarti},
title = {Provably Correct Algorithms for Matrix Column Subset Selection with Selectively Sampled Data},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We consider the problem of matrix column subset selection, which selects a subset of columns from an input matrix such that the input can be well approximated by the span of the selected columns. Column subset selection has been applied to numerous real-world data applications such as population genetics summarization, electronic circuits testing and recommendation systems. In many applications the complete data matrix is unavailable and one needs to select representative columns by inspecting only a small portion of the input matrix. In this paper we propose the first provably correct column subset selection algorithms for partially observed data matrices. Our proposed algorithms exhibit different merits and limitations in terms of statistical accuracy, computational efficiency, sample complexity and sampling schemes, which provides a nice exploration of the tradeoff between these desired properties for column subset selection. The proposed methods employ the idea of feedback driven sampling and are inspired by several sampling schemes previously introduced for low-rank matrix approximation tasks (Drineas et al., 2008; Frieze et al., 2004; Deshpande and Vempala, 2006; Krishnamurthy and Singh, 2014). Our analysis shows that, under the assumption that the input data matrix has incoherent rows but possibly coherent columns, all algorithms provably converge to the best low-rank approximation of the original data as number of selected columns increases. Furthermore, two of the proposed algorithms enjoy a relative error bound, which is preferred for column subset selection and matrix approximation purposes. We also demonstrate through both theoretical and empirical analysis the power of feedback driven sampling compared to uniform random sampling on input matrices with highly correlated columns.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5699–5740},
numpages = {42},
keywords = {column subset selection, active learning, leverage scores}
}

@article{10.5555/3122009.3242012,
author = {Natarajan, Nagarajan and Dhillon, Inderjit S. and Ravikumar, Pradeep and Tewari, Ambuj},
title = {Cost-Sensitive Learning with Noisy Labels},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We study binary classification in the presence of class-conditional random noise, where the learner gets to see labels that are flipped independently with some probability, and where the flip probability depends on the class. Our goal is to devise learning algorithms that are efficient and statistically consistent with respect to commonly used utility measures. In particular, we look at a family of measures motivated by their application in domains where cost-sensitive learning is necessary (for example, when there is class imbalance). In contrast to most of the existing literature on consistent classification that are limited to the classical 0-1 loss, our analysis includes more general utility measures such as the AM measure (arithmetic mean of True Positive Rate and True Negative Rate). For this problem of cost-sensitive learning under class-conditional random noise, we develop two approaches that are based on suitably modifying surrogate losses. First, we provide a simple unbiased estimator of any loss, and obtain performance bounds for empirical utility maximization in the presence of i.i.d. data with noisy labels. If the loss function satis_es a simple symmetry condition, we show that using unbiased estimator leads to an efficient algorithm for empirical maximization. Second, by leveraging a reduction of risk minimization under noisy labels to classification with weighted 0-1 loss, we suggest the use of a simple weighted surrogate loss, for which we are able to obtain strong utility bounds. This approach implies that methods already used in practice, such as biased SVM and weighted logistic regression, are provably noise-tolerant. For two practically important measures in our family, we show that the proposed methods are competitive with respect to recently proposed methods for dealing with label noise in several benchmark data sets.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5666–5698},
numpages = {33},
keywords = {cost-sensitive learning, class-conditional label noise, statistical consistency}
}

@article{10.5555/3122009.3242011,
author = {Cowan, Wesley and Honda, Junya and Katehakis, Michael N.},
title = {Normal Bandits of Unknown Means and Variances},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Consider the problem of sampling sequentially from a finite number of N ≥ 2 populations, specified by random variables Xki, i = 1,...,N; and k = 1,2,..., where Xki denotes the outcome from population i the kth time it is sampled. It is assumed that for each fixed i, {Xki}k≥1 is a sequence of i.i.d. normal random variables, with unknown mean µi and unknown variance σi2. The objective is to have a policy π for deciding from which of the N populations to sample from at any time t = 1,2, ... so as to maximize the expected sum of outcomes of n total samples or equivalently to minimize the regret due to lack on information of the parameters µi and σi2. In this paper, we present a simple inflated sample mean (ISM) index policy that is asymptotically optimal in the sense of Theorem 4 below. This resolves a standing open problem from Burnetas and Katehakis (1996b). Additionally, finite horizon regret bounds are given.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5638–5665},
numpages = {28},
keywords = {sequential allocation, inflated sample means, multi-armed bandits, UCB policies}
}

@article{10.5555/3122009.3242010,
author = {Baydin, At\i{}l\i{}m G\"{u}nes and Pearlmutter, Barak A. and Radul, Alexey Andreyevich and Siskind, Jeffrey Mark},
title = {Automatic Differentiation in Machine Learning: A Survey},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Derivatives, mostly in the form of gradients and Hessians, are ubiquitous in machine learning. Automatic differentiation (AD), also called algorithmic differentiation or simply "auto-diff", is a family of techniques similar to but more general than backpropagation for efficiently and accurately evaluating derivatives of numeric functions expressed as computer programs. AD is a small but established field with applications in areas including computational uid dynamics, atmospheric sciences, and engineering design optimization. Until very recently, the fields of machine learning and AD have largely been unaware of each other and, in some cases, have independently discovered each other's results. Despite its relevance, general-purpose AD has been missing from the machine learning toolbox, a situation slowly changing with its ongoing adoption under the names "dynamic computational graphs" and "differentiable programming". We survey the intersection of AD and machine learning, cover applications where AD has direct relevance, and address the main implementation techniques. By precisely defining the main differentiation techniques and their interrelationships, we aim to bring clarity to the usage of the terms "autodiff", "automatic differentiation", and "symbolic differentiation" as these are encountered more and more in machine learning settings.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5595–5637},
numpages = {43},
keywords = {differentiable programming, backpropagation}
}

@article{10.5555/3122009.3242009,
author = {Heusser, Andrew C. and Ziman, Kirsten and Owen, Lucy L. W. and Manning, Jeremy R.},
title = {HyperTools: A Python Toolbox for Gaining Geometric Insights into High-Dimensional Data},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Dimensionality reduction algorithms have played a foundational role in facilitating the deep understanding of complex high-dimensional data. One particularly useful application of dimensionality reduction techniques is in data visualization. Low-dimensional visualizations can help practitioners understand where machine learning algorithms might leverage the geometric properties of a dataset to improve performance. Another challenge is to generalize insights across datasets [e.g. data from multiple modalities describing the same system (Haxby et al., 2011), artwork or photographs of similar content in different styles (Zhu et al., 2017), etc.]. Several recently developed techniques (e.g. Haxby et al., 2011; Chen et al., 2015) use the procrustean transformation (Sch\"{o}nemann, 1966) to align the geometries of two or more spaces so that data with different axes may be plotted in a common space. We propose that each of these techniques (dimensionality reduction, alignment, and visualization) applied in sequence should be cast as a single conceptual hyperplot operation for gaining geometric insights into high-dimensional data. Our Python toolbox enables this operation in a single (highly flexible) function call.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5589–5594},
numpages = {6},
keywords = {high-dimensional, time-series data, dimensionality reduction, visualization, procrustes}
}

@article{10.5555/3122009.3242008,
author = {Hensman, James and Durrande, Nicolas and Solin, Arno},
title = {Variational Fourier Features for Gaussian Processes},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {This work brings together two powerful concepts in Gaussian processes: the variational approach to sparse approximation and the spectral representation of Gaussian processes. This gives rise to an approximation that inherits the benefits of the variational approach but with the representational power and computational scalability of spectral representations. The work hinges on a key result that there exist spectral features related to a finite domain of the Gaussian process which exhibit almost-independent covariances. We derive these expressions for Mat\'{e}rn kernels in one dimension, and generalize to more dimensions using kernels with specific structures. Under the assumption of additive Gaussian noise, our method requires only a single pass through the data set, making for very fast and accurate computation. We fit a model to 4 million training points in just a few minutes on a standard laptop. With non-conjugate likelihoods, our MCMC scheme reduces the cost of computation from O(NM2) (for a sparse Gaussian process) to O(NM) per iteration, where N is the number of data and M is the number of features.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5537–5588},
numpages = {52},
keywords = {variational inference, Gaussian processes, Fourier features}
}

@article{10.5555/3122009.3242007,
author = {Yu, Felix X. and Bhaskara, Aditya and Kumar, Sanjiv and Gong, Yunchao and Chang, Shih-Fu},
title = {On Binary Embedding Using Circulant Matrices},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Binary embeddings provide efficient and powerful ways to perform operations on large scale data. However binary embedding typically requires long codes in order to preserve the discriminative power of the input space. Thus binary coding methods traditionally suffer from high computation and storage costs in such a scenario. To address this problem, we propose Circulant Binary Embedding (CBE) which generates binary codes by projecting the data with a circulant matrix. The circulant structure allows us to use Fast Fourier Transform algorithms to speed up the computation. For obtaining k-bit binary codes from d-dimensional data, our method improves the time complexity from O(dk) to O(d log d), and the space complexity from O(dk) to O(d).We study two settings, which differ in the way we choose the parameters of the circulant matrix. In the first, the parameters are chosen randomly and in the second, the parameters are learned using the data. For randomized CBE, we give a theoretical analysis comparing it with binary embedding using an unstructured random projection matrix. The challenge here is to show that the dependencies in the entries of the circulant matrix do not lead to a loss in performance. In the second setting, we design a novel time-frequency alternating optimization to learn data-dependent circulant projections, which alternatively minimizes the objective in original and Fourier domains. In both the settings, we show by extensive experiments that the CBE approach gives much better performance than the state-of-the-art approaches if we fix a running time, and provides much faster computation with negligible performance degradation if we fix the number of bits in the embedding.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5507–5536},
numpages = {30},
keywords = {structured matrix, dimensionality reduction, binary embedding, FFT, circulant matrix}
}

@article{10.5555/3122009.3208030,
author = {Wilson, James D. and Palowitch, John and Bhamidi, Shankar and Nobel, Andrew B.},
title = {Community Extraction in Multilayer Networks with Heterogeneous Community Structure},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Multilayer networks are a useful way to capture and model multiple, binary or weighted relationships among a fixed group of objects. While community detection has proven to be a useful exploratory technique for the analysis of single-layer networks, the development of community detection methods for multilayer networks is still in its infancy. We propose and investigate a procedure, called Multilayer Extraction, that identifies densely connected vertex-layer sets in multilayer networks. Multilayer Extraction makes use of a significance based score that quantifies the connectivity of an observed vertex-layer set through comparison with a fixed degree random graph model. Multilayer Extraction directly handles networks with heterogeneous layers where community structure may be different from layer to layer. The procedure can capture overlapping communities, as well as background vertex-layer pairs that do not belong to any community. We establish consistency of the vertex-layer set optimizer of our proposed multilayer score under the multilayer stochastic block model. We investigate the performance of Multilayer Extraction on three applications and a test bed of simulations. Our theoretical and numerical evaluations suggest that Multilayer Extraction is an effective exploratory tool for analyzing complex multilayer networks. Publicly available code is available at https://github.com/jdwilson4/MultilayerExtraction.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5458–5506},
numpages = {49},
keywords = {clustering, modularity, score based methods, multiplex networks, community detection}
}

@article{10.5555/3122009.3208029,
author = {Sadeghi, Kayvan},
title = {Faithfulness of Probability Distributions and Graphs},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {A main question in graphical models and causal inference is whether, given a probability distribution P (which is usually an underlying distribution of data), there is a graph (or graphs) to which P is faithful. The main goal of this paper is to provide a theoretical answer to this problem. We work with general independence models, which contain probabilistic independence models as a special case. We exploit a generalization of ordering, called preordering, of the nodes of (mixed) graphs. This allows us to provide sufficient conditions for a given independence model to be Markov to a graph with the minimum possible number of edges, and more importantly, necessary and sufficient conditions for a given probability distribution to be faithful to a graph. We present our results for the general case of mixed graphs, but specialize the definitions and results to the better-known subclasses of undirected (concentration) and bidirected (covariance) graphs as well as directed acyclic graphs.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5429–5457},
numpages = {29},
keywords = {mixed graph, directed acyclic graph, causal discovery, independence model, compositional graphoid, graphical model selection, Markov property, structural learning, faithfulness}
}

@article{10.5555/3122009.3208028,
author = {Wong, Raymond K. W. and Lee, Thomas C. M.},
title = {Matrix Completion with Noisy Entries and Outliers},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {This paper considers the problem of matrix completion when the observed entries are noisy and contain outliers. It begins with introducing a new optimization criterion for which the recovered matrix is defined as its solution. This criterion uses the celebrated Huber function from the robust statistics literature to downweigh the effects of outliers. A practical algorithm is developed to solve the optimization involved. This algorithm is fast, straightforward to implement, and monotonic convergent. Furthermore, the proposed methodology is theoretically shown to be stable in a well defined sense. Its promising empirical performance is demonstrated via a sequence of simulation experiments, including image inpainting.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5404–5428},
numpages = {25},
keywords = {soft-impute, robust methods, Huber function, stable recovery, ES-algorithm}
}

@article{10.5555/3122009.3208027,
author = {Lecu\'{e}, Guillaume and Mendelson, Shahar},
title = {Regularization and the Small-Ball Method II: Complexity Dependent Error Rates},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We study estimation properties of regularized procedures of the form f ∈ argmin f∈F (1/N Σi=1N (Yi - f(Xi))2 + λψ(f)) for a convex class of functions F, regularization function ψ(undefined) and some well chosen regularization parameter λ, where the given data is an independent sample (Xi, Yi)i=1N.We obtain bounds on the L2 estimation error rate that depend on the complexity of the true model F* := {f ∈ F : ψ(f) ≤ (f*)}, where f* ∈ argminf∈F E(Y - f(X))2 and the (Xi, Yi)'s are independent and distributed as (X, Y). Our estimate holds under weak stochastic assumptions - one of which being a small-ball condition satis\`{e}d by F - and for rather flexible choices of regularization functions ψ(undefined). Moreover, the result holds in the learning theory framework: we do not assume any a-priori connection between the output Y and the input X.As a proof of concept, we apply our general estimation bound to various choices of ψ, for example, the lp and Sp-norms (for p ≥ 1), weak-lp, atomic norms, max-norm and SLOPE. In many cases, the estimation rate almost coincides with the minimax rate in the class F*.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5356–5403},
numpages = {48},
keywords = {regularization, high-dimensional statistics, minimax rates, empirical processes theory, learning theory}
}

@article{10.5555/3122009.3208026,
author = {Huang, Ruitong and Lattimore, Tor and Gy\"{o}rgy, Andr\'{a}s and Szepesv\'{a}ri, Csaba},
title = {Following the Leader and Fast Rates in Online Linear Prediction: Curved Constraint Sets and Other Regularities},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Follow the leader (FTL) is a simple online learning algorithm that is known to perform well when the loss functions are convex and positively curved. In this paper we ask whether there are other settings when FTL achieves low regret. In particular, we study the fundamental problem of linear prediction over a convex, compact domain with non-empty interior. Amongst other results, we prove that the curvature of the boundary of the domain can act as if the losses were curved: In this case, we prove that as long as the mean of the loss vectors have positive lengths bounded away from zero, FTL enjoys logarithmic regret, while for polytope domains and stochastic data it enjoys finite expected regret. The former result is also extended to strongly convex domains by establishing an equivalence between the strong convexity of sets and the minimum curvature of their boundary, which may be of independent interest. Building on a previously known meta-algorithm, we also get an algorithm that simultaneously enjoys the worst-case guarantees and the smaller regret of FTL when the data is 'easy'. Finally, we show that such guarantees are achievable directly (e.g., by the follow the regularized leader algorithm or by a shrinkage-based variant of FTL) when the constraint set is an ellipsoid.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5325–5355},
numpages = {31},
keywords = {follow the leader, online linear optimization, strongly convex decision set, logarithmic regret, curvature}
}

@article{10.5555/3122009.3208025,
author = {Yu, Yaoliang and Zhang, Xinhua and Schuurmans, Dale},
title = {Generalized Conditional Gradient for Sparse Estimation},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Sparsity is an important modeling tool that expands the applicability of convex formulations for data analysis, however it also creates significant challenges for efficient algorithm design. In this paper we investigate the generalized conditional gradient (GCG) algorithm for solving sparse optimization problems--demonstrating that, with some enhancements, it can provide a more efficient alternative to current state of the art approaches. After studying the convergence properties of GCG for general convex composite problems, we develop efficient methods for evaluating polar operators, a subroutine that is required in each GCG iteration. In particular, we show how the polar operator can be efficiently evaluated in learning low-rank matrices, instantiated with detailed examples on matrix completion and dictionary learning. A further improvement is achieved by interleaving GCG with fixed-rank local subspace optimization. A series of experiments on matrix completion, multi-class classification, and multi-view dictionary learning shows that the proposed method can significantly reduce the training cost of current alternatives.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5279–5324},
numpages = {46},
keywords = {multi-view learning, matrix completion, generalized conditional gradient, frank-wolfe, sparse estimation, dictionary learning}
}

@article{10.5555/3122009.3208024,
author = {Wang, Yining and Yu, Adams Wei and Singh, Aarti},
title = {On Computationally Tractable Selection of Experiments in Measurement-Constrained Regression Models},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We derive computationally tractable methods to select a small subset of experiment settings from a large pool of given design points. The primary focus is on linear regression models, while the technique extends to generalized linear models and Delta's method (estimating functions of linear regression models) as well. The algorithms are based on a continuous relaxation of an otherwise intractable combinatorial optimization problem, with sampling or greedy procedures as post-processing steps. Formal approximation guarantees are established for both algorithms, and numerical results on both synthetic and real-world data confirm the effectiveness of the proposed methods.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5238–5278},
numpages = {41},
keywords = {minimax analysis, computationally tractable methods, A-optimality, optimal selection of experiments}
}

@article{10.5555/3122009.3208023,
author = {Coretto, Pietro and Hennig, Christian},
title = {Consistency, Breakdown Robustness, and Algorithms for Robust Improper Maximum Likelihood Clustering},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {The robust improper maximum likelihood estimator (RIMLE) is a new method for robust multivariate clustering finding approximately Gaussian clusters. It maximizes a pseudolikelihood defined by adding a component with improper constant density for accommodating outliers to a Gaussian mixture. A special case of the RIMLE is MLE for multivariate finite Gaussian mixture models. In this paper we treat existence, consistency, and breakdown theory for the RIMLE comprehensively. RIMLE's existence is proved under non-smooth covariance matrix constraints. It is shown that these can be implemented via a computationally feasible Expectation-Conditional Maximization algorithm.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5199–5237},
numpages = {39},
keywords = {mixture models, ECM-algorithm, robustness, improper density, model-based clustering, maximum likelihood}
}

@article{10.5555/3122009.3208022,
author = {Zhang, Huishuai and Zhou, Yi and Liang, Yingbin and Chi, Yuejie},
title = {A Nonconvex Approach for Phase Retrieval: Reshaped Wirtinger Flow and Incremental Algorithms},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We study the problem of solving a quadratic system of equations, i.e., recovering a vector signal x ε Rn from its magnitude measurements yi = |〈ai, x〉|, i = 1, ..., m. We develop a gradient descent algorithm (referred to as RWF for reshaped Wirtinger flow) by minimizing the quadratic loss of the magnitude measurements. Comparing with Wirtinger flow (WF) (Cand\`{e}s et al., 2015), the loss function of RWF is nonconvex and nonsmooth, but better resembles the least-squares loss when the phase information is also available. We show that for random Gaussian measurements, RWF enjoys linear convergence to the true signal as long as the number of measurements is O(n). This improves the sample complexity of WF (O(n log n)), and achieves the same sample complexity as truncated Wirtinger flow (TWF) (Chen and Cand\`{e}s, 2015), but without any sophisticated truncation in the gradient loop. Furthermore, RWF costs less computationally than WF, and runs faster numerically than both WF and TWF. We further develop an incremental (stochastic) version of RWF (IRWF) and connect it with the randomized Kaczmarz method for phase retrieval. We demonstrate that IRWF outperforms existing incremental as well as batch algorithms with experiments.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5164–5198},
numpages = {35},
keywords = {stochastic algorithms, regularity condition, phase retrieval, nonconvex optimization, gradient descent}
}

@article{10.5555/3122009.3208021,
author = {Darnell, Gregory and Georgiev, Stoyan and Mukherjee, Sayan and Engelhardt, Barbara E.},
title = {Adaptive Randomized Dimension Reduction on Massive Data},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {The scalability of statistical estimators is of increasing importance in modern applications. One approach to implementing scalable algorithms is to compress data into a low dimensional latent space using dimension reduction methods. In this paper, we develop an approach for dimension reduction that exploits the assumption of low rank structure in high dimensional data to gain both computational and statistical advantages. We adapt recent randomized low-rank approximation algorithms to provide an efficient solution to principal component analysis (PCA), and we use this efficient solver to improve estimation in large-scale linear mixed models (LMM) for association mapping in statistical genomics. A key observation in this paper is that randomization serves a dual role, improving both computational and statistical performance by implicitly regularizing the covariance matrix estimate of the random effect in an LMM. These statistical and computational advantages are highlighted in our experiments on simulated data and large-scale genomic studies.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5134–5163},
numpages = {30},
keywords = {randomized algorithms, genomics, low-rank, Krylov subspace methods, dimension reduction, supervised, linear mixed models, random projections, generalized eigendecompositon}
}

@article{10.5555/3122009.3208020,
author = {Andersen, Michael Riis and Vehtari, Aki and Winther, Ole and Hansen, Lars Kai},
title = {Bayesian Inference for Spatio-Temporal Spike-and-Slab Priors},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {In this work, we address the problem of solving a series of underdetermined linear inverse problemblems subject to a sparsity constraint. We generalize the spike-and-slab prior distribution to encode a priori correlation of the support of the solution in both space and time by imposing a transformed Gaussian process on the spike-and-slab probabilities. An expectation propagation (EP) algorithm for posterior inference under the proposed model is derived. For large scale problems, the standard EP algorithm can be prohibitively slow. We therefore introduce three different approximation schemes to reduce the computational complexity. Finally, we demonstrate the proposed model using numerical experiments based on both synthetic and real data sets.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5076–5133},
numpages = {58},
keywords = {bayesian inference, spike-and-slab priors, linear inverse problems, sparsity-promoting priors, expectation propagation}
}

@article{10.5555/3122009.3208019,
author = {Serra, Paulo and Mandjes, Michel},
title = {Dimension Estimation Using Random Connection Models},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Information about intrinsic dimension is crucial to perform dimensionality reduction, compress information, design efficient algorithms, and do statistical adaptation. In this paper we propose an estimator for the intrinsic dimension of a data set. The estimator is based on binary neighbourhood information about the observations in the form of two adjacency matrices, and does not require any explicit distance information. The underlying graph is modelled according to a subset of a specific random connection model, sometimes referred to as the Poisson blob model. Computationally the estimator scales like n log n, and we specify its asymptotic distribution and rate of convergence. A simulation study on both real and simulated data shows that our approach compares favourably with some competing methods from the literature, including approaches that rely on distance information.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {5041–5075},
numpages = {35},
keywords = {intrinsic dimension, dimensionality reduction, random graph, adaptation, random connection model}
}

@article{10.5555/3122009.3208018,
author = {Bigot, J\'{e}r\'{e}mie and Deledalle, Charles and F\'{e}ral, Delphine},
title = {Generalized SURE for Optimal Shrinkage of Singular Values in Low-Rank Matrix Denoising},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We consider the problem of estimating a low-rank signal matrix from noisy measurements under the assumption that the distribution of the data matrix belongs to an exponential family. In this setting, we derive generalized Stein's unbiased risk estimation (SURE) formulas that hold for any spectral estimators which shrink or threshold the singular values of the data matrix. This leads to new data-driven spectral estimators, whose optimality is discussed using tools from random matrix theory and through numerical experiments. Under the spiked population model and in the asymptotic setting where the dimensions of the data matrix are let going to infinity, some theoretical properties of our approach are compared to recent results on asymptotically optimal shrinking rules for Gaussian noise. It also leads to new procedures for singular values shrinkage in finite-dimensional matrix denoising for Gamma-distributed and Poisson-distributed measurements.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4991–5040},
numpages = {50},
keywords = {singular value decomposition, optimal shrinkage rule, degrees of freedom, Gaussian spiked population model, spectral estimator, random matrix theory, exponential family, Matrix denoising, low-rank model, Stein's unbiased risk estimate}
}

@article{10.5555/3122009.3208017,
author = {Wirth, Christian and Akrour, Riad and Neumann, Gerhard and F\"{u}rnkranz, Johannes},
title = {A Survey of Preference-Based Reinforcement Learning Methods},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Reinforcement learning (RL) techniques optimize the accumulated long-term reward of a suitably chosen reward function. However, designing such a reward function often requires a lot of task-specific prior knowledge. The designer needs to consider different objectives that do not only influence the learned behavior but also the learning progress. To alleviate these issues, preference-based reinforcement learning algorithms (PbRL) have been proposed that can directly learn from an expert's preferences instead of a hand-designed numeric reward. PbRL has gained traction in recent years due to its ability to resolve the reward shaping problem, its ability to learn from non numeric rewards and the possibility to reduce the dependence on expert knowledge. We provide a unified framework for PbRL that describes the task formally and points out the different design principles that affect the evaluation task for the human as well as the computational complexity. The design principles include the type of feedback that is assumed, the representation that is learned to capture the preferences, the optimization problem that has to be solved as well as how the exploration/exploitation problem is tackled. Furthermore, we point out shortcomings of current algorithms, propose open research questions and briefly survey practical tasks that have been solved using PbRL.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4945–4990},
numpages = {46},
keywords = {preference-based reinforcement learning, qualitative feedback, reinforcement learning, temporal difference learning, policy search, Markov decision process, preference learning}
}

@article{10.5555/3122009.3208016,
author = {Sun, Will Wei and Li, Lexin},
title = {STORE: Sparse Tensor Response Regression and Neuroimaging Analysis},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Motivated by applications in neuroimaging analysis, we propose a new regression model, Sparse TensOr REsponse regression (STORE), with a tensor response and a vector predictor. STORE embeds two key sparse structures: element-wise sparsity and low-rankness. It can handle both a non-symmetric and a symmetric tensor response, and thus is applicable to both structural and functional neuroimaging data. We formulate the parameter estimation as a non-convex optimization problem, and develop an efficient alternating updating algorithm. We establish a non-asymptotic estimation error bound for the actual estimator obtained from the proposed algorithm. This error bound reveals an interesting interaction between the computational efficiency and the statistical rate of convergence. When the distribution of the error tensor is Gaussian, we further obtain a fast estimation error rate which allows the tensor dimension to grow exponentially with the sample size. We illustrate the efficacy of our model through intensive simulations and an analysis of the Autism spectrum disorder neuroimaging data.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4908–4944},
numpages = {37},
keywords = {magnetic resonance imaging, tensor decomposition, non-asymptotic error bound, functional connectivity analysis, high-dimensional statistical learning}
}

@article{10.5555/3122009.3208015,
author = {Mandt, Stephan and Hoffman, Matthew D. and Blei, David M.},
title = {Stochastic Gradient Descent as Approximate Bayesian Inference},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Stochastic Gradient Descent with a constant learning rate (constant SGD) simulates a Markov chain with a stationary distribution. With this perspective, we derive several new results. (1) We show that constant SGD can be used as an approximate Bayesian posterior inference algorithm. Specifically, we show how to adjust the tuning parameters of constant SGD to best match the stationary distribution to a posterior, minimizing the Kullback-Leibler divergence between these two distributions. (2) We demonstrate that constant SGD gives rise to a new variational EM algorithm that optimizes hyperparameters in complex probabilistic models. (3) We also show how to tune SGD with momentum for approximate sampling. (4)We analyze stochastic-gradient MCMC algorithms. For Stochastic-Gradient Langevin Dynamics and Stochastic-Gradient Fisher Scoring, we quantify the approximation errors due to finite learning rates. Finally (5), we use the stochastic process perspective to give a short proof of why Polyak averaging is optimal. Based on this idea, we propose a scalable approximate MCMC algorithm, the Averaged Stochastic Gradient Sampler.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4873–4907},
numpages = {35},
keywords = {approximate Bayesian inference, stochastic optimization, stochastic differential equations, variational inference, stochastic gradient MCMC}
}

@article{10.5555/3122009.3208014,
author = {Schiratti, Jean-Baptiste and Allassonni\`{e}re, St\'{e}phanie and Colliot, Olivier and Durrleman, Stanley},
title = {A Bayesian Mixed-Effects Model to Learn Trajectories of Changes from Repeated Manifold-Valued Observations},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We propose a generic Bayesian mixed-effects model to estimate the temporal progression of a biological phenomenon from observations obtained at multiple time points for a group of individuals. The progression is modeled by continuous trajectories in the space of measurements. Individual trajectories of progression result from spatiotemporal transformations of an average trajectory. These transformations allow for the quantification of changes in direction and pace at which the trajectories are followed. The framework of Riemannian geometry allows the model to be used with any kind of measurements with smooth constraints. A stochastic version of the Expectation-Maximization algorithm is used to produce maximum a posteriori estimates of the parameters. We evaluated our method using a series of neuropsychological test scores from patients with mild cognitive impairments, later diagnosed with Alzheimer's disease, and simulated evolutions of symmetric positive definite matrices. The data-driven model of impairment of cognitive functions illustrated the variability in the ordering and timing of the decline of these functions in the population. We showed that the estimated spatiotemporal transformations effectively put into correspondence significant events in the progression of individuals.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4840–4872},
numpages = {33},
keywords = {spatiotemporal analysis, stochastic expectation-maximization algorithm, longitudinal model, Riemannian geometry}
}

@article{10.5555/3122009.3208013,
author = {Kumar, K. S. Sesh and Bach, Francis},
title = {Active-Set Methods for Submodular Minimization Problems},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We consider the submodular function minimization (SFM) and the quadratic minimization problems regularized by the Lov\'{a}sz extension of the submodular function. These optimization problems are intimately related; for example, min-cut problems and total variation denoising problems, where the cut function is submodular and its Lov\'{a}sz extension is given by the associated total variation. When a quadratic loss is regularized by the total variation of a cut function, it thus becomes a total variation denoising problem and we use the same terminology in this paper for "general" submodular functions. We propose a new active-set algorithm for total variation denoising with the assumption of an oracle that solves the corresponding SFM problem. This can be seen as local descent algorithm over ordered partitions with explicit convergence guarantees. It is more flexible than the existing algorithms with the ability for warm-restarts using the solution of a closely related problem. Further, we also consider the case when a submodular function can be decomposed into the sum of two submodular functions F1 and F2 and assume SFM oracles for these two functions. We propose a new active-set algorithm for total variation denoising (and hence SFM by thresholding the solution at zero). This algorithm also performs local descent over ordered partitions and its ability to warm start considerably improves the performance of the algorithm. In the experiments, we compare the performance of the proposed algorithms with state-of-the-art algorithms, showing that it reduces the calls to SFM oracles.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4809–4839},
numpages = {31},
keywords = {convex optimization, cut functions, discrete optimization, submodular function minimization, total variation denoising}
}

@article{10.5555/3122009.3208012,
author = {Ma, Yuting and Zheng, Tian},
title = {Stabilized Sparse Online Learning for Sparse Data},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Stochastic gradient descent (SGD) is commonly used for optimization in large-scale machine learning problems. Langford et al. (2009) introduce a sparse online learning method to induce sparsity via truncated gradient. With high-dimensional sparse data, however, this method suffers from slow convergence and high variance due to heterogeneity in feature sparsity. To mitigate this issue, we introduce a stabilized truncated stochastic gradient descent algorithm. We employ a soft-thresholding scheme on the weight vector where the imposed shrinkage is adaptive to the amount of information available in each feature. The variability in the resulted sparse weight vector is further controlled by stability selection integrated with the informative truncation. To facilitate better convergence, we adopt an annealing strategy on the truncation rate, which leads to a balanced trade-off between exploration and exploitation in learning a sparse weight vector. Numerical experiments show that our algorithm compares favorably with the original truncated gradient SGD in terms of prediction accuracy, achieving both better sparsity and stability.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4773–4808},
numpages = {36},
keywords = {adaptive shrinkage, sparse online learning, truncated gradient, sparse features, stability selection}
}

@article{10.5555/3122009.3208011,
author = {Trouillon, Th\'{e}o and Dance, Christopher R. and Gaussier, \'{E}ric and Welbl, Johannes and Riedel, Sebastian and Bouchard, Guillaume},
title = {Knowledge Graph Completion via Complex Tensor Factorization},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {In statistical relational learning, knowledge graph completion deals with automatically understanding the structure of large knowledge graphs--labeled directed graphs-- and predicting missing relationships--labeled edges. State-of-the-art embedding models propose different trade-offs between modeling expressiveness, and time and space complexity. We reconcile both expressiveness and complexity through the use of complex-valued embeddings and explore the link between such complex-valued embeddings and unitary diagonalization. We corroborate our approach theoretically and show that all real square matrices--thus all possible relation/adjacency matrices--are the real part of some unitarily diagonalizable matrix. This results opens the door to a lot of other applications of square matrices factorization. Our approach based on complex embeddings is arguably simple, as it only involves a Hermitian dot product, the complex counterpart of the standard dot product between real vectors, whereas other methods resort to more and more complicated composition functions to increase their expressiveness. The proposed complex embeddings are scalable to large data sets as it remains linear in both space and time, while consistently outperforming alternative approaches on standard link prediction benchmarks.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4735–4772},
numpages = {38},
keywords = {statistical relational learning, complex embeddings, tensor factorization, knowledge graph, matrix completion}
}

@article{10.5555/3122009.3208010,
author = {Hamm, Jihun},
title = {Minimax Filter: Learning to Preserve Privacy from Inference Attacks},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Preserving privacy of continuous and/or high-dimensional data such as images, videos and audios, can be challenging with syntactic anonymization methods which are designed for discrete attributes. Differentially privacy, which uses a more rigorous definition of privacy loss, has shown more success in sanitizing continuous data. However, both syntactic and differential privacy are susceptible to inference attacks, i.e., an adversary can accurately infer sensitive attributes from sanitized data. The paper proposes a novel filter-based mechanism which preserves privacy of continuous and high-dimensional attributes against inference attacks. Finding the optimal utility-privacy tradeoff is formulated as a min-diff-max optimization problem. The paper provides an ERM-like analysis of the generalization error and also a practical algorithm to perform minimax optimization. In addition, the paper proposes a noisy minimax filter which combines minimax filter and differentially-private mechanism. Advantages of the method over purely noisy mechanisms is explained and demonstrated with examples. Experiments with several real-world tasks including facial expression classification, speech emotion classification, and activity classification from motion, show that the minimax filter can simultaneously achieve similar or higher target task accuracy and lower inference accuracy, often significantly lower than previous methods.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4704–4734},
numpages = {31},
keywords = {empirical risk minimization, differential privacy, minimax optimization, k-anonymity, inference attack}
}

@article{10.5555/3122009.3208009,
author = {Ndiaye, Eugene and Fercoq, Olivier and Gramfort, Alexandre and Salmon, Joseph},
title = {Gap Safe Screening Rules for Sparsity Enforcing Penalties},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {In high dimensional regression settings, sparsity enforcing penalties have proved useful to regularize the data-fitting term. A recently introduced technique called screening rules propose to ignore some variables in the optimization leveraging the expected sparsity of the solutions and consequently leading to faster solvers. When the procedure is guaranteed not to discard variables wrongly the rules are said to be safe. In this work, we propose a unifying framework for generalized linear models regularized with standard sparsity enforcing penalties such as l1 or l1/l2 norms. Our technique allows to discard safely more variables than previously considered safe rules, particularly for low regularization parameters. Our proposed Gap Safe rules (so called because they rely on duality gap computation) can cope with any iterative solver but are particularly well suited to (block) coordinate descent methods. Applied to many standard learning tasks, Lasso, Sparse-Group Lasso, multitask Lasso, binary and multinomial logistic regression, etc., we report significant speedups compared to previously proposed safe rules on all tested data sets.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4671–4703},
numpages = {33},
keywords = {sparse logistic regression, sparse-group Lasso, Lasso, convex optimization, multi-task Lasso, screening rules}
}

@article{10.5555/3122009.3208008,
author = {Perrone, Valerio and Jenkins, Paul A. and Span\`{o}, Dario and Teh, Yee Whye},
title = {Poisson Random Fields for Dynamic Feature Models},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We present the Wright-Fisher Indian buffet process (WF-IBP), a probabilistic model for time-dependent data assumed to have been generated by an unknown number of latent features. This model is suitable as a prior in Bayesian nonparametric feature allocation models in which the features underlying the observed data exhibit a dependency structure over time. More specifically, we establish a new framework for generating dependent Indian buffet processes, where the Poisson random field model from population genetics is used as a way of constructing dependent beta processes. Inference in the model is complex, and we describe a sophisticated Markov Chain Monte Carlo algorithm for exact posterior simulation. We apply our construction to develop a nonparametric focused topic model for collections of time-stamped text documents and test it on the full corpus of NIPS papers published from 1987 to 2015.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4626–4670},
numpages = {45},
keywords = {indian buffet process, Poisson random field, topic model, Markov chain Monte Carlo, Bayesian nonparametrics}
}

@article{10.5555/3122009.3208007,
author = {Dupuy, Christophe and Bach, Francis},
title = {Online but Accurate Inference for Latent Variable Models with Local Gibbs Sampling},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We study parameter inference in large-scale latent variable models. We first propose a unified treatment of online inference for latent variable models from a non-canonical exponential family, and draw explicit links between several previously proposed frequentist or Bayesian methods. We then propose a novel inference method for the frequentist estimation of parameters, that adapts MCMC methods to online inference of latent variable models with the proper use of local Gibbs sampling. Then, for latent Dirichlet allocation, we provide an extensive set of experiments and comparisons with existing work, where our new approach outperforms all previously proposed methods. In particular, using Gibbs sampling for latent variable inference is superior to variational inference in terms of test log-likelihoods. Moreover, Bayesian inference through variational methods perform poorly, sometimes leading to worse fits with latent variables of higher dimensionality.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4581–4625},
numpages = {45},
keywords = {topic modelling, Gibbs sampling, latent variables models, online learning, latent Dirichlet allocation}
}

@article{10.5555/3122009.3208006,
author = {Yang, Fanny and Balakrishnan, Sivaraman and Wainwright, Martin J.},
title = {Statistical and Computational Guarantees for the Baum-Welch Algorithm},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {The Hidden Markov Model (HMM) is one of the mainstays of statistical modeling of discrete time series, with applications including speech recognition, computational biology, computer vision and econometrics. Estimating an HMM from its observation process is often addressed via the Baum-Welch algorithm, which is known to be susceptible to local optima. In this paper, we first give a general characterization of the basin of attraction associated with any global optimum of the population likelihood. By exploiting this characterization, we provide non-asymptotic finite sample guarantees on the Baum-Welch updates and show geometric convergence to a small ball of radius on the order of the minimax rate around a global optimum. As a concrete example, we prove a linear rate of convergence for a hidden Markov mixture of two isotropic Gaussians given a suitable mean separation and an initialization within a ball of large radius around (one of) the true parameters. To our knowledge, these are the first rigorous local convergence guarantees to global optima for the Baum-Welch algorithm in a setting where the likelihood function is nonconvex. We complement our theoretical results with thorough numerical simulations studying the convergence of the Baum-Welch algorithm and illustrating the accuracy of our predictions.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4528–4580},
numpages = {53},
keywords = {graphical models, Baum-Welch algorithm, non-convex optimization, EM algorithm, Hidden Markov models}
}

@article{10.5555/3122009.3208005,
author = {Minsker, Stanislav and Srivastava, Sanvesh and Lin, Lizhen and Dunson, David B.},
title = {Robust and Scalable Bayes via a Median of Subset Posterior Measures},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We propose a novel approach to Bayesian analysis that is provably robust to outliers in the data and often has computational advantages over standard methods. Our technique is based on splitting the data into non-overlapping subgroups, evaluating the posterior distribution given each independent subgroup, and then combining the resulting measures. The main novelty of our approach is the proposed aggregation step, which is based on the evaluation of a median in the space of probability measures equipped with a suitable collection of distances that can be quickly and efficiently evaluated in practice. We present both theoretical and numerical evidence illustrating the improvements achieved by our method.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4488–4527},
numpages = {40},
keywords = {big data, distributed computing, Wasserstein distance, parallel MCMC, geometric median}
}

@article{10.5555/3122009.3176867,
author = {Singer, Marco and Krivobokova, Tatyana and Munk, Axel},
title = {Kernel Partial Least Squares for Stationary Data},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We consider the kernel partial least squares algorithm for non-parametric regression with stationary dependent data. Probabilistic convergence rates of the kernel partial least squares estimator to the true regression function are established under a source and an effective dimensionality condition. It is shown both theoretically and in simulations that long range dependence results in slower convergence rates. A protein dynamics example shows high predictive power of kernel partial least squares.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4447–4487},
numpages = {41},
keywords = {protein dynamics, nonparametric regression, source condition, long range dependence, effective dimensionality}
}

@article{10.5555/3122009.3176866,
author = {Lee, Jason D. and Lin, Qihang and Ma, Tengyu and Yang, Tianbao},
title = {Distributed Stochastic Variance Reduced Gradient Methods by Sampling Extra Data with Replacement},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We study the round complexity of minimizing the average of convex functions under a new setting of distributed optimization where each machine can receive two subsets of functions. The first subset is from a random partition and the second subset is randomly sampled with replacement. Under this setting, we define a broad class of distributed algorithms whose local computation can utilize both subsets and design a distributed stochastic variance reduced gradient method belonging to in this class. When the condition number of the problem is small, our method achieves the optimal parallel runtime, amount of communication and rounds of communication among all distributed first-order methods up to constant factors. When the condition number is relatively large, a lower bound is provided for the number of rounds of communication needed by any algorithm in this class. Then, we present an accelerated version of our method whose the rounds of communication matches the lower bound up to logarithmic terms, which establishes that this accelerated algorithm has the lowest round complexity among all algorithms in our class under this new setting.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4404–4446},
numpages = {43},
keywords = {stochastic variance reduced gradient, distributed optimization, first-order method, communication complexity, lower bound}
}

@article{10.5555/3122009.3176865,
author = {Guillame-Bert, Mathieu and Dubrawski, Artur},
title = {Classification of Time Sequences Using Graphs of Temporal Constraints},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We introduce two algorithms that learn to classify Symbolic and Scalar Time Sequences (SSTS); an extension of multivariate time series. An SSTS is a set of events and a set of scalars. An event is defined by a symbol and a time-stamp. A scalar is defined by a symbol and a function mapping a number for each possible time stamp of the data. The proposed algorithms rely on temporal patterns called Graph of Temporal Constraints (GTC). A GTC is a directed graph in which vertices express occurrences of specific events, and edges express temporal constraints between occurrences of pairs of events. Additionally, each vertex of a GTC can be augmented with numeric constraints on scalar values. We allow GTCs to be cyclic and/or disconnected. The first of the introduced algorithms extracts sets of co-dependent GTCs to be used in a voting mechanism. The second algorithm builds decision forest like representations where each node is a GTC. In both algorithms, extraction of GTCs and model building are interleaved. Both algorithms are closely related to each other and they exhibit complementary properties including complexity, performance, and interpretability. The main novelties of this work reside in direct building of the model and efficient learning of GTC structures. We explain the proposed algorithms and evaluate their performance against a diverse collection of 59 benchmark data sets. In these experiments, our algorithms come across as highly competitive and in most cases closely match or outperform state-of-the-art alternatives in terms of the computational speed while dominating in terms of the accuracy of classification of time sequences.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4370–4403},
numpages = {34},
keywords = {temporal data, classification, decision forests, graphical constraint models, sequential data, supervised learning, symbolic and scalar time sequences}
}

@article{10.5555/3122009.3176864,
author = {Silva, Ricardo and Shimizu, Shohei},
title = {Learning Instrumental Variables with Structural and Non-Gaussianity Assumptions},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Learning a causal effect from observational data requires strong assumptions. One possible method is to use instrumental variables, which are typically justified by background knowledge. It is possible, under further assumptions, to discover whether a variable is structurally instrumental to a target causal effect X → Y. However, the few existing approaches are lacking on how general these assumptions can be, and how to express possible equivalence classes of solutions. We present instrumental variable discovery methods that systematically characterize which set of causal effects can and cannot be discovered under local graphical criteria that define instrumental variables, without reconstructing full causal graphs. We also introduce the first methods to exploit non-Gaussianity assumptions, highlighting identifiability problems and solutions. Due to the difficulty of estimating such models from finite data, we investigate how to strengthen assumptions in order to make the statistical problem more manageable.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4321–4369},
numpages = {49},
keywords = {causality, instrumental variables, causal discovery}
}

@article{10.5555/3122009.3176863,
author = {Mahsereci, Maren and Hennig, Philipp},
title = {Probabilistic Line Searches for Stochastic Optimization},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {In deterministic optimization, line searches are a standard tool ensuring stability and efficiency. Where only stochastic gradients are available, no direct equivalent has so far been formulated, because uncertain gradients do not allow for a strict sequence of decisions collapsing the search space. We construct a probabilistic line search by combining the structure of existing deterministic methods with notions from Bayesian optimization. Our method retains a Gaussian process surrogate of the univariate optimization objective, and uses a probabilistic belief over the Wolfe conditions to monitor the descent. The algorithm has very low computational cost, and no user-controlled parameters. Experiments show that it effectively removes the need to define a learning rate for stochastic gradient descent.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4262–4320},
numpages = {59},
keywords = {line searches, Gaussian processes, Bayesian optimization, learning rates, stochastic optimization}
}

@article{10.5555/3122009.3176862,
author = {Guo, Zheng-Chu and Shi, Lei and Wu, Qiang},
title = {Learning Theory of Distributed Regression with Bias Corrected Regularization Kernel Network},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Distributed learning is an effective way to analyze big data. In distributed regression, a typical approach is to divide the big data into multiple blocks, apply a base regression algorithm on each of them, and then simply average the output functions learnt from these blocks. Since the average process will decrease the variance, not the bias, bias correction is expected to improve the learning performance if the base regression algorithm is a biased one. Regularization kernel network is an effective and widely used method for nonlinear regression analysis. In this paper we will investigate a bias corrected version of regularization kernel network. We derive the error bounds when it is applied to a single data set and when it is applied as a base algorithm in distributed regression. We show that, under certain appropriate conditions, the optimal learning rates can be reached in both situations.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4237–4261},
numpages = {25},
keywords = {regularization, kernel method, error bound, distributed learning, bias correction}
}

@article{10.5555/3122009.3176861,
author = {Lin, Jiahe and Michailidis, George},
title = {Regularized Estimation and Testing for High-Dimensional Multi-Block Vector-Autoregressive Models},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Dynamical systems comprising of multiple components that can be partitioned into distinct blocks originate in many scientific areas. A pertinent example is the interactions between financial assets and selected macroeconomic indicators, which has been studied at aggregate level--e.g. a stock index and an employment index--extensively in the macroeconomics literature. A key shortcoming of this approach is that it ignores potential influences from other related components (e.g. Gross Domestic Product) that may impact the system's dynamics and structure and thus produces incorrect results. To mitigate this issue, we consider a multi-block linear dynamical system with Granger-causal ordering between blocks, wherein the blocks' temporal dynamics are described by vector autoregressive processes and are influenced by blocks higher in the system hierarchy. We derive the maximum likelihood estimator for the posited model for Gaussian data in the high-dimensional setting based on appropriate regularization schemes for the parameters of the block components. To optimize the underlying non-convex likelihood function, we develop an iterative algorithm with convergence guarantees. We establish theoretical properties of the maximum likelihood estimates, leveraging the decomposability of the regularizers and a careful analysis of the iterates. Finally, we develop testing procedures for the null hypothesis of whether a block "Granger-causes" another block of variables. The performance of the model and the testing procedures are evaluated on synthetic data, and illustrated on a data set involving log-returns of the US S&P100 component stocks and key macroeconomic variables for the 2001-16 period.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4188–4236},
numpages = {49},
keywords = {block-coordinate descent, global testing, consistency, vector-autoregression, stability}
}

@article{10.5555/3122009.3176860,
author = {Agarwal, Naman and Bullins, Brian and Hazan, Elad},
title = {Second-Order Stochastic Optimization for Machine Learning in Linear Time},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {First-order stochastic methods are the state-of-the-art in large-scale machine learning optimization owing to efficient per-iteration complexity. Second-order methods, while able to provide faster convergence, have been much less explored due to the high cost of computing the second-order information. In this paper we develop second-order stochastic methods for optimization problems in machine learning that match the per-iteration cost of gradient based methods, and in certain settings improve upon the overall running time over popular first-order methods. Furthermore, our algorithm has the desirable property of being implementable in time linear in the sparsity of the input data.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4148–4187},
numpages = {40},
keywords = {regression, convex optimization, second-order optimization}
}

@article{10.5555/3122009.3176859,
author = {Zheng, Shun and Wang, Jialei and Xia, Fen and Xu, Wei and Zhang, Tong},
title = {A General Distributed Dual Coordinate Optimization Framework for Regularized Loss Minimization},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {In modern large-scale machine learning applications, the training data are often partitioned and stored on multiple machines. It is customary to employ the "data parallelism" approach, where the aggregated training loss is minimized without moving data across machines. In this paper, we introduce a novel distributed dual formulation for regularized loss minimization problems that can directly handle data parallelism in the distributed setting. This formulation allows us to systematically derive dual coordinate optimization procedures, which we refer to as Distributed Alternating Dual Maximization (DADM). The framework extends earlier studies described in (Boyd et al., 2011; Ma et al., 2017; Jaggi et al., 2014; Yang, 2013) and has rigorous theoretical analyses. Moreover, with the help of the new formulation, we develop the accelerated version of DADM (Acc-DADM) by generalizing the acceleration technique from (Shalev-Shwartz and Zhang, 2014) to the distributed setting. We also provide theoretical results for the proposed accelerated version, and the new result improves previous ones (Yang, 2013; Ma et al., 2017) whose iteration complexities grow linearly on the condition number. Our empirical studies validate our theory and show that our accelerated approach significantly improves the previous state-of-the-art distributed dual coordinate optimization algorithms.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4096–4117},
numpages = {22},
keywords = {regularized loss minimization, distributed optimization, computational complexity, acceleration, stochastic dual coordinate ascent}
}

@article{10.5555/3122009.3176858,
author = {Fenn, Shannon and Moscato, Pablo},
title = {Target Curricula via Selection of Minimum Feature Sets: A Case Study in Boolean Networks},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We consider the effect of introducing a curriculum of targets when training Boolean models on supervised Multi Label Classification (MLC) problems. In particular, we consider how to order targets in the absence of prior knowledge, and how such a curriculum may be enforced when using meta-heuristics to train discrete non-linear models.We show that hierarchical dependencies between targets can be exploited by enforcing an appropriate curriculum using hierarchical loss functions. On several multi-output circuit-inference problems with known target difficulties, Feedforward Boolean Networks (FBNs) trained with such a loss function achieve significantly lower out-of-sample error, up to 10% in some cases. This improvement increases as the loss places more emphasis on target order and is strongly correlated with an easy-to-hard curricula. We also demonstrate the same improvements on three real-world models and two Gene Regulatory Network (GRN) inference problems.We posit a simple a-priori method for identifying an appropriate target order and estimating the strength of target relationships in Boolean MLCs. These methods use intrinsic dimension as a proxy for target difficulty, which is estimated using optimal solutions to a combinatorial optimisation problem known as the Minimum-Feature-Set (minFS) problem. We also demonstrate that the same generalisation gains can be achieved without providing any knowledge of target difficulty.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4070–4095},
numpages = {26},
keywords = {k-feature Set, multi-label classification, target curriculum, Boolean betworks}
}

@article{10.5555/3122009.3176857,
author = {Lauly, Stanislas and Zheng, Yin and Allauzen, Alexandre and Larochelle, Hugo},
title = {Document Neural Autoregressive Distribution Estimation},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We present an approach based on feed-forward neural networks for learning the distribution over textual documents. This approach is inspired by the Neural Autoregressive Distribution Estimator (NADE) model which has been shown to be a good estimator of the distribution over discrete-valued high-dimensional vectors. In this paper, we present how NADE can successfully be adapted to textual data, retaining the property that sampling or computing the probability of an observation can be done exactly and efficiently. The approach can also be used to learn deep representations of documents that are competitive to those learned by alternative topic modeling approaches. Finally, we describe how the approach can be combined with a regular neural network N-gram model and substantially improve its performance, by making its learned representation sensitive to the larger, document-level context.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4046–4069},
numpages = {24},
keywords = {autoregressive models, language models, deep learning, neural networks, topic models}
}

@article{10.5555/3122009.3176856,
author = {Narayanan, Hariharan and Rakhlin, Alexander},
title = {Efficient Sampling from Time-Varying Log-Concave Distributions},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We propose a computationally efficient random walk on a convex body which rapidly mixes with respect to a fixed log-concave distribution and closely tracks a time-varying log-concave distribution. We develop general theoretical guarantees on the required number of steps; this number can be calculated on the fly according to the distance from and the shape of the next distribution. We then illustrate the technique on several examples. Within the context of exponential families, the proposed method produces samples from a posterior distribution which is updated as data arrive in a streaming fashion. The sampling technique can be used to track time-varying truncated distributions, as well as to obtain samples from a changing mixture model, fitted in a streaming fashion to data. In the setting of linear optimization, the proposed method has oracle complexity with best known dependence on the dimension for certain geometries. In the context of online learning and repeated games, the algorithm is an efficient method for implementing no-regret mixture forecasting strategies. Remarkably, in some of these examples, only one step of the random walk is needed to track the next distribution.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {4017–4045},
numpages = {29}
}

@article{10.5555/3122009.3176855,
author = {Le, Trung and Nguyen, Tu Dinh and Nguyen, Vu and Phung, Dinh},
title = {Approximation Vector Machines for Large-Scale Online Learning},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {One of the most challenging problems in kernel online learning is to bound the model size

license: Unlicense

repository: goyalkaraniit/acm-cr

repo_name: goyalkaraniit/acm-cr