text:
@article{10.5555/3322706.3322735,
author = {Chazelle, Bernard and Wang, Chu},
title = {Iterated Learning in Dynamic Social Networks},
year = {2019},
issue_date = {January 2019},
publisher = {JMLR.org},
volume = {20},
number = {1},
issn = {1532-4435},
abstract = {A classic finding by (Kalish et al., 2007) shows that no language can be learned iteratively by rational agents in a self-sustained manner. In other words, if A teaches a foreign language to B, who then teaches what she learned to C, and so on, the language will quickly get lost and agents will wind up teaching their own common native language. If so, how can linguistic novelty ever be sustained? We address this apparent paradox by considering the case of iterated learning in a social network: we show that by varying the lengths of the learning sessions over time or by keeping the networks dynamic, it is possible for iterated learning to endure forever with arbitrarily small loss.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {979–1006},
numpages = {28}
}

@article{10.5555/3322706.3322734,
author = {Bingham, Eli and Chen, Jonathan P. and Jankowiak, Martin and Obermeyer, Fritz and Pradhan, Neeraj and Karaletsos, Theofanis and Singh, Rohit and Szerlip, Paul and Horsfall, Paul and Goodman, Noah D.},
title = {Pyro: Deep Universal Probabilistic Programming},
year = {2019},
issue_date = {January 2019},
publisher = {JMLR.org},
volume = {20},
number = {1},
issn = {1532-4435},
abstract = {Pyro is a probabilistic programming language built on Python as a platform for developing advanced probabilistic models in AI research. To scale to large data sets and high-dimensional models, Pyro uses stochastic variational inference algorithms and probability distributions built on top of PyTorch, a modern GPU-accelerated deep learning framework. To accommodate complex or model-specific algorithmic behavior, Pyro leverages Poutine, a library of composable building blocks for modifying the behavior of probabilistic programs.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {973–978},
numpages = {6},
keywords = {deep learning, generative models, graphical models, approximate Bayesian inference, probabilistic programming}
}

@article{10.5555/3322706.3322733,
author = {Elser, Veit and Schmidt, Dan and Yedidia, Jonathan},
title = {Monotone Learning with Rectified Wire Networks},
year = {2019},
issue_date = {January 2019},
publisher = {JMLR.org},
volume = {20},
number = {1},
issn = {1532-4435},
abstract = {We introduce a new neural network model, together with a tractable and monotone online learning algorithm. Our model describes feed-forward networks for classification, with one output node for each class. The only nonlinear operation is rectification using a ReLU function with a bias. However, there is a rectifier on every edge rather than at the nodes of the network. There are also weights, but these are positive, static, and associated with the nodes. Our rectified wire networks are able to represent arbitrary Boolean functions. Only the bias parameters, on the edges of the network, are learned. Another departure in our approach, from standard neural networks, is that the loss function is replaced by a constraint. This constraint is simply that the value of the output node associated with the correct class should be zero. Our model has the property that the exact norm-minimizing parameter update, required to correctly classify a training item, is the solution to a quadratic program that can be computed with a few passes through the network. We demonstrate a training algorithm using this update, called sequential deactivation (SDA), on MNIST and some synthetic datasets. Upon adopting a natural choice for the nodal weights, SDA has no hyperparameters other than those describing the network structure. Our experiments explore behavior with respect to network size and depth in a family of sparse expander networks.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {931–972},
numpages = {42},
keywords = {rectified linear unit, neural networks, online training algorithms}
}

@article{10.5555/3322706.3322732,
author = {Kossaifi, Jean and Panagakis, Yannis and Anandkumar, Anima and Pantic, Maja},
title = {TensorLy: Tensor Learning in Python},
year = {2019},
issue_date = {January 2019},
publisher = {JMLR.org},
volume = {20},
number = {1},
issn = {1532-4435},
abstract = {Tensors are higher-order extensions of matrices. While matrix methods form the cornerstone of traditional machine learning and data analysis, tensor methods have been gaining increasing traction. However, software support for tensor operations is not on the same footing. In order to bridge this gap, we have developed TensorLy, a Python library that provides a high-level API for tensor methods and deep tensorized neural networks. TensorLy aims to follow the same standards adopted by the main projects of the Python scientific community, and to seamlessly integrate with them. Its BSD license makes it suitable for both academic and commercial applications. TensorLy's backend system allows users to perform computations with several libraries such as NumPy or PyTorch to name but a few. They can be scaled on multiple CPU or GPU machines. In addition, using the deep-learning frameworks as backend allows to easily design and train deep tensorized neural networks. TensorLy is available at https://github.com/tensorly/tensorly},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {925–930},
numpages = {6}
}

@article{10.5555/3322706.3322731,
author = {Bietti, Alberto and Mairal, Julien},
title = {Group Invariance, Stability to Deformations, and Complexity of Deep Convolutional Representations},
year = {2019},
issue_date = {January 2019},
publisher = {JMLR.org},
volume = {20},
number = {1},
issn = {1532-4435},
abstract = {The success of deep convolutional architectures is often attributed in part to their ability to learn multiscale and invariant representations of natural signals. However, a precise study of these properties and how they affect learning guarantees is still missing. In this paper, we consider deep convolutional representations of signals; we study their invariance to translations and to more general groups of transformations, their stability to the action of diffeomorphisms, and their ability to preserve signal information. This analysis is carried by introducing a multilayer kernel based on convolutional kernel networks and by studying the geometry induced by the kernel mapping. We then characterize the corresponding reproducing kernel Hilbert space (RKHS), showing that it contains a large class of convolutional neural networks with homogeneous activation functions. This analysis allows us to separate data representation from learning, and to provide a canonical measure of model complexity, the RKHS norm, which controls both stability and generalization of any learned model. In addition to models in the constructed RKHS, our stability analysis also applies to convolutional networks with generic activations such as rectified linear units, and we discuss its relationship with recent generalization bounds based on spectral norms.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {876–924},
numpages = {49},
keywords = {kernel methods, invariant representations, stability, deep learning}
}

@article{10.5555/3322706.3322730,
author = {Ferrer, Luciana and McLaren, Mitchell},
title = {Joint PLDA for Simultaneous Modeling of Two Factors},
year = {2019},
issue_date = {January 2019},
publisher = {JMLR.org},
volume = {20},
number = {1},
issn = {1532-4435},
abstract = {Probabilistic linear discriminant analysis (PLDA) is a method used for biometric problems like speaker or face recognition that models the variability of the samples using two latent variables, one that depends on the class of the sample and another one that is assumed independent across samples and models the within-class variability. In this work, we propose a generalization of PLDA that enables joint modeling of two sample-dependent factors: the class of interest and a nuisance condition. The approach does not change the basic form of PLDA but rather modifies the training procedure to consider the dependency across samples of the latent variable that models within-class variability. While the identity of the nuisance condition is needed during training, it is not needed during testing since we propose a scoring procedure that marginalizes over the corresponding latent variable. We show results on a multilingual speaker-verification task, where the language spoken is considered a nuisance condition. The proposed joint PLDA approach leads to significant performance gains in this task for two different data sets, in particular when the training data contains mostly or only monolingual speakers.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {847–875},
numpages = {29},
keywords = {probabilistic linear discriminant analysis, factor analysis, speaker recognition, robustness to acoustic conditions, language variability}
}

@article{10.5555/3322706.3322729,
author = {Shi, Chengchun and Lu, Wenbin and Song, Rui},
title = {Determining the Number of Latent Factors in Statistical Multi-Relational Learning},
year = {2019},
issue_date = {January 2019},
publisher = {JMLR.org},
volume = {20},
number = {1},
issn = {1532-4435},
abstract = {Statistical relational learning is primarily concerned with learning and inferring relationships between entities in large-scale knowledge graphs. Nickel et al. (2011) proposed a RESCAL tensor factorization model for statistical relational learning, which achieves better or at least comparable results on common benchmark data sets when compared to other state-of-the-art methods. Given a positive integer s, RESCAL computes an s-dimensional latent vector for each entity. The latent factors can be further used for solving relational learning tasks, such as collective classification, collective entity resolution and link-based clustering.The focus of this paper is to determine the number of latent factors in the RESCAL model. Due to the structure of the RESCAL model, its log-likelihood function is not concave. As a result, the corresponding maximum likelihood estimators (MLEs) may not be consistent. Nonetheless, we design a specific pseudometric, prove the consistency of the MLEs under this pseudometric and establish its rate of convergence. Based on these results, we propose a general class of information criteria and prove their model selection consistencies when the number of relations is either bounded or diverges at a proper rate of the number of entities. Simulations and real data examples show that our proposed information criteria have good finite sample properties.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {809–846},
numpages = {38},
keywords = {RESCAL model, information criteria, knowledge graph, statistical relational learning, model selection consistency, tensor factorization}
}

@article{10.5555/3322706.3322728,
author = {Shen, Yanning and Chen, Tianyi and Giannakis, Georgios B.},
title = {Random Feature-Based Online Multi-Kernel Learning in Environments with Unknown Dynamics},
year = {2019},
issue_date = {January 2019},
publisher = {JMLR.org},
volume = {20},
number = {1},
issn = {1532-4435},
abstract = {Kernel-based methods exhibit well-documented performance in various nonlinear learning tasks. Most of them rely on a preselected kernel, whose prudent choice presumes task-specific prior information. Especially when the latter is not available, multikernel learning has gained popularity thanks to its "exibility in choosing kernels from a prescribed kernel dictionary. Leveraging the random feature approximation and its recent orthogonality-promoting variant, the present contribution develops a scalable multikernel learning scheme (termed Raker) to obtain the sought nonlinear learning function 'on the fly,' first for static environments. To further boost performance in dynamic environments, an adaptive multi-kernel learning scheme (termed AdaRaker) is developed. AdaRaker accounts not only for data-driven learning of kernel combination, but also for the unknown dynamics. Performance is analyzed in terms of both static and dynamic regrets. AdaRaker is uniquely capable of tracking nonlinear learning functions in environments with unknown dynamics, and with with analytic performance guarantees. Tests with synthetic and real datasets are carried out to showcase the effectiveness of the novel algorithms.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {773–808},
numpages = {36},
keywords = {dynamic and adversarial environments, online learning, reproducing kernel Hilbert space, multi-kernel learning, random features}
}

@article{10.5555/3322706.3322727,
author = {Khetan, Ashish and Oh, Sewoong},
title = {Spectrum Estimation from a Few Entries},
year = {2019},
issue_date = {January 2019},
publisher = {JMLR.org},
volume = {20},
number = {1},
issn = {1532-4435},
abstract = {Singular values of a data in a matrix form provide insights on the structure of the data, the effective dimensionality, and the choice of hyper-parameters on higher-level data analysis tools. However, in many practical applications such as collaborative filtering and network analysis, we only get a partial observation. Under such scenarios, we consider the fundamental problem of recovering spectral properties of the underlying matrix from a sampling of its entries. In this paper, we address the problem of directly recovering the spectrum, which is the set of singular values, and also in sample-efficient approaches for recovering a spectral sum function, which is an aggregate sum of a fixed function applied to each of the singular values. Our approach is to first estimate the Schatten k-norms of a matrix for a small set of values of k, and then apply Chebyshev approximation when estimating a spectral sum function or apply moment matching in Wasserstein distance when estimating the singular values directly. The main technical challenge is in accurately estimating the Schatten norms from a sampling of a matrix. We introduce a novel unbiased estimator based on counting small structures called network motifs in a graph and provide guarantees that match its empirical performance. Our theoretical analysis shows that Schatten norms can be recovered accurately from strictly smaller number of samples compared to what is needed to recover the underlying low-rank matrix. Numerical experiments suggest that we significantly improve upon a competing approach of using matrix completion methods, below the matrix completion threshold, above which matrix completion algorithms recover the underlying low-rank matrix exactly.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {718–772},
numpages = {55},
keywords = {spectrum estimation, counting subgraphs, matrix completion}
}

@article{10.5555/3322706.3322726,
author = {Cai, HanQin and Cai, Jian-Feng and Wei, Ke},
title = {Accelerated Alternating Projections for Robust Principal Component Analysis},
year = {2019},
issue_date = {January 2019},
publisher = {JMLR.org},
volume = {20},
number = {1},
issn = {1532-4435},
abstract = {We study robust PCA for the fully observed setting, which is about separating a low rank matrix L and a sparse matrix S from their sum D = L + S. In this paper, a new algorithm, dubbed accelerated alternating projections, is introduced for robust PCA which significantly improves the computational efficiency of the existing alternating projections proposed in (Netrapalli et al., 2014) when updating the low rank factor. The acceleration is achieved by first projecting a matrix onto some low dimensional subspace before obtaining a new estimate of the low rank matrix via truncated SVD. Exact recovery guarantee has been established which shows linear convergence of the proposed algorithm. Empirical performance evaluations establish the advantage of our algorithm over other state-of-the-art algorithms for robust PCA.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {685–717},
numpages = {33},
keywords = {alternating projections, subspace projection, matrix manifold, tangent space, robust PCA}
}

@article{10.5555/3322706.3322725,
author = {Rodrigo, Enrique G. and Aledo, Juan A. and G\'{a}mez, Jos\'{e} A.},
title = {Spark-Crowd: A Spark Package for Learning from Crowdsourced Big Data},
year = {2019},
issue_date = {January 2019},
publisher = {JMLR.org},
volume = {20},
number = {1},
issn = {1532-4435},
abstract = {As the data sets increase in size, the process of manually labeling data becomes unfeasible by small groups of experts. Thus, it is common to rely on crowdsourcing platforms which provide inexpensive, but noisy, labels. Although implementations of algorithms to tackle this problem exist, none of them focus on scalability, limiting the area of application to relatively small data sets. In this paper, we present spark-crowd, an Apache Spark package for learning from crowdsourced data with scalability in mind.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {680–684},
numpages = {5},
keywords = {spark, crowdsourced data, learning from crowds, big data, crowdsourcing, multiple noisy labeling}
}

@article{10.5555/3322706.3322724,
author = {G\'{a}miz, Mar\'{\i}a Luz and Mart\'{\i}nez-Miranda, Mar\'{\i}a Dolores and Nielsen, Jens Perch},
title = {Multiplicative Local Linear Hazard Estimation and Best One-Sided Cross-Validation},
year = {2019},
issue_date = {January 2019},
publisher = {JMLR.org},
volume = {20},
number = {1},
issn = {1532-4435},
abstract = {This paper develops detailed mathematical statistical theory of a new class of cross-validation techniques of local linear kernel hazards and their multiplicative bias corrections. The new class of cross-validation combines principles of local information and recent advances in indirect cross-validation. A few applications of cross-validating multiplicative kernel hazard estimation do exist in the literature. However, detailed mathematical statistical theory and small sample performance are introduced via this paper and further upgraded to our new class of best one-sided cross-validation. Best one-sided cross-validation turns out to have excellent performance in its practical illustrations, in its small sample performance and in its mathematical statistical theoretical performance.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {651–650},
numpages = {29},
keywords = {multiplicative bias correction, indirect cross-validation, Aalen's multiplicative model, bandwidth}
}

@article{10.5555/3322706.3322723,
author = {Cesa-Bianchi, Nicol\`{o} and Gentile, Claudio and Mansour, Yishay},
title = {Delay and Cooperation in Nonstochastic Bandits},
year = {2019},
issue_date = {January 2019},
publisher = {JMLR.org},
volume = {20},
number = {1},
issn = {1532-4435},
abstract = {We study networks of communicating learning agents that cooperate to solve a common nonstochastic bandit problem. Agents use an underlying communication network to get messages about actions selected by other agents, and drop messages that took more than d hops to arrive, where d is a delay parameter. We introduce Exp3-Coop, a cooperative version of the Exp3 algorithm and prove that with K actions and N agents the average per-agent regret after T rounds is at most of order √(d + 1 + K/N α≤d)(T ln K), where α≤d is the independence number of the d-th power of the communication graph G. We then show that for any connected graph, for d = √K the regret bound is K1/4√T, strictly better than the minimax regret √KT for noncooperating agents. More informed choices of d lead to bounds which are arbitrarily close to the full information minimax regret √T ln K when G is dense. When G has sparse components, we show that a variant of Exp3-Coop, allowing agents to choose their parameters according to their centrality in G, strictly improves the regret. Finally, as a by-product of our analysis, we provide the first characterization of the minimax regret for bandit learning with delay.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {613–650},
numpages = {38},
keywords = {regret minimization, multi-armed bandits, distributed learning, cooperative multi-agent systems, local communication}
}

@article{10.5555/3322706.3322722,
author = {Dai, Ben and Wang, Junhui and Shen, Xiaotong and Qu, Annie},
title = {Smooth Neighborhood Recommender Systems},
year = {2019},
issue_date = {January 2019},
publisher = {JMLR.org},
volume = {20},
number = {1},
issn = {1532-4435},
abstract = {Recommender systems predict users' preferences over a large number of items by pooling similar information from other users and/or items in the presence of sparse observations. One major challenge is how to utilize user-item specific covariates and networks describing user-item interactions in a high-dimensional situation, for accurate personalized prediction. In this article, we propose a smooth neighborhood recommender in the framework of the latent factor models. A similarity kernel is utilized to borrow neighborhood information from continuous covariates over a user-item specific network, such as a user's social network, where the grouping information defined by discrete covariates is also integrated through the network. Consequently, user-item specific information is built into the recommender to battle the "cold-start" issue in the absence of observations in collaborative and content-based filtering. Moreover, we utilize a "divide-and-conquer" version of the alternating least squares algorithm to achieve scalable computation, and establish asymptotic results for the proposed method, demonstrating that it achieves superior prediction accuracy. Finally, we illustrate that the proposed method improves substantially over its competitors in simulated examples and real benchmark data-Last.fm music data.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {589–612},
numpages = {24},
keywords = {singular value decomposition, Kernel smoothing, social networks, blockwise coordinate decent, cold-start, neighborhood, personalized prediction}
}

@article{10.5555/3322706.3322721,
author = {Campbell, Trevor and Broderick, Tamara},
title = {Automated Scalable Bayesian Inference via Hilbert Coresets},
year = {2019},
issue_date = {January 2019},
publisher = {JMLR.org},
volume = {20},
number = {1},
issn = {1532-4435},
abstract = {The automation of posterior inference in Bayesian data analysis has enabled experts and nonexperts alike to use more sophisticated models, engage in faster exploratory modeling and analysis, and ensure experimental reproducibility. However, standard automated posterior inference algorithms are not tractable at the scale of massive modern data sets, and modifications to make them so are typically model-specific, require expert tuning, and can break theoretical guarantees on inferential quality. Building on the Bayesian coresets framework, this work instead takes advantage of data redundancy to shrink the data set itself as a preprocessing step, providing fully-automated, scalable Bayesian inference with theoretical guarantees. We begin with an intuitive reformulation of Bayesian coreset construction as sparse vector sum approximation, and demonstrate that its automation and performance-based shortcomings arise from the use of the supremum norm. To address these shortcomings we develop Hilbert coresets, i.e., Bayesian coresets constructed under a norm induced by an inner-product on the log-likelihood function space. We propose two Hilbert coreset construction algorithms--one based on importance sampling, and one based on the Frank-Wolfe algorithm--along with theoretical guarantees on approximation quality as a function of coreset size. Since the exact computation of the proposed inner-products is model-specific, we automate the construction with a random finite-dimensional projection of the log-likelihood functions. The resulting automated coreset construction algorithm is simple to implement, and experiments on a variety of models with real and synthetic data sets show that it provides high-quality posterior approximations and a significant reduction in the computational cost of inference.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {551–588},
numpages = {38},
keywords = {scalable, bayesian inference, automated, hilbert, coreset, frank-wolfe}
}

@article{10.5555/3322706.3322720,
author = {Gr\"{u}new\"{a}lder, Steffen and Khaleghi, Azadeh},
title = {Approximations of the Restless Bandit Problem},
year = {2019},
issue_date = {January 2019},
publisher = {JMLR.org},
volume = {20},
number = {1},
issn = {1532-4435},
abstract = {The multi-armed restless bandit problem is studied in the case where the pay-off distributions are stationary φ-mixing. This version of the problem provides a more realistic model for most real-world applications, but cannot be optimally solved in practice, since it is known to be PSPACE-hard. The objective of this paper is to characterize a sub-class of the problem where good approximate solutions can be found using tractable approaches. Specifically, it is shown that under some conditions on the φ-mixing coefficients, a modified version of UCB can prove effective. The main challenge is that, unlike in the i.i.d. setting, the distributions of the sampled pay-offs may not have the same characteristics as those of the original bandit arms. In particular, the φ-mixing property does not necessarily carry over. This is overcome by carefully controlling the effect of a sampling policy on the pay-off distributions. Some of the proof techniques developed in this paper can be more generally used in the context of online sampling under dependence. Proposed algorithms are accompanied with corresponding regret analysis.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {514–550},
numpages = {37}
}

@article{10.5555/3322706.3322719,
author = {Meshi, Ofer and London, Ben and Weller, Adrian and Sontag, David},
title = {Train and Test Tightness of LP Relaxations in Structured Prediction},
year = {2019},
issue_date = {January 2019},
publisher = {JMLR.org},
volume = {20},
number = {1},
issn = {1532-4435},
abstract = {Structured prediction is used in areas including computer vision and natural language processing to predict structured outputs such as segmentations or parse trees. In these settings, prediction is performed by MAP inference or, equivalently, by solving an integer linear program. Because of the complex scoring functions required to obtain accurate predictions, both learning and inference typically require the use of approximate solvers. We propose a theoretical explanation for the striking observation that approximations based on linear programming (LP) relaxations are often tight (exact) on real-world instances. In particular, we show that learning with LP relaxed inference encourages integrality of training instances, and that this training tightness generalizes to test data.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {480–513},
numpages = {34}
}

@article{10.5555/3322706.3322718,
author = {Wang, Shusen and Gittens, Alex and Mahoney, Michael W.},
title = {Scalable Kernel K-Means Clustering with Nystr\"{o}m Approximation: Relative-Error Bounds},
year = {2019},
issue_date = {January 2019},
publisher = {JMLR.org},
volume = {20},
number = {1},
issn = {1532-4435},
abstract = {Kernel k-means clustering can correctly identify and extract a far more varied collection of cluster structures than the linear k-means clustering algorithm. However, kernel k- means clustering is computationally expensive when the non-linear feature map is high-dimensional and there are many input points.Kernel approximation, e.g., the Nystr\"{o}m method, has been applied in previous works to approximately solve kernel learning problems when both of the above conditions are present. This work analyzes the application of this paradigm to kernel k-means clustering, and shows that applying the linear k-means clustering algorithm to k/ε (1 + o(1)) features constructed using a so-called rank-restricted Nystr\"{o}m approximation results in cluster assignments that satisfy a 1+ε approximation ratio in terms of the kernel k-means cost function, relative to the guarantee provided by the same algorithm without the use of the Nystr\"{o}m method. As part of the analysis, this work establishes a novel 1+ε relative-error trace norm guarantee for low-rank approximation using the rank-restricted Nystr\"{o}m approximation.Empirical evaluations on the 8:1 million instance MNIST8M dataset demonstrate the scalability and usefulness of kernel k-means clustering with Nystr\"{o}m approximation. This work argues that spectral clustering using Nystr\"{o}m approximation--a popular and computationally efficient, but theoretically unsound approach to non-linear clustering-- should be replaced with the efficient and theoretically sound combination of kernel k-means clustering with Nystr\"{o}m approximation. The superior performance of the latter approach is empirically verified.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {431–479},
numpages = {49},
keywords = {the Nystr\"{o}m method, randomized linear algebra, kernel k-means clustering}
}

@article{10.5555/3322706.3322717,
author = {Ahsen, Mehmet Eren and Vidyasagar, Mathukumalli},
title = {An Approach to One-Bit Compressed Sensing Based on Probably Approximately Correct Learning Theory},
year = {2019},
issue_date = {January 2019},
publisher = {JMLR.org},
volume = {20},
number = {1},
issn = {1532-4435},
abstract = {In this paper, the problem of one-bit compressed sensing (OBCS) is formulated as a problem in probably approximately correct (PAC) learning. It is shown that the Vapnik-Chervonenkis (VC-) dimension of the set of half-spaces in ℝn generated by k-sparse vectors is bounded below by k(⌊lg(n=k)⌋+1) and above by ⌊2k lg(en)⌋. By coupling this estimate with well-established results in PAC learning theory, we show that a consistent algorithm can recover a k-sparse vector with O(k lg n) measurements, given only the signs of the measurement vector. This result holds for all probability measures on ℝn. The theory is also applicable to the case of noisy labels, where the signs of the measurements are flipped with some unknown probability.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {408–430},
numpages = {23}
}

@article{10.5555/3322706.3322716,
author = {Fattahi, Salar and Sojoudi, Somayeh},
title = {Graphical Lasso and Thresholding: Equivalence and Closed-Form Solutions},
year = {2019},
issue_date = {January 2019},
publisher = {JMLR.org},
volume = {20},
number = {1},
issn = {1532-4435},
abstract = {Graphical Lasso (GL) is a popular method for learning the structure of an undirected graphical model, which is based on an l1 regularization technique. The objective of this paper is to compare the computationally-heavy GL technique with a numerically-cheap heuristic method that is based on simply thresholding the sample covariance matrix. To this end, two notions of sign-consistent and inverse-consistent matrices are developed, and then it is shown that the thresholding and GL methods are equivalent if: (i) the thresholded sample covariance matrix is both sign-consistent and inverse-consistent, and (ii) the gap between the largest thresholded and the smallest un-thresholded entries of the sample covariance matrix is not too small. By building upon this result, it is proved that the GL method-- as a conic optimization problem--has an explicit closed-form solution if the thresholded sample covariance matrix has an acyclic structure. This result is then generalized to arbitrary sparse support graphs, where a formula is found to obtain an approximate solution of GL. Furthermore, it is shown that the approximation error of the derived explicit formula decreases exponentially fast with respect to the length of the minimum-length cycle of the sparsity graph. The developed results are demonstrated on synthetic data, functional MRI data, traffic flows for transportation networks, and massive randomly generated data sets. We show that the proposed method can obtain an accurate approximation of the GL for instances with the sizes as large as 80, 000 \texttimes{} 80, 000 (more than 3.2 billion variables) in less than 30 minutes on a standard laptop computer running MATLAB, while other state-of-the-art methods do not converge within 4 hours.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {364–407},
numpages = {44},
keywords = {graphical lasso, sparse graphs, graphical model, optimization}
}

@article{10.5555/3322706.3322715,
author = {Javanmard, Adel and Nazerzadeh, Hamid},
title = {Dynamic Pricing in High-Dimensions},
year = {2019},
issue_date = {January 2019},
publisher = {JMLR.org},
volume = {20},
number = {1},
issn = {1532-4435},
abstract = {We study the pricing problem faced by a firm that sells a large number of products, described via a wide range of features, to customers that arrive over time. Customers independently make purchasing decisions according to a general choice model that includes products features and customers' characteristics, encoded as d-dimensional numerical vectors, as well as the price offered. The parameters of the choice model are a priori unknown to the firm, but can be learned as the (binary-valued) sales data accrues over time. The firm's objective is to maximize its revenue. We benchmark the performance using the classic regret minimization framework where the regret is defined as the expected revenue loss against a clairvoyant policy that knows the parameters of the choice model in advance, and always offers the revenue-maximizing price. This setting is motivated in part by the prevalence of online marketplaces that allow for real-time pricing.We assume a structured choice model, parameters of which depend on s0 out of the d product features. Assuming that the market noise distribution is known, we propose a dynamic policy, called Regularized Maximum Likelihood Pricing (RMLP) that leverages the (sparsity) structure of the high-dimensional model and obtains a logarithmic regret in T. More specifically, the regret of our algorithm is of O(s0 log d · log T). Furthermore, we show that no policy can obtain regret better than O(s0(log d + log T)). In addition, we propose a generalization of our policy to a setting that the market noise distribution is unknown but belongs to a parametrized family of distributions. This policy obtains regret of O(√(log d)T). We further show that no policy can obtain regret better than Ω(√T) in such environments.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {315–363},
numpages = {49},
keywords = {maximum likelihood, regret, high-dimensional regression, revenue management, sparsity, dynamic pricing}
}

@article{10.5555/3322706.3322714,
author = {Borboudakis, Giorgos and Tsamardinos, Ioannis},
title = {Forward-Backward Selection with Early Dropping},
year = {2019},
issue_date = {January 2019},
publisher = {JMLR.org},
volume = {20},
number = {1},
issn = {1532-4435},
abstract = {Forward-backward selection is one of the most basic and commonly-used feature selection algorithms available. It is also general and conceptually applicable to many different types of data. In this paper, we propose a heuristic that significantly improves its running time, while preserving predictive performance. The idea is to temporarily discard the variables that are conditionally independent with the outcome given the selected variable set. Depending on how those variables are reconsidered and reintroduced, this heuristic gives rise to a family of algorithms with increasingly stronger theoretical guarantees. In distributions that can be faithfully represented by Bayesian networks or maximal ancestral graphs, members of this algorithmic family are able to correctly identify the Markov blanket in the sample limit. In experiments we show that the proposed heuristic increases computational efficiency by about 1-2 orders of magnitude, while selecting fewer or the same number of variables and retaining predictive performance. Furthermore, we show that the proposed algorithm and feature selection with LASSO perform similarly when restricted to select the same number of variables, making the proposed algorithm an attractive alternative for problems where no (efficient) algorithm for LASSO exists.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {276–314},
numpages = {39},
keywords = {Markov blanket discovery, Bayesian networks, maximal ancestral graphs, forward selection, feature selection}
}

@article{10.5555/3322706.3322713,
author = {Erdogdu, Murat A. and Bayati, Mohsen and Dicker, Lee H.},
title = {Scalable Approximations for Generalized Linear Problems},
year = {2019},
issue_date = {January 2019},
publisher = {JMLR.org},
volume = {20},
number = {1},
issn = {1532-4435},
abstract = {In stochastic optimization, the population risk is generally approximated by the empirical risk which is in turn minimized by an iterative algorithm. However, in the large-scale setting, empirical risk minimization may be computationally restrictive. In this paper, we design an efficient algorithm to approximate the population risk minimizer in generalized linear problems such as binary classification with surrogate losses and generalized linear regression models. We focus on large-scale problems where the iterative minimization of the empirical risk is computationally intractable, i.e., the number of observations n is much larger than the dimension of the parameter p (n ≫ p ≫ 1). We show that under random sub-Gaussian design, the true minimizer of the population risk is approximately proportional to the corresponding ordinary least squares (OLS) estimator. Using this relation, we design an algorithm that achieves the same accuracy as the empirical risk minimizer through iterations that attain up to a quadratic convergence rate, and that are computationally cheaper than any batch optimization algorithm by at least a factor of O(p). We provide theoretical guarantees for our algorithm, and analyze the convergence behavior in terms of data dimensions. Finally, we demonstrate the performance of our algorithm on well-known classification and regression problems, through extensive numerical studies on large-scale datasets, and show that it achieves the highest performance compared to several other widely used optimization algorithms.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {231–275},
numpages = {45},
keywords = {subsampling, stochastic optimization, dimension reduction in optimization, generalized linear problems}
}

@article{10.5555/3322706.3322712,
author = {Szymanski, Piotr and Kajdanowicz, Tomasz},
title = {Scikit-Multilearn: A Scikit-Based Python Environment for Performing Multi-Label Classification},
year = {2019},
issue_date = {January 2019},
publisher = {JMLR.org},
volume = {20},
number = {1},
issn = {1532-4435},
abstract = {The scikit-multilearn is a Python library for performing multi-label classification. It is compatible with the scikit-learn and scipy ecosystems and uses sparse matrices for all internal operations; provides native Python implementations of popular multi-label classification methods alongside a novel framework for label space partitioning and division and includes modern algorithm adaptation methods, network-based label space division approaches, which extracts label dependency information and multi-label embedding classifiers. The library provides Python wrapped access to the extensive multi-label method stack from Java libraries and makes it possible to extend deep learning single-label methods for multilabel tasks. The library allows multi-label stratification and data set management. The implementation is more efficient in problem transformation than other established libraries, has good test coverage and follows PEP8. Source code and documentation can be downloaded from http://scikit.ml and also via pip. The project is BSD-licensed.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {209–230},
numpages = {22},
keywords = {label-space clustering, multi-label embedding, multi-label classification, multi-label stratification, Python}
}

@article{10.5555/3322706.3322711,
author = {Chen, Han and Raskutti, Garvesh and Yuan, Ming},
title = {Non-Convex Projected Gradient Descent for Generalized Low-Rank Tensor Regression},
year = {2019},
issue_date = {January 2019},
publisher = {JMLR.org},
volume = {20},
number = {1},
issn = {1532-4435},
abstract = {In this paper, we consider the problem of learning high-dimensional tensor regression problems with low-rank structure. One of the core challenges associated with learning high-dimensional models is computation since the underlying optimization problems are often non-convex. While convex relaxations could lead to polynomial-time algorithms they are often slow in practice. On the other hand, limited theoretical guarantees exist for nonconvex methods. In this paper we provide a general framework that provides theoretical guarantees for learning high-dimensional tensor regression models under different low-rank structural assumptions using the projected gradient descent algorithm applied to a potentially non-convex constraint set Θ in terms of its localized Gaussian width (due to Gaussian design). We juxtapose our theoretical results for non-convex projected gradient descent algorithms with previous results on regularized convex approaches. The two main differences between the convex and non-convex approach are: (i) from a computational perspective whether the non-convex projection operator is computable and whether the projection has desirable contraction properties and (ii) from a statistical error bound perspective, the non-convex approach has a superior rate for a number of examples. We provide three concrete examples of low-dimensional structure which address these issues and explain the pros and cons for the non-convex and convex approaches. We supplement our theoretical results with simulations which show that, under several common settings of generalized low rank tensor regression, the projected gradient descent approach is superior both in terms of statistical error and run-time provided the step-sizes of the projected descent algorithm are suitably chosen.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {172–208},
numpages = {37},
keywords = {non-convex optimization, low-rank, high-dimensional regression, tensors}
}

@article{10.5555/3322706.3322710,
author = {Bouttier, Cl\'{e}ment and Gavra, Ioana},
title = {Convergence Rate of a Simulated Annealing Algorithm with Noisy Observations},
year = {2019},
issue_date = {January 2019},
publisher = {JMLR.org},
volume = {20},
number = {1},
issn = {1532-4435},
abstract = {In this paper we propose a modified version of the simulated annealing algorithm for solving a stochastic global optimization problem. More precisely, we address the problem of finding a global minimizer of a function with noisy evaluations. We provide a rate of convergence and its optimized parametrization to ensure a minimal number of evaluations for a given accuracy and a confidence level close to 1. This work is completed with a set of numerical experimentations and assesses the practical performance both on benchmark test cases and on real world examples.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {127–171},
numpages = {45},
keywords = {simulated annealing, Markov process, aircraft trajectory optimization, stochastic optimization, convergence rate}
}

@article{10.5555/3322706.3322709,
author = {Koppel, Alec and Warnell, Garrett and Stump, Ethan and Ribeiro, Alejandro},
title = {Parsimonious Online Learning with Kernels via Sparse Projections in Function Space},
year = {2019},
issue_date = {January 2019},
publisher = {JMLR.org},
volume = {20},
number = {1},
issn = {1532-4435},
abstract = {Despite their attractiveness, popular perception is that techniques for nonparametric function approximation do not scale to streaming data due to an intractable growth in the amount of storage they require. To solve this problem in a memory-affordable way, we propose an online technique based on functional stochastic gradient descent in tandem with supervised sparsification based on greedy function subspace projections. The method, called parsimonious online learning with kernels (POLK), provides a controllable tradeoff between its solution accuracy and the amount of memory it requires. We derive conditions under which the generated function sequence converges almost surely to the optimal function, and we establish that the memory requirement remains finite. We evaluate POLK for kernel multi-class logistic regression and kernel hinge-loss classification on three canonical data sets: a synthetic Gaussian mixture model, the MNIST hand-written digits, and the Brodatz texture database. On all three tasks, we observe a favorable trade-off of objective function evaluation, classification performance, and complexity of the nonparametric regressor extracted by the proposed method.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {83–126},
numpages = {44},
keywords = {stochastic optimization, online learning, kernel methods, nonparametric regression, supervised learning, orthogonal matching pursuit}
}

@article{10.5555/3322706.3322708,
author = {Sonoda, Sho and Murata, Noboru},
title = {Transport Analysis of Infinitely Deep Neural Network},
year = {2019},
issue_date = {January 2019},
publisher = {JMLR.org},
volume = {20},
number = {1},
issn = {1532-4435},
abstract = {We investigated the feature map inside deep neural networks (DNNs) by tracking the transport map. We are interested in the role of depth--why do DNNs perform better than shallow models?--and the interpretation of DNNs--what do intermediate layers do? Despite the rapid development in their application, DNNs remain analytically unexplained because the hidden layers are nested and the parameters are not faithful. Inspired by the integral representation of shallow NNs, which is the continuum limit of the width, or the hidden unit number, we developed the flow representation and transport analysis of DNNs. The flow representation is the continuum limit of the depth, or the hidden layer number, and it is specified by an ordinary differential equation (ODE) with a vector field. We interpret an ordinary DNN as a transport map or an Euler broken line approximation of the flow. Technically speaking, a dynamical system is a natural model for the nested feature maps. In addition, it opens a new way to the coordinate-free treatment of DNNs by avoiding the redundant parametrization of DNNs. Following Wasserstein geometry, we analyze a flow in three aspects: dynamical system, continuity equation, and Wasserstein gradient flow. A key finding is that we specified a series of transport maps of the denoising autoencoder (DAE), which is a cornerstone for the development of deep learning. Starting from the shallow DAE, this paper develops three topics: the transport map of the deep DAE, the equivalence between the stacked DAE and the composition of DAEs, and the development of the double continuum limit or the integral representation of the flow representation. As partial answers to the research questions, we found that deeper DAEs converge faster and the extracted features are better; in addition, a deep Gaussian DAE transports mass to decrease the Shannon entropy of the data distribution. We expect that further investigations on these questions lead to the development of an interpretable and principled alternatives to DNNs.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {31–82},
numpages = {52},
keywords = {flow representation, denoising autoencoder, Wasserstein geometry, backward heat equation, representation learning, continuum limit, ridgelet analysis}
}

@article{10.5555/3322706.3322707,
author = {Cortes, Corinna and Mohri, Mehryar and Medina, Andr\'{e}s Mu\~{n}oz},
title = {Adaptation Based on Generalized Discrepancy},
year = {2019},
issue_date = {January 2019},
publisher = {JMLR.org},
volume = {20},
number = {1},
issn = {1532-4435},
abstract = {We present a new algorithm for domain adaptation improving upon a discrepancy minimization algorithm, (DM), previously shown to outperform a number of algorithms for this problem. Unlike many previously proposed solutions for domain adaptation, our algorithm does not consist of a fixed reweighting of the losses over the training sample. Instead, the reweighting depends on the hypothesis sought. The algorithm is derived from a less conservative notion of discrepancy than the DM algorithm called generalized discrepancy. We present a detailed description of our algorithm and show that it can be formulated as a convex optimization problem. We also give a detailed theoretical analysis of its learning guarantees which helps us select its parameters. Finally, we report the results of experiments demonstrating that it improves upon discrepancy minimization.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1–30},
numpages = {30},
keywords = {learning theory, domain adaptation}
}

@article{10.5555/3291125.3309646,
author = {Biecek, Przemys\l{}aw},
title = {DALEX: Explainers for Complex Predictive Models in R},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {Predictive modeling is invaded by elastic, yet complex methods such as neural networks or ensembles (model stacking, boosting or bagging). Such methods are usually described by a large number of parameters or hyper parameters - a price that one needs to pay for elasticity. The very number of parameters makes models hard to understand.This paper describes a consistent collection of explainers for predictive models, a.k.a. black boxes. Each explainer is a technique for exploration of a black box model. Presented approaches are model-agnostic, what means that they extract useful information from any predictive method irrespective of its internal structure. Each explainer is linked with a specific aspect of a model. Some are useful in decomposing predictions, some serve better in understanding performance, while others are useful in understanding importance and conditional responses of a particular variable.Every explainer presented here works for a single model or for a collection of models. In the latter case, models can be compared against each other. Such comparison helps to find strengths and weaknesses of different models and gives additional tools for model validation. Presented explainers are implemented in the DALEX package for R. They are based on a uniform standardized grammar of model exploration which may be easily extended.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3245–3249},
numpages = {5},
keywords = {explainable artificial intelligence, interpretable machine learning, predictive modelling, model visualization}
}

@article{10.5555/3291125.3309645,
author = {Burns, David M. and Whyne, Cari M.},
title = {Seglearn: A Python Package for Learning Sequences and Time Series},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {seglearn is an open-source Python package for performing machine learning on time series or sequences. The implementation provides a flexible pipeline for tackling classification, regression, and forecasting problems with multivariate sequence and contextual data. Sequences and series may be learned directly with deep learning models or via feature representation with classical machine learning estimators. This package is compatible with scikit-learn and is listed under scikit-learn "Related Projects". The package depends on numpy, scipy, and scikit-learn. seglearn is distributed under the BSD 3-Clause License. Documentation includes a detailed API description, user guide, and examples. Unit tests provide a high degree of code coverage. Source code and documentation can be downloaded from https://github.com/dmbee/seglearn.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3238–3244},
numpages = {7},
keywords = {machine-learning, time-series, sequences, python}
}

@article{10.5555/3291125.3309644,
author = {Tepper, Mariano and Sengupta, Anirvan M. and Chklovskii, Dmitri},
title = {Clustering is Semidefinitely Not That Hard: Nonnegative SDP for Manifold Disentangling},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {In solving hard computational problems, semidefinite program (SDP) relaxations often play an important role because they come with a guarantee of optimality. Here, we focus on a popular semidefinite relaxation of K-means clustering which yields the same solution as the nonconvex original formulation for well segregated datasets. We report an unexpected finding: when data contains (greater than zero-dimensional) manifolds, the SDP solution captures such geometrical structures. Unlike traditional manifold embedding techniques, our approach does not rely on manually defining a kernel but rather enforces locality via a nonnegativity constraint. We thus call our approach NOnnegative MAnifold Disentangling, or NOMAD. To build an intuitive understanding of its manifold learning capabilities, we develop a theoretical analysis of NOMAD on idealized datasets. While NOMAD is convex and the globally optimal solution can be found by generic SDP solvers with polynomial time complexity, they are too slow for modern datasets. To address this problem, we analyze a non-convex heuristic and present a new, convex and yet efficient, algorithm, based on the conditional gradient method. Our results render NOMAD a versatile, understandable, and powerful tool for manifold learning.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3208–3237},
numpages = {30},
keywords = {conditional gradient method, manifolds, k-means, semidefinite programming}
}

@article{10.5555/3291125.3309643,
author = {Leblond, R\'{e}mi and Pedregosa, Fabian and Lacoste-Julien, Simon},
title = {Improved Asynchronous Parallel Optimization Analysis for Stochastic Incremental Methods},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {As data sets continue to increase in size and multi-core computer architectures are developed, asynchronous parallel optimization algorithms become more and more essential to the field of Machine Learning. Unfortunately, conducting the theoretical analysis asynchronous methods is difficult, notably due to the introduction of delay and inconsistency in inherently sequential algorithms. Handling these issues often requires resorting to simplifying but unrealistic assumptions. Through a novel perspective, we revisit and clarify a subtle but important technical issue present in a large fraction of the recent convergence rate proofs for asynchronous parallel optimization algorithms, and propose a simplification of the recently introduced "perturbed iterate" framework that resolves it. We demonstrate the usefulness of our new framework by analyzing three distinct asynchronous parallel incremental optimization algorithms: HOGWILD (asynchronous SGD), KROMAGNON (asynchronous SVRG) and ASAGA, a novel asynchronous parallel version of the incremental gradient algorithm SAGA that enjoys fast linear convergence rates. We are able to both remove problematic assumptions and obtain better theoretical results. Notably, we prove that ASAGA and KROMAGNON can obtain a theoretical linear speedup on multi-core systems even without sparsity assumptions. We present results of an implementation on a 40-core architecture illustrating the practical speedups as well as the hardware overhead. Finally, we investigate the overlap constant, an ill-understood but central quantity for the theoretical analysis of asynchronous parallel algorithms. We find that it encompasses much more complexity than suggested in previous work, and often is order-of-magnitude bigger than traditionally thought.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3140–3207},
numpages = {68},
keywords = {machine learning, sparsity, asynchronous parallel, large scale, optimization}
}

@article{10.5555/3291125.3309642,
author = {Zhang, Teng and Yang, Yi},
title = {Robust PCA by Manifold Optimization},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {Robust PCA is a widely used statistical procedure to recover an underlying low-rank matrix with grossly corrupted observations. This work considers the problem of robust PCA as a nonconvex optimization problem on the manifold of low-rank matrices and proposes two algorithms based on manifold optimization. It is shown that, with a properly designed initialization, the proposed algorithms are guaranteed to converge to the underlying low-rank matrix linearly. Compared with a previous work based on the factorization of low-rank matrices Yi et al. (2016), the proposed algorithms reduce the dependence on the condition number of the underlying low-rank matrix theoretically. Simulations and real data examples confirm the competitive performance of our method.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3101–3139},
numpages = {39},
keywords = {low-rank modeling, principal component analysis, manifold of low-rank matrices}
}

@article{10.5555/3291125.3309641,
author = {Mai, Xiaoyi and Couillet, Romain},
title = {A Random Matrix Analysis and Improvement of Semi-Supervised Learning for Large Dimensional Data},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {This article provides an original understanding of the behavior of a class of graph-oriented semi-supervised learning algorithms in the limit of large and numerous data. It is demonstrated that the intuition at the root of these methods collapses in this limit and that, as a result, most of them become inconsistent. Corrective measures and a new data-driven parametrization scheme are proposed along with a theoretical analysis of the asymptotic performances of the resulting approach. A surprisingly close behavior between theoretical performances on Gaussian mixture models and on real data sets is also illustrated throughout the article, thereby suggesting the importance of the proposed analysis for dealing with practical data. As a result, significant performance gains are observed on practical data classification using the proposed parametrization.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3074–3100},
numpages = {27},
keywords = {random matrix theory, kernel methods, high dimensional statistics, semi-supervised learning}
}

@article{10.5555/3291125.3309640,
author = {Fang, Yixin and Xu, Jinfeng and Yang, Lei},
title = {Online Bootstrap Confidence Intervals for the Stochastic Gradient Descent Estimator},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {In many applications involving large dataset or online learning, stochastic gradient descent (SGD) is a scalable algorithm to compute parameter estimates and has gained increasing popularity due to its numerical convenience and memory efficiency. While the asymptotic properties of SGD-based estimators have been well established, statistical inference such as interval estimation remains much unexplored. The classical bootstrap is not directly applicable if the data are not stored in memory. The plug-in method is not applicable when there is no explicit formula for the covariance matrix of the estimator. In this paper, we propose an online bootstrap procedure for the estimation of confidence intervals, which, upon the arrival of each observation, updates the SGD estimate as well as a number of randomly perturbed SGD estimates. The proposed method is easy to implement in practice. We establish its theoretical properties for a general class of models that includes linear regressions, generalized linear models, M-estimators and quantile regressions as special cases. The finite-sample performance and numerical utility is evaluated by simulation studies and real data applications.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3053–3073},
numpages = {21},
keywords = {generalized linear models, resampling methods, stochastic gradient descent, quantile regression, interval estimation, M-estimators, large datasets, bootstrap}
}

@article{10.5555/3291125.3309639,
author = {Rohe, Karl and Tao, Jun and Han, Xintian and Binkiewicz, Norbert},
title = {A Note on Quickly Sampling a Sparse Matrix with Low Rank Expectation},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {Given matrices X;Y ε Rn\texttimes{}K and Sε RK\texttimes{}K with positive elements, this paper proposes an algorithm fastRG to sample a sparse matrix A with low rank expectation E(A)=XSYT and independent Poisson elements. This allows for quickly sampling from a broad class of stochastic blockmodel graphs (degree-corrected, mixed membership, overlapping) all of which are specific parameterizations of the generalized random product graph model defined in Section 2.2. The basic idea of fastRG is to first sample the number of edges m and then sample each edge. The key insight is that because of the the low rank expectation, it is easy to sample individual edges. The naive "element-wise" algorithm requires O(n2) operations to generate the n\texttimes{}n adjacency matrix A. In sparse graphs, where m = O(n), ignoring log terms, fastRG runs in time O(n). An implementation in R is available on github. A computational experiment in Section 2.4 simulates graphs up to n = 10;000;000 nodes with m = 100;000;000 edges. For example, on a graph with n = 500;000 and m = 5;000; 000, fastRG runs in less than one second on a 3.5 GHz Intel i5.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3040–3052},
numpages = {13},
keywords = {random dot product graph, edge exchangeable, simulation}
}

@article{10.5555/3291125.3309638,
author = {Chiang, Kai-Yang and Dhillon, Inderjit S. and Hsieh, Cho-Jui},
title = {Using Side Information to Reliably Learn Low-Rank Matrices from Missing and Corrupted Observations},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {Learning a low-rank matrix from missing and corrupted observations is a fundamental problem in many machine learning applications. However, the role of side information in low-rank matrix learning has received little attention, and most current approaches are either ad-hoc or only applicable in certain restrictive cases. In this paper, we propose a general model that exploits side information to better learn low-rank matrices from missing and corrupted observations, and show that the proposed model can be further applied to several popular scenarios such as matrix completion and robust PCA. Furthermore, we study the effect of side information on sample complexity and show that by using our model, the efficiency for learning can be improved given sufficiently informative side information. This result thus provides theoretical insight into the usefulness of side information in our model. Finally, we conduct comprehensive experiments in three real-world applications-- relationship prediction, semi-supervised clustering and noisy image classification, showing that our proposed model is able to properly exploit side information for more effective learning both in theory and practice.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {3005–3039},
numpages = {35},
keywords = {matrix completion, side information, robust PCA, low-rank matrix learning, learning from missing and corrupted observations}
}

@article{10.5555/3291125.3309637,
author = {Miasojedow, B\l{}aundefinedej and Rejchel, Wojciech},
title = {Sparse Estimation in Ising Model via Penalized Monte Carlo Methods},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {We consider a model selection problem in high-dimensional binary Markov random fields. The usefulness of the Ising model in studying systems of complex interactions has been confirmed in many papers. The main drawback of this model is the intractable norming constant that makes estimation of parameters very challenging. In the paper we propose a Lasso penalized version of the Monte Carlo maximum likelihood method. We prove that our algorithm, under mild regularity conditions, recognizes the true dependence structure of the graph with high probability. The efficiency of the proposed method is also investigated via numerical studies.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2979–3004},
numpages = {26},
keywords = {Lasso penalty, Monte Carlo Markov chain, Ising model, Markov random field, model selection}
}

@article{10.5555/3291125.3309636,
author = {Mahajan, Dhruv and Agrawal, Nikunj and Keerthi, S. Sathiya and Sellamanickam, Sundararajan and Bottou, L\'{e}on},
title = {An Efficient Distributed Learning Algorithm Based on Effective Local Functional Approximations},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {Scalable machine learning over big data is an important problem that is receiving a lot of attention in recent years. On popular distributed environments such as Hadoop running on a cluster of commodity machines, communication costs are substantial and algorithms need to be designed suitably considering those costs. In this paper we give a novel approach to the distributed training of linear classifiers (involving smooth losses and L2 regularization) that is designed to reduce the total communication costs. At each iteration, the nodes minimize locally formed approximate objective functions; then the resulting minimizers are combined to form a descent direction to move. Our approach gives a lot of freedom in the formation of the approximate objective function as well as in the choice of methods to solve them. The method is shown to have O(log(1/ε)) time convergence. The method can be viewed as an iterative parameter mixing method. A special instantiation yields a parallel stochastic gradient descent method with strong convergence. When communication times between nodes are large, our method is much faster than the Terascale method (Agarwal et al., 2011), which is a state of the art distributed solver based on the statistical query model (Chu et al., 2006) that computes function and gradient values in a distributed fashion. We also evaluate against other recent distributed methods and demonstrate superior performance of our method.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2942–2978},
numpages = {37},
keywords = {L2 regularization, example partitioning, distributed learning}
}

@article{10.5555/3291125.3309635,
author = {Burr, Michael and Gao, Shuhong and Knoll, Fiona},
title = {Optimal Bounds for Johnson-Lindenstrauss Transformations},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {In 1984, Johnson and Lindenstrauss proved that any finite set of data in a high-dimensional space can be projected to a lower-dimensional space while preserving the pairwise Euclidean distances between points up to a bounded relative error. If the desired dimension of the image is too small, however, Kane, Meka, and Nelson (2011) and Jayram and Woodruff (2013) proved that such a projection does not exist. In this paper, we provide a precise asymptotic threshold for the dimension of the image, above which, there exists a projection preserving the Euclidean distance, but, below which, there does not exist such a projection.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2920–2941},
numpages = {22},
keywords = {dimension reduction, phase transition, asymptotic threshold, Johnson-Lindenstrauss transformation}
}

@article{10.5555/3291125.3309634,
author = {Montiel, Jacob and Read, Jesse and Bifet, Albert and Abdessalem, Talel},
title = {Scikit-Multiflow: A Multi-Output Streaming Framework},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {scikit-multiflow is a framework for learning from data streams and multi-output learning in Python. Conceived to serve as a platform to encourage the democratization of stream learning research, it provides multiple state-of-the-art learning methods, data generators and evaluators for different stream learning problems, including single-output, multi-output and multi-label. scikit-multiflow builds upon popular open source frameworks including scikit-learn, MOA and MEKA. Development follows the FOSS principles. Quality is enforced by complying with PEP8 guidelines, using continuous integration and functional testing. The source code is available at https://github.com/scikit-multiflow/scikit-multiflow.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2915–2914},
numpages = {5},
keywords = {drift detection, stream data, python, multi-output, machine learning}
}

@article{10.5555/3291125.3309633,
author = {Arunachalam, Srinivasan and De Wolf, Ronald},
title = {Optimal Quantum Sample Complexity of Learning Algorithms},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {In learning theory, the VC dimension of a concept class ℒ is the most common way to measure its "richness." A fundamental result says that the number of examples needed to learn an unknown target concept c ∈ ℒ under an unknown distribution D, is tightly determined by the VC dimension d of the concept class ℒ. Specifically, in the PAC model Θ(d/ε + log(1/δ)/ε) examples are necessary and sufficient for a learner to output, with probability 1 - δ, a hypothesis h that is ε-close to the target concept c (measured under D). In the related agnostic model, where the samples need not come from a c ∈ ℒ, we know that Θ(d/ε2 + log(1/δ)/ε2) examples are necessary and sufficient to output an hypothesis h ∈ ℒ whose error is at most ε worse than the error of the best concept in ℒ.Here we analyze quantum sample complexity, where each example is a coherent quantum state. This model was introduced by Bshouty and Jackson (1999), who showed that quantum examples are more powerful than classical examples in some fixed-distribution settings. However, Atici and Servedio (2005), improved by Zhang (2010), showed that in the PAC setting (where the learner has to succeed for every distribution), quantum examples cannot be much more powerful: the required number of quantum examples is Ω(d1-ν/ε =+ d + log(1/δ)/ε) for arbitrarily small constant η ≥ 0. Our main result is that quantum and classical sample complexity are in fact equal up to constant factors in both the PAC and agnostic models. We give two proof approaches. The first is a fairly simple information-theoretic argument that yields the above two classical bounds and yields the same bounds for quantum sample complexity up to a log(d/ε) factor. We then give a second approach that avoids the log-factor loss, based on analyzing the behavior of the "Pretty Good Measurement" on the quantum state-identification problems that correspond to learning. This shows classical and quantum sample complexity are equal up to constant factors for every concept class ℒ.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2879–2878},
numpages = {36},
keywords = {PAC learning, quantum computing, sample complexity, lower bounds}
}

@article{10.5555/3291125.3309632,
author = {Soudry, Daniel and Hoffer, Elad and Nacson, Mor Shpigel and Gunasekar, Suriya and Srebro, Nathan},
title = {The Implicit Bias of Gradient Descent on Separable Data},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {We examine gradient descent on unregularized logistic regression problems, with homogeneous linear predictors on linearly separable datasets. We show the predictor converges to the direction of the max-margin (hard margin SVM) solution. The result also generalizes to other monotone decreasing loss functions with an infimum at infinity, to multi-class problems, and to training a weight layer in a deep network in a certain restricted setting. Furthermore, we show this convergence is very slow, and only logarithmic in the convergence of the loss itself. This can help explain the benefit of continuing to optimize the logistic or cross-entropy loss even after the training error is zero and the training loss is extremely small, and, as we show, even if the validation loss increases. Our methodology can also aid in understanding implicit regularization in more complex models and with other optimization methods.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2822–2878},
numpages = {57},
keywords = {implicit regularization, gradient descent, margin, logistic regression, generalization}
}

@article{10.5555/3291125.3309631,
author = {\v{S}o\v{s}i\'{c}, Adrian and Zoubir, Abdelhak M. and Rueckert, Elmar and Peters, Jan and Koeppl, Heinz},
title = {Inverse Reinforcement Learning via Nonparametric Spatio-Temporal Subgoal Modeling},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {Advances in the field of inverse reinforcement learning (IRL) have led to sophisticated inference frameworks that relax the original modeling assumption of observing an agent behavior that reflects only a single intention. Instead of learning a global behavioral model, recent IRL methods divide the demonstration data into parts, to account for the fact that different trajectories may correspond to different intentions, e.g., because they were generated by different domain experts. In this work, we go one step further: using the intuitive concept of subgoals, we build upon the premise that even a single trajectory can be explained more efficiently locally within a certain context than globally, enabling a more compact representation of the observed behavior. Based on this assumption, we build an implicit intentional model of the agent's goals to forecast its behavior in unobserved situations. The result is an integrated Bayesian prediction framework that significantly outperforms existing IRL solutions and provides smooth policy estimates consistent with the expert's plan. Most notably, our framework naturally handles situations where the intentions of the agent change over time and classical IRL algorithms fail. In addition, due to its probabilistic nature, the model can be straightforwardly applied in active learning scenarios to guide the demonstration process of the expert.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2777–2821},
numpages = {45},
keywords = {subgoal inference, Bayesian nonparametric modeling, gibbs sampling, graphical models, inverse reinforcement learning, learning from demonstration}
}

@article{10.5555/3291125.3309630,
author = {Jammalamadaka, S. Rao and Qiu, Jinwen and Ning, Ning},
title = {Multivariate Bayesian Structural Time Series Model},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {This paper deals with inference and prediction for multiple correlated time series, where one also has the choice of using a candidate pool of contemporaneous predictors for each target series. Starting with a structural model for time series, we use Bayesian tools for model fitting, prediction and feature selection, thus extending some recent works along these lines for the univariate case. The Bayesian paradigm in this multivariate setting helps the model avoid overfitting, as well as captures correlations among multiple target time series with various state components. The model provides needed flexibility in selecting a different set of components and available predictors for each target series. The cyclical component in the model can handle large variations in the short term, which may be caused by external shocks. Extensive simulations were run to investigate properties such as estimation accuracy and performance in forecasting. This was followed by an empirical study with one-step-ahead prediction on the max log return of a portfolio of stocks that involve four leading financial institutions. Both the simulation studies and the extensive empirical study confirm that this multivariate model outperforms three other benchmark models, viz. a model that treats each target series as independent, the autoregressive integrated moving average model with regression (ARIMAX), and the multivariate ARIMAX (MARIMAX) model.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2744–2776},
numpages = {33},
keywords = {feature selection, cyclical component, Bayesian model averaging, multivariate time series, estimation and prediction}
}

@article{10.5555/3291125.3309629,
author = {Donner, Christian and Opper, Manfred},
title = {Efficient Bayesian Inference of Sigmoidal Gaussian Cox Processes},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {We present an approximate Bayesian inference approach for estimating the intensity of a inhomogeneous Poisson process, where the intensity function is modelled using a Gaussian process (GP) prior via a sigmoid link function. Augmenting the model using a latent marked Poisson process and P\'{o}lya-Gamma random variables we obtain a representation of the likelihood which is conjugate to the GP prior. We estimate the posterior using a variational free-form mean field optimisation together with the framework of sparse GPs. Furthermore, as alternative approximation we suggest a sparse Laplace's method for the posterior, for which an efficient expectation-maximisation algorithm is derived to find the posterior's mode. Both algorithms compare well against exact inference obtained by a Markov Chain Monte Carlo sampler and standard variational Gauss approach solving the same model, while being one order of magnitude faster. Furthermore, the performance and speed of our method is competitive with that of another recently proposed Poisson process model based on a quadratic link function, while not being limited to GPs with squared exponential kernels and rectangular domains.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2710–2743},
numpages = {34},
keywords = {cox process, poisson process, data augmentation, variational inference, gaussian process}
}

@article{10.5555/3291125.3309628,
author = {Spantini, Alessio and Bigoni, Daniele and Marzouk, Youssef},
title = {Inference via Low-Dimensional Couplings},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {We investigate the low-dimensional structure of deterministic transformations between random variables, i.e., transport maps between probability measures. In the context of statistics and machine learning, these transformations can be used to couple a tractable "reference" measure (e.g., a standard Gaussian) with a target measure of interest. Direct simulation from the desired measure can then be achieved by pushing forward reference samples through the map. Yet characterizing such a map--e.g., representing and evaluating it--grows challenging in high dimensions. The central contribution of this paper is to establish a link between the Markov properties of the target measure and the existence of low-dimensional couplings, induced by transport maps that are sparse and/or decomposable. Our analysis not only facilitates the construction of transformations in high-dimensional settings, but also suggests new inference methodologies for continuous non-Gaussian graphical models. For instance, in the context of nonlinear state-space models, we describe new variational algorithms for filtering, smoothing, and sequential parameter inference. These algorithms can be understood as the natural generalization--to the non-Gaussian case--of the square-root Rauch-Tung-Striebel Gaussian smoother.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2639–2709},
numpages = {71},
keywords = {variational inference, graphical models, sparsity, transport map, state-space models, joint parameter and state estimation}
}

@article{10.5555/3291125.3309627,
author = {Zheng, Charles and Achanta, Rakesh and Benjamini, Yuval},
title = {Extrapolating Expected Accuracies for Large Multi-Class Problems},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {The difficulty of multi-class classification generally increases with the number of classes. Using data for a small set of the classes, can we predict how well the classifier scales as the number of classes increases? We propose a framework for studying this question, assuming that classes in both sets are sampled from the same population and that the classifier is based on independently learned scoring functions. Under this framework, we can express the classification accuracy on a set of k classes as the (k-1)st moment of a discriminability function; the discriminability function itself does not depend on k. We leverage this result to develop a non-parametric regression estimator for the discriminability function, which can extrapolate accuracy results to larger unobserved sets. We also formalize an alternative approach that extrapolates accuracy separately for each class, and identify tradeoffs between the two methods. We show that both methods can accurately predict classifier performance on label sets up to ten times the size of the original set, both in simulations as well as in realistic face recognition or character recognition tasks.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2609–2638},
numpages = {30},
keywords = {face recognition, multi-class problems, nonparametric models, object recognition, transfer learning}
}

@article{10.5555/3291125.3309626,
author = {Duan, Leo L. and Johndrow, James E. and Dunson, David B.},
title = {Scaling up Data Augmentation MCMC via Calibration},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {There has been considerable interest in making Bayesian inference more scalable. In big data settings, most of the focus has been on reducing the computing time per iteration rather than reducing the number of iterations needed in Markov chain Monte Carlo (MCMC). This article considers data augmentation MCMC (DA-MCMC), a widely used technique. DA-MCMC samples tend to become highly autocorrelated in large samples, due to a mis-calibration problem in which conditional posterior distributions given augmented data are too concentrated. This makes it necessary to collect very long MCMC paths to obtain acceptably low MC error. To combat this inefficiency, we propose a family of calibrated data augmentation algorithms, which appropriately adjust the variance of conditional posterior distributions. A Metropolis-Hastings step is used to eliminate bias in the stationary distribution of the resulting sampler. Compared to existing alternatives, this approach can dramatically reduce MC error by reducing autocorrelation and increasing the effective number of DA-MCMC samples per unit of computing time. The approach is simple and applicable to a broad variety of existing data augmentation algorithms. We focus on three popular generalized linear models: probit, logistic and Poisson log-linear. Dramatic gains in computational eficiency are shown in applications.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2575–2608},
numpages = {34},
keywords = {logistic regression, log-linear model, data augmentation, big n, biased subsampling, Bayesian probit, polya-gamma, maximal correlation}
}

@article{10.5555/3291125.3309625,
author = {Lai, Zhao-Rong and Yang, Pei-Yi and Fang, Liangda and Wu, Xiaotian},
title = {Short-Term Sparse Portfolio Optimization Based on Alternating Direction Method of Multipliers},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {We propose a short-term sparse portfolio optimization (SSPO) system based on alternating direction method of multipliers (ADMM). Although some existing strategies have also exploited sparsity, they either constrain the quantity of the portfolio change or aim at the long-term portfolio optimization. Very few of them are dedicated to constructing sparse portfolios for the short-term portfolio optimization, which will be complemented by the proposed SSPO. SSPO concentrates wealth on a small proportion of assets that have good increasing potential according to some empirical financial principles, so as to maximize the cumulative wealth for the whole investment. We also propose a solving algorithm based on ADMM to handle the l1-regularization term and the self-financing constraint simultaneously. As a significant improvement in the proposed ADMM, we have proven that its augmented Lagrangian has a saddle point, which is the foundation of the iterative formulae of ADMM but is seldom addressed by other sparsity strategies. Extensive experiments on 5 benchmark data sets from real-world stock markets show that SSPO outperforms other state-of-the-art systems in thorough evaluations, withstands reasonable transaction costs and runs fast. Thus it is suitable for real-world financial environments.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2547–2574},
numpages = {28},
keywords = {sparse portfolio, alternating direction method of multipliers, short-term portfolio optimization}
}

@article{10.5555/3291125.3309624,
author = {Raviv, Dolev and Hazan, Tamir and Osadchy, Margarita},
title = {Hinge-Minimax Learner for the Ensemble of Hyperplanes},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {In this work we consider non-linear classifiers that comprise intersections of hyperplanes. We learn these classifiers by minimizing the "minimax" bound over the negative training examples and the hinge type loss of the positive training examples. These classifiers fit typical real-life datasets that consist of a small number of positive data points and a large number of negative data points. Such an approach is computationally appealing since the majority of training examples (belonging to the negative class) are represented by the statistics of their distribution, which is used in a single constraint on the empirical risk, as opposed to SVM, in which the number of variables is equal to the size of the training set. We first focus on intersection of K hyperplanes, for which we provide empirical risk bounds. We show that these bounds are dimensionally independent and decay as K/√m for m samples. We then extend the K-hyperplane mixed risk to the latent mixed risk for training a union of C K-hyperplane models, which can form an arbitrary complex, piecewise linear boundaries. We propose efficient algorithms for training the proposed models. Finally, we show how to combine hinge-minimax training with deep architectures and extend it to multi-class settings using transfer learning. The empirical evaluation of the proposed models shows their advantage over the existing methods in a small training labeled data regime.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2517–2546},
numpages = {30},
keywords = {imbalanced classification, transfer learning, intersection of K hyperplanes, minimiax}
}

@article{10.5555/3291125.3309623,
author = {Needell, Deanna and Saab, Rayan and Woolf, Tina},
title = {Simple Classification Using Binary Data},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {Binary, or one-bit, representations of data arise naturally in many applications, and are appealing in both hardware implementations and algorithm design. In this work, we study the problem of data classification from binary data obtained from the sign pattern of low-dimensional projections and propose a framework with low computation and resource costs. We illustrate the utility of the proposed approach through stylized and realistic numerical experiments, and provide a theoretical analysis for a simple case. We hope that our framework and analysis will serve as a foundation for studying similar types of approaches.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2487–2516},
numpages = {30},
keywords = {binary measurements, classification, one-bit representations}
}

@article{10.5555/3291125.3309622,
author = {Oliveira, Ivo F. D. and Ailon, Nir and Davidov, Ori},
title = {A New and Flexible Approach to the Analysis of Paired Comparison Data},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {We consider the situation where I items are ranked by paired comparisons. It is usually assumed that the probability that item i is preferred over item j is pij = F(µi-µj) where F is a symmetric distribution function, which we refer to as the comparison function, and µi and µj are the merits or scores of the compared items. This modelling framework, which is ubiquitous in the paired comparison literature, strongly depends on the assumption that the comparison function F is known. In practice, however, this assumption is often unrealistic and may result in poor fit and erroneous inferences. This limitation has motivated us to relax the assumption that F is fully known and simultaneously estimate the merits of the objects and the underlying comparison function. Our formulation yields a flexible semi-definite programming problem that we use as a refinement step for estimating the paired comparison probability matrix. We provide a detailed sensitivity analysis and, as a result, we establish the consistency of the resulting estimators and provide bounds on the estimation and approximation errors. Some statistical properties of the resulting estimators as well as model selection criteria are investigated. Finally, using a large dataset of computer chess matches, we estimate the comparison function and find that the model used by the International Chess Federation does not seem to apply to computer chess.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2458–2486},
numpages = {29},
keywords = {model selection, statistical ranking, chess, sensitivity analysis, semi-definite programming, linear stochastic transitivity}
}

@article{10.5555/3291125.3309621,
author = {Acharya, Jayadev and Falahatgar, Moein and Jafarpour, Ashkan and Orlitsky, Alon and Suresh, Ananda Theertha},
title = {Maximum Selection and Sorting with Adversarial Comparators},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {We study maximum selection and sorting of n numbers using imperfect pairwise comparators. The imperfect comparator returns the larger of the two inputs if the inputs are more than a given threshold apart and an adversarially-chosen input otherwise. We consider two adversarial models: a non-adaptive adversary that decides on the outcomes in advance and an adaptive adversary that decides on the outcome of each comparison depending on the previous comparisons and outcomes.Against the non-adaptive adversary, we derive a maximum-selection algorithm that uses at most 2n comparisons in expectation and a sorting algorithm that uses at most 2n ln n comparisons in expectation. In the presence of the adaptive adversary, the proposed maximum-selection algorithm uses Θ(n log(1/ε)) comparisons to output a correct answer with probability at least 1 - ε, resolving an open problem in Ajtai et al. (2015).Our study is motivated by a density-estimation problem. Given samples from an unknown distribution, we would like to find a distribution among a known class of n candidate distributions that is close to the underlying distribution in l1 distance. Scheffe's algorithm, for example, in Devroye and Lugosi (2001) outputs a distribution at an l1 distance at most 9 times the minimum and runs in time Θ(n2 log n). Using our algorithm, the runtime reduces to Θ(n log n).},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2427–2457},
numpages = {31},
keywords = {adversarial comparators, noisy sorting, Scheffe estimator, density estimation}
}

@article{10.5555/3291125.3309620,
author = {Celisse, Alain and Mary-Huard, Tristan},
title = {Theoretical Analysis of Cross-Validation for Estimating the Risk of the k-Nearest Neighbor Classifier},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {The present work aims at deriving theoretical guaranties on the behavior of some cross-validation procedures applied to the k-nearest neighbors (kNN) rule in the context of binary classification. Here we focus on the leave-p-out cross-validation (LpO) used to assess the performance of the kNN classifier. Remarkably this LpO estimator can be efficiently computed in this context using closed-form formulas derived by Celisse and Mary-Huard (2011).We describe a general strategy to derive moment and exponential concentration inequalities for the LpO estimator applied to the kNN classifier. Such results are obtained first by exploiting the connection between the LpO estimator and U-statistics, and second by making an intensive use of the generalized Efron-Stein inequality applied to the L1O estimator. One other important contribution is made by deriving new quantifications of the discrepancy between the LpO estimator and the classification error/risk of the kNN classifier. The optimality of these bounds is discussed by means of several lower bounds as well as simulation experiments.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2373–2426},
numpages = {54},
keywords = {cross-validation, risk estimation, classification}
}

@article{10.5555/3291125.3309619,
author = {Yang, Zhuoran and Ning, Yang and Liu, Han},
title = {On Semiparametric Exponential Family Graphical Models},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {We propose a new class of semiparametric exponential family graphical models for the analysis of high dimensional mixed data. Different from the existing mixed graphical models, we allow the nodewise conditional distributions to be semiparametric generalized linear models with unspecified base measure functions. Thus, one advantage of our method is that it is unnecessary to specify the type of each node and the method is more convenient to apply in practice. Under the proposed model, we consider both problems of parameter estimation and hypothesis testing in high dimensions. In particular, we propose a symmetric pairwise score test for the presence of a single edge in the graph. Compared to the existing methods for hypothesis tests, our approach takes into account of the symmetry of the parameters, such that the inferential results are invariant with respect to the di\'{e}rent parametrizations of the same edge. Thorough numerical simulations and a real data example are provided to back up our theoretical results.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2314–2372},
numpages = {59},
keywords = {high dimensional inference, graphical models, exponential family}
}

@article{10.5555/3291125.3309618,
author = {Barbero, \`{A}lvaro and Sra, Suvrit},
title = {Modular Proximal Optimization for Multidimensional Total-Variation Regularization},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {We study TV regularization, a widely used technique for eliciting structured sparsity. In particular, we propose efficient algorithms for computing prox-operators for lp-norm TV. The most important among these is l1-norm TV, for whose prox-operator we present a new geometric analysis which unveils a hitherto unknown connection to taut-string methods. This connection turns out to be remarkably useful as it shows how our geometry guided implementation results in efficient weighted and unweighted 1D-TV solvers, surpassing state-of-the-art methods. Our 1D-TV solvers provide the backbone for building more complex (two or higher-dimensional) TV solvers within a modular proximal optimization approach. We review the literature for an array of methods exploiting this strategy, and illustrate the benefits of our modular design through extensive suite of experiments on (i) image denoising, (ii) image deconvolution, (iii) four variants of fused-lasso, and (iv) video denoising. To underscore our claims and permit easy reproducibility, we provide all the reviewed and our new TV solvers in an easy to use multi-threaded C++, Matlab and Python library.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2232–2313},
numpages = {82},
keywords = {non-smooth optimization, proximal optimization, sparsity, regularized learning, total variation}
}

@article{10.5555/3291125.3309617,
author = {Chen, Yuansi and Dwivedi, Raaz and Wainwright, Martin J. and Yu, Bin},
title = {Fast MCMC Sampling Algorithms on Polytopes},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {We propose and analyze two new MCMC sampling algorithms, the Vaidya walk and the John walk, for generating samples from the uniform distribution over a polytope. Both random walks are sampling algorithms derived from interior point methods. The former is based on volumetric-logarithmic barrier introduced by Vaidya whereas the latter uses John's ellipsoids. We show that the Vaidya walk mixes in significantly fewer steps than the logarithmic-barrier based Dikin walk studied in past work. For a polytope in ℝd defined by n ≥ d linear constraints, we show that the mixing time from a warm start is bounded as O(n0.5d1.5), compared to the O(nd) mixing time bound for the Dikin walk. The cost of each step of the Vaidya walk is of the same order as the Dikin walk, and at most twice as large in terms of constant pre-factors. For the John walk, we prove an O(d2.5 ۪ log4(n/d) bound on its mixing time and conjecture that an improved variant of it could achieve a mixing time of O(d2 ۪ poly-log(n/d)). Additionally, we propose variants of the Vaidya and John walks that mix in polynomial time from a deterministic starting point. The speed-up of the Vaidya walk over the Dikin walk are illustrated in numerical examples.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2146–2231},
numpages = {86},
keywords = {polytopes, sampling from convex sets, MCMC methods, interior point methods}
}

@article{10.5555/3291125.3309616,
author = {Dunlop, Matthew M. and Girolami, Mark A. and Stuart, Andrew M. and Teckentrup, Aretha L.},
title = {How Deep Are Deep Gaussian Processes?},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {Recent research has shown the potential utility of deep Gaussian processes. These deep structures are probability distributions, designed through hierarchical construction, which are conditionally Gaussian. In this paper, the current published body of work is placed in a common framework and, through recursion, several classes of deep Gaussian processes are defined. The resulting samples generated from a deep Gaussian process have a Markovian structure with respect to the depth parameter, and the effective depth of the resulting process is interpreted in terms of the ergodicity, or non-ergodicity, of the resulting Markov chain. For the classes of deep Gaussian processes introduced, we provide results concerning their ergodicity and hence their effective depth. We also demonstrate how these processes may be used for inference; in particular we show how a Metropolis-within-Gibbs construction across the levels of the hierarchy can be used to derive sampling tools which are robust to the level of resolution used to represent the functions on a computer. For illustration, we consider the effect of ergodicity in some simple numerical examples.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2100–2145},
numpages = {46},
keywords = {deep learning, deep kernels, deep gaussian processes}
}

@article{10.5555/3291125.3309615,
author = {Lamprier, Sylvain and Gisselbrecht, Thibault and Gallinari, Patrick},
title = {Profile-Based Bandit with Unknown Profiles},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {Stochastic bandits have been widely studied since decades. A very large panel of settings have been introduced, some of them for the inclusion of some structure between actions. If actions are associated with feature vectors that underlie their usefulness, the discovery of a mapping parameter between such proffles and rewards can help the exploration process of the bandit strategies. This is the setting studied in this paper, but in our case the action profiles (constant feature vectors) are unknown beforehand. Instead, the agent is only given sample vectors, with mean centered on the true profiles, for a subset of actions at each step of the process. In this new bandit instance, policies have thus to deal with a doubled uncertainty, both on the profile estimators and the reward mapping parameters learned so far. We propose a new algorithm, called SampLinUCB, specifically designed for this case. Theoretical convergence guarantees are given for this strategy, according to various profile samples delivery scenarios. Finally, experiments are conducted on both artificial data and a task of focused data capture from online social networks. Obtained results demonstrate the relevance of the approach in various settings.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2060–2099},
numpages = {40},
keywords = {stochastic linear bandits, profile-based exploration, upper confidence bounds}
}

@article{10.5555/3291125.3309614,
author = {Obuchi, Tomoyuki and Kabashima, Yoshiyuki},
title = {Accelerating Cross-Validation in Multinomial Logistic Regression with l<sub>1</sub>-Regularization},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {We develop an approximate formula for evaluating a cross-validation estimator of predictive likelihood for multinomial logistic regression regularized by an l1-norm. This allows us to avoid repeated optimizations required for literally conducting cross-validation; hence, the computational time can be significantly reduced. The formula is derived through a perturbative approach employing the largeness of the data size and the model dimensionality. An extension to the elastic net regularization is also addressed. The usefulness of the approximate formula is demonstrated on simulated data and the ISOLET dataset from the UCI machine learning repository. MATLAB and python codes implementing the approximate formula are distributed in (Obuchi, 2017; Takahashi and Obuchi, 2017).},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {2030–2059},
numpages = {30},
keywords = {self-averaging approximation, cross-validation, linear perturbation, multinomial logistic regression, classification}
}

@article{10.5555/3291125.3309613,
author = {Giordano, Ryan and Broderick, Tamara and Jordan, Michael I.},
title = {Covariances, Robustness and Variational Bayes},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {Mean-field Variational Bayes (MFVB) is an approximate Bayesian posterior inference technique that is increasingly popular due to its fast runtimes on large-scale data sets. However, even when MFVB provides accurate posterior means for certain parameters, it often mis-estimates variances and covariances. Furthermore, prior robustness measures have remained undeveloped for MFVB. By deriving a simple formula for the effect of infinitesimal model perturbations on MFVB posterior means, we provide both improved covariance estimates and local robustness measures for MFVB, thus greatly expanding the practical usefulness of MFVB posterior approximations. The estimates for MFVB posterior covariances rely on a result from the classical Bayesian robustness literature that relates derivatives of posterior expectations to posterior covariances and includes the Laplace approximation as a special case. Our key condition is that the MFVB approximation provides good estimates of a select subset of posterior means--an assumption that has been shown to hold in many practical settings. In our experiments, we demonstrate that our methods are simple, general, and fast, providing accurate posterior uncertainty estimates and robustness measures with runtimes that can be an order of magnitude faster than MCMC.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1981–2029},
numpages = {49},
keywords = {variational bayes, automatic differentiation, Bayesian robustness, linear response theory, Laplace approximation, mean field approximation}
}

@article{10.5555/3291125.3309612,
author = {Achille, Alessandro and Soatto, Stefano},
title = {Emergence of Invariance and Disentanglement in Deep Representations},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {Using established principles from Statistics and Information Theory, we show that invariance to nuisance factors in a deep neural network is equivalent to information minimality of the learned representation, and that stacking layers and injecting noise during training naturally bias the network towards learning invariant representations. We then decompose the cross-entropy loss used during training and highlight the presence of an inherent overfitting term. We propose regularizing the loss by bounding such a term in two equivalent ways: One with a Kullbach-Leibler term, which relates to a PAC-Bayes perspective; the other using the information in the weights as a measure of complexity of a learned model, yielding a novel Information Bottleneck for the weights. Finally, we show that invariance and independence of the components of the representation learned by the network are bounded above and below by the information in the weights, and therefore are implicitly optimized during training. The theory enables us to quantify and predict sharp phase transitions between underfitting and overfitting of random labels when using our regularized loss, which we verify in experiments, and sheds light on the relation between the geometry of the loss function, invariance properties of the learned representation, and generalization error.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1947–1980},
numpages = {34},
keywords = {information bottleneck, invariance, flat minima, PAC-bayes, generalization, representation learning, independence}
}

@article{10.5555/3291125.3309611,
author = {Shah, Nihar B. and Tabibian, Behzad and Muandet, Krikamol and Guyon, Isabelle and Von Luxburg, Ulrike},
title = {Design and Analysis of the NIPS 2016 Review Process},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {Neural Information Processing Systems (NIPS) is a top-tier annual conference in machine learning. The 2016 edition of the conference comprised more than 2,400 paper submissions, 3,000 reviewers, and 8,000 attendees. This represents a growth of nearly 40% in terms of submissions, 96% in terms of reviewers, and over 100% in terms of attendees as compared to the previous year. The massive scale as well as rapid growth of the conference calls for a thorough quality assessment of the peer-review process and novel means of improvement. In this paper, we analyze several aspects of the data collected during the review process, including an experiment investigating the efficacy of collecting ordinal rankings from reviewers. We make a number of key observations, provide suggestions that may be useful for subsequent conferences, and discuss open problems towards the goal of improving peer review.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1913–1946},
numpages = {34},
keywords = {consistency, NIPS, ordinal, post hoc analysis, peer review}
}

@article{10.5555/3291125.3309610,
author = {Yu, Huizhen and Mahmood, A. Rupam and Sutton, Richard S.},
title = {On Generalized Bellman Equations and Temporal-Difference Learning},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {We consider off-policy temporal-difference (TD) learning in discounted Markov decision processes, where the goal is to evaluate a policy in a model-free way by using observations of a state process generated without executing the policy. To curb the high variance issue in off-policy TD learning, we propose a new scheme of setting the λ-parameters of TD, based on generalized Bellman equations. Our scheme is to set λ according to the eligibility trace iterates calculated in TD, thereby easily keeping these traces in a desired bounded range. Compared with prior work, this scheme is more direct and flexible, and allows much larger λ values for off-policy TD learning with bounded traces. As to its soundness, using Markov chain theory, we prove the ergodicity of the joint state-trace process under nonrestrictive conditions, and we show that associated with our scheme is a generalized Bellman equation (for the policy to be evaluated) that depends on both the evolution of λ and the unique invariant probability measure of the state-trace process. These results not only lead immediately to a characterization of the convergence behavior of least-squares based implementation of our scheme, but also prepare the ground for further analysis of gradient-based implementations.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1864–1912},
numpages = {49},
keywords = {reinforcement learning, randomized stopping time, approximate policy evaluation, Markov chain, Markov decision process, generalized Bellman equation, temporal-difference method}
}

@article{10.5555/3291125.3309609,
author = {K\"{u}mmerle, Christian and Sigl, Juliane},
title = {Harmonic Mean Iteratively Reweighted Least Squares for Low-Rank Matrix Recovery},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {We propose a new iteratively reweighted least squares (IRLS) algorithm for the recovery of a matrix X ∈ Cd1\texttimes{}d2 of rank r ≪ min(d1, d2) from incomplete linear observations, solving a sequence of low complexity linear problems. The easily implementable algorithm, which we call harmonic mean iteratively reweighted least squares (HM-IRLS), optimizes a non-convex Schatten-p quasi-norm penalization to promote low-rankness and carries three major strengths, in particular for the matrix completion setting. First, we observe a remarkable global convergence behavior of the algorithm's iterates to the low-rank matrix for relevant, interesting cases, for which any other state-of-the-art optimization approach fails the recovery. Secondly, HM-IRLS exhibits an empirical recovery probability close to 1 even for a number of measurements very close to the theoretical lower bound r(d1+d2-r), i.e., already for significantly fewer linear observations than any other tractable approach in the literature. Thirdly, HM-IRLS exhibits a locally superlinear rate of convergence (of order 2 - p) if the linear observations fulfill a suitable null space property. While for the first two properties we have so far only strong empirical evidence, we prove the third property as our main theoretical result.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1815–1863},
numpages = {49},
keywords = {non-convex optimization, matrix completion, low-rank matrix recovery, iteratively reweighted least squares}
}

@article{10.5555/3291125.3309608,
author = {Van De Geer, Sara},
title = {On Tight Bounds for the Lasso},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {We present upper and lower bounds for the prediction error of the Lasso. For the case of random Gaussian design, we show that under mild conditions the prediction error of the Lasso is up to smaller order terms dominated by the prediction error of its noiseless counterpart. We then provide exact expressions for the prediction error of the latter, in terms of compatibility constants. Here, we assume the active components of the underlying regression function satisfy some "betamin" condition. For the case of fixed design, we provide upper and lower bounds, again in terms of compatibility constants. As an example, we give an up to a logarithmic term tight bound for the least squares estimator with total variation penalty.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1767–1814},
numpages = {48},
keywords = {lasso, compatibility, lower bound, linear model}
}

@article{10.5555/3291125.3309607,
author = {Au, Timothy C.},
title = {Random Forests, Decision Trees, and Categorical Predictors: The "Absent Levels" Problem},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {One advantage of decision tree based methods like random forests is their ability to natively handle categorical predictors without having to first transform them (e.g., by using feature engineering techniques). However, in this paper, we show how this capability can lead to an inherent "absent levels" problem for decision tree based methods that has never been thoroughly discussed, and whose consequences have never been carefully explored. This problem occurs whenever there is an indeterminacy over how to handle an observation that has reached a categorical split which was determined when the observation in question's level was absent during training. Although these incidents may appear to be innocuous, by using Leo Breiman and Adele Cutler's random forests FORTRAN code and the randomForest R package (Liaw and Wiener, 2002) as motivating case studies, we examine how overlooking the absent levels problem can systematically bias a model. Furthermore, by using three real data examples, we illustrate how absent levels can dramatically alter a model's performance in practice, and we empirically demonstrate how some simple heuristics can be used to help mitigate the effects of the absent levels problem until a more robust theoretical solution is found.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1737–1766},
numpages = {30},
keywords = {random forests, CART, categorical predictors, absent levels, decision trees}
}

@article{10.5555/3291125.3309606,
author = {Simon-Gabriel, Carl-Johann and Sch\"{o}lkopf, Bernhard},
title = {Kernel Distribution Embeddings: Universal Kernels, Characteristic Kernels and Kernel Metrics on Distributions},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {Kernel mean embeddings have become a popular tool in machine learning. They map probability measures to functions in a reproducing kernel Hilbert space. The distance between two mapped measures defines a semi-distance over the probability measures known as the maximum mean discrepancy (MMD). Its properties depend on the underlying kernel and have been linked to three fundamental concepts of the kernel literature: universal, characteristic and strictly positive definite kernels.The contributions of this paper are three-fold. First, by slightly extending the usual definitions of universal, characteristic and strictly positive definite kernels, we show that these three concepts are essentially equivalent. Second, we give the first complete characterization of those kernels whose associated MMD-distance metrizes the weak convergence of probability measures. Third, we show that kernel mean embeddings can be extended from probability measures to generalized measures called Schwartz-distributions and analyze a few properties of these distribution embeddings.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1708–1736},
numpages = {29},
keywords = {metrisation of the weak topology, schwartz-distributions, universal kernel, characteristic kernel, kernel metrics on distributions, kernel mean embedding}
}

@article{10.5555/3291125.3309605,
author = {Liu, Xu-Qing and Liu, Xin-Sheng},
title = {Markov Blanket and Markov Boundary of Multiple Variables},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {Markov blanket (Mb) and Markov boundary (MB) are two key concepts in Bayesian networks (BNs). In this paper, we study the problem of Mb and MB for multiple variables. First, we show that Mb possesses the additivity property under the local intersection assumption, that is, an Mb of multiple targets can be constructed by simply taking the union of Mbs of the individual targets and removing the targets themselves. MB is also proven to have additivity under the local intersection assumption. Second, we analyze the cases of violating additivity of Mb and MB and then put forward the notions of Markov blanket supplementary (MbS) and Markov boundary supplementary (MBS). The properties of MbS and MBS are studied in detail. Third, we build two MB discovery algorithms and prove their correctness under the local composition assumption. We also discuss the ways of practically doing conditional independence tests and analyze the complexities of the algorithms. Finally, we make a benchmarking study based on six synthetic BNs and then apply MB discovery to multi-class prediction based on a real data set. The experimental results reveal our algorithms have higher accuracies and lower complexities than existing algorithms.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1658–1707},
numpages = {50},
keywords = {Markov boundary, Markov blanket supplementary, Bayesian network, Markov blanket, Markov boundary supplementary}
}

@article{10.5555/3291125.3291167,
author = {Ah-Pine, Julien},
title = {An Efficient and Effective Generic Agglomerative Hierarchical Clustering Approach},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {We introduce an agglomerative hierarchical clustering (AHC) framework which is generic, efficient and effective. Our approach embeds a sub-family of Lance-Williams (LW) clusterings and relies on inner-products instead of squared Euclidean distances. We carry out a constrained bottom-up merging procedure on a sparsified normalized inner-product matrix. Our method is named SNK-AHC for Sparsified Normalized Kernel matrix based AHC. SNK-AHC is more scalable than the classic dissimilarity matrix based AHC. It can also produce better results when clusters have arbitrary shapes. Artificial and real-world benchmarks are used to exemplify these points. From a theoretical standpoint, SNK-AHC provides another interpretation of the classic techniques which relies on the concept of weighted penalized similarities. The di_erences between group average, Mcquitty, centroid, median and Ward, can be explained by their distinct averaging strategies for aggregating clusters inter-similarities and intra-similarities. Other features of SNK-AHC are examined. We provide sufficient conditions in order to have monotonic dendrograms, we elaborate a stored data matrix approach for centroid and median, we underline the diagonal translation invariance property of group average, Mcquitty and Ward and we show to what extent SNK-AHC can determine the number of clusters.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1615–1658},
numpages = {44},
keywords = {Kernel methods, scalability, manifold learning, agglomerative hierarchical clustering, Lance-Williams formula}
}

@article{10.5555/3291125.3291166,
author = {Dai, Bin and Wang, Yu and Aston, John and Hua, Gang and Wipf, David},
title = {Connections with Robust PCA and the Role of Emergent Sparsity in Variational Autoencoder Models},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {Variational autoencoders (VAE) represent a popular, exible form of deep generative model that can be stochastically _t to samples from a given random process using an information-theoretic variational bound on the true underlying distribution. Once so-obtained, the model can be putatively used to generate new samples from this distribution, or to provide a low-dimensional latent representation of existing samples. While quite effective in numerous application domains, certain important mechanisms which govern the behavior of the VAE are obfuscated by the intractable integrals and resulting stochastic approximations involved. Moreover, as a highly non-convex model, it remains unclear exactly how minima of the underlying energy relate to original design purposes. We attempt to better quantify these issues by analyzing a series of tractable special cases of increasing complexity. In doing so, we unveil interesting connections with more traditional dimensionality reduction models, as well as an intrinsic yet underappreciated propensity for robustly dismissing sparse outliers when estimating latent manifolds. With respect to the latter, we demonstrate that the VAE can be viewed as the natural evolution of recent robust PCA models, capable of learning nonlinear manifolds of unknown dimension obscured by gross corruptions.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1573–1614},
numpages = {42},
keywords = {deep generative model, variational autoencoder, robust PCA}
}

@article{10.5555/3291125.3291165,
author = {Negahban, Sahand and Oh, Sewoong and Thekumparampil, Kiran K. and Xu, Jiaming},
title = {Learning from Comparisons and Choices},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {When tracking user-specific online activities, each user's preference is revealed in the form of choices and comparisons. For example, a user's purchase history is a record of her choices, i.e. which item was chosen among a subset of offerings. A user's preferences can be observed either explicitly as in movie ratings or implicitly as in viewing times of news articles. Given such individualized ordinal data in the form of comparisons and choices, we address the problem of collaboratively learning representations of the users and the items. The learned features can be used to predict a user's preference of an unseen item to be used in recommendation systems. This also allows one to compute similarities among users and items to be used for categorization and search. Motivated by the empirical successes of the MultiNomial Logit (MNL) model in marketing and transportation, and also more recent successes in word embedding and crowdsourced image embedding, we pose this problem as learning the MNL model parameters that best explain the data. We propose a convex relaxation for learning the MNL model, and show that it is minimax optimal up to a logarithmic factor by comparing its performance to a fundamental lower bound. This characterizes the minimax sample complexity of the problem, and proves that the proposed estimator cannot be improved upon other than by a logarithmic factor. Further, the analysis identifies how the accuracy depends on the topology of sampling via the spectrum of the sampling graph. This provides a guideline for designing surveys when one can choose which items are to be compared. This is accompanied by numerical simulations on synthetic and real data sets, confirming our theoretical predictions.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1478–1572},
numpages = {95},
keywords = {nuclear norm minimization, collaborative ranking, multi-nomial logit model}
}

@article{10.5555/3291125.3291164,
author = {Leh\'{e}ricy, Luc},
title = {State-by-State Minimax Adaptive Estimation for Nonparametric Hidden Markov Models},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {In this paper, we introduce a new estimator for the emission densities of a nonparametric hidden Markov model. It is adaptive and minimax with respect to each state's regularity-as opposed to globally minimax estimators, which adapt to the worst regularity among the emission densities. Our method is based on Goldenshluger and Lepski's methodology. It is computationally efficient and only requires a family of preliminary estimators, without any restriction on the type of estimators considered. We present two such estimators that allow to reach minimax rates up to a logarithmic term: a spectral estimator and a least squares estimator. We show how to calibrate it in practice and assess its performance on simulations and on real data.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1432–1477},
numpages = {46},
keywords = {oracle inequality, least squares method, adaptive minimax estimation, spectral method, model selection, nonparametric density estimation, hidden Markov model}
}

@article{10.5555/3291125.3291163,
author = {Yousefi, Niloofar and Lei, Yunwen and Kloft, Marius and Mollaghasemi, Mansooreh and Anagnostopoulos, Georgios C.},
title = {Local Rademacher Complexity-Based Learning Guarantees for Multi-Task Learning},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {We show a Talagrand-type concentration inequality for Multi-Task Learning (MTL), with which we establish sharp excess risk bounds for MTL in terms of the Local Rademacher Complexity (LRC). We also give a new bound on the LRC for any norm regularized hypothesis classes, which applies not only to MTL, but also to the standard Single-Task Learning (STL) setting. By combining both results, one can easily derive fast-rate bounds on the excess risk for many prominent MTL methods, including--as we demonstrate--Schatten norm, group norm, and graph regularized MTL. The derived bounds reflect a relationship akin to a conservation law of asymptotic convergence rates. When compared to the rates obtained via a traditional, global Rademacher analysis, this very relationship allows for trading off slower rates with respect to the number of tasks for faster rates with respect to the number of available samples per task.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1385–1431},
numpages = {47},
keywords = {local rademacher complexity, multi-task learning, excess risk bounds}
}

@article{10.5555/3291125.3291162,
author = {Thanei, Gian-Andrea and Meinshausen, Nicolai and Shah, Rajen D.},
title = {The Xyz Algorithm for Fast Interaction Search in High-Dimensional Data},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {When performing regression on a data set with p variables, it is often of interest to go beyond using main linear effects and include interactions as products between individual variables. For small-scale problems, these interactions can be computed explicitly but this leads to a computational complexity of at least O(p2) if done naively. This cost can be prohibitive if p is very large.We introduce a new randomised algorithm that is able to discover interactions with high probability and under mild conditions has a runtime that is subquadratic in p. We show that strong interactions can be discovered in almost linear time, whilst finding weaker interactions requires O(pα) operations for 1 < α < 2 depending on their strength. The underlying idea is to transform interaction search into a closest pair problem which can be solved efficiently in subquadratic time. The algorithm is called xyz and is implemented in the language R. We demonstrate its efficiency for application to genome-wide association studies, where more than 1011 interactions can be screened in under 280 seconds with a single-core 1:2 GHz CPU.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1343–1384},
numpages = {42},
keywords = {computational tradeoffs, interactions, close pairs, high-dimensional data, regression}
}

@article{10.5555/3291125.3291161,
author = {Rojas-Carulla, Mateo and Sch\"{o}lkopf, Bernhard and Turner, Richard and Peters, Jonas},
title = {Invariant Models for Causal Transfer Learning},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {Methods of transfer learning try to combine knowledge from several related tasks (or domains) to improve performance on a test task. Inspired by causal methodology, we relax the usual covariate shift assumption and assume that it holds true for a subset of predictor variables: the conditional distribution of the target variable given this subset of predictors is invariant over all tasks. We show how this assumption can be motivated from ideas in the field of causality. We focus on the problem of Domain Generalization, in which no examples from the test task are observed. We prove that in an adversarial setting using this subset for prediction is optimal in Domain Generalization; we further provide examples, in which the tasks are sufficiently diverse and the estimator therefore outperforms pooling the data, even on average. If examples from the test task are available, we also provide a method to transfer knowledge from the training tasks and exploit all available features for prediction. However, we provide no guarantees for this method. We introduce a practical method which allows for automatic inference of the above subset and provide corresponding code. We present results on synthetic data sets and a gene deletion data set.},
journal = {J. Mach. Learn. Res.},
month = jan,
pages = {1309–1342},
numpages = {34},
keywords = {multi-task learning, domain generalization, domain adaptation, transfer learning, causality}
}

@article{10.5555/3291125.3291160,
author = {Hang, Hanyuan and Steinwart, Ingo and Feng, Yunlong and Suykens, Johan A. K.},
title = {Kernel Density Estimation for Dynamical Systems},
year = {2018},
issue_date = {January 2018},
publisher = {JMLR.org},
volume = {19},
number = {1},
issn = {1532-4435},
abstract = {We study the density estimation problem with observations generated by certain dynamical systems that

license: Unlicense

repository: goyalkaraniit/acm-cr

repo_name: goyalkaraniit/acm-cr