text:
and to promote model sparsity. Sparse models not only improve computation and memory usage, but also enhance the generalization capacity - a principle that concurs with the law of parsimony. However, inappropriate sparsity modeling may also significantly degrade the performance. In this paper, we propose Approximation Vector Machine (AVM), a model that can simultaneously encourage sparsity and safeguard its risk in compromising the performance. In an online setting context, when an incoming instance arrives, we approximate this instance by one of its neighbors whose distance to it is less than a predefined threshold. Our key intuition is that since the newly seen instance is expressed by its nearby neighbor the optimal performance can be analytically formulated and maintained. We develop theoretical foundations to support this intuition and further establish an analysis for the common loss functions including Hinge, smooth Hinge, and Logistic (i.e., for the classification task) and l1, l2, and ε-insensitive (i.e., for the regression task) to characterize the gap between the approximation and optimal solutions. This gap crucially depends on two key factors including the frequency of approximation (i.e., how frequent the approximation operation takes place) and the predefined threshold. We conducted extensive experiments for classification and regression tasks in batch and online modes using several benchmark datasets. The quantitative results show that our proposed AVM obtained comparable predictive performances with current state-of-the-art methods while simultaneously achieving significant computational speed-up due to the ability of the proposed AVM in maintaining the model size.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3962–4016},
numpages = {55},
keywords = {online learning, stochastic gradient descent, convergence analysis, large-scale machine learning, kernel, sparsity, big data, core set}
}

@article{10.5555/3122009.3176854,
author = {Lin, Lin and Li, Jia},
title = {Clustering with Hidden Markov Model on Variable Blocks},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Large-scale data containing multiple important rare clusters, even at moderately high dimensions, pose challenges for existing clustering methods. To address this issue, we propose a new mixture model called Hidden Markov Model on Variable Blocks (HMM-VB) and a new mode search algorithm called Modal Baum-Welch (MBW) for mode-association clustering. HMM-VB leverages prior information about chain-like dependence among groups of variables to achieve the effect of dimension reduction. In case such a dependence structure is unknown or assumed merely for the sake of parsimonious modeling, we develop a recursive search algorithm based on BIC to optimize the formation of ordered variable blocks. The MBW algorithm ensures the feasibility of clustering via mode association, achieving linear complexity in terms of the number of variable blocks despite the exponentially growing number of possible state sequences in HMM-VB. In addition, we provide theoretical investigations about the identifiability of HMM-VB as well as the consistency of our approach to search for the block partition of variables in a special case. Experiments on simulated and real data show that our proposed method outperforms other widely used methods.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3913–3961},
numpages = {49},
keywords = {hidden Markov model, Gaussian mixture model, modal Baum-Welch algorithm, modal clustering}
}

@article{10.5555/3122009.3176853,
author = {Bach, Stephen H. and Broecheler, Matthias and Huang, Bert and Getoor, Lise},
title = {Hinge-Loss Markov Random Fields and Probabilistic Soft Logic},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {A fundamental challenge in developing high-impact machine learning technologies is balancing the need to model rich, structured domains with the ability to scale to big data. Many important problem areas are both richly structured and large scale, from social and biological networks, to knowledge graphs and the Web, to images, video, and natural language. In this paper, we introduce two new formalisms for modeling structured data, and show that they can both capture rich structure and scale to big data. The first, hingeloss Markov random fields (HL-MRFs), is a new kind of probabilistic graphical model that generalizes different approaches to convex inference. We unite three approaches from the randomized algorithms, probabilistic graphical models, and fuzzy logic communities, showing that all three lead to the same inference objective. We then define HL-MRFs by generalizing this unified objective. The second new formalism, probabilistic soft logic (PSL), is a probabilistic programming language that makes HL-MRFs easy to define using a syntax based on first-order logic. We introduce an algorithm for inferring most-probable variable assignments (MAP inference) that is much more scalable than general-purpose convex optimization methods, because it uses message passing to take advantage of sparse dependency structures. We then show how to learn the parameters of HL-MRFs. The learned HL-MRFs are as accurate as analogous discrete models, but much more scalable. Together, these algorithms enable HL-MRFs and PSL to model rich, structured data at scales not previously possible.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3846–3912},
numpages = {67},
keywords = {probabilistic graphical models, structured prediction, statistical relational learning}
}

@article{10.5555/3122009.3176852,
author = {Shang, Zuofeng and Cheng, Guang},
title = {Computational Limits of a Distributed Algorithm for Smoothing Spline},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {In this paper, we explore statistical versus computational trade-off to address a basic question in the application of a distributed algorithm: what is the minimal computational cost in obtaining statistical optimality? In smoothing spline setup, we observe a phase transition phenomenon for the number of deployed machines that ends up being a simple proxy for computing cost. Speci_cally, a sharp upper bound for the number of machines is established: when the number is below this bound, statistical optimality (in terms of non-parametric estimation or testing) is achievable; otherwise, statistical optimality becomes impossible. These sharp bounds partly capture intrinsic computational limits of the distributed algorithm considered in this paper, and turn out to be fully determined by the smoothness of the regression function. We name the asymptotic analysis on such split-and-aggregation estimation/inference as "splitotic" theory. As a side remark, we argue that sample splitting may be viewed as an alternative form of regularization, playing a similar role as smoothing parameter.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3809–3845},
numpages = {37},
keywords = {computational limits, splitotic theory, divide-and-conquer, smoothing spline}
}

@article{10.5555/3122009.3176851,
author = {Sheriff, Mohammed Rayyan and Chatterjee, Debasish},
title = {Optimal Dictionary for Least Squares Representation},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Dictionaries are collections of vectors used for the representation of a class of vectors in Euclidean spaces. Recent research on optimal dictionaries is focused on constructing dictionaries that offer sparse representations, i.e., l0-optimal representations. Here we consider the problem of finding optimal dictionaries with which representations of a given class of vectors is optimal in an l2-sense: optimality of representation is defined as attaining the minimal average l2-norm of the coefficients used to represent the vectors in the given class. With the help of recent results on rank-1 decompositions of symmetric positive semidefinite matrices, we provide an explicit description of l2-optimal dictionaries as well as their algorithmic constructions in polynomial time.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3781–3808},
numpages = {28},
keywords = {rank-1 decomposition, l2-optimal dictionary, finite tight frames}
}

@article{10.5555/3122009.3176850,
author = {Hasenclever, Leonard and Webb, Stefan and Lienart, Thibaut and Vollmer, Sebastian and Lakshminarayanan, Balaji and Blundell, Charles and Teh, Yee Whye},
title = {Distributed Bayesian Learning with Stochastic Natural Gradient Expectation Propagation and the Posterior Server},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {This paper makes two contributions to Bayesian machine learning algorithms. Firstly, we propose stochastic natural gradient expectation propagation (SNEP), a novel alternative to expectation propagation (EP), a popular variational inference algorithm. SNEP is a black box variational algorithm, in that it does not require any simplifying assumptions on the distribution of interest, beyond the existence of some Monte Carlo sampler for estimating the moments of the EP tilted distributions. Further, as opposed to EP which has no guarantee of convergence, SNEP can be shown to be convergent, even when using Monte Carlo moment estimates. Secondly, we propose a novel architecture for distributed Bayesian learning which we call the posterior server. The posterior server allows scalable and robust Bayesian learning in cases where a data set is stored in a distributed manner across a cluster, with each compute node containing a disjoint subset of data. An independent Monte Carlo sampler is run on each compute node, with direct access only to the local data subset, but which targets an approximation to the global posterior distribution given all data across the whole cluster. This is achieved by using a distributed asynchronous implementation of SNEP to pass messages across the cluster. We demonstrate SNEP and the posterior server on distributed Bayesian learning of logistic regression and neural networks.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3744–3780},
numpages = {37},
keywords = {natural gradient, distributed learning, stochastic approximation, deep learning, Bayesian learning, posterior server, Markov chain Monte Carlo, expectation propagation, variational inference, parameter server, large scale learning}
}

@article{10.5555/3122009.3176849,
author = {Wang, Mengdi and Liu, Ji and Fang, Ethan X.},
title = {Accelerating Stochastic Composition Optimization},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We consider the stochastic nested composition optimization problem where the objective is a composition of two expected-value functions. We propose a new stochastic first-order method, namely the accelerated stochastic compositional proximal gradient (ASC-PG) method. This algorithm updates the solution based on noisy gradient queries using a two-timescale iteration. The ASC-PG is the first proximal gradient method for the stochastic composition problem that can deal with nonsmooth regularization penalty. We show that the ASC-PG exhibits faster convergence than the best known algorithms, and that it achieves the optimal sample-error complexity in several important special cases. We demonstrate the application of ASC-PG to reinforcement learning and conduct numerical experiments.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3721–3743},
numpages = {23},
keywords = {large-scale optimization, composition optimization, stochastic gradient, sample complexity}
}

@article{10.5555/3122009.3176848,
author = {Bui, Thang D. and Yan, Josiah and Turner, Richard E.},
title = {A Unifying Framework for Gaussian Process Pseudo-Point Approximations Using Power Expectation Propagation},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Gaussian processes (GPs) are flexible distributions over functions that enable highlevel assumptions about unknown functions to be encoded in a parsimonious, flexible and general way. Although elegant, the application of GPs is limited by computational and analytical intractabilities that arise when data are su_ciently numerous or when employing non-Gaussian models. Consequently, a wealth of GP approximation schemes have been developed over the last 15 years to address these key limitations. Many of these schemes employ a small set of pseudo data points to summarise the actual data. In this paper we develop a new pseudo-point approximation framework using Power Expectation Propagation (Power EP) that uni_es a large number of these pseudo-point approximations. Unlike much of the previous venerable work in this area, the new framework is built on standard methods for approximate inference (variational free-energy, EP and Power EP methods) rather than employing approximations to the probabilistic generative model itself. In this way all of the approximation is performed at 'inference time' rather than at 'modelling time', resolving awkward philosophical and empirical questions that trouble previous approaches. Crucially, we demonstrate that the new framework includes new pseudopoint approximation methods that outperform current approaches on regression and classification tasks.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3649–3720},
numpages = {72},
keywords = {variational inference, sparse approximation, expectation propagation, Gaussian process}
}

@article{10.5555/3122009.3176847,
author = {Chaudhuri, Sougata and Tewari, Ambuj},
title = {Online Learning to Rank with Top-k Feedback},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We consider two settings of online learning to rank where feedback is restricted to top ranked items. The problem is cast as an online game between a learner and sequence of users, over T rounds. In both settings, the learners objective is to present ranked list of items to the users. The learner's performance is judged on the entire ranked list and true relevances of the items. However, the learner receives highly restricted feedback at end of each round, in form of relevances of only the top k ranked items, where k ≪ m. The first setting is non-contextual, where the list of items to be ranked is fixed. The second setting is contextual, where lists of items vary, in form of traditional query-document lists. No stochastic assumption is made on the generation process of relevances of items and contexts. We provide efficient ranking strategies for both the settings. The strategies achieve O(T2/3) regret, where regret is based on popular ranking measures in first setting and ranking surrogates in second setting. We also provide impossibility results for certain ranking measures and a certain class of surrogates, when feedback is restricted to the top ranked item, i.e. k = 1. We empirically demonstrate the performance of our algorithms on simulated and real world data sets.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3599–3648},
numpages = {50},
keywords = {learning theory, online bandits, learning to rank, partial monitoring, online learning}
}

@article{10.5555/3122009.3176846,
author = {Denis, Christophe and Hebiri, Mohamed},
title = {Confidence Sets with Expected Sizes for Multiclass Classification},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Multiclass classification problems such as image annotation can involve a large number of classes. In this context, confusion between classes can occur, and single label classification may be misleading. We provide in the present paper a general device that, given an unlabeled dataset and a score function defined as the minimizer of some empirical and convex risk, outputs a set of class labels, instead of a single one. Interestingly, this procedure does not require that the unlabeled dataset explores the whole classes. Even more, the method is calibrated to control the expected size of the output set while minimizing the classification risk. We show the statistical optimality of the procedure and establish rates of convergence under the Tsybakov margin condition. It turns out that these rates are linear on the number of labels. We apply our methodology to convex aggregation of confidence sets based on the V-fold cross validation principle also known as the superlearning principle (van der Laan et al., 2007). We illustrate the numerical performance of the procedure on real data and demonstrate in particular that with moderate expected size, w.r.t. the number of labels, the procedure provides significant improvement of the classification risk.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3571–3598},
numpages = {28},
keywords = {convex loss, multiclass classification, superlearning, confidence sets, empirical risk minimization}
}

@article{10.5555/3122009.3176845,
author = {Dieuleveut, Aymeric and Flammarion, Nicolas and Bach, Francis},
title = {Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We consider the optimization of a quadratic objective function whose gradients are only accessible through a stochastic oracle that returns the gradient at any given point plus a zero-mean finite variance random error. We present the first algorithm that achieves jointly the optimal prediction error rates for least-squares regression, both in terms of forgetting the initial conditions in O(1/n2), and in terms of dependence on the noise and dimension d of the problem, as O(d/n). Our new algorithm is based on averaged accelerated regularized gradient descent, and may also be analyzed through finer assumptions on initial conditions and the Hessian matrix, leading to dimension-free quantities that may still be small in some distances while the "optimal" terms above are large. In order to characterize the tightness of these new bounds, we consider an application to non-parametric regression and use the known lower bounds on the statistical performance (without computational limits), which happen to match our bounds obtained from a single pass on the data and thus show optimality of our algorithm in a wide variety of particular trade-offs between bias and variance.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3520–3570},
numpages = {51},
keywords = {accelerated gradient, least-squares regression, stochastic gradient, non-parametric estimation, convex optimization}
}

@article{10.5555/3122009.3176844,
author = {Vinogradska, Julia and Bischoff, Bastian and Nguyen-Tuong, Duy and Peters, Jan},
title = {Stability of Controllers for Gaussian Process Dynamics},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Learning control has become an appealing alternative to the derivation of control laws based on classic control theory. However, a major shortcoming of learning control is the lack of performance guarantees which prevents its application in many real-world scenarios. As a step towards widespread deployment of learning control, we provide stability analysis tools for controllers acting on dynamics represented by Gaussian processes (GPs). We consider differentiable Markovian control policies and system dynamics given as (i) the mean of a GP, and (ii) the full GP distribution. For both cases, we analyze finite and infinite time horizons. Furthermore, we study the effect of disturbances on the stability results. Empirical evaluations on simulated benchmark problems support our theoretical results.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3483–3519},
numpages = {37},
keywords = {Gaussian process, control, reinforcement learning, stability}
}

@article{10.5555/3122009.3176843,
author = {Park, Young Woong and Klabjan, Diego},
title = {Bayesian Network Learning via Topological Order},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We propose a mixed integer programming (MIP) model and iterative algorithms based on topological orders to solve optimization problems with acyclic constraints on a directed graph. The proposed MIP model has a signi_cantly lower number of constraints compared to popular MIP models based on cycle elimination constraints and triangular inequalities. The proposed iterative algorithms use gradient descent and iterative reordering approaches, respectively, for searching topological orders. A computational experiment is presented for the Gaussian Bayesian network learning problem, an optimization problem minimizing the sum of squared errors of regression models with L1 penalty over a feature network with application of gene network inference in bioinformatics.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3451–3482},
numpages = {32},
keywords = {directed acyclic graphs, Gaussian Bayesian network, topological orders, Bayesian networks}
}

@article{10.5555/3122009.3176842,
author = {Ashraphijuo, Morteza and Wang, Xiaodong and Aggarwal, Vaneet},
title = {Rank Determination for Low-Rank Data Completion},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Recently, fundamental conditions on the sampling patterns have been obtained for finite completability of low-rank matrices or tensors given the corresponding ranks. In this paper, we consider the scenario where the rank is not given and we aim to approximate the unknown rank based on the location of sampled entries and some given completion. We consider a number of data models, including single-view matrix, multi-view matrix, CP tensor, tensor-train tensor and Tucker tensor. For each of these data models, we provide an upper bound on the rank when an arbitrary low-rank completion is given. We characterize these bounds both deterministically, i.e., with probability one given that the sampling pattern satisfies certain combinatorial properties, and probabilistically, i.e., with high probability given that the sampling probability is above some threshold. Moreover, for both single-view matrix and CP tensor, we are able to show that the obtained upper bound is exactly equal to the unknown rank if the lowest-rank completion is given. Furthermore, we provide numerical experiments for the case of single-view matrix, where we use nuclear norm minimization to find a low-rank completion of the sampled data and we observe that in most of the cases the proposed upper bound on the rank is equal to the true rank.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3422–3450},
numpages = {29},
keywords = {CP rank, Tucker rank, low-rank data completion, rank estimation, multi-view matrix, tensor, manifold, matrix, tensor-train rank}
}

@article{10.5555/3122009.3176841,
author = {Lin, Junhong and Rosasco, Lorenzo},
title = {Optimal Rates for Multi-Pass Stochastic Gradient Methods},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We analyze the learning properties of the stochastic gradient method when multiple passes over the data and mini-batches are allowed. We study how regularization properties are controlled by the step-size, the number of passes and the mini-batch size. In particular, we consider the square loss and show that for a universal step-size choice, the number of passes acts as a regularization parameter, and optimal finite sample bounds can be achieved by early-stopping. Moreover, we show that larger step-sizes are allowed when considering mini-batches. Our analysis is based on a unifying approach, encompassing both batch and stochastic gradient methods as special cases. As a byproduct, we derive optimal convergence results for batch gradient methods (even in the non-attainable cases).},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3375–3421},
numpages = {47}
}

@article{10.5555/3122009.3176840,
author = {Schmitt, Maximilian and Schuller, Bj\"{o}rn},
title = {OpenXBOW: Introducing the Passau Open-Source Crossmodal Bag-of-Words Toolkit},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We introduce openXBOW, an open-source toolkit for the generation of bag-of-words (BoW) representations from multimodal input. In the BoW principle, word histograms were first used as features in document classification, but the idea was and can easily be adapted to, e. g., acoustic or visual descriptors, introducing a prior step of vector quantisation. The openXBOW toolkit supports arbitrary numeric input features and text input and concatenates computed sub-bags to a final bag. It provides a variety of extensions and options. To our knowledge, openXBOW is the first publicly available toolkit for the generation of crossmodal bags-of-words. The capabilities of the tool have been exemplified in different scenarios: sentiment analysis in tweets, classification of snore sounds, and time-dependent emotion recognition based on acoustic, linguistic, and visual information, where improved results over other feature representations were observed.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3370–3374},
numpages = {5},
keywords = {multimodal signal processing, bag-of-words, histogram feature representations, feature learning}
}

@article{10.5555/3122009.3176839,
author = {Tasche, Dirk},
title = {Fisher Consistency for Prior Probability Shift},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We introduce Fisher consistency in the sense of unbiasedness as a desirable property for estimators of class prior probabilities. Lack of Fisher consistency could be used as a criterion to dismiss estimators that are unlikely to deliver precise estimates in test data sets under prior probability and more general data set shift. The usefulness of this unbiasedness concept is demonstrated with three examples of classifiers used for quantification: Adjusted Count, EM-algorithm and CDE-Iterate. We find that Adjusted Count and EM-algorithm are Fisher consistent. A counter-example shows that CDE-Iterate is not Fisher consistent and, therefore, cannot be trusted to deliver reliable estimates of class probabilities.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3338–3369},
numpages = {32},
keywords = {fisher consistency, class distribution estimation, quantification, data set shift, classification}
}

@article{10.5555/3122009.3176838,
author = {Liu, Weiwei and Tsang, Ivor W. and M\"{u}ller, Klaus-Robert},
title = {An Easy-to-Hard Learning Paradigm for Multiple Classes and Multiple Labels},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Many applications, such as human action recognition and object detection, can be formulated as a multiclass classification problem. One-vs-rest (OVR) is one of the most widely used approaches for multiclass classification due to its simplicity and excellent performance. However, many confusing classes in such applications will degrade its results. For example, hand clap and boxing are two confusing actions. Hand clap is easily misclassified as boxing, and vice versa. Therefore, precisely classifying confusing classes remains a challenging task. To obtain better performance for multiclass classifications that have confusing classes, we first develop a classifier chain model for multiclass classification (CCMC) to transfer class information between classifiers. Then, based on an analysis of our proposed model, we propose an easy-to-hard learning paradigm for multiclass classification to automatically identify easy and hard classes and then use the predictions from simpler classes to help solve harder classes. Similar to CCMC, the classifier chain (CC) model is also proposed by Read et al. (2009) to capture the label dependency for multi-label classification. However, CC does not consider the order of di_culty of the labels and achieves degenerated performance when there are many confusing labels. Therefore, it is non-trivial to learn the appropriate label order for CC. Motivated by our analysis for CCMC, we also propose the easy-to-hard learning paradigm for multi-label classification to automatically identify easy and hard labels, and then use the predictions from simpler labels to help solve harder labels. We also demonstrate that our proposed strategy can be successfully applied to a wide range of applications, such as ordinal classification and relationship prediction. Extensive empirical studies validate our analysis and the efiectiveness of our proposed easy-to-hard learning strategies.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3300–3337},
numpages = {38},
keywords = {multi-label classification, easy-to-hard learning paradigm, multiclass classification, classifier Chain}
}

@article{10.5555/3122009.3176837,
author = {Jagabathula, Srikanth and Subramanian, Lakshminarayanan and Venkataraman, Ashwin},
title = {Identifying Unreliable and Adversarial Workers in Crowdsourced Labeling Tasks},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We study the problem of identifying unreliable and adversarial workers in crowdsourcing systems where workers (or users) provide labels for tasks (or items). Most existing studies assume that worker responses follow specific probabilistic models; however, recent evidence shows the presence of workers adopting non-random or even malicious strategies. To account for such workers, we suppose that workers comprise a mixture of honest and adversarial workers. Honest workers may be reliable or unreliable, and they provide labels according to an unknown but explicit probabilistic model. Adversaries adopt labeling strategies different from those of honest workers, whether probabilistic or not. We propose two reputation algorithms to identify unreliable honest workers and adversarial workers from only their responses. Our algorithms assume that honest workers are in the majority, and they classify workers with outlier label patterns as adversaries. Theoretically, we show that our algorithms successfully identify unreliable honest workers, workers adopting deterministic strategies, and worst-case sophisticated adversaries who can adopt arbitrary labeling strategies to degrade the accuracy of the inferred task labels. Empirically, we show that filtering out outliers using our algorithms can significantly improve the accuracy of several state-of-the-art label aggregation algorithms in real-world crowdsourcing datasets.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3233–3299},
numpages = {67},
keywords = {crowdsourcing, outliers, reputation, adversary}
}

@article{10.5555/3122009.3176836,
author = {Lin, Shao-Bo and Guo, Xin and Zhou, Ding-Xuan},
title = {Distributed Learning with Regularized Least Squares},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We study distributed learning with the least squares regularization scheme in a reproducing kernel Hilbert space (RKHS). By a divide-and-conquer approach, the algorithm partitions a data set into disjoint data subsets, applies the least squares regularization scheme to each data subset to produce an output function, and then takes an average of the individual output functions as a final global estimator or predictor. We show with error bounds and learning rates in expectation in both the L2-metric and RKHS-metric that the global output function of this distributed learning is a good approximation to the algorithm processing the whole data in one single machine. Our derived learning rates in expectation are optimal and stated in a general setting without any eigenfunction assumption. The analysis is achieved by a novel second order decomposition of operator differences in our integral operator approach. Even for the classical least squares regularization scheme in the RKHS associated with a general kernel, we give the best learning rate in expectation in the literature.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3202–3232},
numpages = {31},
keywords = {divide-and-conquer, integral operator, error analysis, second order decomposition, distributed learning}
}

@article{10.5555/3122009.3176835,
author = {Mahajan, Dhruv and Keerthi, S. Sathiya and Sundararajan, S.},
title = {A Distributed Block Coordinate Descent Method for Training l<sub>1</sub>Regularized Linear Classifiers},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Distributed training of l1 regularized classifiers has received great attention recently. Most existing methods approach this problem by taking steps obtained from approximating the objective by a quadratic approximation that is decoupled at the individual variable level. These methods are designed for multicore systems where communication costs are low. They are inefficient on systems such as Hadoop running on a cluster of commodity machines where communication costs are substantial. In this paper we design a distributed algorithm for l1 regularization that is much better suited for such systems than existing algorithms. A careful cost analysis is used to support these points and motivate our method. The main idea of our algorithm is to do block optimization of many variables on the actual objective function within each computing node; this increases the computational cost per step that is matched with the communication cost, and decreases the number of outer iterations, thus yielding a faster overall method. Distributed Gauss-Seidel and Gauss-Southwell greedy schemes are used for choosing variables to update in each step. We establish global convergence theory for our algorithm, including Q-linear rate of convergence. Experiments on two benchmark problems show our method to be much faster than existing methods.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3167–3201},
numpages = {35},
keywords = {l1 regularization, distributed learning}
}

@article{10.5555/3122009.3176834,
author = {McMahan, H. Brendan},
title = {A Survey of Algorithms and Analysis for Adaptive Online Learning},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We present tools for the analysis of Follow-The-Regularized-Leader (FTRL), Dual Averaging, and Mirror Descent algorithms when the regularizer (equivalently, proxfunction or learning rate schedule) is chosen adaptively based on the data. Adaptivity can be used to prove regret bounds that hold on every round, and also allows for data-dependent regret bounds as in AdaGrad-style algorithms (e.g., Online Gradient Descent with adaptive per-coordinate learning rates). We present results from a large number of prior works in a unified manner, using a modular and tight analysis that isolates the key arguments in easily re-usable lemmas. This approach strengthens previously known FTRL analysis techniques to produce bounds as tight as those achieved by potential functions or primal-dual analysis. Further, we prove a general and exact equivalence between adaptive Mirror Descent algorithms and a corresponding FTRL update, which allows us to analyze Mirror Descent algorithms in the same framework. The key to bridging the gap between Dual Averaging and Mirror Descent algorithms lies in an analysis of the FTRL-Proximal algorithm family. Our regret bounds are proved in the most general form, holding for arbitrary norms and non-smooth regularizers with time-varying weight.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3117–3166},
numpages = {50},
keywords = {online learning, online convex optimization, dual averaging, adaptive algorithms, mirror descent, follow-the-regularized-leader, regret analysis}
}

@article{10.5555/3122009.3176833,
author = {Oliehoek, Frans A. and Spaan, Matthijs T. J. and Terwijn, Bas and Robbel, Philipp and Messias, Jo\~{a}o V.},
title = {The MADP Toolbox: An Open Source Library for Planning and Learning in (Multi-)Agent Systems},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {This article describes the Multiagent Decision Process (MADP) Toolbox, a software library to support planning and learning for intelligent agents and multiagent systems in uncertain environments. Key features are that it supports partially observable environments and stochastic transition models; has unified support for single- and multiagent systems; provides a large number of models for decision-theoretic decision making, including one-shot and sequential decision making under various assumptions of observability and cooperation, such as Dec-POMDPs and POSGs; provides tools and parsers to quickly prototype new problems; provides an extensive range of planning and learning algorithms for single- and multiagent systems; is released under the GNU GPL v3 license; and is written in C++ and designed to be extensible via the object-oriented paradigm.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3112–3116},
numpages = {5},
keywords = {software, multiagent systems, reinforcement learning, decision-theoretic planning}
}

@article{10.5555/3122009.3176832,
author = {Roy, Aurko and Pokutta, Sebastian},
title = {Hierarchical Clustering via Spreading Metrics},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We study the cost function for hierarchical clusterings introduced by (Dasgupta, 2016) where hierarchies are treated as first-class objects rather than deriving their cost from projections into flat clusters. It was also shown in (Dasgupta, 2016) that a top-down algorithm based on the uniform Sparsest Cut problem returns a hierarchical clustering of cost at most O(αn logn) times the cost of the optimal hierarchical clustering, where an is the approximation ratio of the Sparsest Cut subroutine used. Thus using the best known approximation algorithm for Sparsest Cut due to Arora-Rao-Vazirani, the top-down algorithm returns a hierarchical clustering of cost at most O(log3/2n) times the cost of the optimal solution. We improve this by giving an O(log n)-approximation algorithm for this problem. Our main technical ingredients are a combinatorial characterization of ultrametrics induced by this cost function, deriving an Integer Linear Programming (ILP) formulation for this family of ultrametrics, and showing how to iteratively round an LP relaxation of this formulation by using the idea of sphere growing which has been extensively used in the context of graph partitioning. We also prove that our algorithm returns an O(log n)- approximate hierarchical clustering for a generalization of this cost function also studied in (Dasgupta, 2016). Experiments show that the hierarchies found by using the ILP formulation as well as our rounding algorithm often have better projections into flat clusters than the standard linkage based algorithms. We conclude with constant factor inapproximability results for this problem: 1) no polynomial size LP or SDP can achieve a constant factor approximation for this problem and 2) no polynomial time algorithm can achieve a constant factor approximation under the Small Set Expansion hypothesis.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3077–3111},
numpages = {35},
keywords = {linear programming, approximation algorithms, convex optimization, clustering, hierarchical clustering}
}

@article{10.5555/3122009.3176831,
author = {Gates, Alexander J. and Ahn, Yong-Yeol},
title = {The Impact of Random Models on Clustering Similarity},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Clustering is a central approach for unsupervised learning. After clustering is applied, the most fundamental analysis is to quantitatively compare clusterings. Such comparisons are crucial for the evaluation of clustering methods as well as other tasks such as consensus clustering. It is often argued that, in order to establish a baseline, clustering similarity should be assessed in the context of a random ensemble of clusterings. The prevailing assumption for the random clustering ensemble is the permutation model in which the number and sizes of clusters are fixed. However, this assumption does not necessarily hold in practice; for example, multiple runs of K-means clustering returns clusterings with a fixed number of clusters, while the cluster size distribution varies greatly. Here, we derive corrected variants of two clustering similarity measures (the Rand index and Mutual Information) in the context of two random clustering ensembles in which the number and sizes of clusters vary. In addition, we study the impact of one-sided comparisons in the scenario with a reference clustering. The consequences of different random models are illustrated using synthetic examples, handwriting recognition, and gene expression data. We demonstrate that the choice of random model can have a drastic impact on the ranking of similar clustering pairs, and the evaluation of a clustering method with respect to a random baseline; thus, the choice of random clustering model should be carefully justified.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3049–3076},
numpages = {28},
keywords = {clustering comparison, Rand index, normalized mutual information, clustering evaluation, adjustment for chance}
}

@article{10.5555/3122009.3176830,
author = {Tolstikhin, Ilya and Sriperumbudur, Bharath K. and Muandet, Krikamol},
title = {Minimax Estimation of Kernel Mean Embeddings},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {In this paper, we study the minimax estimation of the Bochner integral µk(P):= ∫χk(undefinedx)dP(x) also called as the kernel mean embedding, based on random samples drawn i.i.d. from P, where k : χ\texttimes{}χ → R is a positive de_nite kernel. Various estimators (including the empirical estimator), Θn of µk(P) are studied in the literature wherein all of them satisfy ||Θn_µk(P)||Hk = OP (n-1/2) with Hk being the reproducing kernel Hilbert space induced by k. The main contribution of the paper is in showing that the above mentioned rate of n-1/2 is minimax in ||undefined||Hk and ||undefined|| L2(Rd)-norms over the class of discrete measures and the class of measures that has an in_nitely di_erentiable density, with k being a continuous translation-invariant kernel on Rd. The interesting aspect of this result is that the minimax rate is independent of the smoothness of the kernel and the density of P (if it exists).},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3002–3048},
numpages = {47},
keywords = {reproducing kernel Hilbert space, kernel mean embeddings, translation invariant kernel, minimax lower bounds, Bochner integral, Bochner's theorem}
}

@article{10.5555/3122009.3176829,
author = {Sun, Hui and Craig, Bruce A. and Zhang, Lingsong},
title = {Angle-Based Multicategory Distance-Weighted SVM},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Classification is an important supervised learning technique with numerous applications. We develop an angle-based multicategory distance-weighted support vector machine (MDWSVM) classification method that is motivated from the binary distance-weighted support vector machine (DWSVM) classification method. The new method has the merits of both support vector machine (SVM) and distance-weighted discrimination (DWD) but also alleviates both the data piling issue of SVM and the imbalanced data issue of DWD. Theoretical and numerical studies demonstrate the advantages of MDWSVM method over existing angle-based methods.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2981–3001},
numpages = {21},
keywords = {high dimension, discriminant analysis, support vector machine, distance-weighted discrimination, imbalanced data}
}

@article{10.5555/3122009.3176828,
author = {Zhang, Yuchen and Xiao, Lin},
title = {Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We consider a generic convex optimization problem associated with regularized empirical risk minimization of linear predictors. The problem structure allows us to reformulate it as a convex-concave saddle point problem. We propose a stochastic primal-dual coordinate (SPDC) method, which alternates between maximizing over a randomly chosen dual variable and minimizing over the primal variables. An extrapolation step on the primal variables is performed to obtain accelerated convergence rate. We also develop a mini-batch version of the SPDC method which facilitates parallel computing, and an extension with weighted sampling probabilities on the dual variables, which has a better complexity than uniform sampling on unnormalized data. Both theoretically and empirically, we show that the SPDC method has comparable or better performance than several state-of-the-art optimization methods.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2939–2980},
numpages = {42},
keywords = {point problems, primal-dual algorithms, randomized algorithms, convex-concave saddle, empirical risk minimization, computational complexity}
}

@article{10.5555/3122009.3176827,
author = {Papyan, Vardan and Romano, Yaniv and Elad, Michael},
title = {Convolutional Neural Networks Analyzed via Convolutional Sparse Coding},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Convolutional neural networks (CNN) have led to many state-of-the-art results spanning through various fields. However, a clear and profound theoretical understanding of the forward pass, the core algorithm of CNN, is still lacking. In parallel, within the wide field of sparse approximation, Convolutional Sparse Coding (CSC) has gained increasing attention in recent years. A theoretical study of this model was recently conducted, establishing it as a reliable and stable alternative to the commonly practiced patch-based processing. Herein, we propose a novel multi-layer model, ML-CSC, in which signals are assumed to emerge from a cascade of CSC layers. This is shown to be tightly connected to CNN, so much so that the forward pass of the CNN is in fact the thresholding pursuit serving the ML-CSC model. This connection brings a fresh view to CNN, as we are able to attribute to this architecture theoretical claims such as uniqueness of the representations throughout the network, and their stable estimation, all guaranteed under simple local sparsity conditions. Lastly, identifying the weaknesses in the above pursuit scheme, we propose an alternative to the forward pass, which is connected to deconvolutional and recurrent networks, and also has better theoretical guarantees.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2887–2938},
numpages = {52},
keywords = {forward pass, thresholding algorithm, convolutional neural networks, sparse representation, convolutional sparse coding, deep learning, basis pursuit}
}

@article{10.5555/3122009.3176826,
author = {Al-Shedivat, Maruan and Wilson, Andrew Gordon and Saatchi, Yunus and Hu, Zhiting and Xing, Eric P.},
title = {Learning Scalable Deep Kernels with Recurrent Structure},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Many applications in speech, robotics, finance, and biology deal with sequential data, where ordering matters and recurrent structures are common. However, this structure cannot be easily captured by standard kernel functions. To model such structure, we propose expressive closed-form kernel functions for Gaussian processes. The resulting model, GP-LSTM, fully encapsulates the inductive biases of long short-term memory (LSTM) recurrent networks, while retaining the non-parametric probabilistic advantages of Gaussian processes. We learn the properties of the proposed kernels by optimizing the Gaussian process marginal likelihood using a new provably convergent semi-stochastic gradient procedure, and exploit the structure of these kernels for scalable training and prediction. This approach provides a practical representation for Bayesian LSTMs. We demonstrate state-of-the-art performance on several benchmarks, and thoroughly investigate a consequential autonomous driving application, where the predictive uncertainties provided by GP-LSTM are uniquely valuable.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2850–2886},
numpages = {37}
}

@article{10.5555/3122009.3176825,
author = {Liu, Weiwei and Tsang, Ivor W.},
title = {Making Decision Trees Feasible in Ultrahigh Feature and Label Dimensions},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Due to the non-linear but highly interpretable representations, decision tree (DT) models have significantly attracted a lot of attention of researchers. However, it is difficult to understand and interpret DT models in ultrahigh dimensions and DT models usually suffer from the curse of dimensionality and achieve degenerated performance when there are many noisy features. To address these issues, this paper first presents a novel data-dependent generalization error bound for the perceptron decision tree (PDT), which provides the theoretical justification to learn a sparse linear hyperplane in each decision node and to prune the tree. Following our analysis, we introduce the notion of budget-aware classifier (BAC) with a budget constraint on the weight coefficients, and propose a supervised budgeted tree (SBT) algorithm to achieve non-linear prediction performance. To avoid generating an unstable and complicated decision tree and improve the generalization of the SBT, we present a pruning strategy by learning classifiers to minimize cross-validation errors on each BAC. To deal with ultrahigh label dimensions, based on three important phenomena of real-world data sets from a variety of application domains, we develop a sparse coding tree framework for multi-label annotation problems and provide the theoretical analysis. Extensive empirical studies verify that 1) SBT is easy to understand and interpret in ultrahigh dimensions and is more resilient to noisy features. 2) Compared with state-of-the-art algorithms, our proposed sparse coding tree framework is more efficient, yet accurate in ultrahigh label and feature dimensions.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2814–2849},
numpages = {36},
keywords = {ultrahigh label dimensions, classification, ultrahigh feature dimensions, perceptron decision tree}
}

@article{10.5555/3122009.3176824,
author = {Flammarion, Nicolas and Palaniappan, Balamurugan and Bach, Francis},
title = {Robust Discriminative Clustering with Sparse Regularizers},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Clustering high-dimensional data often requires some form of dimensionality reduction, where clustered variables are separated from "noise-looking" variables. We cast this problem as finding a low-dimensional projection of the data which is well-clustered. This yields a one-dimensional projection in the simplest situation with two clusters, and extends naturally to a multi-label scenario for more than two clusters. In this paper, (a) we first show that this joint clustering and dimension reduction formulation is equivalent to previously proposed discriminative clustering frameworks, thus leading to convex relaxations of the problem; (b) we propose a novel sparse extension, which is still cast as a convex relaxation and allows estimation in higher dimensions; (c) we propose a natural extension for the multi-label scenario; (d) we provide a new theoretical analysis of the performance of these formulations with a simple probabilistic model, leading to scalings over the form d = O(√n) for the affine invariant case and d = O(n) for the sparse case, where n is the number of examples and d the ambient dimension; and finally, (e) we propose an efficient iterative algorithm with running-time complexity proportional to O(nd2), improving on earlier algorithms for discriminative clustering with the square loss, which had quadratic complexity in the number of examples.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2764–2813},
numpages = {50}
}

@article{10.5555/3122009.3176823,
author = {Guhaniyogi, Rajarshi and Qamar, Shaan and Dunson, David B.},
title = {Bayesian Tensor Regression},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We propose a Bayesian approach to regression with a scalar response on vector and tensor covariates. Vectorization of the tensor prior to analysis fails to exploit the structure, often leading to poor estimation and predictive performance. We introduce a novel class of multiway shrinkage priors for tensor coefficients in the regression setting and present posterior consistency results under mild conditions. A computationally efficient Markov chain Monte Carlo algorithm is developed for posterior computation. Simulation studies illustrate substantial gains over existing tensor regression methods in terms of estimation and parameter inference. Our approach is further illustrated in a neuroimaging application.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2733–2763},
numpages = {31},
keywords = {parafac decomposition, multiway shrinkage prior, magnetic resonance imaging (MRI), tensor regression, posterior consistency}
}

@article{10.5555/3122009.3176822,
author = {Mart\'{\i}nez, David and Aleny\`{a}, Guillem and Ribeiro, Tony and Inoue, Katsumi and Torras, Carme},
title = {Relational Reinforcement Learning for Planning with Exogenous Effects},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Probabilistic planners have improved recently to the point that they can solve difficult tasks with complex and expressive models. In contrast, learners cannot tackle yet the expressive models that planners do, which forces complex models to be mostly handcrafted. We propose a new learning approach that can learn relational probabilistic models with both action effects and exogenous effects. The proposed learning approach combines a multivalued variant of inductive logic programming for the generation of candidate models, with an optimization method to select the best set of planning operators to model a problem. We also show how to combine this learner with reinforcement learning algorithms to solve complete problems. Finally, experimental validation is provided that shows improvements over previous work in both simulation and a robotic task. The robotic task involves a dynamic scenario with several agents where a manipulator robot has to clear the tableware on a table. We show that the exogenous effects learned by our approach allowed the robot to clear the table in a more efficient way.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2689–2732},
numpages = {44},
keywords = {probabilistic planning, model-based RL, active learning, learning models for planning, robot learning}
}

@article{10.5555/3122009.3176821,
author = {Benavoli, Alessio and Corani, Giorgio and Dem\v{s}ar, Janez and Zaffalon, Marco},
title = {Time for a Change: A Tutorial for Comparing Multiple Classifiers through Bayesian Analysis},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {The machine learning community adopted the use of null hypothesis significance testing (NHST) in order to ensure the statistical validity of results. Many scientific fields however realized the shortcomings of frequentist reasoning and in the most radical cases even banned its use in publications. We should do the same: just as we have embraced the Bayesian paradigm in the development of new machine learning methods, so we should also use it in the analysis of our own results. We argue for abandonment of NHST by exposing its fallacies and, more importantly, offer better--more sound and useful--alternatives for it.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2653–2688},
numpages = {36},
keywords = {Bayesian correlated t-test, pitfalls of p-values, Bayesian hierarchical correlated t-test, comparing classifiers, null hypothesis significance testing, Bayesian hypothesis tests, Bayesian signed-rank test}
}

@article{10.5555/3122009.3176820,
author = {Brockmeier, Austin J. and Mu, Tingting and Ananiadou, Sophia and Goulermas, John Y.},
title = {Quantifying the Informativeness of Similarity Measurements},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {In this paper, we describe an unsupervised measure for quantifying the 'informativeness' of correlation matrices formed from the pairwise similarities or relationships among data instances. The measure quantifies the heterogeneity of the correlations and is defined as the distance between a correlation matrix and the nearest correlation matrix with constant off-diagonal entries. This non-parametric notion generalizes existing test statistics for equality of correlation coefficients by allowing for alternative distance metrics, such as the Bures and other distances from quantum information theory. For several distance and dissimilarity metrics, we derive closed-form expressions of informativeness, which can be applied as objective functions for machine learning applications. Empirically, we demonstrate that informativeness is a useful criterion for selecting kernel parameters, choosing the dimension for kernel-based nonlinear dimensionality reduction, and identifying structured graphs. We also consider the problem of finding a maximally informative correlation matrix around a target matrix, and explore parameterizing the optimization in terms of the coordinates of the sample or through a lower-dimensional embedding. In the latter case, we find that maximizing the Bures-based informativeness measure, which is maximal for centered rank-1 correlation matrices, is equivalent to minimizing a specific matrix norm, and present an algorithm to solve the minimization problem using the norm's proximal operator. The proposed correlation denoising algorithm consistently improves spectral clustering. Overall, we find informativeness to be a novel and useful criterion for identifying non-trivial correlation structure.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2592–2652},
numpages = {61},
keywords = {kernel methods, clustering, quantum information theory, correlation matrices, similarity information, information theory}
}

@article{10.5555/3122009.3176819,
author = {Kundu, Abhisek and Drineas, Petros and Magdon-Ismail, Malik},
title = {Recovering PCA and Sparse PCA via Hybrid- (l<sub>1</sub>, l<sub>2</sub>)Sparse Sampling of Data Elements},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {This paper addresses how well we can recover a data matrix when only given a few of its elements. We present a randomized algorithm that element-wise sparsifies the data, retaining only a few of its entries. Our new algorithm independently samples the data using probabilities that depend on both squares (l2 sampling) and absolute values (l1 sampling) of the entries. We prove that this hybrid algorithm (i) achieves a near-PCA reconstruction of the data, and (ii) recovers sparse principal components of the data, from a sketch formed by a sublinear sample size. Hybrid-(l1, l2) inherits the l2-ability to sample the important elements, as well as the regularization properties of l1 sampling, and maintains strictly better quality than either l1 or l2 on their own. Extensive experimental results on synthetic, image, text, biological, and financial data show that not only are we able to recover PCA and sparse PCA from incomplete data, but we can speed up such computations significantly using our sparse sketch.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2558–2591},
numpages = {34},
keywords = {element-wise sampling, pca, hybrid-(l1, sparse pca, sparse representation, l2)}
}

@article{10.5555/3122009.3176818,
author = {Bilodeau, Martin and Nangue, Aur\'{e}lien Guetsop},
title = {Tests of Mutual or Serial Independence of Random Vectors with Applications},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {The problem of testing mutual independence between many random vectors is addressed. The closely related problem of testing serial independence of a multivariate stationary sequence is also considered. The M\"{o}bius transformation of characteristic functions is used to characterize independence. A generalization to p vectors of distance covariance and Hilbert-Schmidt independence criterion (HSIC) tests with the translation invariant kernel of a stable probability distribution is proposed. Both test statistics can be expressed in a simple form as a sum over all elements of a componentwise product of p doubly-centered matrices. It is shown that an HSIC statistic with sufficiently small scale parameters is equivalent to a distance covariance statistic. Consistency and weak convergence of both types of statistics are established. Approximation of p-values is made by randomization tests without recomputing interpoint distances for each randomized sample. The dependogram is adapted to the proposed tests for the graphical identification of sources of dependencies. Empirical rejection rates obtained through extensive simulations confirm both the applicability of the testing procedures in small samples and the high level of competitiveness in terms of power. Applications to meteorological and financial data provide some interesting interpretations of dependencies revealed by dependograms.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2518–2557},
numpages = {40},
keywords = {mutual independence, serial independence, Hilbert-Schmidt independence criterion, M\"{o}bius transformation, distance covariance}
}

@article{10.5555/3122009.3176817,
author = {Van Hoof, Herke and Neumann, Gerhard and Peters, Jan},
title = {Non-Parametric Policy Search with Limited Information Loss},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Learning complex control policies from non-linear and redundant sensory input is an important challenge for reinforcement learning algorithms. Non-parametric methods that approximate values functions or transition models can address this problem, by adapting to the complexity of the data set. Yet, many current non-parametric approaches rely on unstable greedy maximization of approximate value functions, which might lead to poor convergence or oscillations in the policy update. A more robust policy update can be obtained by limiting the information loss between successive state-action distributions. In this paper, we develop a policy search algorithm with policy updates that are both robust and non-parametric. Our method can learn non-parametric control policies for infinite horizon continuous Markov decision processes with non-linear and redundant sensory representations. We investigate how we can use approximations of the kernel function to reduce the time requirements of the demanding non-parametric computations. In our experiments, we show the strong performance of the proposed method, and how it can be approximated efficiently. Finally, we show that our algorithm can learn a real-robot under-powered swing-up task directly from image data.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2472–2517},
numpages = {46},
keywords = {reinforcement learning, policy search, kernel methods, robotics}
}

@article{10.5555/3122009.3176816,
author = {Gerber, Samuel and Maggioni, Mauro},
title = {Multiscale Strategies for Computing Optimal Transport},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {This paper presents a multiscale approach to efficiently compute approximate optimal transport plans between point sets. It is particularly well-suited for point sets that are in high-dimensions, but are close to being intrinsically low-dimensional. The approach is based on an adaptive multiscale decomposition of the point sets. The multiscale decomposition yields a sequence of optimal transport problems, that are solved in a top-to-bottom fashion from the coarsest to the finest scale. We provide numerical evidence that this multiscale approach scales approximately linearly, in time and memory, in the number of nodes, instead of quadratically or worse for a direct solution. Empirically, the multiscale approach results in less than one percent relative error in the objective function. Furthermore, the multiscale plans constructed are of interest by themselves as they may be used to introduce novel features and notions of distances between point sets. An analysis of sets of brain MRI based on optimal transport distances illustrates the effectiveness of the proposed method on a real world data set. The application demonstrates that multiscale optimal transport distances have the potential to improve on state-of-the-art metrics currently used in computational anatomy.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2440–2471},
numpages = {32}
}

@article{10.5555/3122009.3176815,
author = {Ding, A. Adam and Dy, Jennifer G. and Li, Yi and Chang, Yale},
title = {A Robust-Equitable Measure for Feature Ranking and Selection},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {In many applications, not all the features used to represent data samples are important. Often only a few features are relevant for the prediction task. The choice of dependence measures often affect the final result of many feature selection methods. To select features that have complex nonlinear relationships with the response variable, the dependence measure should be equitable, a concept proposed by Reshef et al. (2011); that is, the dependence measure treats linear and nonlinear relationships equally. Recently, Kinney and Atwal (2014) gave a mathematical definition of self-equitability. In this paper, we introduce a new concept of robust-equitability and identify a robust-equitable copula dependence measure, the robust copula dependence (RCD) measure. RCD is based on the L1-distance of the copula density from uniform and we show that it is equitable under both equitability definitions. We also prove theoretically that RCD is much easier to estimate than mutual information. Because of these theoretical properties, the RCD measure has the following advantages compared to existing dependence measures: it is robust to different relationship forms and robust to unequal sample sizes of different features. Experiments on both synthetic and real-world data sets confirm the theoretical analysis, and illustrate the advantage of using the dependence measure RCD for feature selection.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2394–2439},
numpages = {46},
keywords = {dependence measure, equitability, feature selection, mutual information, copula}
}

@article{10.5555/3122009.3176814,
author = {Wang, Tong and Rudin, Cynthia and Doshi-Velez, Finale and Liu, Yimin and Klampfl, Erica and MacNeille, Perry},
title = {A Bayesian Framework for Learning Rule Sets for Interpretable Classification},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We present a machine learning algorithm for building classifiers that are comprised of a small number of short rules. These are restricted disjunctive normal form models. An example of a classifier of this form is as follows: If X satisfies (condition A AND condition B) OR (condition C) OR ..., then Y = 1. Models of this form have the advantage of being interpretable to human experts since they produce a set of rules that concisely describe a specific class. We present two probabilistic models with prior parameters that the user can set to encourage the model to have a desired size and shape, to conform with a domain-specific definition of interpretability. We provide a scalable MAP inference approach and develop theoretical bounds to reduce computation by iteratively pruning the search space. We apply our method (Bayesian Rule Sets - BRS) to characterize and predict user behavior with respect to in-vehicle context-aware personalized recommender systems. Our method has a major advantage over classical associative classification methods and decision trees in that it does not greedily grow the model.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2357–2393},
numpages = {37},
keywords = {data mining, statistical learning, disjunctive normal form, Bayesian modeling, association rules, interpretable classifier}
}

@article{10.5555/3122009.3176813,
author = {Saeedi, Ardavan and Kulkarni, Tejas D. and Mansinghka, Vikash K. and Gershman, Samuel J.},
title = {Variational Particle Approximations},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Approximate inference in high-dimensional, discrete probabilistic models is a central problem in computational statistics and machine learning. This paper describes discrete particle variational inference (DPVI), a new approach that combines key strengths of Monte Carlo, variational and search-based techniques. DPVI is based on a novel family of particle-based variational approximations that can be fit using simple, fast, deterministic search techniques. Like Monte Carlo, DPVI can handle multiple modes, and yields exact results in a well-defined limit. Like unstructured mean-field, DPVI is based on optimizing a lower bound on the partition function; when this quantity is not of intrinsic interest, it facilitates convergence assessment and debugging. Like both Monte Carlo and combinatorial search, DPVI can take advantage of factorization, sequential structure, and custom search operators. This paper defines DPVI particle-based approximation family and partition function lower bounds, along with the sequential DPVI and local DPVI algorithm templates for optimizing them. DPVI is illustrated and evaluated via experiments on lattice Markov Random Fields, nonparametric Bayesian mixtures and block-models, and parametric as well as non-parametric hidden Markov models. Results include applications to real-world spike-sorting and relational modeling problems, and show that DPVI can offer appealing time/accuracy trade-offs as compared to multiple alternatives.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2328–2356},
numpages = {29},
keywords = {ising model, infinite relational model, Bayesian inference, variational methods, hidden Markov model, dirichlet process mixture model}
}

@article{10.5555/3122009.3176812,
author = {Norton, Matthew and Mafusalov, Alexander and Uryasev, Stan},
title = {Soft Margin Support Vector Classification as Buffered Probability Minimization},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {In this paper, we show that the popular C-SVM, soft-margin support vector classifier is equivalent to minimization of Buffered Probability of Exceedance (bPOE), a recently introduced characterization of uncertainty. To show this, we introduce a new SVM formulation, called the EC-SVM, which is derived from a simple bPOE minimization problem that is easy to interpret with a meaningful free parameter, optimal objective value, and probabilistic derivation. Over the range of its free parameter, the EC-SVM has both a convex and non-convex case which we connect to existing SVM formulations. We first show that the C-SVM, formulated with any regularization norm, is equivalent to the convex EC-SVM. Similarly, we show that the Ev-SVM is equivalent to the EC-SVM over its entire parameter range, which includes both the convex and non-convex case. These equivalences, coupled with the interpretability of the EC-SVM, allow us to gain surprising new insights into the C-SVM and fully connect soft margin support vector classification with superquantile and bPOE concepts. We also show that the EC-SVM can easily be cast as a robust optimization problem, where bPOE is minimized with data lying in a fixed uncertainty set. This reformulation allows us to clearly differentiate between the convex and non-convex case, with convexity associated with pessimistic views of uncertainty and non-convexity associated with optimistic views of uncertainty. Finally, we address some practical considerations. First, we show that these new insights can assist in making parameter selection more efficient. Second, we discuss optimization approaches for solving the EC-SVM. Third, we address the issue of generalization, providing generalization bounds for both bPOE and misclassification rate.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2285–2327},
numpages = {43},
keywords = {support vector machines, robust optimization, conditional value-at-risk, buffered probability of exceedance, binary Classification}
}

@article{10.5555/3122009.3176811,
author = {Stucky, Benjamin and Van De Geer, Sara},
title = {Sharp Oracle Inequalities for Square Root Regularization},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We study a set of regularization methods for high-dimensional linear regression models. These penalized estimators have the square root of the residual sum of squared errors as loss function, and any weakly decomposable norm as penalty function. This fit measure is chosen because of its property that the estimator does not depend on the unknown standard deviation of the noise. On the other hand, a generalized weakly decomposable norm penalty is very useful in being able to deal with different underlying sparsity structures. We can choose a different sparsity inducing norm depending on how we want to interpret the unknown parameter vector β. Structured sparsity norms, as defined in Micchelli et al. (2010), are special cases of weakly decomposable norms, therefore we also include the square root LASSO (Belloni et al., 2011), the group square root LASSO (Bunea et al., 2014) and a new method called the square root SLOPE (in a similar fashion to the SLOPE from Bogdan et al. 2015). For this collection of estimators our results provide sharp oracle inequalities with the Karush-Kuhn-Tucker conditions. We discuss some examples of estimators. Based on a simulation we illustrate some advantages of the square root SLOPE.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2256–2284},
numpages = {29},
keywords = {structured sparsity, Karush-Kuhn-Tucker, sharp oracale inequality, weak decomposability, square root LASSO}
}

@article{10.5555/3122009.3176810,
author = {Chen, Jie and Avron, Haim and Sindhwani, Vikas},
title = {Hierarchically Compositional Kernels for Scalable Nonparametric Learning},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We propose a novel class of kernels to alleviate the high computational cost of large-scale nonparametric learning with kernel methods. The proposed kernel is defined based on a hierarchical partitioning of the underlying data domain, where the Nystr\"{o}m method (a globally low-rank approximation) is married with a locally lossless approximation in a hierarchical fashion. The kernel maintains (strict) positive-definiteness. The corresponding kernel matrix admits a recursively off-diagonal low-rank structure, which allows for fast linear algebra computations. Suppressing the factor of data dimension, the memory and arithmetic complexities for training a regression or a classifier are reduced from O(n2) and O(n3) to O(nr) and O(nr2), respectively, where n is the number of training examples and r is the rank on each level of the hierarchy. Although other randomized approximate kernels entail a similar complexity, empirical results show that the proposed kernel achieves a matching performance with a smaller r. We demonstrate comprehensive experiments to show the effective use of the proposed kernel on data sizes up to the order of millions.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2214–2255},
numpages = {42},
keywords = {nonparametric learning, hierarchical kernels}
}

@article{10.5555/3122009.3176809,
author = {Pinto, Jervis and Fern, Alan},
title = {Learning Partial Policies to Speedup MDP Tree Search via Reduction to I.I.D. Learning},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {A popular approach for online decision-making in large MDPs is time-bounded tree search. The effectiveness of tree search, however, is largely influenced by the action branching factor, which limits the search depth given a time bound. An obvious way to reduce action branching is to consider only a subset of potentially good actions at each state as specified by a provided partial policy. In this work, we consider offline learning of such partial policies with the goal of speeding up search without significantly reducing decision-making quality. Our first contribution consists of reducing the learning problem to set learning. We give a reduction-style analysis of three such algorithms, each making different assumptions, which relates the set learning objectives to the sub-optimality of search using the learned partial policies. Our second contribution is to describe concrete implementations of the algorithms within the popular framework of Monte-Carlo tree search. Finally, the third contribution is to evaluate the learning algorithms on two challenging MDPs with large action branching factors. The results show that the learned partial policies can significantly improve the anytime performance of Monte-Carlo tree search.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2179–2213},
numpages = {35},
keywords = {partial policy, imitation learning, Monte-Carlo tree search, partial policy learning, reductions, online sequential decision-making}
}

@article{10.5555/3122009.3176808,
author = {Tran, An C. and Dietrich, Jens and Guesgen, Hans W. and Marsland, Stephen},
title = {Parallel Symmetric Class Expression Learning},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {In machine learning, one often encounters data sets where a general pattern is violated by a relatively small number of exceptions (for example, a rule that says that all birds can fly is violated by examples such as penguins). This complicates the concept learning process and may lead to the rejection of some simple and expressive rules that cover many cases. In this paper we present an approach to this problem in description logic learning by computing partial descriptions (which are not necessarily entirely complete) of both positive and negative examples and combining them. Our Symmetric Parallel Class Expression Learning approach enables the generation of general rules with exception patterns included. We demonstrate that this algorithm provides significantly better results (in terms of metrics such as accuracy, search space covered, and learning time) than standard approaches on some typical data sets. Further, the approach has the added benefit that it can be parallelised relatively simply, leading to much faster exploration of the search tree on modern computers.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2145–2178},
numpages = {34},
keywords = {description logic learning, exception, symmetric, parallel}
}

@article{10.5555/3122009.3153019,
author = {Ashraphijuo, Morteza and Wang, Xiaodong},
title = {Fundamental Conditions for Low-CP-Rank Tensor Completion},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We consider the problem of low canonical polyadic (CP) rank tensor completion. A completion is a tensor whose entries agree with the observed entries and its rank matches the given CP rank. We analyze the manifold structure corresponding to the tensors with the given rank and define a set of polynomials based on the sampling pattern and CP decomposition. Then, we show that finite completability of the sampled tensor is equivalent to having a certain number of algebraically independent polynomials among the defined polynomials. Our proposed approach results in characterizing the maximum number of algebraically independent polynomials in terms of a simple geometric structure of the sampling pattern, and therefore we obtain the deterministic necessary and sufficient condition on the sampling pattern for finite completability of the sampled tensor. Moreover, assuming that the entries of the tensor are sampled independently with probability p and using the mentioned deterministic analysis, we propose a combinatorial method to derive a lower bound on the sampling probability p, or equivalently, the number of sampled entries that guarantees finite completability with high probability. We also show that the existing result for the matrix completion problem can be used to obtain a loose lower bound on the sampling probability p. In addition, we obtain deterministic and probabilistic conditions for unique completability. It is seen that the number of samples required for finite or unique completability obtained by the proposed analysis on the CP manifold is orders-of-magnitude lower than that is obtained by the existing analysis on the Grassmannian manifold.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2116–2145},
numpages = {30},
keywords = {algebraic geometry, finite completability, unique completability, Bernstein's theorem, canonical polyadic (CP) decomposition, low-rank tensor completion}
}

@article{10.5555/3122009.3153018,
author = {Papanikolaou, Yannis and Foulds, James R. and Rubin, Timothy N. and Tsoumakas, Grigorios},
title = {Dense Distributions from Sparse Samples: Improved Gibbs Sampling Parameter Estimators for LDA},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We introduce a novel approach for estimating Latent Dirichlet Allocation (LDA) parameters from collapsed Gibbs samples (CGS), by leveraging the full conditional distributions over the latent variable assignments to efficiently average over multiple samples, for little more computational cost than drawing a single additional collapsed Gibbs sample. Our approach can be understood as adapting the soft clustering methodology of Collapsed Variational Bayes (CVB0) to CGS parameter estimation, in order to get the best of both techniques. Our estimators can straightforwardly be applied to the output of any existing implementation of CGS, including modern accelerated variants. We perform extensive empirical comparisons of our estimators with those of standard collapsed inference algorithms on real-world data for both unsupervised LDA and Prior-LDA, a supervised variant of LDA for multilabel classification. Our results show a consistent advantage of our approach over traditional CGS under all experimental conditions, and over CVB0 inference in the majority of conditions. More broadly, our results highlight the importance of averaging over multiple samples in LDA parameter estimation, and the use of efficient computational techniques to do so.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2058–2115},
numpages = {58},
keywords = {multi-label classification, text mining, topic models, unsupervised learning, Bayesian inference, CVB0, collapsed Gibbs sampling, latent dirichlet allocation}
}

@article{10.5555/3122009.3153017,
author = {Balachandran, Prakash and Kolaczyk, Eric D. and Viles, Weston D.},
title = {On the Propagation of Low-Rate Measurement Error to Subgraph Counts in Large Networks},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Our work in this paper is inspired by a statistical observation that is both elementary and broadly relevant to network analysis in practice--that the uncertainty in approximating some true graph G = (V,E) by some estimated graph G = (V, E) manifests as errors in our knowledge of the presence/absence of edges between vertex pairs, which must necessarily propagate to any estimates of network summaries η(G) we seek. Motivated by the common practice of using plug-in estimates η(G) as proxies for η(G), our focus is on the problem of characterizing the distribution of the discrepancy D = η(G) - η(G), in the case where η(undefined) is a subgraph count. Specifically, we study the fundamental case where the statistic of interest is |E|, the number of edges in G. Our primary contribution in this paper is to show that in the empirically relevant setting of large graphs with low-rate measurement errors, the distribution of DE = |E| - |E| is well-characterized by a Skellam distribution, when the errors are independent or weakly dependent. Under an assumption of independent errors, we are able to further show conditions under which this characterization is strictly better than that of an appropriate normal distribution. These results derive from our formulation of a general result, quantifying the accuracy with which the difference of two sums of dependent Bernoulli random variables may be approximated by the difference of two independent Poisson random variables, i.e., by a Skellam distribution. This general result is developed through the use of Stein's method, and may be of some general interest. We finish with a discussion of possible extension of our work to subgraph counts η(G) of higher order.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2025–2057},
numpages = {33},
keywords = {skellam distribution, limit distribution, stein's method, network analysis}
}

@article{10.5555/3122009.3153016,
author = {Gao, Chao and Ma, Zongming and Zhang, Anderson Y. and Zhou, Harrison H.},
title = {Achieving Optimal Misclassification Proportion in Stochastic Block Models},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Community detection is a fundamental statistical problem in network data analysis. In this paper, we present a polynomial time two-stage method that provably achieves optimal statistical performance in misclassification proportion for stochastic block model under weak regularity conditions. Our two-stage procedure consists of a refinement stage motivated by penalized local maximum likelihood estimation. This stage can take a wide range of weakly consistent community detection procedures as its initializer, to which it applies and outputs a community assignment that achieves optimal misclassification proportion with high probability. The theoretical property is confirmed by simulated examples.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1980–2024},
numpages = {45},
keywords = {community detection, network analysis, clustering, minimax rates, spectral clustering}
}

@article{10.5555/3122009.3153015,
author = {Chakrabarti, Deepayan and Funiak, Stanislav and Chang, Jonathan and Macskassy, Sofus A.},
title = {Joint Label Inference in Networks},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We consider the problem of inferring node labels in a partially labeled graph where each node in the graph has multiple label types and each label type has a large number of possible labels. Our primary example, and the focus of this paper, is the joint inference of label types such as hometown, current city, and employers for people connected by a social network; by predicting these user profile fields, the network can provide a better experience to its users. Existing approaches such as Label Propagation (Zhu et al., 2003) fail to consider interactions between the label types. Our proposed method, called Edge-Explain, explicitly models these interactions, while still allowing scalable inference under a distributed message-passing architecture. On a large subset of the Facebook social network, collected in a previous study (Chakrabarti et al., 2014), EdgeExplain outperforms label propagation for several label types, with lifts of up to 120% for recall@1 and 60% for recall@3.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1941–1979},
numpages = {39},
keywords = {label inference, variational methods, label propagation, social networks, graphs}
}

@article{10.5555/3122009.3153014,
author = {Kleindessner, Matth\"{a}us and Von Luxburg, Ulrike},
title = {Lens Depth Function and K-Relative Neighborhood Graph: Versatile Tools for Ordinal Data Analysis},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {In recent years it has become popular to study machine learning problems in a setting of ordinal distance information rather than numerical distance measurements. By ordinal distance information we refer to binary answers to distance comparisons such as d(A, B) < d(C, D). For many problems in machine learning and statistics it is unclear how to solve them in such a scenario. Up to now, the main approach is to explicitly construct an ordinal embedding of the data points in the Euclidean space, an approach that has a number of drawbacks. In this paper, we propose algorithms for the problems of medoid estimation, outlier identification, classification, and clustering when given only ordinal data. They are based on estimating the lens depth function and the k-relative neighborhood graph on a data set. Our algorithms are simple, are much faster than an ordinal embedding approach and avoid some of its drawbacks, and can easily be parallelized.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1889–1940},
numpages = {52},
keywords = {comparison-based algorithms, k-relative neighborhood graph, ordinal distance information, non-metric multi-dimensional scaling, ordinal embedding, ordinal data, lens depth function}
}

@article{10.5555/3122009.3153013,
author = {Sriperumbudur, Bharath and Fukumizu, Kenji and Gretton, Arthur and Hyv\"{a}rinen, Aapo and Kumar, Revant},
title = {Density Estimation in Infinite Dimensional Exponential Families},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {In this paper, we consider an infinite dimensional exponential family P of probability densities, which are parametrized by functions in a reproducing kernel Hilbert space H, and show it to be quite rich in the sense that a broad class of densities on Rd can be approximated arbitrarily well in Kullback-Leibler (KL) divergence by elements in P. Motivated by this approximation property, the paper addresses the question of estimating an unknown density p0 through an element in P. Standard techniques like maximum likelihood estimation (MLE) or pseudo MLE (based on the method of sieves), which are based on minimizing the KL divergence between p0 and P, do not yield practically useful estimators because of their inability to efficiently handle the log-partition function. We propose an estimator pn based on minimizing the Fisher divergence, J(p0||p) between p0 and p ∈ P, which involves solving a simple finite-dimensional linear system. When p0 ∈ P, we show that the proposed estimator is consistent, and provide a convergence rate of n-min{2/3, 2β+1/2β+2} in Fisher divergence under the smoothness assumption that log p0 ∈ R(Cβ) for some β ≥ 0, where C is a certain Hilbert-Schmidt operator on H and R(Cβ) denotes the image of Cβ. We also investigate the misspecified case of p0 ∉ P and show that J(p0||pn) → infp∈P J(p0||p) as n → ∞, and provide a rate for this convergence under a similar smoothness condition as above. Through numerical simulations we demonstrate that the proposed estimator outperforms the non-parametric kernel density estimator, and that the advantage of the proposed estimator grows as d increases.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1830–1888},
numpages = {59},
keywords = {kernel density estimator, score matching, exponential family, maximum likelihood, interpolation space, tikhonov regularization, fisher divergence, inverse problem, reproducing kernel Hilbert space, density estimation}
}

@article{10.5555/3122009.3153012,
author = {Takenouchi, Takashi and Kanamori, Takafumi},
title = {Statistical Inference with Unnormalized Discrete Models and Localized Homogeneous Divergences},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {In this paper, we focus on parameters estimation of probabilistic models in discrete space. A naive calculation of the normalization constant of the probabilistic model on discrete space is often infeasible and statistical inference based on such probabilistic models has difficulty. In this paper, we propose a novel estimator for probabilistic models on discrete space, which is derived from an empirically localized homogeneous divergence. The idea of the empirical localization makes it possible to ignore an unobserved domain on sample space, and the homogeneous divergence is a discrepancy measure between two positive measures and has a weak coincidence axiom. The proposed estimator can be constructed without calculating the normalization constant and is asymptotically consistent and Fisher efficient. We investigate statistical properties of the proposed estimator and reveal a relationship between the empirically localized homogeneous divergence and a mixture of the α-divergence. The α-divergence is a non-homogeneous discrepancy measure that is frequently discussed in the context of information geometry. Using the relationship, we also propose an asymptotically consistent estimator of the normalization constant. Experiments showed that the proposed estimator comparably performs to the maximum likelihood estimator but with drastically lower computational cost.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1804–1829},
numpages = {26},
keywords = {discrete model, homogeneous divergence, empirical localization, unnormalized model}
}

@article{10.5555/3122009.3153011,
author = {Pedregosa, Fabian and Bach, Francis and Gramfort, Alexandre},
title = {On the Consistency of Ordinal Regression Methods},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Many of the ordinal regression models that have been proposed in the literature can be seen as methods that minimize a convex surrogate of the zero-one, absolute, or squared loss functions. A key property that allows to study the statistical implications of such approximations is that of Fisher consistency. Fisher consistency is a desirable property for surrogate loss functions and implies that in the population setting, i.e., if the probability distribution that generates the data were available, then optimization of the surrogate would yield the best possible model. In this paper we will characterize the Fisher consistency of a rich family of surrogate loss functions used in the context of ordinal regression, including support vector ordinal regression, ORBoosting and least absolute deviation. We will see that, for a family of surrogate loss functions that subsumes support vector ordinal regression and ORBoosting, consistency can be fully characterized by the derivative of a real-valued function at zero, as happens for convex margin-based surrogates in binary classification. We also derive excess risk bounds for a surrogate of the absolute error that generalize existing risk bounds for binary classification. Finally, our analysis suggests a novel surrogate of the squared error loss. We compare this novel surrogate with competing approaches on 9 different datasets. Our method shows to be highly competitive in practice, outperforming the least squares loss on 7 out of 9 datasets.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1769–1803},
numpages = {35},
keywords = {surrogate loss, calibration, excess risk bound, ordinal regression, fisher consistency}
}

@article{10.5555/3122009.3153010,
author = {Ahsen, Mehmet Eren and Challapalli, Niharika and Vidyasagar, Mathukumalli},
title = {Two New Approaches to Compressed Sensingexhibiting Both Robust Sparse Recovery and the Grouping Effect},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {In this paper we introduce a new optimization formulation for sparse regression and compressed sensing, called CLOT (Combined L-One and Two), wherein the regularizer is a convex combination of the l1- and l2-norms. This formulation differs from the Elastic Net (EN) formulation, in which the regularizer is a convex combination of the l1- and l2-norm squared. It is shown that, in the context of compressed sensing, the EN formulation does not achieve robust recovery of sparse vectors, whereas the new CLOT formulation achieves robust recovery. Also, like EN but unlike LASSO, the CLOT formulation achieves the grouping effect, wherein coefficients of highly correlated columns of the measurement (or design) matrix are assigned roughly comparable values. It is already known LASSO does not have the grouping effect. Therefore the CLOT formulation combines the best features of both LASSO (robust sparse recovery) and EN (grouping effect).The CLOT formulation is a special case of another one called SGL (Sparse Group LASSO) which was introduced into the literature previously, but without any analysis of either the grouping effect or robust sparse recovery. It is shown here that SGL achieves robust sparse recovery, and also achieves a version of the grouping effect in that coefficients of highly correlated columns belonging to the same group of the measurement (or design) matrix are assigned roughly comparable values.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1745–1768},
numpages = {24},
keywords = {compressed sensing, sparse group LASSO, elastic net, sparse regression, LASSO}
}

@article{10.5555/3122009.3153009,
author = {Javanmard, Adel},
title = {Perishability of Data: Dynamic Pricing under Varying-Coefficient Models},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We consider a firm that sells a large number of products to its customers in an online fashion. Each product is described by a high dimensional feature vector, and the market value of a product is assumed to be linear in the values of its features. Parameters of the valuation model are unknown and can change over time. The firm sequentially observes a product's features and can use the historical sales data (binary sale/no sale feedbacks) to set the price of current product, with the objective of maximizing the collected revenue. We measure the performance of a dynamic pricing policy via regret, which is the expected revenue loss compared to a clairvoyant that knows the sequence of model parameters in advance.We propose a pricing policy based on projected stochastic gradient descent (PSGD) and characterize its regret in terms of time T, features dimension d, and the temporal variability in the model parameters, δt. We consider two settings. In the first one, feature vectors are chosen antagonistically by nature and we prove that the regret of PSGD pricing policy is of order O(√T + Σt=1T √tδt). In the second setting (referred to as stochastic features model), the feature vectors are drawn independently from an unknown distribution. We show that in this case, the regret of PSGD pricing policy is of order O(d2 log T + Σt=1T tδt/d).},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1714–1744},
numpages = {31},
keywords = {regret, varying-coefficient models, revenue management, stochastic gradient descent, hypothesis testing, dynamic pricing}
}

@article{10.5555/3122009.3153008,
author = {Shamir, Ohad},
title = {An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We consider the closely related problems of bandit convex optimization with two-point feedback, and zero-order stochastic convex optimization with two function evaluations per round. We provide a simple algorithm and analysis which is optimal for convex Lipschitz functions. This improves on Duchi et al. (2015), which only provides an optimal result for smooth functions; Moreover, the algorithm and analysis are simpler, and readily extend to non-Euclidean problems. The algorithm is based on a small but surprisingly powerful modification of the gradient estimator.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1703–1713},
numpages = {11},
keywords = {zero-order optimization, gradient estimator, stochastic optimization, bandit optimization}
}

@article{10.5555/3122009.3153007,
author = {De Castro, Yohann and Espinasse, Thibault and Rochet, Paul},
title = {Reconstructing Undirected Graphs from Eigenspaces},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We aim at recovering the weighted adjacency matrix W of an undirected graph from a perturbed version of its eigenspaces. This situation arises for instance when working with stationary signals on graphs or Markov chains observed at random times. Our approach relies on minimizing a cost function based on the Frobenius norm of the commutator AB--BA between symmetric matrices A and B. We describe a particular framework in which we have access to an estimation of the eigenspaces and provide support selection procedures from theoretical and practical points of view. In the Erdos-R\'{e}nyi model on N vertices with no self-loops, we show that identifiability (i.e., the ability to reconstruct W from the knowledge of its eigenspaces) follows a sharp phase transition on the expected number of edges with threshold function N log N/2. Simulated and real life numerical experiments assert our methodology.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1679–1702},
numpages = {24},
keywords = {support recovery, backward selection algorithm, graphs, identifiability, stationary signal processing}
}

@article{10.5555/3122009.3153006,
author = {Ghoshdastidar, Debarghya and Dukkipati, Ambedkar},
title = {Uniform Hypergraph Partitioning: Provable Tensor Methods and Sampling Techniques},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {In a series of recent works, we have generalised the consistency results in the stochastic block model literature to the case of uniform and non-uniform hypergraphs. The present paper continues the same line of study, where we focus on partitioning weighted uniform hypergraphs--a problem often encountered in computer vision. This work is motivated by two issues that arise when a hypergraph partitioning approach is used to tackle computer vision problems: (i) The uniform hypergraphs constructed for higher-order learning contain all edges, but most have negligible weights. Thus, the adjacency tensor is nearly sparse, and yet, not binary. (ii) A more serious concern is that standard partitioning algorithms need to compute all edge weights, which is computationally expensive for hypergraphs. This is usually resolved in practice by merging the clustering algorithm with a tensor sampling strategy--an approach that is yet to be analysed rigorously.We build on our earlier work on partitioning dense unweighted uniform hypergraphs (Ghoshdastidar and Dukkipati, ICML, 2015), and address the aforementioned issues by proposing provable and efficient partitioning algorithms. Our analysis justifies the empirical success of practical sampling techniques. We also complement our theoretical findings by elaborate empirical comparison of various hypergraph partitioning schemes.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1638–1678},
numpages = {41},
keywords = {planted model, sampling, tensors, hypergraph partitioning, subspace clustering, spectral method}
}

@article{10.5555/3122009.3153005,
author = {Lim, Shiau Hong and Chen, Yudong and Xu, Huan},
title = {Clustering from General Pairwise Observations with Applications to Time-Varying Graphs},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We present a general framework for graph clustering and bi-clustering where we are given a general observation (called a label) between each pair of nodes. This framework allows a rich encoding of various types of pairwise interactions between nodes. We propose a new tractable and robust approach to this problem based on convex optimization and maximum likelihood estimators. We analyze our algorithms under a general statistical model extending the planted partition and stochastic block models. Both sufficient and necessary conditions are provided for successful recovery of the underlying clusters. Our theoretical results subsume many existing graph clustering results for a wide range of settings, including planted partition, weighted clustering, submatrix localization and partially observed graphs. Furthermore, our results are applicable to novel settings including time-varying graphs, providing new insights to solutions of these problems. We provide empirical results on both synthetic and real data that corroborate with our theoretical findings.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1591–1637},
numpages = {47},
keywords = {pairwise observation, time-varying graphs, graph clustering, dynamic graphs, low-rank matrix, convex optimization, information divergence}
}

@article{10.5555/3122009.3153004,
author = {Wyner, Abraham J. and Olson, Matthew and Bleich, Justin and Mease, David},
title = {Explaining the Success of Adaboost and Random Forests as Interpolating Classifiers},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {There is a large literature explaining why AdaBoost is a successful classifier. The literature on AdaBoost focuses on classifier margins and boosting's interpretation as the optimization of an exponential likelihood function. These existing explanations, however, have been pointed out to be incomplete. A random forest is another popular ensemble method for which there is substantially less explanation in the literature. We introduce a novel perspective on AdaBoost and random forests that proposes that the two algorithms work for similar reasons. While both classifiers achieve similar predictive accuracy, random forests cannot be conceived as a direct optimization procedure. Rather, random forests is a self-averaging, interpolating algorithm which creates what we denote as a "spiked-smooth" classifier, and we view AdaBoost in the same light. We conjecture that both AdaBoost and random forests succeed because of this mechanism. We provide a number of examples to support this explanation. In the process, we question the conventional wisdom that suggests that boosting algorithms for classification require regularization or early stopping and should be limited to low complexity classes of learners, such as decision stumps. We conclude that boosting should be used like random forests: with large decision trees, without regularization or early stopping.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1558–1590},
numpages = {33},
keywords = {tree-ensembles, adaboost, overfitting, classification, random forests}
}

@article{10.5555/3122009.3153003,
author = {Bardenet, R\'{e}mi and Doucet, Arnaud and Holmes, Chris},
title = {On Markov Chain Monte Carlo Methods for Tall Data},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Markov chain Monte Carlo methods are often deemed too computationally intensive to be of any practical use for big data applications, and in particular for inference on datasets containing a large number n of individual data points, also known as tall datasets. In scenarios where data are assumed independent, various approaches to scale up the Metropolis-Hastings algorithm in a Bayesian inference context have been recently proposed in machine learning and computational statistics. These approaches can be grouped into two categories: divide-and-conquer approaches and, subsampling-based algorithms. The aims of this article are as follows. First, we present a comprehensive review of the existing literature, commenting on the underlying assumptions and theoretical guarantees of each method. Second, by leveraging our understanding of these limitations, we propose an original subsampling-based approach relying on a control variate method which samples under regularity conditions from a distribution provably close to the posterior distribution of interest, yet can require less than O(n) data point likelihood evaluations at each iteration for certain statistical models in favourable scenarios. Finally, we emphasize that we have only been able so far to propose subsampling-based methods which display good performance in scenarios where the Bernstein-von Mises approximation of the target posterior distribution is excellent. It remains an open challenge to develop such methods in scenarios where the Bernstein-von Mises approximation is poor.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1515–1557},
numpages = {43}
}

@article{10.5555/3122009.3122055,
author = {Chang, Xiangyu and Lin, Shao-Bo and Zhou, Ding-Xuan},
title = {Distributed Semi-Supervised Learning with Kernel Ridge Regression},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {This paper provides error analysis for distributed semi-supervised learning with kernel ridge regression (DSKRR) based on a divide-and-conquer strategy. DSKRR applies kernel ridge regression (KRR) to data subsets that are distributively stored on multiple servers to produce individual output functions, and then takes a weighted average of the individual output functions as a final estimator. Using a novel error decomposition which divides the generalization error of DSKRR into the approximation error, sample error and distributed error, we find that the sample error and distributed error reect the power and limitation of DSKRR, compared with KRR processing the whole data. Thus a small distributed error provides a large range of the number of data subsets to guarantee a small generalization error. Our results show that unlabeled data play important roles in reducing the distributed error and enlarging the number of data subsets in DSKRR. Our analysis also applies to the case when the regression function is out of the reproducing kernel Hilbert space. Numerical experiments including toy simulations and a music-prediction task are employed to demonstrate our theoretical statements and show the power of unlabeled data in distributed learning.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1493–1514},
numpages = {22},
keywords = {unlabeled data, error decomposition, distributed learning, learning theory, kernel ridge regression, semi-supervised learning}
}

@article{10.5555/3122009.3122054,
author = {Huang, Hanwen},
title = {Asymptotic Behavior of Support Vector Machine for Spiked Population Model},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {For spiked population model, we investigate the large dimension N and large sample size M asymptotic behavior of the Support Vector Machine (SVM) classification method in the limit of N, M → ∞ at fixed α = M/N. We focus on the generalization performance by analytically evaluating the angle between the normal direction vectors of SVM separating hyperplane and corresponding Bayes optimal separating hyperplane. This is an analogous result to the one shown in Paul (2007) and Nadler (2008) for the angle between the sample eigenvector and the population eigenvector in random matrix theorem. We provide not just bound, but sharp prediction of the asymptotic behavior of SVM that can be determined by a set of nonlinear equations. Based on the analytical results, we propose a new method of selecting tuning parameter which significantly reduces the computational cost. A surprising finding is that SVM achieves its best performance at small value of the tuning parameter under spiked population model. These results are confirmed to be correct by comparing with those of numerical simulations on finite-size systems. We also apply our formulas to an actual dataset of breast cancer and find agreement between analytical derivations and numerical computations based on cross validation.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1472–1492},
numpages = {21},
keywords = {spiked population model, support vector machine, asymptotic behavior}
}

@article{10.5555/3122009.3122053,
author = {Kpotufe, Samory and Verma, Nakul},
title = {Time-Accuracy Tradeoffs in Kernel Prediction: Controlling Prediction Quality},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Kernel regression or classification (also referred to as weighted ε-NN methods in Machine Learning) are appealing for their simplicity and therefore ubiquitous in data analysis. However, practical implementations of kernel regression or classification consist of quantizing or sub-sampling data for improving time efficiency, often at the cost of prediction quality. While such tradeoffs are necessary in practice, their statistical implications are generally not well understood, hence practical implementations come with few performance guarantees. In particular, it is unclear whether it is possible to maintain the statistical accuracy of kernel prediction--crucial in some applications--while improving prediction time.The present work provides guiding principles for combining kernel prediction with data-quantization so as to guarantee good tradeoffs between prediction time and accuracy, and in particular so as to approximately maintain the good accuracy of vanilla kernel prediction. Furthermore, our tradeoff guarantees are worked out explicitly in terms of a tuning parameter which acts as a knob that favors either time or accuracy depending on practical needs. On one end of the knob, prediction time is of the same order as that of single-nearestneighbor prediction (which is statistically inconsistent) while maintaining consistency; on the other end of the knob, the prediction risk is nearly minimax-optimal (in terms of the original data size) while still reducing time complexity. The analysis thus reveals the interaction between the data-quantization approach and the kernel prediction method, and most importantly gives explicit control of the tradeoff to the practitioner rather than fixing the tradeoff in advance or leaving it opaque.The theoretical results are validated on data from a range of real-world application domains; in particular we demonstrate that the theoretical knob performs as expected.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1443–1471},
numpages = {29}
}

@article{10.5555/3122009.3122052,
author = {Durante, Daniele and Mukherjee, Nabanita and Steorts, Rebecca C.},
title = {Bayesian Learning of Dynamic Multilayer Networks},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {A plethora of networks is being collected in a growing number of fields, including disease transmission, international relations, social interactions, and others. As data streams continue to grow, the complexity associated with these highly multidimensional connectivity data presents novel challenges. In this paper, we focus on the time-varying interconnections among a set of actors in multiple contexts, called layers. Current literature lacks flexible statistical models for dynamic multilayer networks, which can enhance quality in inference and prediction by efficiently borrowing information within each network, across time, and between layers. Motivated by this gap, we develop a Bayesian nonparametric model leveraging latent space representations. Our formulation characterizes the edge probabilities as a function of shared and layer-specific actors positions in a latent space, with these positions changing in time via Gaussian processes. This representation facilitates dimensionality reduction and incorporates different sources of information in the observed data. In addition, we obtain tractable procedures for posterior computation, inference, and prediction. We provide theoretical results on the flexibility of our model. Our methods are tested on simulations and infection studies monitoring dynamic face-to-face contacts among individuals in multiple days, where we perform better than current methods in inference and prediction.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1414–1442},
numpages = {29},
keywords = {edge prediction, face-to-face contact network, Gaussian process, dynamic multilayer network, latent space model}
}

@article{10.5555/3122009.3122051,
author = {Yu, Guo and Bien, Jacob},
title = {Learning Local Dependence in Ordered Data},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {In many applications, data come with a natural ordering. This ordering can often induce local dependence among nearby variables. However, in complex data, the width of this dependence may vary, making simple assumptions such as a constant neighborhood size unrealistic. We propose a framework for learning this local dependence based on estimating the inverse of the Cholesky factor of the covariance matrix. Penalized maximum likelihood estimation of this matrix yields a simple regression interpretation for local dependence in which variables are predicted by their neighbors. Our proposed method involves solving a convex, penalized Gaussian likelihood problem with a hierarchical group lasso penalty. The problem decomposes into independent subproblems which can be solved efficiently in parallel using first-order methods. Our method yields a sparse, symmetric, positive definite estimator of the precision matrix, encoding a Gaussian graphical model. We derive theoretical results not found in existing methods attaining this structure. In particular, our conditions for signed support recovery and estimation consistency rates in multiple norms are as mild as those in a regression problem. Empirical results show our method performing favorably compared to existing methods. We apply our method to genomic data to flexibly model linkage disequilibrium. Our method is also applied to improve the performance of discriminant analysis in sound recording classification.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1354–1413},
numpages = {60},
keywords = {precision matrices, Gaussian graphical models, local dependence, hierarchical group lasso, Cholesky factor}
}

@article{10.5555/3122009.3122050,
author = {Farajtabar, Mehrdad and Wang, Yichen and Gomez-Rodriguez, Manuel and Li, Shuang and Zha, Hongyuan and Song, Le},
title = {COEVOLVE: A Joint Point Process Model for Information Diffusion and Network Evolution},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Information diffusion in online social networks is affected by the underlying network topology, but it also has the power to change it. Online users are constantly creating new links when exposed to new information sources, and in turn these links are alternating the way information spreads. However, these two highly intertwined stochastic processes, information diffusion and network evolution, have been predominantly studied separately, ignoring their co-evolutionary dynamicsWe propose a temporal point process model, Coevolve, for such joint dynamics, allowing the intensity of one process to be modulated by that of the other. This model allows us to efficiently simulate interleaved diffusion and network events, and generate traces obeying common diffusion and network patterns observed in real-world networks such as Twitter. Furthermore, we also develop a convex optimization framework to learn the parameters of the model from historical diffusion and network evolution traces. We experimented with both synthetic data and data gathered from Twitter, and show that our model provides a good fit to the data as well as more accurate predictions than alternatives.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1305–1353},
numpages = {49},
keywords = {survival analysis, social networks, information diffusion, point processes, co-evolutionary dynamics, network structure, Hawkes process}
}

@article{10.5555/3122009.3122049,
author = {De G. Matthews, Alexander G. and Van Der Wilk, Mark and Nickson, Tom and Fujii, Keisuke and Boukouvalas, Alexis and Le\'{o}n-Villagr\'{a}, Pablo and Ghahramani, Zoubin and Hensman, James},
title = {GPflow: A Gaussian Process Library Using Tensorflow},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {GPflow is a Gaussian process library that uses TensorFlow for its core computations and Python for its front end. The distinguishing features of GPflow are that it uses variational inference as the primary approximation method, provides concise code through the use of automatic differentiation, has been engineered with a particular emphasis on software testing and is able to exploit GPU hardware.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1299–1304},
numpages = {6}
}

@article{10.5555/3122009.3122048,
author = {Lepp\"{a}aho, Eemeli and Ammad-ud-din, Muhammad and Kaski, Samuel},
title = {GFA: Exploratory Analysis of Multiple Data Sources with Group Factor Analysis},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {The R package GFA provides a full pipeline for factor analysis of multiple data sources that are represented as matrices with co-occurring samples. It allows learning dependencies between subsets of the data sources, decomposed into latent factors. The package also implements sparse priors for the factorization, providing interpretable biclusters of the multi-source data.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1294–1298},
numpages = {5},
keywords = {multi-view learning, factor analysis, biclustering, data integration, Bayesian latent variable modelling}
}

@article{10.5555/3122009.3122047,
author = {Popovici, Elena},
title = {Bridging Supervised Learning and Test-Based Co-Optimization},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {This paper takes a close look at the important commonalities and subtle differences between the well-established field of supervised learning and the much younger one of cooptimization. It explains the relationships between the problems, algorithms and views on cost and performance of the two fields, all throughout providing a two-way dictionary for the respective terminologies used to describe these concepts. The intent is to facilitate advancement of both fields through transfer and cross-pollination of ideas, techniques and results. As a proof of concept, a theoretical study is presented on the connection between existence / lack of free lunch in the two fields, showcasing a few ideas for improving computational complexity of certain supervised learning approaches.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1255–1293},
numpages = {39},
keywords = {supervised learning, optimal algorithms, free lunch, co-optimization, active learning}
}

@article{10.5555/3122009.3122046,
author = {Gottlieb, Lee-Ad and Kontorovich, Aryeh and Nisnevitch, Pinhas},
title = {Nearly Optimal Classification for Semimetrics},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We initiate the rigorous study of classification in semimetric spaces, which are point sets with a distance function that is non-negative and symmetric, but need not satisfy the triangle inequality. We define the density dimension dens and discover that it plays a central role in the statistical and algorithmic feasibility of learning in semimetric spaces. We compute this quantity for several widely used semimetrics and present nearly optimal sample compression algorithms, which are then used to obtain generalization guarantees, including fast rates.Our claim of near-optimality holds in both computational and statistical senses. When the sample has radius R and margin γ, we show that it can be compressed down to roughly d = (R/γ )dens points, and further that finding a significantly better compression is algorithmically intractable unless P=NP. This compression implies generalization via standard Occam-type arguments, to which we provide a nearly matching lower bound.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1233–1254},
numpages = {22},
keywords = {compression, classification, generalization, semimetric}
}

@article{10.5555/3122009.3122045,
author = {Tikka, Santtu and Karvanen, Juha},
title = {Simplifying Probabilistic Expressions in Causal Inference},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Obtaining a non-parametric expression for an interventional distribution is one of the most fundamental tasks in causal inference. Such an expression can be obtained for an identifiable causal effect by an algorithm or by manual application of do-calculus. Often we are left with a complicated expression which can lead to biased or inefficient estimates when missing data or measurement errors are involved.We present an automatic simplification algorithm that seeks to eliminate symbolically unnecessary variables from these expressions by taking advantage of the structure of the underlying graphical model. Our method is applicable to all causal effect formulas and is readily available in the R package causaleffect.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1203–1232},
numpages = {30},
keywords = {graph theory, probabilistic expression, graphical model, simplification, causal inference}
}

@article{10.5555/3122009.3122044,
author = {Melnyk, Igor and Banerjee, Arindam},
title = {A Spectral Algorithm for Inference in Hidden Semi-Markov Models},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Hidden semi-Markov models (HSMMs) are latent variable models which allow latent state persistence and can be viewed as a generalization of the popular hidden Markov models (HMMs). In this paper, we introduce a novel spectral algorithm to perform inference in HSMMs. Unlike expectation maximization (EM), our approach correctly estimates the probability of given observation sequence based on a set of training sequences. Our approach is based on estimating moments from the sample, whose number of dimensions depends only logarithmically on the maximum length of the hidden state persistence. Moreover, the algorithm requires only a few matrix inversions and is therefore computationally efficient. Empirical evaluations on synthetic and real data demonstrate the advantage of the algorithm over EM in terms of speed and accuracy, especially for large data sets.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1164–1202},
numpages = {39},
keywords = {aviation safety, graphical models, tensor analysis, hidden semi-Markov model, spectral algorithm}
}

@article{10.5555/3122009.3122043,
author = {Sourati, Jamshid and Akcakaya, Murat and Leen, Todd K. and Erdogmus, Deniz and Dy, Jennifer G.},
title = {Asymptotic Analysis of Objectives Based on Fisher Information in Active Learning},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {Obtaining labels can be costly and time-consuming. Active learning allows a learning algorithm to intelligently query samples to be labeled for a more efficient learning. Fisher information ratio (FIR) has been used as an objective for selecting queries. However, little is known about the theory behind the use of FIR for active learning. There is a gap between the underlying theory and the motivation of its usage in practice. In this paper, we attempt to fill this gap and provide a rigorous framework for analyzing existing FIR-based active learning methods. In particular, we show that FIR can be asymptotically viewed as an upper bound of the expected variance of the log-likelihood ratio. Additionally, our analysis suggests a unifying framework that not only enables us to make theoretical comparisons among the existing querying methods based on FIR, but also allows us to give insight into the development of new active learning approaches based on this objective.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1123–1163},
numpages = {41},
keywords = {fisher information ratio, classification active learning, upper-bound minimization, asymptotic log-loss}
}

@article{10.5555/3122009.3122042,
author = {Shi, Tianlin and Zhu, Jun},
title = {Online Bayesian Passive-Aggressive Learning},
year = {2017},
issue_date = {January 2017},
publisher = {JMLR.org},
volume = {18},
number = {1},
issn = {1532-4435},
abstract = {We present online Bayesian Passive-Aggressive (BayesPA) learning, a generic online learning framework for hierarchical Bayesian models with max-margin posterior regularization. We show that BayesPA subsumes the standard online Passive-Aggressive (PA) learning and extends naturally to incorporate latent variables for both parametric and nonparametric Bayesian inference, therefore providing great flexibility for explorative analysis. As an important example, we apply BayesPA to topic modeling and derive efficient online learning algorithms for max-margin topic models. We further develop nonparametric BayesPA topic models to infer the unknown number of topics in an online manner. Experimental results on 20newsgroups and a large Wikipedia multi-label dataset (with 1.1 millions of training documents and 0.9 million of unique terms in the vocabulary) show that our approaches significantly improve time efficiency while achieving comparable accuracy with the corresponding batch algorithms.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1084–1122},
numpages = {39}
}

@article{10.5555/3122009.3122041,
author = {McDonald, Daniel J. and Shalizi,

license_type: permissive

branch_name: refs/heads/main

extension: bib