- title: 'Minimax Gaussian Classification & Clustering'
abstract: 'We present minimax bounds for classification and clustering error in the setting where covariates are drawn from a mixture of two isotropic Gaussian distributions. Here, we define clustering error in a discriminative fashion, demonstrating fundamental connections between classification (supervised) and clustering (unsupervised). For both classification and clustering, our lower bounds show that without enough samples, the best any classifier or clustering rule can do is close to random guessing. For classification, as part of our upper bound analysis, we show that Fisher''s linear discriminant achieves a fast minimax rate $\Theta(1/n)$ with enough samples $n$. For clustering, as part of our upper bound analysis, we show that a clustering rule constructed using principal component analysis achieves the minimax rate with enough samples. We also provide lower and upper bounds for the high-dimensional sparse setting where the dimensionality of the covariates $p$ is potentially larger than the number of samples $n$, but where the difference between the Gaussian means is sparse.
'
volume: 54
URL: https://proceedings.mlr.press/v54/li17a.html
PDF: http://proceedings.mlr.press/v54/li17a/li17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-li17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Tianyang
family: Li
- given: Xinyang
family: Yi
- given: Constantine
family: Carmanis
- given: Pradeep
family: Ravikumar
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1-9
id: li17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1
lastpage: 9
published: 2017-04-10 00:00:00 +0000
- title: 'Conditions beyond treewidth for tightness of higher-order LP relaxations'
abstract: 'Linear programming (LP) relaxations are a popular method to attempt to find a most likely configuration of a discrete graphical model. If a solution to the relaxed problem is obtained at an integral vertex then the solution is guaranteed to be exact and we say that the relaxation is tight. We consider binary pairwise models and introduce new methods which allow us to demonstrate refined conditions for tightness of LP relaxations in the Sherali-Adams hierarchy. Our results include showing that for higher order LP relaxations, treewidth is not precisely the right way to characterize tightness. This work is primarily theoretical, with insights that can improve efficiency in practice.'
volume: 54
URL: https://proceedings.mlr.press/v54/rowland17a.html
PDF: http://proceedings.mlr.press/v54/rowland17a/rowland17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-rowland17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Mark
family: Rowland
- given: Aldo
family: Pacchiano
- given: Adrian
family: Weller
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 10-18
id: rowland17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 10
lastpage: 18
published: 2017-04-10 00:00:00 +0000
- title: 'Large-Scale Data-Dependent Kernel Approximation'
abstract: 'Learning a computationally efficient kernel from data is an important machine learning problem. The majority of kernels in the literature do not leverage the geometry of the data, and those that do are computationally infeasible for contemporary datasets. Recent advances in approximation techniques have expanded the applicability of the kernel methodology to scale linearly with the data size. Data-dependent kernels, which could leverage this computational advantage, have however not yet seen the benefit. Here we derive an approximate large-scale learning procedure for data-dependent kernels that is efficient and performs well in practice. We provide a Lemma that can be used to derive the asymptotic convergence of the approximation in the limit of infinite random features, and, under certain conditions, an estimate of the convergence speed. We empirically prove that our construction represents a valid, yet efficient approximation of the data-dependent kernel. For large-scale datasets of millions of datapoints, where the proposed method is now applicable for the first time, we notice a significant performance boost over both baselines consisting of data independent kernels and of kernel approximations, at comparable computational cost.'
volume: 54
URL: https://proceedings.mlr.press/v54/ionescu17a.html
PDF: http://proceedings.mlr.press/v54/ionescu17a/ionescu17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-ionescu17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Catalin
family: Ionescu
- given: Alin
family: Popa
- given: Cristian
family: Sminchisescu
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 19-27
id: ionescu17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 19
lastpage: 27
published: 2017-04-10 00:00:00 +0000
- title: 'Clustering from Multiple Uncertain Experts'
abstract: 'Utilizing expert input often improves clustering performance. However in a knowledge discovery problem, ground truth is unknown even to an expert. Thus, instead of one expert, we solicit the opinion from multiple experts. The key question motivating this work is: which experts should be assigned higher weights when there is disagreement on whether to put a pair of samples in the same group? To model the uncertainty in constraints from different experts, we build a probabilistic model for pairwise constraints through jointly modeling each expert’s accuracy and the mapping from features to latent cluster assignments. After learning our probabilistic discriminative clustering model and accuracies of different experts, 1) samples that were not annotated by any expert can be clustered using the discriminative clustering model; and 2) experts with higher accuracies are automatically assigned higher weights in determining the latent cluster assignments. Experimental results on UCI benchmark datasets and a real-world disease subtyping dataset demonstrate that our proposed approach outperforms competing alternatives, including semi-crowdsourced clustering, semi-supervised clustering with constraints from majority voting, and consensus clustering.'
volume: 54
URL: https://proceedings.mlr.press/v54/chang17a.html
PDF: http://proceedings.mlr.press/v54/chang17a/chang17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-chang17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Yale
family: Chang
- given: Junxiang
family: Chen
- given: Michael
family: Cho
- given: Peter
family: Castaldi
- given: Ed
family: Silverman
- given: Jennifer
family: Dy
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 28-36
id: chang17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 28
lastpage: 36
published: 2017-04-10 00:00:00 +0000
- title: 'Online Nonnegative Matrix Factorization with General Divergences'
abstract: 'We develop a unified and systematic framework for performing online nonnegative matrix factorization under a wide variety of important divergences. The online nature of our algorithms makes them particularly amenable to large-scale data. We prove that the sequence of learned dictionaries converges almost surely to the set of critical points of the expected loss function. Experimental results demonstrate the computational efficiency and outstanding performances of our algorithms on several real-life applications, including topic modeling, document clustering and foreground-background separation.'
volume: 54
URL: https://proceedings.mlr.press/v54/zhao17a.html
PDF: http://proceedings.mlr.press/v54/zhao17a/zhao17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-zhao17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Renbo
family: Zhao
- given: Vincent
family: Tan
- given: Huan
family: Xu
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 37-45
id: zhao17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 37
lastpage: 45
published: 2017-04-10 00:00:00 +0000
- title: 'ASAGA: Asynchronous Parallel SAGA'
abstract: 'We describe ASAGA, an asynchronous parallel version of the incremental gradient algorithm SAGA that enjoys fast linear convergence rates. 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 thereby prove that ASAGA 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 speedup as well as the hardware overhead.'
volume: 54
URL: https://proceedings.mlr.press/v54/leblond17a.html
PDF: http://proceedings.mlr.press/v54/leblond17a/leblond17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-leblond17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Rémi
family: Leblond
- given: Fabian
family: Pedregosa
- given: Simon
family: Lacoste-Julien
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 46-54
id: leblond17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 46
lastpage: 54
published: 2017-04-10 00:00:00 +0000
- title: 'Lower Bounds on Active Learning for Graphical Model Selection'
abstract: 'We consider the problem of estimating the underlying graph associated with a Markov random field, with the added twist that the decoding algorithm can iteratively choose which subsets of nodes to sample based on the previous samples, resulting in an active learning setting. Considering both Ising and Gaussian models, we provide algorithm-independent lower bounds for high-probability recovery within the class of degree-bounded graphs. Our main results are minimax lower bounds for the active setting that match the best known lower bounds for the passive setting, which in turn are known to be tight in several cases of interest. Our analysis is based on Fano’s inequality, along with novel mutual information bounds for the active learning setting, and the application of restricted graph ensembles. While we consider ensembles that are similar or identical to those used in the passive setting, we require different analysis techniques, with a key challenge being bounding a mutual information quantity associated with observed subsets of nodes, as opposed to full observations.'
volume: 54
URL: https://proceedings.mlr.press/v54/scarlett17a.html
PDF: http://proceedings.mlr.press/v54/scarlett17a/scarlett17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-scarlett17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Jonathan
family: Scarlett
- given: Volkan
family: Cevher
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 55-64
id: scarlett17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 55
lastpage: 64
published: 2017-04-10 00:00:00 +0000
- title: 'Non-square matrix sensing without spurious local minima via the Burer-Monteiro approach'
abstract: 'We consider the non-square matrix sensing problem, under restricted isometry property (RIP) assumptions. We focus on the non-convex formulation, where any rank-r matrix $X ∈R^m x n$ is represented as $UV^T$, where $U ∈R^m x r$ and $V ∈R^n x r$. In this paper, we complement recent findings on the non-convex geometry of the analogous PSD setting [5], and show that matrix factorization does not introduce any spurious local minima, under RIP. '
volume: 54
URL: https://proceedings.mlr.press/v54/park17a.html
PDF: http://proceedings.mlr.press/v54/park17a/park17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-park17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Dohyung
family: Park
- given: Anastasios
family: Kyrillidis
- given: Constantine
family: Carmanis
- given: Sujay
family: Sanghavi
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 65-74
id: park17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 65
lastpage: 74
published: 2017-04-10 00:00:00 +0000
- title: 'Sparse Accelerated Exponential Weights'
abstract: 'We consider the stochastic optimization problem where a convex function is minimized observing recursively the gradients. We introduce SAEW, a new procedure that accelerates exponential weights procedures with the slow rate $1/\sqrtT$ to procedures achieving the fast rate $1/T$. Under the strong convexity of the risk, we achieve the optimal rate of convergence for approximating sparse parameters in $R^d$. The acceleration is achieved by using successive averaging steps in an online fashion. The procedure also produces sparse estimators thanks to additional hard threshold steps. '
volume: 54
URL: https://proceedings.mlr.press/v54/gaillard17a.html
PDF: http://proceedings.mlr.press/v54/gaillard17a/gaillard17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-gaillard17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Pierre
family: Gaillard
- given: Olivier
family: Wintenberger
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 75-82
id: gaillard17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 75
lastpage: 82
published: 2017-04-10 00:00:00 +0000
- title: 'On the Learnability of Fully-Connected Neural Networks'
abstract: 'Despite the empirical success of deep neural networks, there is limited theoretical understanding on the learnability of these models using a polynomial-time algorithm. In this paper, we characterize the learnability of fully-connected neural networks via both positive and negative results. We focus on $\ell_1$-regularized networks, where the $\ell_1$-norm of the incoming weights of every neuron is assumed to be bounded by a constant $B > 0$. Our first result shows that such networks are properly learnable in $\text{poly}(n,d,\exp(1/ε^2))$ time, where $n$ and $d$ are the sample size and the input dimension, and $ε> 0$ is the gap to optimality. The bound is achieved by repeatedly sampling over a low-dimensional manifold so as to ensure approximate optimality, but avoids the $\exp(d)$ cost of exhaustively searching over the parameter space. We also establish a hardness result showing that the exponential dependence on $1/ε$ is unavoidable unless $\bf RP = \bf NP$. Our second result shows that the exponential dependence on $1/ε$ can be avoided by exploiting the underlying structure of the data distribution. In particular, if the positive and negative examples can be separated with margin $γ> 0$ by an unknown neural network, then the network can be learned in $\text{poly}(n,d,1/ε)$ time. The bound is achieved by an ensemble method which uses the first algorithm as a weak learner. We further show that the separability assumption can be weakened to tolerate noisy labels. Finally, we show that the exponential dependence on $1/γ$ is unimprovable under a certain cryptographic assumption.'
volume: 54
URL: https://proceedings.mlr.press/v54/zhang17a.html
PDF: http://proceedings.mlr.press/v54/zhang17a/zhang17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-zhang17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Yuchen
family: Zhang
- given: Jason
family: Lee
- given: Martin
family: Wainwright
- given: Michael I.
family: Jordan
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 83-91
id: zhang17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 83
lastpage: 91
published: 2017-04-10 00:00:00 +0000
- title: 'An Information-Theoretic Route from Generalization in Expectation to Generalization in Probability'
abstract: 'One fundamental goal in any learning algorithm is to mitigate its risk for overfitting. Mathematically, this requires that the learning algorithm enjoys a small generalization risk, which is defined either in expectation or in probability. Both types of generalization are commonly used in the literature. For instance, generalization in expectation has been used to analyze algorithms, such as ridge regression and SGD, whereas generalization in probability is used in the VC theory, among others. Recently, a third notion of generalization has been studied, called uniform generalization, which requires that the generalization risk vanishes uniformly in expectation across all bounded parametric losses. It has been shown that uniform generalization is, in fact, equivalent to an information-theoretic stability constraint, and that it recovers classical results in learning theory. It is achievable under various settings, such as sample compression schemes, finite hypothesis spaces, finite domains, and differential privacy. However, the relationship between uniform generalization and concentration remained unknown. In this paper, we answer this question by proving that, while a generalization in expectation does not imply a generalization in probability, a uniform generalization in expectation does imply concentration. We establish a chain rule for the uniform generalization risk of the composition of hypotheses and use it to derive a large deviation bound. Finally, we prove that the bound is tight.'
volume: 54
URL: https://proceedings.mlr.press/v54/alabdulmohsin17a.html
PDF: http://proceedings.mlr.press/v54/alabdulmohsin17a/alabdulmohsin17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-alabdulmohsin17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Ibrahim
family: Alabdulmohsin
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 92-100
id: alabdulmohsin17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 92
lastpage: 100
published: 2017-04-10 00:00:00 +0000
- title: 'Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selection'
abstract: 'In the Best-k-Arm problem, we are given n stochastic bandit arms, each associated with an unknown reward distribution. We are required to identify the k arms with the largest means by taking as few samples as possible. In this paper, we make progress towards a complete characterization of the instance-wise sample complexity bounds for the Best-k-Arm problem. On the lower bound side, we obtain a novel complexity term to measure the sample complexity that every Best-k-Arm instance requires. This is derived by an interesting and nontrivial reduction from the Best-1-Arm problem. We also provide an elimination-based algorithm that matches the instance-wise lower bound within doubly-logarithmic factors. The sample complexity of our algorithm strictly dominates the state-of-the-art for Best-k-Arm (module constant factors).'
volume: 54
URL: https://proceedings.mlr.press/v54/chen17a.html
PDF: http://proceedings.mlr.press/v54/chen17a/chen17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-chen17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Lijie
family: Chen
- given: Jian
family: Li
- given: Mingda
family: Qiao
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 101-110
id: chen17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 101
lastpage: 110
published: 2017-04-10 00:00:00 +0000
- title: 'Guaranteed Non-convex Optimization: Submodular Maximization over Continuous Domains'
abstract: 'Submodular continuous functions are a category of (generally) non-convex/non-concave functions with a wide spectrum of applications. We characterize these functions and demonstrate that they can be maximized efficiently with approximation guarantees. Specifically, i) We introduce the weak DR property that gives a unified characterization of submodularity for all set, integer-lattice and continuous functions; ii) for maximizing monotone DR-submodular continuous functions under general down-closed convex constraints, we propose a Frank-Wolfe variant with (1-1/e) approximation guarantee, and sub-linear convergence rate; iii) for maximizing general non-monotone submodular continuous functions subject to box constraints, we propose a DoubleGreedy algorithm with 1/3 approximation guarantee. Submodular continuous functions naturally find applications in various real-world settings, including influence and revenue maximization with continuous assignments, sensor energy management, facility location, etc. Experimental results show that the proposed algorithms efficiently generate superior solutions compared to baseline algorithms.'
volume: 54
URL: https://proceedings.mlr.press/v54/bian17a.html
PDF: http://proceedings.mlr.press/v54/bian17a/bian17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-bian17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Andrew An
family: Bian
- given: Baharan
family: Mirzasoleiman
- given: Joachim
family: Buhmann
- given: Andreas
family: Krause
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 111-120
id: bian17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 111
lastpage: 120
published: 2017-04-10 00:00:00 +0000
- title: 'Tensor-Dictionary Learning with Deep Kruskal-Factor Analysis'
abstract: 'A multi-way factor analysis model is introduced for tensor-variate data of any order. Each data item is represented as a (sparse) sum of Kruskal decompositions, a Kruskal- factor analysis (KFA). KFA is nonparametric and can infer both the tensor-rank of each dictionary atom and the number of dictionary atoms. The model is adapted for online learning, which allows dictionary learning on large data sets. After KFA is introduced, the model is extended to a deep convolutional tensor-factor analysis, supervised by a Bayesian SVM. The experiments section demonstrates the improvement of KFA over vectorized approaches (e.g., BPFA), tensor decompositions, and convolutional neural networks (CNN) in multi-way denoising, blind inpainting, and image classification. The improvement in PSNR for the inpainting results over other methods exceeds 1dB in several cases and we achieve state of the art results on Caltech101 image classification. '
volume: 54
URL: https://proceedings.mlr.press/v54/stevens17a.html
PDF: http://proceedings.mlr.press/v54/stevens17a/stevens17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-stevens17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Andrew
family: Stevens
- given: Yunchen
family: Pu
- given: Yannan
family: Sun
- given: Gregory
family: Spell
- given: Lawrence
family: Carin
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 121-129
id: stevens17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 121
lastpage: 129
published: 2017-04-10 00:00:00 +0000
- title: 'Consistent and Efficient Nonparametric Different-Feature Selection'
abstract: 'Two-sample feature selection is a ubiquitous problem in both scientific and engineering studies. We propose a feature selection method to find features that describe a difference in two probability distributions. The proposed method is nonparametric and does not assume any specific parametric models on data distributions. We show that the proposed method is computationally efficient and does not require any extra computation for model selection. Moreover, we prove that the proposed method provides a consistent estimator of features under mild conditions. Our experimental results show that the proposed method outperforms the current method with regard to both accuracy and computation time.'
volume: 54
URL: https://proceedings.mlr.press/v54/hara17a.html
PDF: http://proceedings.mlr.press/v54/hara17a/hara17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-hara17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Satoshi
family: Hara
- given: Takayuki
family: Katsuki
- given: Hiroki
family: Yanagisawa
- given: Takafumi
family: Ono
- given: Ryo
family: Okamoto
- given: Shigeki
family: Takeuchi
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 130-138
id: hara17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 130
lastpage: 138
published: 2017-04-10 00:00:00 +0000
- title: 'Annular Augmentation Sampling'
abstract: 'The exponentially large sample space of general binary probabilistic models renders intractable standard operations such as exact marginalization, inference, and normalization. Typically, researchers deal with these distributions via deterministic approximations, the class of belief propagation methods being a prominent example. Comparatively, Markov Chain Monte Carlo methods have been significantly less used in this domain. In this work, we introduce an auxiliary variable MCMC scheme that samples from an annular augmented space, translating to a great circle path around the hypercube of the binary sample space. This annular augmentation sampler explores the sample space more effectively than coordinate-wise samplers and has no tunable parameters, leading to substantial performance gains in estimating quantities of interest in large binary models. We extend the method to incorporate into the sampler any existing mean-field approximation (such as from belief propagation), leading to further performance improvements. Empirically, we consider a range of large Ising models and an application to risk factors for heart disease.'
volume: 54
URL: https://proceedings.mlr.press/v54/fagan17a.html
PDF: http://proceedings.mlr.press/v54/fagan17a/fagan17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-fagan17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Francois
family: Fagan
- given: Jalaj
family: Bhandari
- given: John
family: Cunningham
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 139-147
id: fagan17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 139
lastpage: 147
published: 2017-04-10 00:00:00 +0000
- title: 'Less than a Single Pass: Stochastically Controlled Stochastic Gradient'
abstract: 'We develop and analyze a procedure for gradient-based optimization that we refer to as stochastically controlled stochastic gradient (SCSG). As a member of the SVRG family of algorithms, SCSG makes use of gradient estimates at two scales. Unlike most existing algorithms in this family, both the computation cost and the communication cost of SCSG do not necessarily scale linearly with the sample size n; indeed, these costs are independent of n when the target accuracy is small. An experimental evaluation of SCSG on the MNIST dataset shows that it can yield accurate results on this dataset on a single commodity machine with a memory footprint of only 2.6MB and only eight disk accesses.'
volume: 54
URL: https://proceedings.mlr.press/v54/lei17a.html
PDF: http://proceedings.mlr.press/v54/lei17a/lei17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-lei17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Lihua
family: Lei
- given: Michael
family: Jordan
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 148-156
id: lei17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 148
lastpage: 156
published: 2017-04-10 00:00:00 +0000
- title: 'Learning Time Series Detection Models from Temporally Imprecise Labels'
abstract: 'In this paper, we consider a new low-quality label learning problem: learning time series detection models from temporally imprecise labels. In this problem, the data consist of a set of input time series, and supervision is provided by a sequence of noisy time stamps corresponding to the occurrence of positive class events. Such temporally imprecise labels commonly occur in areas like mobile health research where human annotators are tasked with labeling the occurrence of very short duration events. We propose a general learning framework for this problem that can accommodate different base classifiers and noise models. We present results on real mobile health data showing that the proposed framework significantly outperforms a number of alternatives including assuming that the label time stamps are noise-free, transforming the problem into the multiple instance learning framework, and learning on labels that were manually re-aligned.'
volume: 54
URL: https://proceedings.mlr.press/v54/adams17a.html
PDF: http://proceedings.mlr.press/v54/adams17a/adams17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-adams17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Roy
family: Adams
- given: Ben
family: Marlin
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 157-165
id: adams17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 157
lastpage: 165
published: 2017-04-10 00:00:00 +0000
- title: 'Learning Cost-Effective and Interpretable Treatment Regimes'
abstract: 'Decision makers, such as doctors and judges, make crucial decisions such as recommending treatments to patients, and granting bails to defendants on a daily basis. Such decisions typically involve weighting the potential benefits of taking an action against the costs involved. In this work, we aim to automate this task of learning cost-effective, interpretable and actionable treatment regimes. We formulate this as a problem of learning a decision list – a sequence of if-then-else rules – which maps characteristics of subjects (eg., diagnostic test results of patients) to treatments. We propose a novel objective to construct a decision list which maximizes outcomes for the population, and minimizes overall costs. Since we do not observe the outcomes corresponding to counterfactual scenarios, we use techniques from causal inference literature to infer them. We model the problem of learning the decision list as a Markov Decision Process (MDP) and employ a variant of the Upper Confidence Bound for Trees (UCT) strategy which leverages customized checks for pruning the search space effectively. Experimental results on real world observational data capturing judicial bail decisions and treatment recommendations for asthma patients demonstrate the effectiveness of our approach.'
volume: 54
URL: https://proceedings.mlr.press/v54/lakkaraju17a.html
PDF: http://proceedings.mlr.press/v54/lakkaraju17a/lakkaraju17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-lakkaraju17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Himabindu
family: Lakkaraju
- given: Cynthia
family: Rudin
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 166-175
id: lakkaraju17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 166
lastpage: 175
published: 2017-04-10 00:00:00 +0000
- title: 'Linear Thompson Sampling Revisited'
abstract: 'We derive an alternative proof for the regret of Thompson sampling (TS) in the stochastic linear bandit setting. While we obtain a regret bound of order $O(d^3/2\sqrtT)$ as in previous results, the proof sheds new light on the functioning of the TS. We leverage on the structure of the problem to show how the regret is related to the sensitivity (i.e., the gradient) of the objective function and how selecting optimal arms associated to \textitoptimistic parameters does control it. Thus we show that TS can be seen as a generic randomized algorithm where the sampling distribution is designed to have a fixed probability of being optimistic, at the cost of an additional $\sqrtd$ regret factor compared to a UCB-like approach. Furthermore, we show that our proof can be readily applied to regularized linear optimization and generalized linear model problems.'
volume: 54
URL: https://proceedings.mlr.press/v54/abeille17a.html
PDF: http://proceedings.mlr.press/v54/abeille17a/abeille17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-abeille17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Marc
family: Abeille
- given: Alessandro
family: Lazaric
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 176-184
id: abeille17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 176
lastpage: 184
published: 2017-04-10 00:00:00 +0000
- title: 'A Sub-Quadratic Exact Medoid Algorithm'
abstract: 'We present a new algorithm, ‘trimed’ for obtaining the medoid of a set, that is the element of the set which minimises the mean distance to all other elements. The algorithm is shown to have, under certain assumptions, expected run time $O(N^(3/2))$ in $R^d$ where N is the set size, making it the first sub-quadratic exact medoid algorithm for $d > 1$. Experiments show that it performs very well on spatial network data, frequently requiring two orders of magnitude fewer distance calculations than state-of-the-art approximate algorithms. As an application, we show how trimed can be used as a component in an accelerated K-medoids algorithm, and then how it can be relaxed to obtain further computational gains with only a minor loss in cluster quality. '
volume: 54
URL: https://proceedings.mlr.press/v54/newling17a.html
PDF: http://proceedings.mlr.press/v54/newling17a/newling17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-newling17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: James
family: Newling
- given: Francois
family: Fleuret
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 185-193
id: newling17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 185
lastpage: 193
published: 2017-04-10 00:00:00 +0000
- title: 'Minimax Density Estimation for Growing Dimension'
abstract: 'This paper presents minimax rates for density estimation when the data dimension $d$ is allowed to grow with the number of observations $n$ rather than remaining fixed as in previous analyses. We prove a non-asymptotic lower bound which gives the worst-case rate over standard classes of smooth densities, and we show that kernel density estimators achieve this rate. We also give oracle choices for the bandwidth and derive the fastest rate $d$ can grow with $n$ to maintain estimation consistency.'
volume: 54
URL: https://proceedings.mlr.press/v54/mcdonald17a.html
PDF: http://proceedings.mlr.press/v54/mcdonald17a/mcdonald17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-mcdonald17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Daniel
family: McDonald
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 194-203
id: mcdonald17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 194
lastpage: 203
published: 2017-04-10 00:00:00 +0000
- title: 'Estimating Density Ridges by Direct Estimation of Density-Derivative-Ratios'
abstract: 'Estimation of \emphdensity ridges has been gathering a great deal of attention since it enables us to reveal lower-dimensional structures hidden in data. Recently, \emphsubspace constrained mean shift (SCMS) was proposed as a practical algorithm for density ridge estimation. A key technical ingredient in SCMS is to accurately estimate the ratios of the density derivatives to the density. SCMS takes a three-step approach for this purpose — first estimating the data density, then computing its derivatives, and finally taking their ratios. However, this three-step approach can be unreliable because a good density estimator does not necessarily mean a good density derivative estimator and division by an estimated density could significantly magnify the estimation error. To overcome these problems, we propose a novel method that directly estimates the ratios without going through density estimation and division. Our proposed estimator has an analytic-form solution and it can be computed efficiently. We further establish a non-parametric convergence bound for the proposed ratio estimator. Finally, based on this direct ratio estimator, we develop a practical algorithm for density ridge estimation and experimentally demonstrate its usefulness on a variety of datasets.'
volume: 54
URL: https://proceedings.mlr.press/v54/sasaki17a.html
PDF: http://proceedings.mlr.press/v54/sasaki17a/sasaki17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-sasaki17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Hiroaki
family: Sasaki
- given: Takafumi
family: Kanamori
- given: Masashi
family: Sugiyama
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 204-212
id: sasaki17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 204
lastpage: 212
published: 2017-04-10 00:00:00 +0000
- title: 'Learning Theory for Conditional Risk Minimization'
abstract: 'In this work we study the learnability of stochastic processes with respect to the conditional risk, i.e. the existence of a learning algorithm that improves its next-step performance with the amount of observed data. We introduce a notion of pairwise discrepancy between conditional distributions at different times steps and show how certain properties of these discrepancies can be used to construct a successful learning algorithm. Our main results are two theorems that establish criteria for learnability for many classes of stochastic processes, including all special cases studied previously in the literature. '
volume: 54
URL: https://proceedings.mlr.press/v54/zimin17a.html
PDF: http://proceedings.mlr.press/v54/zimin17a/zimin17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-zimin17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Alexander
family: Zimin
- given: Christoph
family: Lampert
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 213-222
id: zimin17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 213
lastpage: 222
published: 2017-04-10 00:00:00 +0000
- title: 'Near-optimal Bayesian Active Learning with Correlated and Noisy Tests'
abstract: ' We consider the Bayesian active learning and experimental design problem, where the goal is to learn the value of some unknown target variable through a sequence of informative, noisy tests. In contrast to prior work, we focus on the challenging, yet practically relevant setting where test outcomes can be conditionally dependent given the hidden target variable. Under such assumptions, common heuristics, such as greedily performing tests that maximize the reduction in uncertainty of the target, often perform poorly. We propose ECED, a novel, efficient active learning algorithm, and prove strong theoretical guarantees that hold with correlated, noisy tests. Rather than directly optimizing the prediction error, at each step, ECED picks the test that maximizes the gain in a surrogate objective, which takes into account the dependencies between tests. Our analysis relies on an information-theoretic auxiliary function to track the progress of ECED, and utilizes adaptive submodularity to attain the approximation bound. We demonstrate strong empirical performance of ECED on two problem instances, including a Bayesian experimental design task intended to distinguish among economic theories of how people make risky decisions, and an active preference learning task via pairwise comparisons.'
volume: 54
URL: https://proceedings.mlr.press/v54/chen17b.html
PDF: http://proceedings.mlr.press/v54/chen17b/chen17b.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-chen17b.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Yuxin
family: Chen
- given: Hamed
family: Hassani
- given: Andreas
family: Krause
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 223-231
id: chen17b
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 223
lastpage: 231
published: 2017-04-10 00:00:00 +0000
- title: 'Learning Nash Equilibrium for General-Sum Markov Games from Batch Data'
abstract: 'This paper addresses the problem of learning a Nash equilibrium in $γ$-discounted multiplayer general-sum Markov Games (MGs) in a batch setting. As the number of players increases in MG, the agents may either collaborate or team apart to increase their final rewards. One solution to address this problem is to look for a Nash equilibrium. Although, several techniques were found for the subcase of two-player zero-sum MGs, those techniques fail to find a Nash equilibrium in general-sum Markov Games. In this paper, we introduce a new definition of $ε$-Nash equilibrium in MGs which grasps the strategy’s quality for multiplayer games. We prove that minimizing the norm of two Bellman-like residuals implies to learn such an $ε$-Nash equilibrium. Then, we show that minimizing an empirical estimate of the $L_p$ norm of these Bellman-like residuals allows learning for general-sum games within the batch setting. Finally, we introduce a neural network architecture that successfully learns a Nash equilibrium in generic multiplayer general-sum turn-based MGs.'
volume: 54
URL: https://proceedings.mlr.press/v54/perolat17a.html
PDF: http://proceedings.mlr.press/v54/perolat17a/perolat17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-perolat17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Julien
family: Perolat
- given: Florian
family: Strub
- given: Bilal
family: Piot
- given: Olivier
family: Pietquin
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 232-241
id: perolat17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 232
lastpage: 241
published: 2017-04-10 00:00:00 +0000
- title: 'Distance Covariance Analysis'
abstract: 'We propose a dimensionality reduction method to identify linear projections that capture interactions between two or more sets of variables. The method, distance covariance analysis (DCA), can detect both linear and nonlinear relationships, and can take dependent variables into account. On previous testbeds and a new testbed that systematically assesses the ability to detect both linear and nonlinear interactions, DCA performs better than or comparable to existing methods, while being one of the fastest methods. To showcase the versatility of DCA, we also applied it to three different neurophysiological datasets.'
volume: 54
URL: https://proceedings.mlr.press/v54/cowley17a.html
PDF: http://proceedings.mlr.press/v54/cowley17a/cowley17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-cowley17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Benjamin
family: Cowley
- given: Joao
family: Semedo
- given: Amin
family: Zandvakili
- given: Matthew
family: Smith
- given: Adam
family: Kohn
- given: Byron
family: Yu
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 242-251
id: cowley17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 242
lastpage: 251
published: 2017-04-10 00:00:00 +0000
- title: 'Phase Retrieval Meets Statistical Learning Theory: A Flexible Convex Relaxation'
abstract: 'We propose a flexible convex relaxation for the phase retrieval problem that operates in the natural domain of the signal. Therefore, we avoid the prohibitive computational cost associated with “lifting” and semidefinite programming (SDP) in methods such as PhaseLift and compete with recently developed non-convex techniques for phase retrieval. We relax the quadratic equations for phaseless measurements to inequality constraints each of which representing a symmetric “slab”. Through a simple convex program, our proposed estimator finds an extreme point of the intersection of these slabs that is best aligned with a given anchor vector. We characterize geometric conditions that certify success of the proposed estimator. Furthermore, using classic results in statistical learning theory, we show that for random measurements the geometric certificates hold with high probability at an optimal sample complexity. Phase transition of our estimator is evaluated through simulations. Our numerical experiments also suggest that the proposed method can solve phase retrieval problems with coded diffraction measurements as well.'
volume: 54
URL: https://proceedings.mlr.press/v54/bahmani17a.html
PDF: http://proceedings.mlr.press/v54/bahmani17a/bahmani17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-bahmani17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Sohail
family: Bahmani
- given: Justin
family: Romberg
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 252-260
id: bahmani17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 252
lastpage: 260
published: 2017-04-10 00:00:00 +0000
- title: 'Regret Bounds for Lifelong Learning'
abstract: 'We consider the problem of transfer learning in an online setting. Different tasks are presented sequentially and processed by a within-task algorithm. We propose a lifelong learning strategy which refines the underlying data representation used by the within-task algorithm, thereby transferring information from one task to the next. We show that when the within-task algorithm comes with some regret bound, our strategy inherits this good property. Our bounds are in expectation for a general loss function, and uniform for a convex loss. We discuss applications to dictionary learning and finite set of predictors. In the latter case, we improve previous $O(1/\sqrt{m})$ bounds to $O(1/m)$, where $m$ is the per task sample size.'
volume: 54
URL: https://proceedings.mlr.press/v54/alquier17a.html
PDF: http://proceedings.mlr.press/v54/alquier17a/alquier17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-alquier17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Pierre
family: Alquier
- given: The Tien
family: Mai
- given: Massimiliano
family: Pontil
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 261-269
id: alquier17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 261
lastpage: 269
published: 2017-04-10 00:00:00 +0000
- title: 'Poisson intensity estimation with reproducing kernels'
abstract: 'Despite the fundamental nature of the Poisson process in the theory and application of stochastic processes, and its attractive generalizations (e.g. Cox process), few tractable nonparametric modeling approaches exist, especially in high dimensional settings. In this paper we develop a new, computationally tractable Reproducing Kernel Hilbert Space (RKHS) formulation for the inhomogeneous Poisson process. We model the square root of the intensity as an RKHS function. The modeling challenge is that the usual representer theorem arguments no longer apply due to the form of the inhomogeneous Poisson process likelihood. However, we prove that the representer theorem does hold in an appropriately transformed RKHS, guaranteeing that the optimization of the penalized likelihood can be cast as a tractable finite-dimensional problem. The resulting approach is simple to implement, and readily scales to high dimensions and large-scale datasets. '
volume: 54
URL: https://proceedings.mlr.press/v54/flaxman17a.html
PDF: http://proceedings.mlr.press/v54/flaxman17a/flaxman17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-flaxman17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Seth
family: Flaxman
- given: Yee Whye
family: Teh
- given: Dino
family: Sejdinovic
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 270-279
id: flaxman17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 270
lastpage: 279
published: 2017-04-10 00:00:00 +0000
- title: 'Generalized Pseudolikelihood Methods for Inverse Covariance Estimation'
abstract: 'We introduce PseudoNet, a new pseudolikelihood-based estimator of the inverse covariance matrix, that has a number of useful statistical and computational properties. We show, through detailed experiments with synthetic and also real-world finance as well as wind power data, that PseudoNet outperforms related methods in terms of estimation error and support recovery, making it well-suited for use in a downstream application, where obtaining low estimation error can be important. We also show, under regularity conditions, that PseudoNet is consistent. Our proof assumes the existence of accurate estimates of the diagonal entries of the underlying inverse covariance matrix; we additionally provide a two-step method to obtain these estimates, even in a high-dimensional setting, going beyond the proofs for related methods. Unlike other pseudolikelihood-based methods, we also show that PseudoNet does not saturate, i.e., in high dimensions, there is no hard limit on the number of nonzero entries in the PseudoNet estimate. We present a fast algorithm as well as screening rules that make computing the PseudoNet estimate over a range of tuning parameters tractable.'
volume: 54
URL: https://proceedings.mlr.press/v54/ali17a.html
PDF: http://proceedings.mlr.press/v54/ali17a/ali17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-ali17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Alnur
family: Ali
- given: Kshitij
family: Khare
- given: Sang-Yun
family: Oh
- given: Bala
family: Rajaratnam
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 280-288
id: ali17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 280
lastpage: 288
published: 2017-04-10 00:00:00 +0000
- title: 'Removing Phase Transitions from Gibbs Measures'
abstract: 'Gibbs measures are a fundamental class of distributions for the analysis of high dimensional data. Phase transitions, which are also known as degeneracy in the network science literature, are an emergent property of these models that well describe many physical systems. However, the reach of the Gibbs measure is now far outside the realm of physical systems, and in many of these domains multiphase behavior is a nuisance. This nuisance often makes distribution fitting impossible due to failure of the MCMC sampler, and even when an MLE fit is possible, if the solution is near a phase transition point, the plausibility of the fit can be highly questionable. We introduce a modification to the Gibbs distribution that reduces the effects of phase transitions, and with properly chosen hyper-parameters, provably removes all multiphase behavior. We show that this new distribution is just as easy to fit via MCMCMLE as the Gibbs measure, and provide examples in the Ising model from statistical physics and ERGMs from network science.'
volume: 54
URL: https://proceedings.mlr.press/v54/fellows17a.html
PDF: http://proceedings.mlr.press/v54/fellows17a/fellows17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-fellows17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Ian
family: Fellows
- given: Mark
family: Handcock
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 289-297
id: fellows17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 289
lastpage: 297
published: 2017-04-10 00:00:00 +0000
- title: 'Performance Bounds for Graphical Record Linkage'
abstract: 'Record linkage involves merging records in large, noisy databases to remove duplicate entities. It has become an important area because of its widespread occurrence in bibliometrics, public health, official statistics production, political science, and beyond. Traditional linkage methods directly linking records to one another are computationally infeasible as the number of records grows. As a result, it is increasingly common for researchers to treat linkage as a clustering task, in which each latent entity is associated with one or more noisy database records. We critically assess performance bounds using the Kullback-Leibler (KL) divergence under a Bayesian record linkage framework, making connections to Kolchin partition models. We provide an upper bound using the KL divergence and a lower bound on the minimum probability of misclassifying a latent entity. We give insights for when our bounds hold using simulated data and provide practical user guidance. '
volume: 54
URL: https://proceedings.mlr.press/v54/steorts17a.html
PDF: http://proceedings.mlr.press/v54/steorts17a/steorts17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-steorts17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Rebecca C.
family: Steorts
- given: Mattew
family: Barnes
- given: Willie
family: Neiswanger
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 298-306
id: steorts17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 298
lastpage: 306
published: 2017-04-10 00:00:00 +0000
- title: 'Regret Bounds for Transfer Learning in Bayesian Optimisation'
abstract: 'This paper studies the regret bound of two transfer learning algorithms in Bayesian optimisation. The first algorithm models any difference between the source and target functions as a noise process. The second algorithm proposes a new way to model the difference between the source and target as a Gaussian process which is then used to adapt the source data. We show that in both cases the regret bounds are tighter than in the no transfer case. We also experimentally compare the performance of these algorithms relative to no transfer learning and demonstrate benefits of transfer learning.'
volume: 54
URL: https://proceedings.mlr.press/v54/shilton17a.html
PDF: http://proceedings.mlr.press/v54/shilton17a/shilton17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-shilton17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Alistair
family: Shilton
- given: Sunil
family: Gupta
- given: Santu
family: Rana
- given: Svetha
family: Venkatesh
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 307-315
id: shilton17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 307
lastpage: 315
published: 2017-04-10 00:00:00 +0000
- title: 'Scaling Submodular Maximization via Pruned Submodularity Graphs'
abstract: 'We propose a new random pruning method (called “submodular sparsification (SS)”) to reduce the cost of submodular maximization. The pruning is applied via a “submodularity graph” over the $n$ ground elements, where each directed edge is associated with a pairwise dependency defined by the submodular function. In each step, SS prunes a $1-1/\sqrt{c}$ (for $c>1$) fraction of the nodes using weights on edges computed based on only a small number ($O(\log n)$) of randomly sampled nodes. The algorithm requires $\log_\sqrt{c}n$ steps with a small and highly parallelizable per-step computation. An accuracy-speed tradeoff parameter $c$, set as $c = 8$, leads to a fast shrink rate $\sqrt{2}/4$ and small iteration complexity $\log_{2\sqrt{2}}n$. Analysis shows that w.h.p., the greedy algorithm on the pruned set of size $O(\log^2 n)$ can achieve a guarantee similar to that of processing the original dataset. In news and video summarization tasks, SS is able to substantially reduce both computational costs and memory usage, while maintaining (or even slightly exceeding) the quality of the original (and much more costly) greedy algorithm.'
volume: 54
URL: https://proceedings.mlr.press/v54/zhou17a.html
PDF: http://proceedings.mlr.press/v54/zhou17a/zhou17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-zhou17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Tianyi
family: Zhou
- given: Hua
family: Ouyang
- given: Jeff
family: Bilmes
- given: Yi
family: Chang
- given: Carlos
family: Guestrin
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 316-324
id: zhou17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 316
lastpage: 324
published: 2017-04-10 00:00:00 +0000
- title: 'Localized Lasso for High-Dimensional Regression'
abstract: 'We introduce the localized Lasso, which learns models that both are interpretable and have a high predictive power in problems with high dimensionality d and small sample size n. More specifically, we consider a function defined by local sparse models, one at each data point. We introduce sample-wise network regularization to borrow strength across the models, and sample-wise exclusive group sparsity (a.k.a., l12 norm) to introduce diversity into the choice of feature sets in the local models. The local models are interpretable in terms of similarity of their sparsity patterns. The cost function is convex, and thus has a globally optimal solution. Moreover, we propose a simple yet efficient iterative least-squares based optimization procedure for the localized Lasso, which does not need a tuning parameter, and is guaranteed to converge to a globally optimal solution. The solution is empirically shown to outperform alternatives for both simulated and genomic personalized/precision medicine data.'
volume: 54
URL: https://proceedings.mlr.press/v54/yamada17a.html
PDF: http://proceedings.mlr.press/v54/yamada17a/yamada17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-yamada17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Makoto
family: Yamada
- given: Takeuchi
family: Koh
- given: Tomoharu
family: Iwata
- given: John
family: Shawe-Taylor
- given: Samuel
family: Kaski
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 325-333
id: yamada17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 325
lastpage: 333
published: 2017-04-10 00:00:00 +0000
- title: 'Encrypted Accelerated Least Squares Regression'
abstract: 'Information that is stored in an encrypted format is, by definition, usually not amenable to statistical analysis or machine learning methods. In this paper we present detailed analysis of coordinate and accelerated gradient descent algorithms which are capable of fitting least squares and penalised ridge regression models, using data encrypted under a fully homomorphic encryption scheme. Gradient descent is shown to dominate in terms of encrypted computational speed, and theoretical results are proven to give parameter bounds which ensure correctness of decryption. The characteristics of encrypted computation are empirically shown to favour a non-standard acceleration technique. This demonstrates the possibility of approximating conventional statistical regression methods using encrypted data without compromising privacy.'
volume: 54
URL: https://proceedings.mlr.press/v54/esperanca17a.html
PDF: http://proceedings.mlr.press/v54/esperanca17a/esperanca17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-esperanca17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Pedro
family: Esperanca
- given: Louis
family: Aslett
- given: Chris
family: Holmes
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 334-343
id: esperanca17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 334
lastpage: 343
published: 2017-04-10 00:00:00 +0000
- title: 'Random Consensus Robust PCA'
abstract: 'This paper presents R2PCA, a random consensus method for robust principal component analysis. R2PCA takes RANSAC’s principle of using as little data as possible one step further. It iteratively selects small subsets of the data to identify pieces of the principal components, to then stitch them together. We show that if the principal components are in general position and the errors are sufficiently sparse, R2PCA will exactly recover the principal components with probability 1, in lieu of assumptions on coherence or the distribution of the sparse errors, and even under adversarial settings. R2PCA enjoys many advantages: it works well under noise, its computational complexity scales linearly in the ambient dimension, it is easily parallelizable, and due to its low sample complexity, it can be used in settings where data is so large it cannot even be stored in memory. We complement our theoretical findings with synthetic and real data experiments showing that r2pca outperforms state-of-the-art methods in a broad range of settings.'
volume: 54
URL: https://proceedings.mlr.press/v54/pimentel-alarcon17a.html
PDF: http://proceedings.mlr.press/v54/pimentel-alarcon17a/pimentel-alarcon17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-pimentel-alarcon17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Daniel
family: Pimentel-Alarcon
- given: Robert
family: Nowak
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 344-352
id: pimentel-alarcon17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 344
lastpage: 352
published: 2017-04-10 00:00:00 +0000
- title: 'Gray-box Inference for Structured Gaussian Process Models'
abstract: 'We develop an automated variational inference method for Bayesian structured prediction problems with Gaussian process (GP) priors and linear-chain likelihoods. Our approach does not need to know the details of the structured likelihood model and can scale up to a large number of observations. Furthermore, we show that the required expected likelihood term and its gradients in the variational objective (ELBO) can be estimated efficiently by using expectations over very low-dimensional Gaussian distributions. Optimization of the ELBO is fully parallelizable over sequences and amenable to stochastic optimization, which we use along with control variate techniques to make our framework useful in practice. Results on a set of natural language processing tasks show that our method can be as good as (and sometimes better than, in particular with respect to expected log-likelihood) hard-coded approaches including SVM-struct and CRF, and overcomes the scalability limitations of previous inference algorithms based on sampling. Overall, this is a fundamental step to developing automated inference methods for Bayesian structured prediction.'
volume: 54
URL: https://proceedings.mlr.press/v54/galliani17a.html
PDF: http://proceedings.mlr.press/v54/galliani17a/galliani17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-galliani17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Pietro
family: Galliani
- given: Amir
family: Dezfouli
- given: Edwin
family: Bonilla
- given: Novi
family: Quadrianto
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 353-361
id: galliani17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 353
lastpage: 361
published: 2017-04-10 00:00:00 +0000
- title: 'Frank-Wolfe Algorithms for Saddle Point Problems'
abstract: 'We extend the Frank-Wolfe (FW) optimization algorithm to solve constrained smooth convex-concave saddle point (SP) problems. Remarkably, the method only requires access to linear minimization oracles. Leveraging recent advances in FW optimization, we provide the first proof of convergence of a FW-type saddle point solver over polytopes, thereby partially answering a 30 year-old conjecture. We also survey other convergence results and highlight gaps in the theoretical underpinnings of FW-style algorithms. Motivating applications without known efficient alternatives are explored through structured prediction with combinatorial penalties as well as games over matching polytopes involving an exponential number of constraints.'
volume: 54
URL: https://proceedings.mlr.press/v54/gidel17a.html
PDF: http://proceedings.mlr.press/v54/gidel17a/gidel17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-gidel17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Gauthier
family: Gidel
- given: Tony
family: Jebara
- given: Simon
family: Lacoste-Julien
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 362-371
id: gidel17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 362
lastpage: 371
published: 2017-04-10 00:00:00 +0000
- title: 'A Framework for Optimal Matching for Causal Inference'
abstract: 'We propose a novel framework for matching estimators for causal effect from observational data that is based on minimizing the dual norm of estimation error when expressed as an operator. We show that many popular matching estimators can be expressed as optimal in this framework, including nearest-neighbor matching, coarsened exact matching, and mean-matched sampling. This reveals their motivation and aptness as structural priors formulated by embedding the effect in a particular functional space. This also gives rise to a range of new, kernel-based matching estimators that arise when one embeds the effect in a reproducing kernel Hilbert space. Depending on the case, these estimators can be found using either quadratic optimization or integer optimization. We show that estimators based on universal kernels are universally consistent without model specification. In empirical results using both synthetic and real data, the new, kernel-based estimators outperform all standard causal estimators in estimation error.'
volume: 54
URL: https://proceedings.mlr.press/v54/kallus17a.html
PDF: http://proceedings.mlr.press/v54/kallus17a/kallus17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-kallus17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Nathan
family: Kallus
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 372-381
id: kallus17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 372
lastpage: 381
published: 2017-04-10 00:00:00 +0000
- title: 'Quantifying the accuracy of approximate diffusions and Markov chains'
abstract: 'Markov chains and diffusion processes are indispensable tools in machine learning and statistics that are used for inference, sampling, and modeling. With the growth of large-scale datasets, the computational cost associated with simulating these stochastic processes can be considerable, and many algorithms have been proposed to approximate the underlying Markov chain or diffusion. A fundamental question is how the computational savings trade off against the statistical error incurred due to approximations. This paper develops general results that address this question. We bound the Wasserstein distance between the equilibrium distributions of two diffusions as a function of their mixing rates and the deviation in their drifts. We show that this error bound is tight in simple Gaussian settings. Our general result on continuous diffusions can be discretized to provide insights into the computational–statistical trade-off of Markov chains. As an illustration, we apply our framework to derive finite-sample error bounds of approximate unadjusted Langevin dynamics. We characterize computation-constrained settings where, by using fast-to-compute approximate gradients in the Langevin dynamics, we obtain more accurate samples compared to using the exact gradients. Finally, as an additional application of our approach, we quantify the accuracy of approximate zig-zag sampling. Our theoretical analyses are supported by simulation experiments. '
volume: 54
URL: https://proceedings.mlr.press/v54/huggins17a.html
PDF: http://proceedings.mlr.press/v54/huggins17a/huggins17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-huggins17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Jonathan
family: Huggins
- given: James
family: Zou
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 382-391
id: huggins17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 382
lastpage: 391
published: 2017-04-10 00:00:00 +0000
- title: 'Stochastic Rank-1 Bandits'
abstract: 'We propose stochastic rank-1 bandits, a class of online learning problems where at each step a learning agent chooses a pair of row and column arms, and receives the product of their values as a reward. The main challenge of the problem is that the individual values of the row and column are unobserved. We assume that these values are stochastic and drawn independently. We propose a computationally-efficient algorithm for solving our problem, which we call Rank1Elim. We derive a O((K + L) (1 / Delta) log n) upper bound on its n-step regret, where K is the number of rows, L is the number of columns, and Delta is the minimum of the row and column gaps; under the assumption that the mean row and column rewards are bounded away from zero. To the best of our knowledge, we present the first bandit algorithm that finds the maximum entry of a rank-1 matrix whose regret is linear in K + L, 1 / Delta, and log n. We also derive a nearly matching lower bound. Finally, we evaluate Rank1Elim empirically on multiple problems. We observe that it leverages the structure of our problems and can learn near-optimal solutions even if our modeling assumptions are mildly violated.'
volume: 54
URL: https://proceedings.mlr.press/v54/katariya17a.html
PDF: http://proceedings.mlr.press/v54/katariya17a/katariya17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-katariya17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Sumeet
family: Katariya
- given: Branislav
family: Kveton
- given: Csaba
family: Szepesvari
- given: Claire
family: Vernade
- given: Zheng
family: Wen
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 392-401
id: katariya17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 392
lastpage: 401
published: 2017-04-10 00:00:00 +0000
- title: 'On the Troll-Trust Model for Edge Sign Prediction in Social Networks'
abstract: 'In the problem of edge sign prediction, we are given a directed graph (representing a social network), and our task is to predict the binary labels of the edges (i.e., the positive or negative nature of the social relationships). Many successful heuristics for this problem are based on the troll-trust features, estimating at each node the fraction of outgoing and incoming positive/negative edges. We show that these heuristics can be understood, and rigorously analyzed, as approximators to the Bayes optimal classifier for a simple probabilistic model of the edge labels. We then show that the maximum likelihood estimator for this model approximately corresponds to the predictions of a Label Propagation algorithm run on a transformed version of the original social graph. Extensive experiments on a number of real-world datasets show that this algorithm is competitive against state-of-the-art classifiers in terms of both accuracy and scalability. Finally, we show that troll-trust features can also be used to derive online learning algorithms which have theoretical guarantees even when edges are adversarially labeled.'
volume: 54
URL: https://proceedings.mlr.press/v54/falher17a.html
PDF: http://proceedings.mlr.press/v54/falher17a/falher17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-falher17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Géraud Le
family: Falher
- given: Nicolo
family: Cesa-Bianchi
- given: Claudio
family: Gentile
- given: Fabio
family: Vitale
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 402-411
id: falher17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 402
lastpage: 411
published: 2017-04-10 00:00:00 +0000
- title: 'Online Optimization of Smoothed Piecewise Constant Functions'
abstract: 'We study online optimization of smoothed piecewise constant functions over the domain [0, 1). This is motivated by the problem of adaptively picking parameters of learning algorithms as in the recently introduced framework by Gupta and Roughgarden (2016). Majority of the machine learning literature has focused on Lipschitz-continuous functions or functions with bounded gradients. This is with good reason-any learning algorithm suffers linear regret even against piecewise constant functions that are chosen adversarially, arguably the simplest of non-Lipschitz continuous functions. The smoothed setting we consider is inspired by the seminal work of Spielman and Teng (2004) and the recent work of Gupta and Roughgarden (2016)-in this setting, the sequence of functions may be chosen by an adversary, however, with some uncertainty in the location of discontinuities. We give algorithms that achieve sublinear regret in the full information and bandit settings.'
volume: 54
URL: https://proceedings.mlr.press/v54/cohen-addad17a.html
PDF: http://proceedings.mlr.press/v54/cohen-addad17a/cohen-addad17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-cohen-addad17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Vincent
family: Cohen-Addad
- given: Varun
family: Kanade
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 412-420
id: cohen-addad17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 412
lastpage: 420
published: 2017-04-10 00:00:00 +0000
- title: 'Combinatorial Topic Models using Small-Variance Asymptotics'
abstract: 'Modern topic models typically have a probabilistic formulation, and derive their inference algorithms based on Latent Dirichlet Allocation (LDA) and its variants. In contrast, we approach topic modeling via combinatorial optimization, and take a small-variance limit of LDA to derive a new objective function. We minimize this objective by using ideas from combinatorial optimization, obtaining a new, fast, and high-quality topic modeling algorithm. In particular, we show that our results are not only significantly better than traditional SVA algorithms, but also truly competitive with popular LDA-based approaches; we also discuss the (dis)similarities between our approach and its probabilistic counterparts.'
volume: 54
URL: https://proceedings.mlr.press/v54/jiang17a.html
PDF: http://proceedings.mlr.press/v54/jiang17a/jiang17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-jiang17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Ke
family: Jiang
- given: Suvrit
family: Sra
- given: Brian
family: Kulis
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 421-429
id: jiang17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 421
lastpage: 429
published: 2017-04-10 00:00:00 +0000
- title: 'ConvNets with Smooth Adaptive Activation Functions for Regression'
abstract: 'Within Neural Networks (NN), the parameters of Adaptive Activation Functions (AAF) control the shapes of activation functions. These parameters are trained along with other parameters in the NN. AAFs have improved performance of Convolutional Neural Networks (CNN) in multiple classification tasks. In this paper, we propose and apply AAFs on CNNs for regression tasks. We argue that applying AAFs in the regression (second-to-last) layer of a NN can significantly decrease the bias of the regression NN. However, using existing AAFs may lead to overfitting. To address this problem, we propose a Smooth Adaptive Activation Function (SAAF) with a piecewise polynomial form which can approximate any continuous function to arbitrary degree of error, while having a bounded Lipschitz constant for given bounded model parameters. As a result, NNs with SAAF can avoid overfitting by simply regularizing model parameters. We empirically evaluated CNNs with SAAFs and achieved state-of-the-art results on age and pose estimation datasets.'
volume: 54
URL: https://proceedings.mlr.press/v54/hou17a.html
PDF: http://proceedings.mlr.press/v54/hou17a/hou17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-hou17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Le
family: Hou
- given: Dimitris
family: Samaras
- given: Tahsin
family: Kurc
- given: Yi
family: Gao
- given: Joel
family: Saltz
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 430-439
id: hou17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 430
lastpage: 439
published: 2017-04-10 00:00:00 +0000
- title: 'Rapid Mixing Swendsen-Wang Sampler for Stochastic Partitioned Attractive Models'
abstract: 'The Gibbs sampler is the most popular Markov chain used for learning and inference problems in Graphical Models (GM). These tasks are computationally intractable in general, and the Gibbs sampler often suffers from slow mixing. In this paper, we study the Swendsen-Wang dynamics which is a more sophisticated Markov chain designed to overcome bottlenecks that impede Gibbs sampler. We prove O(log n) mixing time for attractive binary pairwise GMs (i.e., ferromagnetic Ising models) on stochastic partitioned graphs having n vertices, under some mild conditions including low temperature regions where the Gibbs sampler provably mixes exponentially slow. Our experiments also confirm that the Swendsen-Wang sampler significantly outperforms the Gibbs sampler for learning parameters of attractive GMs.'
volume: 54
URL: https://proceedings.mlr.press/v54/park17b.html
PDF: http://proceedings.mlr.press/v54/park17b/park17b.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-park17b.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Sejun
family: Park
- given: Yunhun
family: Jang
- given: Andreas
family: Galanis
- given: Jinwoo
family: Shin
- given: Daniel
family: Stefankovic
- given: Eric
family: Vigoda
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 440-449
id: park17b
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 440
lastpage: 449
published: 2017-04-10 00:00:00 +0000
- title: 'Efficient Rank Aggregation via Lehmer Codes'
abstract: 'We propose a novel rank aggregation method based on converting permutations into their corresponding Lehmer codes or other subdiagonal images. Lehmer codes, also known as inversion vectors, are vector representations of permutations in which each coordinate can take values not restricted by the values of other coordinates. This transformation allows for decoupling of the coordinates and for performing aggregation via simple scalar median or mode computations. We present simulation results illustrating the performance of this completely parallelizable approach and analytically prove that both the mode and median aggregation procedure recover the correct centroid aggregate with small sample complexity when the permutations are drawn according to the well-known Mallows models. The proposed Lehmer code approach may also be used on partial rankings, with similar performance guarantees. '
volume: 54
URL: https://proceedings.mlr.press/v54/li17b.html
PDF: http://proceedings.mlr.press/v54/li17b/li17b.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-li17b.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Pan
family: Li
- given: Arya
family: Mazumdar
- given: Olgica
family: Milenkovic
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 450-459
id: li17b
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 450
lastpage: 459
published: 2017-04-10 00:00:00 +0000
- title: 'Nonlinear ICA of Temporally Dependent Stationary Sources'
abstract: 'We develop a nonlinear generalization of independent component analysis (ICA) or blind source separation, based on temporal dependencies (e.g. autocorrelations). We introduce a nonlinear generative model where the independent sources are assumed to be temporally dependent, non-Gaussian, and stationary, and we observe arbitrarily nonlinear mixtures of them. We develop a method for estimating the model (i.e. separating the sources) based on logistic regression in a neural network which learns to discriminate between a short temporal window of the data vs. a temporal window of temporally permuted data. We prove that the method estimates the sources for general smooth mixing nonlinearities, assuming the sources have sufficiently strong temporal dependencies, and these dependencies are in a certain way different from dependencies found in Gaussian processes. For Gaussian (and similar) sources, the method estimates the nonlinear part of the mixing. We thus provide the first rigorous and general proof of identifiability of nonlinear ICA for temporally dependent sources, together with a practical method for its estimation.'
volume: 54
URL: https://proceedings.mlr.press/v54/hyvarinen17a.html
PDF: http://proceedings.mlr.press/v54/hyvarinen17a/hyvarinen17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-hyvarinen17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Aapo
family: Hyvarinen
- given: Hiroshi
family: Morioka
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 460-469
id: hyvarinen17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 460
lastpage: 469
published: 2017-04-10 00:00:00 +0000
- title: 'Stochastic Difference of Convex Algorithm and its Application to Training Deep Boltzmann Machines'
abstract: 'Difference of convex functions (DC) programming is an important approach to nonconvex optimization problems because these structures can be encountered in several fields. Effective optimization methods, called DC algorithms, have been developed in deterministic optimization literature. In machine learning, a lot of important learning problems such as the Boltzmann machines (BMs) can be formulated as DC programming. However, there is no DC-like algorithm guaranteed by convergence rate analysis for stochastic problems that are more suitable settings for machine learning tasks. In this paper, we propose a stochastic variant of DC algorithm and give computational complexities to converge to a stationary point under several situations. Moreover, we show our method includes expectation-maximization (EM) and Monte Carlo EM (MCEM) algorithm as special cases on training BMs. In other words, we extend EM/MCEM algorithm to more effective methods from DC viewpoint with theoretical convergence guarantees. Experimental results indicate that our method performs well for training binary restricted Boltzmann machines and deep Boltzmann machines without pre-training.'
volume: 54
URL: https://proceedings.mlr.press/v54/nitanda17a.html
PDF: http://proceedings.mlr.press/v54/nitanda17a/nitanda17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-nitanda17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Atsushi
family: Nitanda
- given: Taiji
family: Suzuki
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 470-478
id: nitanda17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 470
lastpage: 478
published: 2017-04-10 00:00:00 +0000
- title: 'Global Convergence of Non-Convex Gradient Descent for Computing Matrix Squareroot'
abstract: 'While there has been a significant amount of work studying gradient descent techniques for non-convex optimization problems over the last few years, all existing results establish either local convergence with good rates or global convergence with highly suboptimal rates, for many problems of interest. In this paper, we take the first step in getting the best of both worlds – establishing global convergence and obtaining a good rate of convergence for the problem of computing squareroot of a positive semidefinite (PSD) matrix, which is a widely studied problem in numerical linear algebra with applications in machine learning and statistics among others. Given a PSD matrix M and a PSD starting point $U_0$, we show that gradient descent with appropriately chosen step-size finds an epsilon-accurate squareroot of M in $O(α\log(||M-U_0||_F^2 / ε))$ iterations, where $α= (\max{||U_0||^2, ||M||} / \min{\sigma_min^2(U_0), \sigma_min(M)} )^3/2$. Our result is the first to establish global convergence for this problem and that it is robust to errors in each iteration. A key contribution of our work is the general proof technique which we believe should further excite research in understanding deterministic and stochastic variants of simple non-convex gradient descent algorithms with good global convergence rates for other problems in machine learning and numerical linear algebra. '
volume: 54
URL: https://proceedings.mlr.press/v54/jain17a.html
PDF: http://proceedings.mlr.press/v54/jain17a/jain17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-jain17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Prateek
family: Jain
- given: Chi
family: Jin
- given: Sham
family: Kakade
- given: Praneeth
family: Netrapalli
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 479-488
id: jain17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 479
lastpage: 488
published: 2017-04-10 00:00:00 +0000
- title: 'Reparameterization Gradients through Acceptance-Rejection Sampling Algorithms'
abstract: 'Variational inference using the reparameterization trick has enabled large-scale approximate Bayesian inference in complex probabilistic models, leveraging stochastic optimization to sidestep intractable expectations. The reparameterization trick is applicable when we can simulate a random variable by applying a differentiable deterministic function on an auxiliary random variable whose distribution is fixed. For many distributions of interest (such as the gamma or Dirichlet), simulation of random variables relies on acceptance-rejection sampling. The discontinuity introduced by the accept-reject step means that standard reparameterization tricks are not applicable. We propose a new method that lets us leverage reparameterization gradients even when variables are outputs of a acceptance-rejection sampling algorithm. Our approach enables reparameterization on a larger class of variational distributions. In several studies of real and synthetic data, we show that the variance of the estimator of the gradient is significantly lower than other state-of-the-art methods. This leads to faster convergence of stochastic gradient variational inference.'
volume: 54
URL: https://proceedings.mlr.press/v54/naesseth17a.html
PDF: http://proceedings.mlr.press/v54/naesseth17a/naesseth17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-naesseth17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Christian
family: Naesseth
- given: Francisco
family: Ruiz
- given: Scott
family: Linderman
- given: David
family: Blei
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 489-498
id: naesseth17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 489
lastpage: 498
published: 2017-04-10 00:00:00 +0000
- title: 'Asymptotically exact inference in differentiable generative models'
abstract: 'Many generative models can be expressed as a differentiable function of random inputs drawn from some simple probability density. This framework includes both deep generative architectures such as Variational Autoencoders and a large class of procedurally defined simulator models. We present a method for performing efficient MCMC inference in such models when conditioning on observations of the model output. For some models this offers an asymptotically exact inference method where Approximate Bayesian Computation might otherwise be employed. We use the intuition that inference corresponds to integrating a density across the manifold corresponding to the set of inputs consistent with the observed outputs. This motivates the use of a constrained variant of Hamiltonian Monte Carlo which leverages the smooth geometry of the manifold to coherently move between inputs exactly consistent with observations. We validate the method by performing inference tasks in a diverse set of models.'
volume: 54
URL: https://proceedings.mlr.press/v54/graham17a.html
PDF: http://proceedings.mlr.press/v54/graham17a/graham17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-graham17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Matthew
family: Graham
- given: Amos
family: Storkey
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 499-508
id: graham17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 499
lastpage: 508
published: 2017-04-10 00:00:00 +0000
- title: 'Decentralized Collaborative Learning of Personalized Models over Networks'
abstract: 'We consider a set of learning agents in a collaborative peer-to-peer network, where each agent learns a personalized model according to its own learning objective. The question addressed in this paper is: how can agents improve upon their locally trained model by communicating with other agents that have similar objectives? We introduce and analyze two asynchronous gossip algorithms running in a fully decentralized manner. Our first approach, inspired from label propagation, aims to smooth pre-trained local models over the network while accounting for the confidence that each agent has in its initial model. In our second approach, agents jointly learn and propagate their model by making iterative updates based on both their local dataset and the behavior of their neighbors. To optimize this challenging objective, our decentralized algorithm is based on ADMM.'
volume: 54
URL: https://proceedings.mlr.press/v54/vanhaesebrouck17a.html
PDF: http://proceedings.mlr.press/v54/vanhaesebrouck17a/vanhaesebrouck17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-vanhaesebrouck17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Paul
family: Vanhaesebrouck
- given: Aurélien
family: Bellet
- given: Marc
family: Tommasi
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 509-517
id: vanhaesebrouck17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 509
lastpage: 517
published: 2017-04-10 00:00:00 +0000
- title: 'Contextual Bandits with Latent Confounders: An NMF Approach'
abstract: 'Motivated by online recommendation and advertising systems, we consider a causal model for stochastic contextual bandits with a latent low-dimensional confounder. In our model, there are $L$ observed contexts and $K$ arms of the bandit. The observed context influences the reward obtained through a latent confounder variable with cardinality $m$ ($m ≪L,K$). The arm choice and the latent confounder causally determines the reward while the observed context is correlated with the confounder. Under this model, the $L \times K$ mean reward matrix $\mathbfU$ (for each context in $[L]$ and each arm in $[K]$) factorizes into non-negative factors $\mathbfA$ ($L \times m$) and $\mathbfW$ ($m \times K$). This insight enables us to propose an $ε$-greedy NMF-Bandit algorithm that designs a sequence of interventions (selecting specific arms), that achieves a balance between learning this low-dimensional structure and selecting the best arm to minimize regret. Our algorithm achieves a regret of $\mathcalO\left(L\mathrmpoly(m, \log K) \log T \right)$ at time $T$, as compared to $\mathcalO(LK\log T)$ for conventional contextual bandits, assuming a constant gap between the best arm and the rest for each context. These guarantees are obtained under mild sufficiency conditions on the factors that are weaker versions of the well-known Statistical RIP condition. We further propose a class of generative models that satisfy our sufficient conditions, and derive a lower bound of $\mathcalO\left(Km\log T\right)$. These are the first regret guarantees for online matrix completion with bandit feedback, when the rank is greater than one. We further compare the performance of our algorithm with the state of the art, on synthetic and real world data-sets.'
volume: 54
URL: https://proceedings.mlr.press/v54/sen17a.html
PDF: http://proceedings.mlr.press/v54/sen17a/sen17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-sen17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Rajat
family: Sen
- given: Karthikeyan
family: Shanmugam
- given: Murat
family: Kocaoglu
- given: Alex
family: Dimakis
- given: Sanjay
family: Shakkottai
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 518-527
id: sen17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 518
lastpage: 527
published: 2017-04-10 00:00:00 +0000
- title: 'Fast Bayesian Optimization of Machine Learning Hyperparameters on Large Datasets'
abstract: 'Bayesian optimization has become a successful tool for hyperparameter optimization of machine learning algorithms, such as support vector machines or deep neural networks. Despite its success, for large datasets, training and validating a single configuration often takes hours, days, or even weeks, which limits the achievable performance. To accelerate hyperparameter optimization, we propose a generative model for the validation error as a function of training set size, which is learned during the optimization process and allows exploration of preliminary configurations on small subsets, by extrapolating to the full dataset. We construct a Bayesian optimization procedure, dubbed FABOLAS, which models loss and training time as a function of dataset size and automatically trades off high information gain about the global optimum against computational cost. Experiments optimizing support vector machines and deep neural networks show that FABOLAS often finds high-quality solutions 10 to 100 times faster than other state-of-the-art Bayesian optimization methods or the recently proposed bandit strategy Hyperband.'
volume: 54
URL: https://proceedings.mlr.press/v54/klein17a.html
PDF: http://proceedings.mlr.press/v54/klein17a/klein17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-klein17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Aaron
family: Klein
- given: Stefan
family: Falkner
- given: Simon
family: Bartels
- given: Philipp
family: Hennig
- given: Frank
family: Hutter
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 528-536
id: klein17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 528
lastpage: 536
published: 2017-04-10 00:00:00 +0000
- title: 'Least-Squares Log-Density Gradient Clustering for Riemannian Manifolds'
abstract: 'Mean shift is a mode-seeking clustering algorithm that has been successfully used in a wide range of applications such as image segmentation and object tracking. To further improve the clustering performance, mean shift has been extended to various directions, including generalization to handle data on Riemannian manifolds and extension to directly estimating the density gradient without density estimation. In this paper, we combine these ideas and propose a novel mode-seeking algorithm for Riemannian manifolds with direct density-gradient estimation. Although the idea of combining the two extensions is rather straightforward, directly estimating the density gradient on Riemannian manifolds is mathematically challenging. We will provide a mathematically sound algorithm and demonstrate its usefulness through experiments.'
volume: 54
URL: https://proceedings.mlr.press/v54/ashizawa17a.html
PDF: http://proceedings.mlr.press/v54/ashizawa17a/ashizawa17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-ashizawa17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Mina
family: Ashizawa
- given: Hiroaki
family: Sasaki
- given: Tomoya
family: Sakai
- given: Masashi
family: Sugiyama
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 537-546
id: ashizawa17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 537
lastpage: 546
published: 2017-04-10 00:00:00 +0000
- title: 'Fast column generation for atomic norm regularization'
abstract: 'We consider optimization problems that consist in minimizing a quadratic function under an atomic norm regularization or constraint. In the line of work on conditional gradient algorithms, we show that the fully corrective Frank-Wolfe (FCFW) algorithm — which is most naturally reformulated as a column generation algorithm in the regularized case — can be made particularly efficient for difficult problems in this family by solving the simplicial or conical subproblems produced by FCFW using a special instance of a classical active set algorithm for quadratic programming that generalizes the min-norm point algorithm.'
volume: 54
URL: https://proceedings.mlr.press/v54/vinyes17a.html
PDF: http://proceedings.mlr.press/v54/vinyes17a/vinyes17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-vinyes17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Marina
family: Vinyes
- given: Guillaume
family: Obozinski
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 547-556
id: vinyes17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 547
lastpage: 556
published: 2017-04-10 00:00:00 +0000
- title: 'Bayesian Hybrid Matrix Factorisation for Data Integration'
abstract: 'We introduce a novel Bayesian hybrid matrix factorisation model (HMF) for data integration, based on combining multiple matrix factorisation methods, that can be used for in- and out-of-matrix prediction of missing values. The model is very general and can be used to integrate many datasets across different entity types, including repeated experiments, similarity matrices, and very sparse datasets. We apply our method on two biological applications, and extensively compare it to state-of-the-art machine learning and matrix factorisation models. For in-matrix predictions on drug sensitivity datasets we obtain consistently better performances than existing methods. This is especially the case when we increase the sparsity of the datasets. Furthermore, we perform out-of-matrix predictions on methylation and gene expression datasets, and obtain the best results on two of the three datasets, especially when the predictivity of datasets is high.'
volume: 54
URL: https://proceedings.mlr.press/v54/brouwer17a.html
PDF: http://proceedings.mlr.press/v54/brouwer17a/brouwer17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-brouwer17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Thomas
family: Brouwer
- given: Pietro
family: Lio
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 557-566
id: brouwer17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 557
lastpage: 566
published: 2017-04-10 00:00:00 +0000
- title: 'Co-Occurring Directions Sketching for Approximate Matrix Multiply'
abstract: 'We introduce co-occurring directions sketching, a deterministic algorithm for approximate matrix product (AMM), in the streaming model. We show that co-occurring directions achieves a better error bound for AMM than other randomized and deterministic approaches for AMM. Co-occurring directions gives a (1 + epsilon) - approximation of the optimal low rank approximation of a matrix product. Empirically our algorithm outperforms competing methods for AMM, for a small sketch size. We validate empirically our theoretical findings and algorithms.'
volume: 54
URL: https://proceedings.mlr.press/v54/mroueh17a.html
PDF: http://proceedings.mlr.press/v54/mroueh17a/mroueh17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-mroueh17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Youssef
family: Mroueh
- given: Etienne
family: Marcheret
- given: Vaibahava
family: Goel
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 567-575
id: mroueh17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 567
lastpage: 575
published: 2017-04-10 00:00:00 +0000
- title: 'Exploration-Exploitation in MDPs with Options'
abstract: 'While a large body of empirical results show that temporally-extended actions and options may significantly affect the learning performance of an agent, the theoretical understanding of how and when options can be beneficial in online reinforcement learning is relatively limited. In this paper, we derive an upper and lower bound on the regret of a variant of UCRL using options. While we first analyze the algorithm in the general case of semi-Markov decision processes (SMDPs), we show how these results can be translated to the specific case of MDPs with options and we illustrate simple scenarios in which the regret of learning with options can be provably much smaller than the regret suffered when learning with primitive actions. '
volume: 54
URL: https://proceedings.mlr.press/v54/fruit17a.html
PDF: http://proceedings.mlr.press/v54/fruit17a/fruit17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-fruit17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Ronan
family: Fruit
- given: Alessandro
family: Lazaric
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 576-584
id: fruit17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 576
lastpage: 584
published: 2017-04-10 00:00:00 +0000
- title: 'Local Perturb-and-MAP for Structured Prediction'
abstract: 'Conditional random fields (CRFs) provide a powerful tool for structured prediction, but cast significant challenges in both the learning and inference steps. Approximation techniques are widely used in both steps, which should be considered jointly to guarantee good performance (a.k.a. “inferning"). Perturb-and-MAP models provide a promising alternative to CRFs, but require global combinatorial optimization and hence they are usable only on specific models. In this work, we present a new Local Perturb-and-MAP (locPMAP) framework that replaces the global optimization with a local optimization by exploiting our observed connection between locPMAP and the pseudolikelihood of the original CRF model. We test our approach on three different vision tasks and show that our method achieves consistently improved performance over other approximate inference techniques optimized to a pseudolikelihood objective. Additionally, we demonstrate that we can integrate our method in the fully convolutional network framework to increase our model’s complexity. Finally, our observed connection between locPMAP and the pseudolikelihood leads to a novel perspective for understanding and using pseudolikelihood. '
volume: 54
URL: https://proceedings.mlr.press/v54/bertasius17a.html
PDF: http://proceedings.mlr.press/v54/bertasius17a/bertasius17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-bertasius17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Gedas
family: Bertasius
- given: Qiang
family: Liu
- given: Lorenzo
family: Torresani
- given: Jianbo
family: Shi
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 585-594
id: bertasius17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 585
lastpage: 594
published: 2017-04-10 00:00:00 +0000
- title: 'Gradient Boosting on Stochastic Data Streams'
abstract: 'Boosting is a popular ensemble algorithm that generates more powerful learners by linearly combining base models from a simpler hypothesis class. In this work, we investigate the problem of adapting batch gradient boosting for minimizing convex loss functions to online setting where the loss at each iteration is i.i.d sampled from an unknown distribution. To generalize from batch to online, we first introduce the definition of online weak learning edge with which for strongly convex and smooth loss functions, we present an algorithm, Streaming Gradient Boosting (SGB) with exponential shrinkage guarantees in the number of weak learners. We further present an adaptation of SGB to optimize non-smooth loss functions, for which we derive a $O(\ln(N)/N)$ convergence rate. We also show that our analysis can extend to adversarial online learning setting under a stronger assumption that the online weak learning edge will hold in adversarial setting. We finally demonstrate experimental results showing that in practice our algorithms can achieve competitive results as classic gradient boosting while using less computation.'
volume: 54
URL: https://proceedings.mlr.press/v54/hu17a.html
PDF: http://proceedings.mlr.press/v54/hu17a/hu17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-hu17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Hanzhang
family: Hu
- given: Wen
family: Sun
- given: Arun
family: Venkatraman
- given: Martial
family: Hebert
- given: Andrew
family: Bagnell
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 595-603
id: hu17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 595
lastpage: 603
published: 2017-04-10 00:00:00 +0000
- title: 'Online Learning and Blackwell Approachability with Partial Monitoring: Optimal Convergence Rates'
abstract: 'Blackwell approachability is an online learning setup generalizing the classical problem of regret minimization by allowing for instance multi-criteria optimization, global (online) optimization of a convex loss, or online linear optimization under some cumulative constraint. We consider partial monitoring where the decision maker does not necessarily observe the outcomes of his decision (unlike the traditional regret/bandit literature). Instead, he receives a random signal correlated to the decision–outcome pair, or only to the outcome. We construct, for the first time, approachability algorithms with convergence rate of order $O(T^-1/2)$ when the signal is independent of the decision and of order $O(T^-1/3)$ in the case of general signals. Those rates are optimal in the sense that they cannot be improved without further assumption on the structure of the objectives and/or the signals.'
volume: 54
URL: https://proceedings.mlr.press/v54/kwon17a.html
PDF: http://proceedings.mlr.press/v54/kwon17a/kwon17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-kwon17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Joon
family: Kwon
- given: Vianney
family: Perchet
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 604-613
id: kwon17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 604
lastpage: 613
published: 2017-04-10 00:00:00 +0000
- title: 'Tensor Decompositions via Two-Mode Higher-Order SVD (HOSVD)'
abstract: 'Tensor decompositions have rich applications in statistics and machine learning, and developing efficient, accurate algorithms for the problem has received much attention recently. Here, we present a new method built on Kruskal’s uniqueness theorem to decompose symmetric, nearly orthogonally decomposable tensors. Unlike the classical higher-order singular value decomposition which unfolds a tensor along a single mode, we consider unfoldings along two modes and use rank-1 constraints to characterize the underlying components. This tensor decomposition method provably handles a greater level of noise compared to previous methods and achieves a high estimation accuracy. Numerical results demonstrate that our algorithm is robust to various noise distributions and that it performs especially favorably as the order increases.'
volume: 54
URL: https://proceedings.mlr.press/v54/wang17a.html
PDF: http://proceedings.mlr.press/v54/wang17a/wang17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-wang17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Miaoyan
family: Wang
- given: Yun
family: Song
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 614-622
id: wang17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 614
lastpage: 622
published: 2017-04-10 00:00:00 +0000
- title: 'Beta calibration: a well-founded and easily implemented improvement on logistic calibration for binary classifiers'
abstract: 'For optimal decision making under variable class distributions and misclassification costs a classifier needs to produce well-calibrated estimates of the posterior probability. Isotonic calibration is a powerful non-parametric method that is however prone to overfitting on smaller datasets; hence a parametric method based on the logistic curve is commonly used. While logistic calibration is designed for normally distributed per-class scores, we demonstrate experimentally that many classifiers including Naive Bayes and Adaboost suffer from a particular distortion where these score distributions are heavily skewed. In such cases logistic calibration can easily yield probability estimates that are worse than the original scores. Moreover, the logistic curve family does not include the identity function, and hence logistic calibration can easily uncalibrate a perfectly calibrated classifier. In this paper we solve all these problems with a richer class of calibration maps based on the beta distribution. We derive the method from first principles and show that fitting it is as easy as fitting a logistic curve. Extensive experiments show that beta calibration is superior to logistic calibration for Naive Bayes and Adaboost. '
volume: 54
URL: https://proceedings.mlr.press/v54/kull17a.html
PDF: http://proceedings.mlr.press/v54/kull17a/kull17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-kull17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Meelis
family: Kull
- given: Telmo Silva
family: Filho
- given: Peter
family: Flach
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 623-631
id: kull17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 623
lastpage: 631
published: 2017-04-10 00:00:00 +0000
- title: 'Detecting Dependencies in Sparse, Multivariate Databases Using Probabilistic Programming and Non-parametric Bayes'
abstract: 'Datasets with hundreds of variables and many missing values are commonplace. In this setting, it is both statistically and computationally challenging to detect true predictive relationships between variables and also to suppress false positives. This paper proposes an approach that combines probabilistic programming, information theory, and non-parametric Bayes. It shows how to use Bayesian non-parametric modeling to (i) build an ensemble of joint probability models for all the variables; (ii) efficiently detect marginal independencies; and (iii) estimate the conditional mutual information between arbitrary subsets of variables, subject to a broad class of constraints. Users can access these capabilities using BayesDB, a probabilistic programming platform for probabilistic data analysis, by writing queries in a simple, SQL-like language. This paper demonstrates empirically that the method can (i) detect context-specific (in)dependencies on challenging synthetic problems and (ii) yield improved sensitivity and specificity over baselines from statistics and machine learning, on a real-world database of over 300 sparsely observed indicators of macroeconomic development and public health.'
volume: 54
URL: https://proceedings.mlr.press/v54/saad17a.html
PDF: http://proceedings.mlr.press/v54/saad17a/saad17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-saad17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Feras
family: Saad
- given: Vikash
family: Mansinghka
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 632-641
id: saad17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 632
lastpage: 641
published: 2017-04-10 00:00:00 +0000
- title: 'High-dimensional Time Series Clustering via Cross-Predictability'
abstract: 'The key to time series clustering is how to characterize the similarity between any two time series. In this paper, we explore a new similarity metric called “cross-predictability”: the degree to which a future value in each time series is predicted by past values of the others. However, it is challenging to estimate such cross-predictability among time series in the high-dimensional regime, where the number of time series is much larger than the length of each time series. We address this challenge with a sparsity assumption: only time series in the same cluster have significant cross-predictability with each other. We demonstrate that this approach is computationally attractive, and provide a theoretical proof that the proposed algorithm will identify the correct clustering structure with high probability under certain conditions. To the best of our knowledge, this is the first practical high-dimensional time series clustering algorithm with a provable guarantee. We evaluate with experiments on both synthetic data and real-world data, and results indicate that our method can achieve more than 80% clustering accuracy on real-world data, which is 20% higher than the state-of-art baselines.'
volume: 54
URL: https://proceedings.mlr.press/v54/hong17a.html
PDF: http://proceedings.mlr.press/v54/hong17a/hong17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-hong17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Dezhi
family: Hong
- given: Quanquan
family: Gu
- given: Kamin
family: Whitehouse
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 642-651
id: hong17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 642
lastpage: 651
published: 2017-04-10 00:00:00 +0000
- title: 'Minimax Approach to Variable Fidelity Data Interpolation'
abstract: 'Engineering problems often involve data sources of variable fidelity with different costs of obtaining an observation. In particular, one can use both a cheap low fidelity function (e.g. a computational experiment with a CFD code) and an expensive high fidelity function (e.g. a wind tunnel experiment) to generate a data sample in order to construct a regression model of a high fidelity function. The key question in this setting is how the sizes of the high and low fidelity data samples should be selected in order to stay within a given computational budget and maximize accuracy of the regression model prior to committing resources on data acquisition. In this paper we obtain minimax interpolation errors for single and variable fidelity scenarios for a multivariate Gaussian process regression. Evaluation of the minimax errors allows us to identify cases when the variable fidelity data provides better interpolation accuracy than the exclusively high fidelity data for the same computational budget. These results allow us to calculate the optimal shares of variable fidelity data samples under the given computational budget constraint. Real and synthetic data experiments suggest that using the obtained optimal shares often outperforms natural heuristics in terms of the regression accuracy. '
volume: 54
URL: https://proceedings.mlr.press/v54/zaytsev17a.html
PDF: http://proceedings.mlr.press/v54/zaytsev17a/zaytsev17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-zaytsev17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Alexey
family: Zaytsev
- given: Evgeny
family: Burnaev
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 652-661
id: zaytsev17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 652
lastpage: 661
published: 2017-04-10 00:00:00 +0000
- title: 'Data Driven Resource Allocation for Distributed Learning'
abstract: 'In distributed machine learning, data is dispatched to multiple machines for processing. Motivated by the fact that similar data points often belong to the same or similar classes, and more generally, classification rules of high accuracy tend to be “locally simple but globally complex” (Vapnik and Bottou, 1993), we propose data dependent dispatching that takes advantage of such structure. We present an in-depth analysis of this model, providing new algorithms with provable worst-case guarantees, analysis proving existing scalable heuristics perform well in natural non worst-case conditions, and techniques for extending a dispatching rule from a small sample to the entire distribution. We overcome novel technical challenges to satisfy important conditions for accurate distributed learning, including fault tolerance and balancedness. We empirically compare our approach with baselines based on random partitioning, balanced partition trees, and locality sensitive hashing, showing that we achieve significantly higher accuracy on both synthetic and real world image and advertising datasets. We also demonstrate that our technique strongly scales with the available computing power.'
volume: 54
URL: https://proceedings.mlr.press/v54/dick17a.html
PDF: http://proceedings.mlr.press/v54/dick17a/dick17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-dick17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Travis
family: Dick
- given: Mu
family: Li
- given: Venkata Krishna
family: Pillutla
- given: Colin
family: White
- given: Nina
family: Balcan
- given: Alex
family: Smola
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 662-671
id: dick17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 662
lastpage: 671
published: 2017-04-10 00:00:00 +0000
- title: 'Learning Nonparametric Forest Graphical Models with Prior Information'
abstract: 'We present a framework for incorporating prior information into nonparametric estimation of graphical models. To avoid distributional assumptions, we restrict the graph to be a forest and build on the work of forest density estimation (FDE). We reformulate the FDE approach from a Bayesian perspective, and introduce prior distributions on the graphs. As two concrete examples, we apply this framework to estimating scale-free graphs and learning multiple graphs with similar structures. The resulting algorithms are equivalent to finding a maximum spanning tree of a weighted graph with a penalty term on the connectivity pattern of the graph. We solve the optimization problem via a minorize-maximization procedure with Kruskal’s algorithm. Simulations show that the proposed methods outperform competing parametric methods, and are robust to the true data distribution. They also lead to improvement in predictive power and interpretability in two real data sets.'
volume: 54
URL: https://proceedings.mlr.press/v54/zhu17a.html
PDF: http://proceedings.mlr.press/v54/zhu17a/zhu17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-zhu17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Yuancheng
family: Zhu
- given: Zhe
family: Liu
- given: Siqi
family: Sun
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 672-680
id: zhu17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 672
lastpage: 680
published: 2017-04-10 00:00:00 +0000
- title: 'Sparse Randomized Partition Trees for Nearest Neighbor Search'
abstract: 'Randomized partition trees have recently been shown to be very effective in solving nearest neighbor search problem. In spite of enjoying strong theoretical guarantee, it suffers from high space complexity, since each internal node of the tree needs to store a $d$ dimensional projection direction leading to a $O(nd)$ space complexity for a dataset of size $n$. Inspired by the fast Johnson-Lindenstrauss transform, in this paper, we propose a sparse version of randomized partition tree where each internal node needs to store only a few non-zero entries, as opposed to all $d$ entries, leading to significant space savings without sacrificing much in terms of nearest neighbor search accuracy. As a by product of this, query time of our proposed method is slightly better than that of its non-sparse counterpart for large dataset size. Our theoretical results indicate that our proposed method enjoys the same theoretical guarantee as that of the original non-sparse RP-tree. Experimental evaluations on four real world dataset strongly suggest that nearest neighbor search performance of our proposed sparse RP-tree is very similar to that of its non-sparse counterpart in terms of accuracy and number of retrieved points.'
volume: 54
URL: https://proceedings.mlr.press/v54/sinha17a.html
PDF: http://proceedings.mlr.press/v54/sinha17a/sinha17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-sinha17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Kaushik
family: Sinha
- given: Omid
family: Keivani
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 681-689
id: sinha17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 681
lastpage: 689
published: 2017-04-10 00:00:00 +0000
- title: 'Horde of Bandits using Gaussian Markov Random Fields'
abstract: 'The gang of bandits (GOB) model [7] is a recent contextual bandits framework that shares information between a set of bandit problems, related by a known (possibly noisy) graph. This model is useful in problems like recommender systems where the large number of users makes it vital to transfer information between users. Despite its effectiveness, the existing GOB model can only be applied to small problems due to its quadratic time-dependence on the number of nodes. Existing solutions to combat the scalability issue require an often-unrealistic clustering assumption. By exploiting a connection to Gaussian Markov random fields (GMRFs), we show that the GOB model can be made to scale to much larger graphs without additional assumptions. In addition, we propose a Thompson sampling algorithm which uses the recent GMRF sampling-by-perturbation technique, allowing it to scale to even larger problems (leading to a “horde” of bandits). We give regret bounds and experimental results for GOB with Thompson sampling and epoch-greedy algorithms, indicating that these methods are as good as or significantly better than ignoring the graph or adopting a clustering-based approach. Finally, when an existing graph is not available, we propose a heuristic for learning it on the fly and show promising results. '
volume: 54
URL: https://proceedings.mlr.press/v54/vaswani17a.html
PDF: http://proceedings.mlr.press/v54/vaswani17a/vaswani17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-vaswani17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Sharan
family: Vaswani
- given: Mark
family: Schmidt
- given: Laks
family: Lakshmanan
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 690-699
id: vaswani17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 690
lastpage: 699
published: 2017-04-10 00:00:00 +0000
- title: 'Random projection design for scalable implicit smoothing of randomly observed stochastic processes'
abstract: 'Sampling at random timestamps, long range dependencies, and scale hamper standard meth- ods for multivariate time series analysis. In this paper we present a novel estimator for cross-covariance of randomly observed time series which unravels the dynamics of an unobserved stochastic process. We analyze the statistical properties of our estimator without needing the assumption that observation timestamps are independent from the process of interest and show that our solution is not hindered by the issues affecting standard estimators for cross-covariance. We implement and evaluate our statistically sound and scalable approach in the distributed setting using Apache Spark and demonstrate its ability to unravel causal dynamics on both simulations and high-frequency financial trading data.'
volume: 54
URL: https://proceedings.mlr.press/v54/belletti17a.html
PDF: http://proceedings.mlr.press/v54/belletti17a/belletti17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-belletti17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Francois
family: Belletti
- given: Evan
family: Sparks
- given: Alexandre
family: Bayen
- given: Joseph
family: Gonzalez
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 700-708
id: belletti17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 700
lastpage: 708
published: 2017-04-10 00:00:00 +0000
- title: 'Trading off Rewards and Errors in Multi-Armed Bandits'
abstract: 'In multi-armed bandits, the most common objective is the maximization of the cumulative reward. Alternative settings include active exploration, where a learner tries to gain accurate estimates of the rewards of all arms. While these objectives are contrasting, in many scenarios it is desirable to trade off rewards and errors. For instance, in educational games the designer wants to gather generalizable knowledge about the behavior of the students and teaching strategies (small estimation errors) but, at the same time, the system needs to avoid giving a bad experience to the players, who may leave the system permanently (large reward). In this paper, we formalize this tradeoff and introduce the ForcingBalance algorithm whose performance is provably close to the best possible tradeoff strategy. Finally, we demonstrate on real-world educational data that ForcingBalance returns useful information about the arms without compromising the overall reward.'
volume: 54
URL: https://proceedings.mlr.press/v54/erraqabi17a.html
PDF: http://proceedings.mlr.press/v54/erraqabi17a/erraqabi17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-erraqabi17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Akram
family: Erraqabi
- given: Alessandro
family: Lazaric
- given: Michal
family: Valko
- given: Emma
family: Brunskill
- given: Yun-En
family: Liu
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 709-717
id: erraqabi17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 709
lastpage: 717
published: 2017-04-10 00:00:00 +0000
- title: 'Adaptive ADMM with Spectral Penalty Parameter Selection'
abstract: 'The alternating direction method of multipliers (ADMM) is a versatile tool for solving a wide range of constrained optimization problems. However, its performance is highly sensitive to a penalty parameter, making ADMM often unreliable and hard to automate for a non-expert user. We tackle this weakness of ADMM by proposing a method that adaptively tunes the penalty parameter to achieve fast convergence. The resulting adaptive ADMM (AADMM) algorithm, inspired by the successful Barzilai-Borwein spectral method for gradient descent, yields fast convergence and relative insensitivity to the initial stepsize and problem scaling.'
volume: 54
URL: https://proceedings.mlr.press/v54/xu17a.html
PDF: http://proceedings.mlr.press/v54/xu17a/xu17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-xu17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Zheng
family: Xu
- given: Mario
family: Figueiredo
- given: Tom
family: Goldstein
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 718-727
id: xu17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 718
lastpage: 727
published: 2017-04-10 00:00:00 +0000
- title: 'The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits'
abstract: 'Stochastic linear bandits are a natural and simple generalisation of finite-armed bandits with numerous practical applications. Current approaches focus on generalising existing techniques for finite-armed bandits, notably the otimism principle and Thompson sampling. Prior analysis has mostly focussed on the worst-case setting. We analyse the asymptotic regret and show matching upper and lower bounds on what is achievable. Surprisingly, our results show that no algorithm based on optimism or Thompson sampling will ever achieve the optimal rate. In fact, they can be arbitrarily far from optimal, even in very simple cases. This is a disturbing result because these techniques are standard tools that are widely used for sequential optimisation, for example, generalised linear bandits and reinforcement learning. '
volume: 54
URL: https://proceedings.mlr.press/v54/lattimore17a.html
PDF: http://proceedings.mlr.press/v54/lattimore17a/lattimore17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-lattimore17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Tor
family: Lattimore
- given: Csaba
family: Szepesvari
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 728-737
id: lattimore17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 728
lastpage: 737
published: 2017-04-10 00:00:00 +0000
- title: 'Dynamic Collaborative Filtering With Compound Poisson Factorization'
abstract: 'Model-based collaborative filtering (CF) analyzes user–item interactions to infer latent factors that represent user preferences and item characteristics in order to predict future interactions. Most CF approaches assume that these latent factors are static; however, in most CF data, user preferences and item perceptions drift over time. Here, we propose a new conjugate and numerically stable dynamic matrix factorization (DCPF) based on hierarchical Poisson factorization that models the smoothly drifting latent factors using gamma-Markov chains. We propose a conjugate gamma chain construction that is numerically stable within our compound-Poisson framework. We then derive a scalable stochastic variational inference approach to estimate the parameters of our model. We apply our model to time-stamped ratings data sets from Netflix, Yelp, and Last.fm. We empirically demonstrate that DCPF achieves a higher predictive accuracy than state-of-the-art static and dynamic factorization algorithms. '
volume: 54
URL: https://proceedings.mlr.press/v54/jerfel17a.html
PDF: http://proceedings.mlr.press/v54/jerfel17a/jerfel17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-jerfel17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Ghassen
family: Jerfel
- given: Mehmet
family: Basbug
- given: Barbara
family: Engelhardt
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 738-747
id: jerfel17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 738
lastpage: 747
published: 2017-04-10 00:00:00 +0000
- title: 'Rank Aggregation and Prediction with Item Features'
abstract: 'We study the problem of rank aggregation with features, where both pairwise comparisons and item features are available to help the rank aggregation task. Observing that traditional rank aggregation methods disregard features, while models adapted from learning-to-rank task are sensitive to feature noise, we propose a general model to learn a total ranking by balancing between comparisons and feature information jointly. As a result, our proposed model takes advantage of item features and is also robust to noise. More importantly, we study the effectiveness of item features in our model and show that given sufficiently informative features, the sample complexity of our model can be asymptotically lower than models based only on comparisons for deriving an $ε$-accurate ranking. The results theoretically justify that our model can achieve efficient learning by leveraging item feature information. In addition, we show that the proposed model can also be extended to two other related problems—online rank aggregation and rank prediction of new items. Finally, experiments show that our model is more effective and robust compared to existing methods on both synthetic and real datasets. '
volume: 54
URL: https://proceedings.mlr.press/v54/chiang17a.html
PDF: http://proceedings.mlr.press/v54/chiang17a/chiang17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-chiang17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Kai-Yang
family: Chiang
- given: Cho-Jui
family: Hsieh
- given: Inderjit
family: Dhillon
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 748-756
id: chiang17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 748
lastpage: 756
published: 2017-04-10 00:00:00 +0000
- title: 'Robust and Efficient Computation of Eigenvectors in a Generalized Spectral Method for Constrained Clustering'
abstract: 'FAST-GE is a generalized spectral method for constrained clustering [Cucuringu et al., AISTATS 2016]. It incorporates the must-link and cannot-link constraints into two Laplacian matrices and then minimizes a Rayleigh quotient via solving a generalized eigenproblem, and is considered to be simple and scalable. However, there are two unsolved issues. Theoretically, since both Laplacian matrices are positive semi-definite and the corresponding pencil is singular, it is not proven whether the minimum of the Rayleigh quotient exists and is equivalent to an eigenproblem. Computationally, the locally optimal block preconditioned conjugate gradient (LOBPCG) method is not designed for solving the eigenproblem of a singular pencil. In fact, to the best of our knowledge, there is no existing eigensolver that is immediately applicable. In this paper, we provide solutions to these two critical issues. We prove a generalization of Courant-Fischer variational principle for the Laplacian singular pencil. We propose a regularization for the pencil so that LOBPCG is applicable. We demonstrate the robustness and efficiency of proposed solutions for constrained image segmentation. The proposed theoretical and computational solutions can be applied to eigenproblems of positive semi-definite pencils arising in other machine learning algorithms, such as generalized linear discriminant analysis in dimension reduction and multisurface classification via eigenvectors. '
volume: 54
URL: https://proceedings.mlr.press/v54/jiang17b.html
PDF: http://proceedings.mlr.press/v54/jiang17b/jiang17b.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-jiang17b.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Chengming
family: Jiang
- given: Huiqing
family: Xie
- given: Zhaojun
family: Bai
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 757-766
id: jiang17b
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 757
lastpage: 766
published: 2017-04-10 00:00:00 +0000
- title: 'Information-theoretic limits of Bayesian network structure learning'
abstract: 'In this paper, we study the information-theoretic limits of learning the structure of Bayesian networks (BNs), on discrete as well as continuous random variables, from a finite number of samples. We show that the minimum number of samples required by any procedure to recover the correct structure grows as $Ω(m)$ and $Ω(k \log m + (k^2)/m)$ for non-sparse and sparse BNs respectively, where m is the number of variables and k is the maximum number of parents per node. We provide a simple recipe, based on an extension of the Fano’s inequality, to obtain information-theoretic limits of structure recovery for any exponential family BN. We instantiate our result for specific conditional distributions in the exponential family to characterize the fundamental limits of learning various commonly used BNs, such as conditional probability table based networks, Gaussian BNs, noisy-OR networks, and logistic regression networks. En route to obtaining our main results, we obtain tight bounds on the number of sparse and non-sparse essential-DAGs. Finally, as a byproduct, we recover the information-theoretic limits of sparse variable selection for logistic regression.'
volume: 54
URL: https://proceedings.mlr.press/v54/ghoshal17a.html
PDF: http://proceedings.mlr.press/v54/ghoshal17a/ghoshal17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-ghoshal17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Asish
family: Ghoshal
- given: Jean
family: Honorio
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 767-775
id: ghoshal17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 767
lastpage: 775
published: 2017-04-10 00:00:00 +0000
- title: 'Markov Chain Truncation for Doubly-Intractable Inference'
abstract: 'Computing partition functions, the normalizing constants of probability distributions, is often hard. Variants of importance sampling give unbiased estimates of a normalizer Z, however, unbiased estimates of the reciprocal 1/Z are harder to obtain. Unbiased estimates of 1/Z allow Markov chain Monte Carlo sampling of “doubly-intractable” distributions, such as the parameter posterior for Markov Random Fields or Exponential Random Graphs. We demonstrate how to construct unbiased estimates for 1/Z given access to black-box importance sampling estimators for Z. We adapt recent work on random series truncation and Markov chain coupling, producing estimators with lower variance and a higher percentage of positive estimates than before. Our debiasing algorithms are simple to implement, and have some theoretical and empirical advantages over existing methods.'
volume: 54
URL: https://proceedings.mlr.press/v54/wei17a.html
PDF: http://proceedings.mlr.press/v54/wei17a/wei17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-wei17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Colin
family: Wei
- given: Iain
family: Murray
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 776-784
id: wei17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 776
lastpage: 784
published: 2017-04-10 00:00:00 +0000
- title: 'Regression Uncertainty on the Grassmannian'
abstract: 'Trends in longitudinal or cross-sectional studies over time are often captured through regression models. In their simplest manifestation, these regression models are formulated in $R^n$. However, in the context of imaging studies, the objects of interest which are to be regressed are frequently best modeled as elements of a Riemannian manifold. Regression on such spaces can be accomplished through geodesic regression. This paper develops an approach to compute confidence intervals for geodesic regression models. The approach is general, but illustrated and specifically developed for the Grassmann manifold, which allows us, e.g., to regress shapes or linear dynamical systems. Extensions to other manifolds can be obtained in a similar manner. We demonstrate our approach for regression with 2D/3D shapes using synthetic and real data.'
volume: 54
URL: https://proceedings.mlr.press/v54/hong17b.html
PDF: http://proceedings.mlr.press/v54/hong17b/hong17b.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-hong17b.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Yi
family: Hong
- given: Xiao
family: Yang
- given: Roland
family: Kwitt
- given: Martin
family: Styner
- given: Marc
family: Niethammer
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 785-793
id: hong17b
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 785
lastpage: 793
published: 2017-04-10 00:00:00 +0000
- title: 'Attributing Hacks'
abstract: 'In this paper, we describe an algorithm for estimating the provenance of hacks on websites. That is, given properties of sites and the temporal occurrence of attacks, we are able to attribute individual attacks to joint causes and vulnerabilities, as well as estimating the evolution of these vulnerabilities over time. Specifically, we use hazard regression with a time-varying additive hazard function parameterized in a generalized linear form. The activation coefficients on each feature are continuous-time functions over time. We formulate the problem of learning these functions as a constrained variational maximum likelihood estimation problem with total variation penalty and show that the optimal solution is a 0th order spline (a piecewise constant function) with a finite number of adaptively chosen knots. This allows the inference problem to be solved efficiently and at scale by solving a finite dimensional optimization problem. Extensive experiments on real data sets show that our method significantly outperforms Cox’s proportional hazard model. We also conduct case studies and verify that the fitted functions are indeed recovering vulnerable features.'
volume: 54
URL: https://proceedings.mlr.press/v54/liu17a.html
PDF: http://proceedings.mlr.press/v54/liu17a/liu17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-liu17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Ziqi
family: Liu
- given: Alex
family: Smola
- given: Kyle
family: Soska
- given: Yu-Xiang
family: Wang
- given: Qinghua
family: Zheng
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 794-802
id: liu17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 794
lastpage: 802
published: 2017-04-10 00:00:00 +0000
- title: 'Unsupervised Sequential Sensor Acquisition'
abstract: 'In many security and healthcare systems a sequence of sensors/tests are used for detection and diagnosis. Each test outputs a prediction of the latent state, and carries with it inherent costs. Our objective is to learn strategies for selecting tests to optimize accuracy and costs. Unfortunately it is often impossible to acquire in-situ ground truth annotations and we are left with the problem of unsupervised sensor selection (USS). We pose USS as a version of stochastic partial monitoring problem with an unusual reward structure (even noisy annotations are unavailable). Unsurprisingly no learner can achieve sublinear regret without further assumptions. To this end we propose the notion of weak-dominance. This is a condition on the joint probability distribution of test outputs and latent state and says that whenever a test is accurate on an example, a later test in the sequence is likely to be accurate as well.'
volume: 54
URL: https://proceedings.mlr.press/v54/hanawal17a.html
PDF: http://proceedings.mlr.press/v54/hanawal17a/hanawal17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-hanawal17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Manjesh
family: Hanawal
- given: Csaba
family: Szepesvari
- given: Venkatesh
family: Saligrama
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 803-811
id: hanawal17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 803
lastpage: 811
published: 2017-04-10 00:00:00 +0000
- title: 'A Stochastic Nonconvex Splitting Method for Symmetric Nonnegative Matrix Factorization'
abstract: 'Symmetric nonnegative matrix factorization (SymNMF) plays an important role in applications of many data analytics problems such as community detection, document clustering and image segmentation. In this paper, we consider a stochastic SymNMF problem in which the observation matrix is generated in a random and sequential manner. We propose a stochastic nonconvex splitting method, which not only guarantees convergence to the set of stationary points of the problem (in the mean-square sense), but further achieves a sublinear convergence rate. Numerical results show that for clustering problems over both synthetic and real world datasets, the proposed algorithm converges quickly to the set of stationary points.'
volume: 54
URL: https://proceedings.mlr.press/v54/lu17a.html
PDF: http://proceedings.mlr.press/v54/lu17a/lu17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-lu17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Songtao
family: Lu
- given: Mingyi
family: Hong
- given: Zhengdao
family: Wang
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 812-821
id: lu17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 812
lastpage: 821
published: 2017-04-10 00:00:00 +0000
- title: 'Hierarchically-partitioned Gaussian Process Approximation'
abstract: 'The Gaussian process (GP) is a simple yet powerful probabilistic framework for various machine learning tasks. However, exact algorithms for learning and prediction are prohibitive to be applied to large datasets due to inherent computational complexity. To overcome this main limitation, various techniques have been proposed, and in particular, local GP algorithms that scales “truly linearly” with respect to the dataset size. In this paper, we introduce a hierarchical model based on local GP for large-scale datasets, which stacks inducing points over inducing points in layers. By using different kernels in each layer, the overall model becomes multi-scale and is able to capture both long- and short-range dependencies. We demonstrate the effectiveness of our model by speed-accuracy performance on challenging real-world datasets.'
volume: 54
URL: https://proceedings.mlr.press/v54/lee17a.html
PDF: http://proceedings.mlr.press/v54/lee17a/lee17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-lee17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Byung-Jun
family: Lee
- given: Jongmin
family: Lee
- given: Kee-Eung
family: Kim
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 822-831
id: lee17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 822
lastpage: 831
published: 2017-04-10 00:00:00 +0000
- title: 'Scalable Learning of Non-Decomposable Objectives'
abstract: 'Modern retrieval systems are often driven by an underlying machine learning model. The goal of such systems is to identify and possibly rank the few most relevant items for a given query or context. Thus, such systems are typically evaluated using a ranking-based performance metric such as the area under the precision-recall curve, the F score, precision at fixed recall, etc. Obviously, it is desirable to train such systems to optimize the metric of interest. In practice, due to the scalability limitations of existing approaches for optimizing such objectives, large-scale retrieval systems are instead trained to maximize classification accuracy, in the hope that performance as measured via the true objective will also be favorable. In this work we present a unified framework that, using straightforward building block bounds, allows for highly scalable optimization of a wide range of ranking-based objectives. We demonstrate the advantage of our approach on several real-life retrieval problems that are significantly larger than those considered in the literature, while achieving substantial improvement in performance over the accuracy-objective baseline. '
volume: 54
URL: https://proceedings.mlr.press/v54/eban17a.html
PDF: http://proceedings.mlr.press/v54/eban17a/eban17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-eban17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Elad
family: Eban
- given: Mariano
family: Schain
- given: Alan
family: Mackey
- given: Ariel
family: Gordon
- given: Ryan
family: Rifkin
- given: Gal
family: Elidan
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 832-840
id: eban17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 832
lastpage: 840
published: 2017-04-10 00:00:00 +0000
- title: 'CPSG-MCMC: Clustering-Based Preprocessing method for Stochastic Gradient MCMC'
abstract: 'In recent years, stochastic gradient Markov Chain Monte Carlo (SG-MCMC) methods have been raised to process large-scale dataset by iterative learning from small minibatches. However, the high variance caused by naive subsampling usually slows down the convergence to the desired posterior distribution. In this paper, we propose an effective subsampling strategy to reduce the variance based on a failed attempt to do importance sampling. In particular, before sampling, we partition the dataset with k-means clustering algorithm in a preprocessing step and use the fixed clustering throughout the entire MCMC simulation. Then during simulation, we approximate the gradient of log-posterior via summing the estimated gradient of each cluster. The resulting procedure is surprisingly simple without enhancing the complexity of the original algorithm during sampling procedure. We apply our Clustering-based Preprocessing strategy on stochastic gradient Langevin dynamics, stochastic gradient Hamilton Monte Carlo and stochastic gradient Riemann Langevin dynamics. Empirically, we provide thorough numerical results to back up the effectiveness and efficiency of our approach.'
volume: 54
URL: https://proceedings.mlr.press/v54/fu17a.html
PDF: http://proceedings.mlr.press/v54/fu17a/fu17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-fu17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Tianfan
family: Fu
- given: Zhihua
family: Zhang
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 841-850
id: fu17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 841
lastpage: 850
published: 2017-04-10 00:00:00 +0000
- title: 'Comparison-Based Nearest Neighbor Search'
abstract: 'We consider machine learning in a comparison-based setting where we are given a set of points in a metric space, but we have no access to the actual distances between the points. Instead, we can only ask an oracle whether the distance between two points i and j is smaller than the distance between the points i and k. We are concerned with data structures and algorithms to find nearest neighbors based on such comparisons. We focus on a simple yet effective algorithm that recursively splits the space by first selecting two random pivot points and then assigning all other points to the closer of the two (comparison tree). We prove that if the metric space satisfies certain expansion conditions, then with high probability the height of the comparison tree is logarithmic in the number of points, leading to efficient search performance. We also provide an upper bound for the failure probability to return the true nearest neighbor. Experiments show that the comparison tree is competitive with algorithms that have access to the actual distance values, and needs less triplet comparisons than other competitors.'
volume: 54
URL: https://proceedings.mlr.press/v54/haghiri17a.html
PDF: http://proceedings.mlr.press/v54/haghiri17a/haghiri17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-haghiri17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Siavash
family: Haghiri
- given: Debarghya
family: Ghoshdastidar
- given: Ulrike von
family: Luxburg
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 851-859
id: haghiri17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 851
lastpage: 859
published: 2017-04-10 00:00:00 +0000
- title: 'A Unified Optimization View on Generalized Matching Pursuit and Frank-Wolfe'
abstract: 'Two of the most fundamental prototypes of greedy optimization are the matching pursuit and Frank-Wolfe algorithms. In this paper we take a unified view on both classes of methods, leading to the first explicit convergence rates of matching pursuit methods in an optimization sense, for general sets of atoms. We derive sublinear (1/t) convergence for both classes on general smooth objectives, and linear convergence on strongly convex objectives, as well as a clear correspondence of algorithm variants. Our presented algorithms and rates are affine invariant, and do not need any incoherence or sparsity assumptions.'
volume: 54
URL: https://proceedings.mlr.press/v54/locatello17a.html
PDF: http://proceedings.mlr.press/v54/locatello17a/locatello17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-locatello17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Francesco
family: Locatello
- given: Rajiv
family: Khanna
- given: Michael
family: Tschannen
- given: Martin
family: Jaggi
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 860-868
id: locatello17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 860
lastpage: 868
published: 2017-04-10 00:00:00 +0000
- title: 'Faster Coordinate Descent via Adaptive Importance Sampling'
abstract: 'Coordinate descent methods employ random partial updates of decision variables in order to solve huge-scale convex optimization problems. In this work, we introduce new adaptive rules for the random selection of their updates. By adaptive, we mean that our selection rules are based on the dual residual or the primal-dual gap estimates and can change at each iteration. We theoretically characterize the performance of our selection rules and demonstrate improvements over the state-of-the-art, and extend our theory and algorithms to general convex objectives. Numerical evidence with hinge-loss support vector machines and Lasso confirm that the practice follows the theory. '
volume: 54
URL: https://proceedings.mlr.press/v54/perekrestenko17a.html
PDF: http://proceedings.mlr.press/v54/perekrestenko17a/perekrestenko17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-perekrestenko17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Dmytro
family: Perekrestenko
- given: Volkan
family: Cevher
- given: Martin
family: Jaggi
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 869-877
id: perekrestenko17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 869
lastpage: 877
published: 2017-04-10 00:00:00 +0000
- title: 'Conjugate-Computation Variational Inference : Converting Variational Inference in Non-Conjugate Models to Inferences in Conjugate Models'
abstract: 'Variational inference is computationally challenging in models that contain both conjugate and non-conjugate terms. Methods specifically designed for conjugate models, even though computationally efficient, find it difficult to deal with non-conjugate terms. On the other hand, stochastic-gradient methods can handle the non-conjugate terms but they usually ignore the conjugate structure of the model which might result in slow convergence. In this paper, we propose a new algorithm called Conjugate-computation Variational Inference (CVI) which brings the best of the two worlds together – it uses conjugate computations for the conjugate terms and employs stochastic gradients for the rest. We derive this algorithm by using a stochastic mirror-descent method in the mean-parameter space, and then expressing each gradient step as a variational inference in a conjugate model. We demonstrate our algorithm’s applicability to a large class of models and establish its convergence. Our experimental results show that our method converges much faster than the methods that ignore the conjugate structure of the model. '
volume: 54
URL: https://proceedings.mlr.press/v54/khan17a.html
PDF: http://proceedings.mlr.press/v54/khan17a/khan17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-khan17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Mohammad
family: Khan
- given: Wu
family: Lin
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 878-887
id: khan17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 878
lastpage: 887
published: 2017-04-10 00:00:00 +0000
- title: 'Hit-and-Run for Sampling and Planning in Non-Convex Spaces'
abstract: 'We propose the Hit-and-Run algorithm for planning and sampling problems in non- convex spaces. For sampling, we show the first analysis of the Hit-and-Run algorithm in non-convex spaces and show that it mixes fast as long as certain smoothness conditions are satisfied. In particular, our analysis reveals an intriguing connection between fast mixing and the existence of smooth measure-preserving mappings from a convex space to the non-convex space. For planning, we show advantages of Hit-and- Run compared to state-of-the-art planning methods such as Rapidly-Exploring Random Trees.'
volume: 54
URL: https://proceedings.mlr.press/v54/abbasi-yadkori17a.html
PDF: http://proceedings.mlr.press/v54/abbasi-yadkori17a/abbasi-yadkori17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-abbasi-yadkori17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Yasin
family: Abbasi-Yadkori
- given: Peter
family: Bartlett
- given: Victor
family: Gabillon
- given: Alan
family: Malek
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 888-895
id: abbasi-yadkori17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 888
lastpage: 895
published: 2017-04-10 00:00:00 +0000
- title: 'DP-EM: Differentially Private Expectation Maximization'
abstract: 'The iterative nature of the expectation maximization (EM) algorithm presents a challenge for privacy-preserving estimation, as each iteration increases the amount of noise needed. We propose a practical private EM algorithm that overcomes this challenge using two innovations: (1) a novel moment perturbation formulation for differentially private EM (DP-EM), and (2) the use of two recently developed composition methods to bound the privacy “cost” of multiple EM iterations: the moments accountant (MA) and zero-mean concentrated differential privacy (zCDP). Both MA and zCDP bound the moment generating function of the privacy loss random variable and achieve a refined tail bound, which effectively decrease the amount of additive noise. We present empirical results showing the benefits of our approach, as well as similar performance between these two composition methods in the DP-EM setting for Gaussian mixture models. Our approach can be readily extended to many iterative learning algorithms, opening up various exciting future directions. '
volume: 54
URL: https://proceedings.mlr.press/v54/park17c.html
PDF: http://proceedings.mlr.press/v54/park17c/park17c.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-park17c.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Mijung
family: Park
- given: James
family: Foulds
- given: Kamalika
family: Choudhary
- given: Max
family: Welling
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 896-904
id: park17c
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 896
lastpage: 904
published: 2017-04-10 00:00:00 +0000
- title: 'On the Hyperprior Choice for the Global Shrinkage Parameter in the Horseshoe Prior'
abstract: 'The horseshoe prior has proven to be a noteworthy alternative for sparse Bayesian estimation, but as shown in this paper, the results can be sensitive to the prior choice for the global shrinkage hyperparameter. We argue that the previous default choices are dubious due to their tendency to favor solutions with more unshrunk coefficients than we typically expect a priori. This can lead to bad results if this parameter is not strongly identified by data. We derive the relationship between the global parameter and the effective number of nonzeros in the coefficient vector, and show an easy and intuitive way of setting up the prior for the global parameter based on our prior beliefs about the number of nonzero coefficients in the model. The results on real world data show that one can benefit greatly – in terms of improved parameter estimates, prediction accuracy, and reduced computation time – from transforming even a crude guess for the number of nonzero coefficients into the prior for the global parameter using our framework.'
volume: 54
URL: https://proceedings.mlr.press/v54/piironen17a.html
PDF: http://proceedings.mlr.press/v54/piironen17a/piironen17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-piironen17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Juho
family: Piironen
- given: Aki
family: Vehtari
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 905-913
id: piironen17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 905
lastpage: 913
published: 2017-04-10 00:00:00 +0000
- title: 'Bayesian Learning and Inference in Recurrent Switching Linear Dynamical Systems'
abstract: 'Many natural systems, such as neurons firing in the brain or basketball teams traversing a court, give rise to time series data with complex, nonlinear dynamics. We can gain insight into these systems by decomposing the data into segments that are each explained by simpler dynamic units. Building on switching linear dynamical systems (SLDS), we develop a model class and Bayesian inference algorithms that not only discover these dynamical units but also, by learning how transition probabilities depend on observations or continuous latent states, explain their switching behavior. Our key innovation is to design these recurrent SLDS models to enable recent Pólya-gamma auxiliary variable techniques and thus make approximate Bayesian learning and inference in these models easy, fast, and scalable.'
volume: 54
URL: https://proceedings.mlr.press/v54/linderman17a.html
PDF: http://proceedings.mlr.press/v54/linderman17a/linderman17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-linderman17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Scott
family: Linderman
- given: Matthew
family: Johnson
- given: Andrew
family: Miller
- given: Ryan
family: Adams
- given: David
family: Blei
- given: Liam
family: Paninski
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 914-922
id: linderman17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 914
lastpage: 922
published: 2017-04-10 00:00:00 +0000
- title: 'Efficient Algorithm for Sparse Tensor-variate Gaussian Graphical Models via Gradient Descent'
abstract: 'We study the sparse tensor-variate Gaussian graphical model (STGGM), where each way of the tensor follows a multivariate normal distribution whose precision matrix has sparse structures. In order to estimate the precision matrices, we propose a sparsity constrained maximum likelihood estimator. However, due to the complex structure of the tensor-variate GGMs, the likelihood based estimator is non-convex, which poses great challenges for both computation and theoretical analysis. In order to address these challenges, we propose an efficient alternating gradient descent algorithm to solve this estimator, and prove that, under certain conditions on the initial estimator, our algorithm is guaranteed to linearly converge to the unknown precision matrices up to the optimal statistical error. Experiments on both synthetic data and real world brain imaging data corroborate our theory.'
volume: 54
URL: https://proceedings.mlr.press/v54/xu17b.html
PDF: http://proceedings.mlr.press/v54/xu17b/xu17b.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-xu17b.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Pan
family: Xu
- given: Tingting
family: Zhang
- given: Quanquan
family: Gu
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 923-932
id: xu17b
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 923
lastpage: 932
published: 2017-04-10 00:00:00 +0000
- title: 'Minimax-optimal semi-supervised regression on unknown manifolds'
abstract: 'We consider semi-supervised regression when the predictor variables are drawn from an unknown manifold. A simple two step approach to this problem is to: (i) estimate the manifold geodesic distance between any pair of points using both the labeled and unlabeled instances; and (ii) apply a k nearest neighbor regressor based on these distance estimates. We prove that given sufficiently many unlabeled points, this simple method of geodesic kNN regression achieves the optimal finite-sample minimax bound on the mean squared error, as if the manifold were known. Furthermore, we show how this approach can be efficiently implemented, requiring only O(k N log N) operations to estimate the regression function at all N labeled and unlabeled points. We illustrate this approach on two datasets with a manifold structure: indoor localization using WiFi fingerprints and facial pose estimation. In both cases, geodesic kNN is more accurate and much faster than the popular Laplacian eigenvector regressor.'
volume: 54
URL: https://proceedings.mlr.press/v54/moscovich17a.html
PDF: http://proceedings.mlr.press/v54/moscovich17a/moscovich17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-moscovich17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Amit
family: Moscovich
- given: Ariel
family: Jaffe
- given: Nadler
family: Boaz
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 933-942
id: moscovich17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 933
lastpage: 942
published: 2017-04-10 00:00:00 +0000
- title: 'Improved Strongly Adaptive Online Learning using Coin Betting'
abstract: 'This paper describes a new parameter-free online learning algorithm for changing environments. In comparing against algorithms with the same time complexity as ours, we obtain a strongly adaptive regret bound that is a factor of at least $\sqrt\log(T)$ better, where $T$ is the time horizon. Empirical results show that our algorithm outperforms state-of-the-art methods in learning with expert advice and metric learning scenarios. '
volume: 54
URL: https://proceedings.mlr.press/v54/jun17a.html
PDF: http://proceedings.mlr.press/v54/jun17a/jun17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-jun17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Kwang-Sung
family: Jun
- given: Francesco
family: Orabona
- given: Stephen
family: Wright
- given: Rebecca
family: Willett
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 943-951
id: jun17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 943
lastpage: 951
published: 2017-04-10 00:00:00 +0000
- title: 'Black-box Importance Sampling'
abstract: 'Importance sampling is widely used in machine learning and statistics, but its power is limited by the restriction of using simple proposals for which the importance weights can be tractably calculated. We address this problem by studying black-box importance sampling methods that calculate importance weights for samples generated from any unknown proposal or black-box mechanism. Our method allows us to use better and richer proposals to solve difficult problems, and (somewhat counter-intuitively) also has the additional benefit of improving the estimation accuracy beyond typical importance sampling. Both theoretical and empirical analyses are provided. '
volume: 54
URL: https://proceedings.mlr.press/v54/liu17b.html
PDF: http://proceedings.mlr.press/v54/liu17b/liu17b.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-liu17b.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Qiang
family: Liu
- given: Jason
family: Lee
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 952-961
id: liu17b
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 952
lastpage: 961
published: 2017-04-10 00:00:00 +0000
- title: 'Fairness Constraints: Mechanisms for Fair Classification'
abstract: 'Algorithmic decision making systems are ubiquitous across a wide variety of online as well as offline services. These systems rely on complex learning methods and vast amounts of data to optimize the service functionality, satisfaction of the end user and profitability. However, there is a growing concern that these automated decisions can lead, even in the absence of intent, to a lack of fairness, i.e., their outcomes can disproportionately hurt (or, benefit) particular groups of people sharing one or more sensitive attributes (e.g., race, sex). In this paper, we introduce a flexible mechanism to design fair classifiers by leveraging a novel intuitive measure of decision boundary (un)fairness. We instantiate this mechanism with two well-known classifiers, logistic regression and support vector machines, and show on real-world data that our mechanism allows for a fine-grained control on the degree of fairness, often at a small cost in terms of accuracy.'
volume: 54
URL: https://proceedings.mlr.press/v54/zafar17a.html
PDF: http://proceedings.mlr.press/v54/zafar17a/zafar17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-zafar17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Muhammad Bilal
family: Zafar
- given: Isabel
family: Valera
- given: Manuel Gomez
family: Rogriguez
- given: Krishna P.
family: Gummadi
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 962-970
id: zafar17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 962
lastpage: 970
published: 2017-04-10 00:00:00 +0000
- title: 'Frequency Domain Predictive Modelling with Aggregated Data'
abstract: 'Existing work in spatio-temporal data analysis invariably assumes data available as individual measurements with localised estimates. However, for many applications like econometrics, financial forecasting and climate science, data is often obtained as aggregates. Data aggregation presents severe mathematical challenges to learning and inference, and application of standard techniques is susceptible to ecological fallacy. In this manuscript we investigate the problem of predictive linear modelling in the scenario where data is aggregated in a non-uniform manner across targets and features. We introduce a novel formulation of the problem in the frequency domain, and develop algorithmic techniques that exploit the duality properties of Fourier analysis to bypass the inherent structural challenges of this setting. We provide theoretical guarantees for generalisation error for our estimation procedure and extend our analysis to capture approximation effects arising from aliasing. Finally, we perform empirical evaluation to demonstrate the efficacy of our algorithmic aproach in predictive modelling on synthetic data, and on three real datasets from agricultural studies, ecological surveys and climate science. approximation effects arising from aliasing. Finally, we perform empirical evaluation to demonstrate the efficacy of our algorithmic aproach in predictive modelling on synthetic data, and on three real datasets from agricultural studies, ecological surveys and climate science.'
volume: 54
URL: https://proceedings.mlr.press/v54/bhowmik17a.html
PDF: http://proceedings.mlr.press/v54/bhowmik17a/bhowmik17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-bhowmik17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Avradeep
family: Bhowmik
- given: Joydeep
family: Ghosh
- given: Oluwasanmi
family: Koyejo
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 971-980
id: bhowmik17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 971
lastpage: 980
published: 2017-04-10 00:00:00 +0000
- title: 'A Unified Computational and Statistical Framework for Nonconvex Low-rank Matrix Estimation'
abstract: 'We propose a unified framework for estimating low-rank matrices through nonconvex optimization based on gradient descent algorithm. Our framework is quite general and can be applied to both noisy and noiseless observations. In the general case with noisy observations, we show that our algorithm is guaranteed to linearly converge to the unknown low-rank matrix up to a minimax optimal statistical error, provided an appropriate initial estimator. While in the generic noiseless setting, our algorithm converges to the unknown low-rank matrix at a linear rate and enables exact recovery with optimal sample complexity. In addition, we develop a new initialization algorithm to provide the desired initial estimator, which outperforms existing initialization algorithms for nonconvex low-rank matrix estimation. We illustrate the superiority of our framework through three examples: matrix regression, matrix completion, and one-bit matrix completion. We also corroborate our theory through extensive experiments on synthetic data.'
volume: 54
URL: https://proceedings.mlr.press/v54/wang17b.html
PDF: http://proceedings.mlr.press/v54/wang17b/wang17b.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-wang17b.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Lingxiao
family: Wang
- given: Xiao
family: Zhang
- given: Quanquan
family: Gu
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 981-990
id: wang17b
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 981
lastpage: 990
published: 2017-04-10 00:00:00 +0000
- title: 'A New Class of Private Chi-Square Hypothesis Tests'
abstract: 'In this paper, we develop new test statistics for hypothesis testing over differentially private data. These statistics are designed specifically so that their asymptotic distributions, after accounting for privacy noise, match the asymptotics of the non-private chi-square tests for testing if the multinomial data parameters lie in lower dimensional manifolds (examples include goodness-of-fit and independence testing). Empirically, these new test statistics outperform prior work, which focused on noisy versions of existing statistics.'
volume: 54
URL: https://proceedings.mlr.press/v54/rogers17a.html
PDF: http://proceedings.mlr.press/v54/rogers17a/rogers17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-rogers17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Ryan
family: Rogers
- given: Daniel
family: Kifer
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 991-1000
id: rogers17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 991
lastpage: 1000
published: 2017-04-10 00:00:00 +0000
- title: 'A Learning Theory of Ranking Aggregation'
abstract: 'Originally formulated in Social Choice theory, Ranking Aggregation, also referred to as Consensus Ranking, has motivated the development of numerous statistical models since the middle of the 20th century. Recently, the analysis of ranking/preference data has been the subject of a renewed interest in machine-learning, boosted by modern applications such as meta-search engines, giving rise to the design of various scalable algorithmic approaches for approximately computing ranking medians, viewed as solutions of a discrete (generally NP-hard) minimization problem. This paper develops a statistical learning theory for ranking aggregation in a general probabilistic setting (avoiding any rigid ranking model assumptions), assessing the generalization ability of empirical ranking medians. Universal rate bounds are established and the situations where convergence occurs at an exponential rate are fully characterized. Minimax lower bounds are also proved, showing that the rate bounds we obtain are optimal.'
volume: 54
URL: https://proceedings.mlr.press/v54/korba17a.html
PDF: http://proceedings.mlr.press/v54/korba17a/korba17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-korba17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Anna
family: Korba
- given: Stéphan
family: Clemencon
- given: Eric
family: Sibony
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1001-1010
id: korba17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1001
lastpage: 1010
published: 2017-04-10 00:00:00 +0000
- title: 'Anomaly Detection in Extreme Regions via Empirical MV-sets on the Sphere'
abstract: 'Extreme regions in the feature space are of particular concern for anomaly detection: anomalies are likely to be located in the tails, whereas data scarcity in such regions makes it difficult to distinguish between large normal instances and anomalies. This paper presents an unsupervised algorithm for anomaly detection in extreme regions. We propose a Minimum Volume set (MV-set) approach relying on multivariate extreme value theory. This framework includes a canonical pre-processing step, which addresses the issue of output sensitivity to standardization choices. The resulting data representation on the sphere highlights the dependence structure of the extremal observations. Anomaly detection is then cast as a MV-set estimation problem on the sphere, where volume is measured by the spherical measure and mass refers to the angular measure. An anomaly then corresponds to an unusual observation given that one of its variables is large. A preliminary rate bound analysis is carried out for the learning method we introduce and its computational advantages are discussed and illustrated by numerical experiments.'
volume: 54
URL: https://proceedings.mlr.press/v54/thomas17a.html
PDF: http://proceedings.mlr.press/v54/thomas17a/thomas17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-thomas17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Albert
family: Thomas
- given: Stéphan
family: Clemencon
- given: Alexandre
family: Gramfort
- given: Anne
family: Sabourin
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1011-1019
id: thomas17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1011
lastpage: 1019
published: 2017-04-10 00:00:00 +0000
- title: 'Structured adaptive and random spinners for fast machine learning computations'
abstract: 'We consider an efficient computational framework for speeding up several machine learning algorithms with almost no loss of accuracy. The proposed framework relies on projections via structured matrices that we call Structured Spinners, which are formed as products of three structured matrix-blocks that incorporate rotations. The approach is highly generic, i.e. i) structured matrices under consideration can either be fully-randomized or learned, ii) our structured family contains as special cases all previously considered structured schemes, iii) the setting extends to the non-linear case where the projections are followed by non-linear functions, and iv) the method finds numerous applications including kernel approximations via random feature maps, dimensionality reduction algorithms,new fast cross-polytope LSH techniques, deep learning, convex optimization algorithms via Newton sketches, quantization with random projection trees, and more. The proposed framework comes with theoretical guarantees characterizing the capacity of the structured model in reference to its unstructured counterpart and is based on a general theoretical principle that we describe in the paper. As a consequence of our theoretical analysis, we provide the first theoretical guarantees for one of the most efficient existing LSH algorithms based on the HD 3 HD 2 HD 1 structured matrix [Andoni et al., 2015]. The exhaustive experimental evaluation confirms the accuracy and efficiency of structured spinners for a variety of different applications.'
volume: 54
URL: https://proceedings.mlr.press/v54/bojarski17a.html
PDF: http://proceedings.mlr.press/v54/bojarski17a/bojarski17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-bojarski17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Mariusz
family: Bojarski
- given: Anna
family: Choromanska
- given: Krzysztof
family: Choromanski
- given: Francois
family: Fagan
- given: Cedric
family: Gouy-Pailler
- given: Anne
family: Morvan
- given: Nouri
family: Sakr
- given: Tamas
family: Sarlos
- given: Jamal
family: Atif
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1020-1029
id: bojarski17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1020
lastpage: 1029
published: 2017-04-10 00:00:00 +0000
- title: 'Complementary Sum Sampling for Likelihood Approximation in Large Scale Classification'
abstract: 'We consider training probabilistic classifiers in the case that the number of classes is too large to perform exact normalisation over all classes. We show that the source of high variance in standard sampling approximations is due to simply not including the correct class of the datapoint into the approximation. To account for this we explicitly sum over a subset of classes and sample the remaining. We show that this simple approach is competitive with recently introduced non likelihood-based approximations. '
volume: 54
URL: https://proceedings.mlr.press/v54/botev17a.html
PDF: http://proceedings.mlr.press/v54/botev17a/botev17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-botev17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Aleksandar
family: Botev
- given: Bowen
family: Zheng
- given: David
family: Barber
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1030-1038
id: botev17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1030
lastpage: 1038
published: 2017-04-10 00:00:00 +0000
- title: 'Learning Optimal Interventions'
abstract: 'Our goal is to identify beneficial interventions from observational data. We consider interventions that are narrowly focused (impacting few covariates) and may be tailored to each individual or globally enacted over a population. For applications where harmful intervention is drastically worse than proposing no change, we propose a conservative definition of the optimal intervention. Assuming the underlying relationship remains invariant under intervention, we develop efficient algorithms to identify the optimal intervention policy from limited data and provide theoretical guarantees for our approach in a Gaussian Process setting. Although our methods assume covariates can be precisely adjusted, they remain capable of improving outcomes in misspecified settings with unintentional downstream effects. Empirically, our approach identifies good interventions in two practical applications: gene perturbation and writing improvement. '
volume: 54
URL: https://proceedings.mlr.press/v54/mueller17a.html
PDF: http://proceedings.mlr.press/v54/mueller17a/mueller17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-mueller17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Jonas
family: Mueller
- given: David
family: Reshef
- given: George
family: Du
- given: Tommi
family: Jaakkola
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1039-1047
id: mueller17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1039
lastpage: 1047
published: 2017-04-10 00:00:00 +0000
- title: 'A Lower Bound on the Partition Function of Attractive Graphical Models in the Continuous Case'
abstract: 'Computing the partition function of an arbitrary graphical model is generally intractable. As a result, approximate inference techniques such as loopy belief propagation and expectation propagation are used to compute an approximation to the true partition function. However, due to general issues of intractability in the continuous case, our understanding of these approximations is relatively limited. In particular, a number of theoretical results known for these approximations in the discrete case are missing in the continuous case. In this work, we use graph covers to extend several such results from the discrete case to the continuous case. Specifically, we provide a graph cover based upper bound for continuous graphical models, and we use this characterization (along with a continuous analog of a discrete correlation-type inequality) to show that the Bethe partition function also provides a lower bound on the true partition function of attractive graphical models in the continuous case.'
volume: 54
URL: https://proceedings.mlr.press/v54/ruozzi17a.html
PDF: http://proceedings.mlr.press/v54/ruozzi17a/ruozzi17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-ruozzi17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Nicholas
family: Ruozzi
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1048-1056
id: ruozzi17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1048
lastpage: 1056
published: 2017-04-10 00:00:00 +0000
- title: 'Scalable Variational Inference for Super Resolution Microscopy'
abstract: 'Super-resolution microscopy methods have become essential tools in biology, opening up a variety of new questions that were previously inaccessible with standard light microscopy methods. In this paper we develop new Bayesian image processing methods that extend the reach of super-resolution microscopy even further. Our method couples variational inference techniques with a data summarization based on Laplace approximation to ensure computational scalability. Our formulation makes it straightforward to incorporate prior information about the underlying sample to further improve accuracy. The proposed method obtains dramatic resolution improvements over previous methods while retaining computational tractability.'
volume: 54
URL: https://proceedings.mlr.press/v54/sun17a.html
PDF: http://proceedings.mlr.press/v54/sun17a/sun17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-sun17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Ruoxi
family: Sun
- given: Evan
family: Archer
- given: Liam
family: Paninski
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1057-1065
id: sun17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1057
lastpage: 1065
published: 2017-04-10 00:00:00 +0000
- title: 'Linear Convergence of Stochastic Frank Wolfe Variants'
abstract: 'In this paper, we show that the Away-step Stochastic Frank-Wolfe (ASFW) and Pairwise Stochastic Frank-Wolfe (PSFW) algorithms converge linearly in expectation. We also show that if an algorithm convergences linearly in expectation then it converges linearly almost surely. In order to prove these results, we develop a novel proof technique based on concepts of empirical processes and concentration inequalities. As far as we know, this technique has not been used previously to derive the convergence rates of stochastic optimization algorithms. In large- scale numerical experiments, ASFW and PSFW perform as well as or better than their stochastic competitors in actual CPU time.'
volume: 54
URL: https://proceedings.mlr.press/v54/goldfarb17a.html
PDF: http://proceedings.mlr.press/v54/goldfarb17a/goldfarb17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-goldfarb17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Donald
family: Goldfarb
- given: Garud
family: Iyengar
- given: Chaoxu
family: Zhou
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1066-1074
id: goldfarb17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1066
lastpage: 1074
published: 2017-04-10 00:00:00 +0000
- title: 'Sequential Graph Matching with Sequential Monte Carlo'
abstract: 'We develop a novel probabilistic model for graph matchings and develop practical inference methods for supervised and unsupervised learning of the parameters of this model. The framework we develop admits joint inference on the parameters and the matching. Furthermore, our framework generalizes naturally to $K$-partite hypergraph matchings or set packing problems. The sequential formulation of the graph matching process naturally leads to sequential Monte Carlo algorithms which can be combined with various parameter inference methods. We apply our method to image matching problems, document ranking, and our own novel quadripartite matching problem arising from the field of computational forestry.'
volume: 54
URL: https://proceedings.mlr.press/v54/jun17b.html
PDF: http://proceedings.mlr.press/v54/jun17b/jun17b.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-jun17b.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Seong-Hwan
family: Jun
- given: Samuel W.K.
family: Wong
- given: James
family: Zidek
- given: Alexandre
family: Bouchard-Cote
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1075-1084
id: jun17b
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1075
lastpage: 1084
published: 2017-04-10 00:00:00 +0000
- title: 'Fast rates with high probability in exp-concave statistical learning'
abstract: 'We present an algorithm for the statistical learning setting with a bounded exp-concave loss in d dimensions that obtains excess risk $O(d \log(1/δ)/n)$ with probability $1 - δ$. The core technique is to boost the confidence of recent in-expectation O(d/n) excess risk bounds for empirical risk minimization (ERM), without sacrificing the rate, by leveraging a Bernstein condition which holds due to exp-concavity. We also show that a regret bound for any online learner in this setting translates to a high probability excess risk bound for the corresponding online-to-batch conversion of the online learner. Lastly, we present high probability bounds for the exp-concave model selection aggregation problem that are quantile-adaptive in a certain sense. One bound obtains a nearly optimal rate without requiring the loss to be Lipschitz continuous, and another requires Lipschitz continuity but obtains the optimal rate.'
volume: 54
URL: https://proceedings.mlr.press/v54/mehta17a.html
PDF: http://proceedings.mlr.press/v54/mehta17a/mehta17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-mehta17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Nishant
family: Mehta
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1085-1093
id: mehta17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1085
lastpage: 1093
published: 2017-04-10 00:00:00 +0000
- title: 'Generalization Error of Invariant Classifiers'
abstract: 'This paper studies the generalization error of invariant classifiers. In particular, we consider the common scenario where the classification task is invariant to certain transformations of the input, and that the classifier is constructed (or learned) to be invariant to these transformations. Our approach relies on factoring the input space into a product of a base space and a set of transformations. We show that whereas the generalization error of a non-invariant classifier is proportional to the complexity of the input space, the generalization error of an invariant classifier is proportional to the complexity of the base space. We also derive a set of sufficient conditions on the geometry of the base space and the set of transformations that ensure that the complexity of the base space is much smaller than the complexity of the input space. Our analysis applies to general classifiers such as convolutional neural networks. We demonstrate the implications of the developed theory for such classifiers with experiments on the MNIST and CIFAR-10 datasets.'
volume: 54
URL: https://proceedings.mlr.press/v54/sokolic17a.html
PDF: http://proceedings.mlr.press/v54/sokolic17a/sokolic17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-sokolic17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Jure
family: Sokolic
- given: Raja
family: Giryes
- given: Guillermo
family: Sapiro
- given: Miguel
family: Rodrigues
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1094-1103
id: sokolic17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1094
lastpage: 1103
published: 2017-04-10 00:00:00 +0000
- title: 'Learning with Feature Feedback: from Theory to Practice'
abstract: 'In supervised learning, a human annotator only needs to assign each data point (document, image, etc.) its correct label. But in many situations, the human can also provide richer feedback at essentially no extra cost. In this paper, we examine a particular type of feature feedback that has been used, with some success, in information retrieval and in computer vision. We formalize two models of feature feedback, give learning algorithms for them, and quantify their usefulness in the learning process. Our experiments also show the efficacy of these methods.'
volume: 54
URL: https://proceedings.mlr.press/v54/poulis17a.html
PDF: http://proceedings.mlr.press/v54/poulis17a/poulis17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-poulis17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Stefanos
family: Poulis
- given: Sanjoy
family: Dasgupta
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1104-1113
id: poulis17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1104
lastpage: 1113
published: 2017-04-10 00:00:00 +0000
- title: 'Optimistic Planning for the Stochastic Knapsack Problem'
abstract: 'The stochastic knapsack problem is a stochastic resource allocation problem that arises frequently and yet is exceptionally hard to solve. We derive and study an optimistic planning algorithm specifically designed for the stochastic knapsack problem. Unlike other optimistic planning algorithms for MDPs, our algorithm, OpStoK, avoids the use of discounting and is adaptive to the amount of resources available. We achieve this behavior by means of a concentration inequality that simultaneously applies to capacity and reward estimates. Crucially, we are able to guarantee that the aforementioned confidence regions hold collectively over all time steps by an application of Doob’s inequality. We demonstrate that the method returns an $ε$-optimal solution to the stochastic knapsack problem with high probability. To the best of our knowledge, our algorithm is the first which provides such guarantees for the stochastic knapsack problem. Furthermore, our algorithm is an anytime algorithm and will return a good solution even if stopped prematurely. This is particularly important given the difficulty of the problem. We also provide theoretical conditions to guarantee OpStoK does not expand all policies and demonstrate favorable performance in a simple experimental setting.'
volume: 54
URL: https://proceedings.mlr.press/v54/pike-burke17a.html
PDF: http://proceedings.mlr.press/v54/pike-burke17a/pike-burke17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-pike-burke17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Ciara
family: Pike-Burke
- given: Steffen
family: Grunewalder
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1114-1122
id: pike-burke17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1114
lastpage: 1122
published: 2017-04-10 00:00:00 +0000
- title: 'Identifying Groups of Strongly Correlated Variables through Smoothed Ordered Weighted $L_1$-norms'
abstract: 'The failure of LASSO to identify groups of correlated predictors in linear regression has sparked significant research interest. Recently, various norms were proposed, which can be best described as instances of ordered weighted $\ell_1$ norms (OWL), as an alternative to $\ell_1$ regularization used in LASSO. OWL can identify groups of correlated variables but it forces the model to be constant within a group. This artifact induces unnecessary bias in the model estimation. In this paper we take a submodular perspective and show that OWL can be posed as the Lovász extension of a suitably defined submodular function. The submodular perspective not only explains the group-wise constant behavior of OWL, but also suggests alternatives. The main contribution of this paper is smoothed OWL (SOWL), a new family of norms, which not only identifies the groups but also allows the model to be flexible inside a group. We establish several algorithmic and theoretical properties of SOWL including group identification and model consistency. We also provide algorithmic tools to compute the SOWL norm and its proximal operator, whose computational complexity $O(d\log d)$ is significantly better than that of general purpose solvers in $O(d^2\log d)$. In our experiments, SOWL compares favorably with respect to OWL in the regimes of interest.'
volume: 54
URL: https://proceedings.mlr.press/v54/sankaran17a.html
PDF: http://proceedings.mlr.press/v54/sankaran17a/sankaran17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-sankaran17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Raman
family: Sankaran
- given: Francis
family: Bach
- given: Chiranjib
family: Bhattacharya
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1123-1131
id: sankaran17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1123
lastpage: 1131
published: 2017-04-10 00:00:00 +0000
- title: 'Tracking Objects with Higher Order Interactions via Delayed Column Generation'
abstract: 'We study the problem of multi-target tracking and data association in video. We formulate this in terms of selecting a subset of high-quality tracks subject to the constraint that no pair of selected tracks is associated with a common detection (of an object). This objective is equivalent to the classic NP-hard problem of finding a maximum-weight set packing (MWSP) where tracks correspond to sets and is made further difficult since the number of candidate tracks grows exponentially in the number of detections. We present a relaxation of this combinatorial problem that uses a column generation formulation where the pricing problem is solved via dynamic programming to efficiently explore the space of tracks. We employ row generation to tighten the bound in such a way as to preserve efficient inference in the pricing problem. We show the practical utility of this algorithm for pedestrian and particle tracking.'
volume: 54
URL: https://proceedings.mlr.press/v54/wang17c.html
PDF: http://proceedings.mlr.press/v54/wang17c/wang17c.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-wang17c.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Shaofei
family: Wang
- given: Steffen
family: Wolf
- given: Charless
family: Fowlkes
- given: Julian
family: Yarkony
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1132-1140
id: wang17c
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1132
lastpage: 1140
published: 2017-04-10 00:00:00 +0000
- title: 'Belief Propagation in Conditional RBMs for Structured Prediction'
abstract: 'Restricted Boltzmann machines (RBMs) and conditional RBMs (CRBMs) are popular models for a wide range of applications. In previous work, learning on such models has been dominated by contrastive divergence (CD) and its variants. Belief propagation (BP) algorithms are believed to be slow for structured prediction on conditional RBMs (e.g., Mnih et al. [2011]), and not as good as CD when applied in learning (e.g., Larochelle et al. [2012]). In this work, we present a matrix-based implementation of belief propagation algorithms on CRBMs, which is easily scalable to tens of thousands of visible and hidden units. We demonstrate that, in both maximum likelihood and max-margin learning, training conditional RBMs with BP as the inference routine can provide significantly better results than current state-of-the-art CD methods on structured prediction problems. We also include practical guidelines on training CRBMs with BP, and some insights on the interaction of learning and inference algorithms for CRBMs.'
volume: 54
URL: https://proceedings.mlr.press/v54/ping17a.html
PDF: http://proceedings.mlr.press/v54/ping17a/ping17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-ping17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Wei
family: Ping
- given: Alex
family: Ihler
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1141-1149
id: ping17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1141
lastpage: 1149
published: 2017-04-10 00:00:00 +0000
- title: 'Sketching Meets Random Projection in the Dual: A Provable Recovery Algorithm for Big and High-dimensional Data'
abstract: 'Sketching techniques scale up machine learning algorithms by reducing the sample size or dimensionality of massive data sets, without sacrificing their statistical properties. In this paper, we study sketching from an optimization point of view. We first show that the iterative Hessian sketch is an optimization process with \emphpreconditioning and develop an \emphaccelerated version using this insight together with conjugate gradient descent. Next, we establish a primal-dual connection between the Hessian sketch and dual random projection, which allows us to develop an \emphaccelerated iterative dual random projection method by applying the preconditioned conjugate gradient descent on the dual problem. Finally, we tackle the problems of large sample size and high-dimensionality in massive data sets by developing the \emphprimal-dual sketch. The primal-dual sketch iteratively sketches the primal and dual formulations and requires only a logarithmic number of calls to solvers of small sub-problems to recover the optimum of the original problem up to \empharbitrary precision. Extensive experiments on synthetic and real data sets complement our theoretical results.'
volume: 54
URL: https://proceedings.mlr.press/v54/wang17d.html
PDF: http://proceedings.mlr.press/v54/wang17d/wang17d.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-wang17d.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Jialei
family: Wang
- given: Jason
family: Lee
- given: Mehrdad
family: Mahdavi
- given: Mladen
family: Kolar
- given: Nati
family: Srebro
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1150-1158
id: wang17d
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1150
lastpage: 1158
published: 2017-04-10 00:00:00 +0000
- title: 'Finite-sum Composition Optimization via Variance Reduced Gradient Descent'
abstract: 'The stochastic composition optimization proposed recently by Wang et al. [2014] minimizes the objective with the composite expectation form: $\min_x (\mathbbE_iF_i ∘\mathbbE_j G_j)(x).$ It summarizes many important applications in machine learning, statistics, and finance. In this paper, we consider the finite-sum scenario for composition optimization: $\min_x f (x) := \frac1n \sum_i = 1^n F_i \left( \frac1m \sum_j = 1^m G_j (x) \right)$. In this paper, two algorithms are proposed to solve this problem by combining the stochastic compositional gradient descent (SCGD) and the stochastic variance reduced gradient (SVRG) technique. A constant linear convergence rate is proved for strongly convex optimization, which substantially improves the sublinear rate $O(K^-0.8)$ of the best known algorithm. '
volume: 54
URL: https://proceedings.mlr.press/v54/lian17a.html
PDF: http://proceedings.mlr.press/v54/lian17a/lian17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-lian17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Xiangru
family: Lian
- given: Mengdi
family: Wang
- given: Ji
family: Liu
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1159-1167
id: lian17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1159
lastpage: 1167
published: 2017-04-10 00:00:00 +0000
- title: 'A Fast and Scalable Joint Estimator for Learning Multiple Related Sparse Gaussian Graphical Models'
abstract: 'Estimating multiple sparse Gaussian Graphical Models (sGGMs) jointly for many related tasks (large $K$) under a high-dimensional (large $p$) situation is an important task. Most previous studies for the joint estimation of multiple sGGMs rely on penalized log-likelihood estimators that involve expensive and difficult non-smooth optimizations. We propose a novel approach, FASJEM for \underlinefast and \underlinescalable \underlinejoint structure-\underlineestimation of \underlinemultiple sGGMs at a large scale. As the first study of joint sGGM using the M-estimator framework, our work has three major contributions: (1) We solve FASJEM through an entry-wise manner which is parallelizable. (2) We choose a proximal algorithm to optimize FASJEM. This improves the computational efficiency from $O(Kp^3)$ to $O(Kp^2)$ and reduces the memory requirement from $O(Kp^2)$ to $O(K)$. (3) We theoretically prove that FASJEM achieves a consistent estimation with a convergence rate of $O(\log(Kp)/n_tot)$. On several synthetic and four real-world datasets, FASJEM shows significant improvements over baselines on accuracy, computational complexity and memory costs.'
volume: 54
URL: https://proceedings.mlr.press/v54/wang17e.html
PDF: http://proceedings.mlr.press/v54/wang17e/wang17e.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-wang17e.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Beilun
family: Wang
- given: Ji
family: Gao
- given: Yanjun
family: Qi
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1168-1177
id: wang17e
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1168
lastpage: 1177
published: 2017-04-10 00:00:00 +0000
- title: 'Communication-efficient Distributed Sparse Linear Discriminant Analysis'
abstract: 'We propose a communication-efficient distributed estimation method for sparse linear discriminant analysis (LDA) in the high dimensional regime. Our method distributes the data of size N into m machines, and estimates a local sparse LDA estimator on each machine using the data subset of size N/m. After the distributed estimation, our method aggregates the debiased local estimators from m machines, and sparsifies the aggregated estimator. We show that the aggregated estimator attains the same statistical rate as the centralized estimation method, as long as the number of machines m is chosen appropriately. Moreover, we prove that our method can attain the model selection consistency under a milder condition than the centralized method. Experiments on both synthetic and real datasets corroborate our theory.'
volume: 54
URL: https://proceedings.mlr.press/v54/tian17a.html
PDF: http://proceedings.mlr.press/v54/tian17a/tian17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-tian17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Lu
family: Tian
- given: Quanquan
family: Gu
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1178-1187
id: tian17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1178
lastpage: 1187
published: 2017-04-10 00:00:00 +0000
- title: 'Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage'
abstract: 'This paper concerns a fundamental class of convex matrix optimization problems. It presents the first algorithm that uses optimal storage and provably computes a low-rank approximation of a solution. In particular, when all solutions have low rank, the algorithm converges to a solution. This algorithm, SketchyCGM, modifies a standard convex optimization scheme, the conditional gradient method, to store only a small randomized sketch of the matrix variable. After the optimization terminates, the algorithm extracts a low-rank approximation of the solution from the sketch. In contrast to nonconvex heuristics, the guarantees for SketchyCGM do not rely on statistical models for the problem data. Numerical work demonstrates the benefits of SketchyCGM over heuristics.'
volume: 54
URL: https://proceedings.mlr.press/v54/yurtsever17a.html
PDF: http://proceedings.mlr.press/v54/yurtsever17a/yurtsever17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-yurtsever17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Alp
family: Yurtsever
- given: Madeleine
family: Udell
- given: Joel
family: Tropp
- given: Volkan
family: Cevher
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1188-1196
id: yurtsever17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1188
lastpage: 1196
published: 2017-04-10 00:00:00 +0000
- title: 'Modal-set estimation with an application to clustering'
abstract: 'We present a procedure that can estimate – with statistical consistency guarantees – any local-maxima of a density, under benign distributional conditions. The procedure estimates all such local maxima, or modal-sets, of any bounded shape or dimension, including usual point-modes. In practice, modal-sets can arise as dense low-dimensional structures in noisy data, and more generally serve to better model the rich variety of locally dense structures in data. The procedure is then shown to be competitive on clustering applications, and moreover is quite stable to a wide range of settings of its tuning parameter. '
volume: 54
URL: https://proceedings.mlr.press/v54/jiang17c.html
PDF: http://proceedings.mlr.press/v54/jiang17c/jiang17c.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-jiang17c.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Heinrich
family: Jiang
- given: Samory
family: Kpotufe
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1197-1206
id: jiang17c
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1197
lastpage: 1206
published: 2017-04-10 00:00:00 +0000
- title: 'Compressed Least Squares Regression revisited'
abstract: 'We revisit compressed least squares (CLS) regression as originally analyzed in Maillard and Munos (2009) and later on in Kaban (2014) with some refinements. Given a set of high-dimensional inputs, CLS applies a random projection and then performs least squares regression based on the projected inputs of lower dimension. This approach can be beneficial with regard to both computation (yielding a smaller least squares problem) and statistical performance (reducing the estimation error). We will argue below that the outcome of previous analysis of the procedure is not meaningful in typical situations, yielding a bound on the prediction error that is inferior to ordinary least squares while requiring the dimension of the projected data to be of the same order as the original dimension. As a fix, we subsequently present a modified analysis with meaningful implications that much better reflects empirical results with simulated and real data.'
volume: 54
URL: https://proceedings.mlr.press/v54/slawski17a.html
PDF: http://proceedings.mlr.press/v54/slawski17a/slawski17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-slawski17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Martin
family: Slawski
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1207-1215
id: slawski17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1207
lastpage: 1215
published: 2017-04-10 00:00:00 +0000
- title: 'Diverse Neural Network Learns True Target Functions'
abstract: 'Neural networks are a powerful class of functions that can be trained with simple gradient descent to achieve state-of-the-art performance on a variety of applications. Despite their practical success, there is a paucity of results that provide theoretical guarantees on why they are so effective. Lying in the center of the problem is the difficulty of analyzing the non-convex loss function with potentially numerous local minima and saddle points. Can neural networks corresponding to the stationary points of the loss function learn the true target function? If yes, what are the key factors contributing to such nice optimization properties? In this paper, we answer these questions by analyzing one-hidden-layer neural networks with ReLU activation, and show that despite the non-convexity, neural networks with diverse units have no spurious local minima. We bypass the non-convexity issue by directly analyzing the first order optimality condition, and show that the loss can be made arbitrarily small if the minimum singular value of the “extended feature matrix” is large enough. We make novel use of techniques from kernel methods and geometric discrepancy, and identify a new relation linking the smallest singular value to the spectrum of a kernel function associated with the activation function and to the diversity of the units. Our results also suggest a novel regularization function to promote unit diversity for potentially better generalization ability.'
volume: 54
URL: https://proceedings.mlr.press/v54/xie17a.html
PDF: http://proceedings.mlr.press/v54/xie17a/xie17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-xie17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Bo
family: Xie
- given: Yingyu
family: Liang
- given: Le
family: Song
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1216-1224
id: xie17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1216
lastpage: 1224
published: 2017-04-10 00:00:00 +0000
- title: 'Local Group Invariant Representations via Orbit Embeddings'
abstract: 'Invariance to nuisance transformations is one of the desirable properties of effective representations. We consider transformations that form a group and propose an approach based on kernel methods to derive local group invariant representations. Locality is achieved by defining a suitable probability distribution over the group which in turn induces distributions in the input feature space. We learn a decision function over these distributions by appealing to the powerful framework of kernel methods and generate local invariant random feature maps via kernel approximations. We show uniform convergence bounds for kernel approximation and provide generalization bounds for learning with these features. We evaluate our method on three real datasets, including Rotated MNIST and CIFAR-10, and observe that it outperforms competing kernel based approaches. The proposed method also outperforms deep CNN on Rotated MNIST and performs comparably to the recently proposed group-equivariant CNN.'
volume: 54
URL: https://proceedings.mlr.press/v54/raj17a.html
PDF: http://proceedings.mlr.press/v54/raj17a/raj17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-raj17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Anant
family: Raj
- given: Abhishek
family: Kumar
- given: Youssef
family: Mroueh
- given: Tom
family: Fletcher
- given: Bernhard
family: Schoelkopf
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1225-1235
id: raj17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1225
lastpage: 1235
published: 2017-04-10 00:00:00 +0000
- title: 'Relativistic Monte Carlo '
abstract: 'Hamiltonian Monte Carlo (HMC) is a popular Markov chain Monte Carlo (MCMC) algorithm that generates proposals for a Metropolis-Hastings algorithm by simulating the dynamics of a Hamiltonian system. However, HMC is sensitive to large time discretizations and performs poorly if there is a mismatch between the spatial geometry of the target distribution and the scales of the momentum distribution. In particular the mass matrix of HMC is hard to tune well. In order to alleviate these problems we propose relativistic Hamiltonian Monte Carlo, a version of HMC based on relativistic dynamics that introduces a maximum velocity on particles. We also derive stochastic gradient versions of the algorithm and show that the resulting algorithms bear interesting relationships to gradient clipping, RMSprop, Adagrad and Adam, popular optimisation methods in deep learning. Based on this, we develop relativistic stochastic gradient descent by taking the zero-temperature limit of relativistic stochastic gradient Hamiltonian Monte Carlo. In experiments we show that the relativistic algorithms perform better than classical Newtonian variants and Adam.'
volume: 54
URL: https://proceedings.mlr.press/v54/lu17b.html
PDF: http://proceedings.mlr.press/v54/lu17b/lu17b.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-lu17b.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Xiaoyu
family: Lu
- given: Valerio
family: Perrone
- given: Leonard
family: Hasenclever
- given: Yee Whye
family: Teh
- given: Sebastian
family: Vollmer
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1236-1245
id: lu17b
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1236
lastpage: 1245
published: 2017-04-10 00:00:00 +0000
- title: 'Thompson Sampling for Linear-Quadratic Control Problems'
abstract: 'We consider the exploration-exploitation tradeoff in linear quadratic (LQ) control problems, where the state dynamics is linear and the cost function is quadratic in states and controls. We analyze the regret of Thompson sampling (TS) (a.k.a. posterior-sampling for reinforcement learning) in the frequentist setting, i.e., when the parameters characterizing the LQ dynamics are fixed. Despite the empirical and theoretical success in a wide range of problems from multi-armed bandit to linear bandit, we show that when studying the frequentist regret TS in control problems, we need to trade-off the frequency of sampling optimistic parameters and the frequency of switches in the control policy. This results in an overall regret of $O(T^2/3)$, which is significantly worse than the regret $O(\sqrtT)$ achieved by the optimism-in-face-of-uncertainty algorithm in LQ control problems.'
volume: 54
URL: https://proceedings.mlr.press/v54/abeille17b.html
PDF: http://proceedings.mlr.press/v54/abeille17b/abeille17b.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-abeille17b.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Marc
family: Abeille
- given: Alessandro
family: Lazaric
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1246-1254
id: abeille17b
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1246
lastpage: 1254
published: 2017-04-10 00:00:00 +0000
- title: 'Fast Classification with Binary Prototypes'
abstract: 'In this work, we propose a new technique for \emphfast k-nearest neighbor (k-NN) classification in which the original database is represented via a small set of learned binary prototypes. The training phase simultaneously learns a hash function which maps the data points to binary codes, and a set of representative binary prototypes. In the prediction phase, we first hash the query into a binary code and then do the k-NN classification using the binary prototypes as the database. Our approach speeds up k-NN classification in two aspects. First, we compress the database into a smaller set of prototypes such that k-NN search only goes through a smaller set rather than the whole dataset. Second, we reduce the original space to a compact binary embedding, where the Hamming distance between two binary codes is very efficient to compute. We propose a formulation to learn the hash function and prototypes such that the classification error is minimized. We also provide a novel theoretical analysis of the proposed technique in terms of Bayes error consistency. Empirically, our method is much faster than the state-of-the-art k-NN compression methods with comparable accuracy.'
volume: 54
URL: https://proceedings.mlr.press/v54/zhong17a.html
PDF: http://proceedings.mlr.press/v54/zhong17a/zhong17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-zhong17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Kai
family: Zhong
- given: Ruiqi
family: Guo
- given: Sanjiv
family: Kumar
- given: Bowei
family: Yan
- given: David
family: Simcha
- given: Inderjit
family: Dhillon
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1255-1263
id: zhong17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1255
lastpage: 1263
published: 2017-04-10 00:00:00 +0000
- title: 'Prediction Performance After Learning in Gaussian Process Regression'
abstract: 'This paper considers the quantification of the prediction performance in Gaussian process regression. The standard approach is to base the prediction error bars on the theoretical predictive variance, which is a lower bound on the mean square-error (MSE). This approach, however, does not take into account that the statistical model is learned from the data. We show that this omission leads to a systematic underestimation of the prediction errors. Starting from a generalization of the Cramér-Rao bound, we derive a more accurate MSE bound which provides a measure of uncertainty for prediction of Gaussian processes. The improved bound is easily computed and we illustrate it using synthetic and real data examples.'
volume: 54
URL: https://proceedings.mlr.press/v54/wagberg17a.html
PDF: http://proceedings.mlr.press/v54/wagberg17a/wagberg17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-wagberg17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Johan
family: Wagberg
- given: Dave
family: Zachariah
- given: Thomas
family: Schon
- given: Petre
family: Stoica
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1264-1272
id: wagberg17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1264
lastpage: 1272
published: 2017-04-10 00:00:00 +0000
- title: 'Communication-Efficient Learning of Deep Networks from Decentralized Data'
abstract: 'Modern mobile devices have access to a wealth of data suitable for learning models, which in turn can greatly improve the user experience on the device. For example, language models can improve speech recognition and text entry, and image models can automatically select good photos. However, this rich data is often privacy sensitive, large in quantity, or both, which may preclude logging to the data center and training there using conventional approaches. We advocate an alternative that leaves the training data distributed on the mobile devices, and learns a shared model by aggregating locally-computed updates. We term this decentralized approach Federated Learning. We present a practical method for the federated learning of deep networks based on iterative model averaging, and conduct an extensive empirical evaluation, considering five different model architectures and four datasets. These experiments demonstrate the approach is robust to the unbalanced and non-IID data distributions that are a defining characteristic of this setting. Communication costs are the principal constraint, and we show a reduction in required communication rounds by 10-100x as compared to synchronized stochastic gradient descent. '
volume: 54
URL: https://proceedings.mlr.press/v54/mcmahan17a.html
PDF: http://proceedings.mlr.press/v54/mcmahan17a/mcmahan17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-mcmahan17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Brendan
family: McMahan
- given: Eider
family: Moore
- given: Daniel
family: Ramage
- given: Seth
family: Hampson
- given: Blaise Aguera y
family: Arcas
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1273-1282
id: mcmahan17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1273
lastpage: 1282
published: 2017-04-10 00:00:00 +0000
- title: 'Learning Structured Weight Uncertainty in Bayesian Neural Networks'
abstract: 'Deep neural networks (DNNs) are increasingly popular in modern machine learning. Bayesian learning affords the opportunity to quantify posterior uncertainty on DNN model parameters. Most existing work adopts independent Gaussian priors on the model weights, ignoring possible structural information. In this paper, we consider the matrix variate Gaussian (MVG) distribution to model structured correlations within the weights of a DNN. To make posterior inference feasible, a reparametrization is proposed for the MVG prior, simplifying the complex MVG-based model to an equivalent yet simpler model with independent Gaussian priors on the transformed weights. Consequently, we develop a scalable Bayesian online inference algorithm by adopting the recently proposed probabilistic backpropagation framework. Experiments on several synthetic and real datasets indicate the superiority of our model, achieving competitive performance in terms of model likelihood and predictive root mean square error. Importantly, it also yields faster convergence speed compared to related Bayesian DNN models.'
volume: 54
URL: https://proceedings.mlr.press/v54/sun17b.html
PDF: http://proceedings.mlr.press/v54/sun17b/sun17b.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-sun17b.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Shengyang
family: Sun
- given: Changyou
family: Chen
- given: Lawrence
family: Carin
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1283-1292
id: sun17b
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1283
lastpage: 1292
published: 2017-04-10 00:00:00 +0000
- title: 'Signal-based Bayesian Seismic Monitoring'
abstract: 'Detecting weak seismic events from noisy sensors is a difficult perceptual task. We formulate this task as Bayesian inference and propose a generative model of seismic events and signals across a network of spatially distributed stations. Our system, SIGVISA, is the first to directly model seismic waveforms, allowing it to incorporate a rich representation of the physics underlying the signal generation process. We use Gaussian processes over wavelet parameters to predict detailed waveform fluctuations based on historical events, while degrading smoothly to simple parametric envelopes in regions with no historical seismicity. Evaluating on data from the western US, we recover three times as many events as previous work, and reduce mean location errors by a factor of four while greatly increasing sensitivity to low-magnitude events.'
volume: 54
URL: https://proceedings.mlr.press/v54/moore17a.html
PDF: http://proceedings.mlr.press/v54/moore17a/moore17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-moore17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: David
family: Moore
- given: Stuart
family: Russell
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1293-1301
id: moore17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1293
lastpage: 1301
published: 2017-04-10 00:00:00 +0000
- title: 'Learning the Network Structure of Heterogeneous Data via Pairwise Exponential Markov Random Fields'
abstract: 'Markov random fields (MRFs) are a useful tool for modeling relationships present in large and high-dimensional data. Often, this data comes from various sources and can have diverse distributions, for example a combination of numerical, binary, and categorical variables. Here, we define the pairwise exponential Markov random field (PE-MRF), an approach capable of modeling exponential family distributions in heterogeneous domains. We develop a scalable method of learning the graphical structure across the variables by solving a regularized approximated maximum likelihood problem. Specifically, we first derive a tractable upper bound on the log-partition function. We then use this upper bound to derive the group graphical lasso, a generalization of the classic graphical lasso problem to heterogeneous domains. To solve this problem, we develop a fast algorithm based on the alternating direction method of multipliers (ADMM). We also prove that our estimator is sparsistent, with guaranteed recovery of the true underlying graphical structure, and that it has a polynomially faster runtime than the current state-of-the-art method for learning such distributions. Experiments on synthetic and real-world examples demonstrate that our approach is both efficient and accurate at uncovering the structure of heterogeneous data.'
volume: 54
URL: https://proceedings.mlr.press/v54/park17d.html
PDF: http://proceedings.mlr.press/v54/park17d/park17d.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-park17d.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Youngsuk
family: Park
- given: David
family: Hallac
- given: Stephen
family: Boyd
- given: Jure
family: Leskovec
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1302-1310
id: park17d
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1302
lastpage: 1310
published: 2017-04-10 00:00:00 +0000
- title: 'Discovering and Exploiting Additive Structure for Bayesian Optimization'
abstract: 'Bayesian optimization has proven invaluable for black-box optimization of expensive functions. Its main limitation is its exponential complexity with respect to the dimensionality of the search space using typical kernels. Luckily, many objective functions can be decomposed into additive subproblems, which can be optimized independently. We investigate how to automatically discover such (typically unknown) additive structure while simultaneously exploiting it through Bayesian optimization. We propose an efficient algorithm based on Metropolis-Hastings sampling and demonstrate its efficacy empirically on synthetic and real-world data sets. Throughout all our experiments we reliably discover hidden additive structure whenever it exists and exploit it to yield significantly faster convergence.'
volume: 54
URL: https://proceedings.mlr.press/v54/gardner17a.html
PDF: http://proceedings.mlr.press/v54/gardner17a/gardner17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-gardner17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Jacob
family: Gardner
- given: Chuan
family: Guo
- given: Kilian
family: Weinberger
- given: Roman
family: Garnett
- given: Roger
family: Grosse
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1311-1319
id: gardner17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1311
lastpage: 1319
published: 2017-04-10 00:00:00 +0000
- title: 'Lipschitz Density-Ratios, Structured Data, and Data-driven Tuning'
abstract: 'Density-ratio estimation (i.e. estimating $f = f_Q/f_P$ for two unknown distributions Q and P) has proved useful in many Machine Learning tasks, e.g., risk-calibration in transfer-learning, two-sample tests, and also useful in common techniques such importance sampling and bias correction. While there are many important analyses of this estimation problem, the present paper derives convergence rates in other practical settings that are less understood, namely, extensions of traditional Lipschitz smoothness conditions, and common high-dimensional settings with structured data (e.g. manifold data, sparse data). Various interesting facts, which hold in earlier settings, are shown to extend to these settings. Namely, (1) optimal rates depend only on the smoothness of the ratio f, and not on the densities $f_Q$, $f_P$, supporting the belief that plugging in estimates for $f_Q$, $f_P$ is suboptimal; (2) optimal rates depend only on the intrinsic dimension of data, i.e. this problem – unlike density estimation – escapes the curse of dimension. We further show that near-optimal rates are attainable by estimators tuned from data alone, i.e. with no prior distributional information. This last fact is of special interest in unsupervised settings such as this one, where only oracle rates seem to be known, i.e., rates which assume critical distributional information usually unavailable in practice. '
volume: 54
URL: https://proceedings.mlr.press/v54/kpotufe17a.html
PDF: http://proceedings.mlr.press/v54/kpotufe17a/kpotufe17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-kpotufe17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Samory
family: Kpotufe
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1320-1328
id: kpotufe17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1320
lastpage: 1328
published: 2017-04-10 00:00:00 +0000
- title: 'Spatial Decompositions for Large Scale SVMs'
abstract: 'Although support vector machines (SVMs) are theoretically well understood, their underlying optimization problem becomes very expensive if, for example, hundreds of thousands of samples and a non-linear kernel are considered. Several approaches have been proposed in the past to address this serious limitation. In this work we investigate a decomposition strategy that learns on small, spatially defined data chunks. Our contributions are two fold: On the theoretical side we establish an oracle inequality for the overall learning method using the hinge loss, and show that the resulting rates match those known for SVMs solving the complete optimization problem with Gaussian kernels. On the practical result we compare our approach to learning SVMs on small, randomly chosen chunks. Here it turns out that for comparable training times our approach is significantly faster during testing and also reduces the test error in most cases significantly. Furthermore, we show that our approach easily scales up to 10 million training samples: including hyper-parameter selection using cross validation, the entire training only takes a few hours on a single machine. Finally, we report an experiment on 32 million training samples. All experiments used liquidSVM (Steinwart and Thomann, 2017)'
volume: 54
URL: https://proceedings.mlr.press/v54/thomann17a.html
PDF: http://proceedings.mlr.press/v54/thomann17a/thomann17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-thomann17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Philipp
family: Thomann
- given: Ingrid
family: Blaschzyk
- given: Mona
family: Meister
- given: Ingo
family: Steinwart
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1329-1337
id: thomann17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1329
lastpage: 1337
published: 2017-04-10 00:00:00 +0000
- title: 'Inference Compilation and Universal Probabilistic Programming'
abstract: 'We introduce a method for using deep neural networks to amortize the cost of inference in models from the family induced by universal probabilistic programming languages, establishing a framework that combines the strengths of probabilistic programming and deep learning methods. We call what we do “compilation of inference” because our method transforms a denotational specification of an inference problem in the form of a probabilistic program written in a universal programming language into a trained neural network denoted in a neural network specification language. When at test time this neural network is fed observational data and executed, it performs approximate inference in the original model specified by the probabilistic program. Our training objective and learning procedure are designed to allow the trained neural network to be used as a proposal distribution in a sequential importance sampling inference engine. We illustrate our method on mixture models and Captcha solving and show significant speedups in the efficiency of inference.'
volume: 54
URL: https://proceedings.mlr.press/v54/le17a.html
PDF: http://proceedings.mlr.press/v54/le17a/le17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-le17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Tuan Anh
family: Le
- given: Atilim Gunes
family: Baydin
- given: Frank
family: Wood
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1338-1348
id: le17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1338
lastpage: 1348
published: 2017-04-10 00:00:00 +0000
- title: 'Active Positive Semidefinite Matrix Completion: Algorithms, Theory and Applications'
abstract: 'In this paper we provide simple, computationally efficient, active algorithms for completion of symmetric positive semidefinite matrices. Our proposed algorithms are based on adaptive Nyström sampling, and are allowed to actively query any element in the matrix, and obtain a possibly noisy estimate of the queried element. We establish sample complexity guarantees on the recovery of the matrix in the max-norm and in the process establish new theoretical results, potentially of independent interest, on adaptive Nyström sampling. We demonstrate the efficacy of our algorithms on problems in multi-armed bandits and kernel dimensionality reduction.'
volume: 54
URL: https://proceedings.mlr.press/v54/bhargava17a.html
PDF: http://proceedings.mlr.press/v54/bhargava17a/bhargava17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-bhargava17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Aniruddha
family: Bhargava
- given: Ravi
family: Ganti
- given: Rob
family: Nowak
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1349-1357
id: bhargava17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1349
lastpage: 1357
published: 2017-04-10 00:00:00 +0000
- title: 'Information Projection and Approximate Inference for Structured Sparse Variables'
abstract: 'Approximate inference via information projection has been recently introduced as a general-purpose technique for efficient probabilistic inference given sparse variables. This manuscript goes beyond classical sparsity by proposing efficient algorithms for approximate inference via information projection that are applicable to any structure on the set of variables that admits enumeration using matroid or knapsack constraints. Further, leveraging recent advances in submodular optimization, we provide an efficient greedy algorithm with strong optimization-theoretic guarantees. The class of probabilistic models that can be expressed in this way is quite broad and, as we show, includes group sparse regression, group sparse principal components analysis and sparse collective matrix factorization, among others. Empirical results on simulated data and high dimensional neuroimaging data highlight the superior performance of the information projection approach as compared to established baselines for a range of probabilistic models.'
volume: 54
URL: https://proceedings.mlr.press/v54/khanna17a.html
PDF: http://proceedings.mlr.press/v54/khanna17a/khanna17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-khanna17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Rajiv
family: Khanna
- given: Joydeep
family: Ghosh
- given: Rusell
family: Poldrack
- given: Oluwasanmi
family: Koyejo
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1358-1366
id: khanna17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1358
lastpage: 1366
published: 2017-04-10 00:00:00 +0000
- title: 'On the Interpretability of Conditional Probability Estimates in the Agnostic Setting'
abstract: 'We study the interpretability of conditional probability estimates for binary classification under the agnostic setting or scenario. Under the agnostic setting, conditional probability estimates do not necessarily reflect the true conditional probabilities. Instead, they have a certain calibration property: among all data points that the classifier has predicted $P(Y = 1|X) = p$, $p$ portion of them actually have label $Y = 1$. For cost-sensitive decision problems, this calibration property provides adequate support for us to use Bayes Decision Theory. In this paper, we define a novel measure for the calibration property together with its empirical counterpart, and prove an uniform convergence result between them. This new measure enables us to formally justify the calibration property of conditional probability estimations, and provides new insights on the problem of estimating and calibrating conditional probabilities. '
volume: 54
URL: https://proceedings.mlr.press/v54/gao17a.html
PDF: http://proceedings.mlr.press/v54/gao17a/gao17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-gao17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Yihan
family: Gao
- given: Aditya
family: Parameswaran
- given: Jian
family: Peng
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1367-1374
id: gao17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1367
lastpage: 1374
published: 2017-04-10 00:00:00 +0000
- title: 'Linking Micro Event History to Macro Prediction in Point Process Models'
abstract: 'User behaviors in social networks are microscopic with fine grained temporal information. Predicting a macroscopic quantity based on users’ collective behaviors is an important problem. However, existing works are mainly problem-specific models for the microscopic behaviors and typically design approximation or heuristic algorithms to compute the macroscopic quantity. In this paper, we propose a unifying framework with a jump stochastic differential equation model that systematically links the microscopic event data and macroscopic inference, and the theory to approximate its probability distribution. We showed that our method can better predict the user behaviors in real-world applications.'
volume: 54
URL: https://proceedings.mlr.press/v54/wang17f.html
PDF: http://proceedings.mlr.press/v54/wang17f/wang17f.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-wang17f.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Yichen
family: Wang
- given: Xiaojing
family: Ye
- given: Haomin
family: Zhou
- given: Hongyuan
family: Zha
- given: Le
family: Song
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1375-1384
id: wang17f
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1375
lastpage: 1384
published: 2017-04-10 00:00:00 +0000
- title: 'Initialization and Coordinate Optimization for Multi-way Matching'
abstract: 'We consider the problem of consistently matching multiple sets of elements to each other, which is a common task in fields such as computer vision. To solve the underlying NP-hard objective, existing methods often relax or approximate it, but end up with unsatisfying empirical performance due to a misaligned objective. We propose a coordinate update algorithm that directly optimizes the target objective. By using pairwise alignment information to build an undirected graph and initializing the permutation matrices along the edges of its Maximum Spanning Tree, our algorithm successfully avoids bad local optima. Theoretically, with high probability our algorithm guarantees an optimal solution under reasonable noise assumptions. Empirically, our algorithm consistently and significantly outperforms existing methods on several benchmark tasks on real datasets.'
volume: 54
URL: https://proceedings.mlr.press/v54/tang17a.html
PDF: http://proceedings.mlr.press/v54/tang17a/tang17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-tang17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Da
family: Tang
- given: Tony
family: Jebara
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1385-1393
id: tang17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1385
lastpage: 1393
published: 2017-04-10 00:00:00 +0000
- title: 'Optimal Recovery of Tensor Slices'
abstract: 'We consider the problem of large scale matrix recovery given side information in the form of additional matrices of conforming dimension. This is a parsimonious model that captures a number of interesting problems including context and location aware recommendations, personalized ‘tag’ learning, demand learning with side information, etc. Viewing the matrix we seek to recover and the side information we have as slices of a tensor, we consider the problem of Slice Recovery, which is to recover specific slices of a tensor from noisy observations of the tensor. We provide an efficient algorithm to recover slices of structurally ’simple’ tensors given noisy observations of the tensor’s entries; our definition of simplicity subsumes low-rank tensors for a variety of definitions of tensor rank. Our algorithm is practical for large datasets and provides a significant performance improvement over state of the art incumbent approaches to tensor recovery. We establish theoretical recovery guarantees that under reasonable assumptions are minimax optimal for slice recovery. These guarantees also imply the first minimax optimal guarantees for recovering tensors of low Tucker rank and general noise. Experiments on data from a music streaming service demonstrate the performance and scalability of our algorithm.'
volume: 54
URL: https://proceedings.mlr.press/v54/farias17a.html
PDF: http://proceedings.mlr.press/v54/farias17a/farias17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-farias17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Vivek
family: Farias
- given: Andrew
family: Li
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1394-1402
id: farias17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1394
lastpage: 1402
published: 2017-04-10 00:00:00 +0000
- title: 'Efficient Online Multiclass Prediction on Graphs via Surrogate Losses'
abstract: ' We develop computationally efficient algorithms for online multi-class prediction. Our construction is based on carefully-chosen data-dependent surrogate loss functions, and the new methods enjoy strong mistake bound guarantees. To illustrate the technique, we study the combinatorial problem of node classification and develop a prediction strategy that is linear-time per round. In contrast, the offline benchmark is NP-hard to compute in general. We demonstrate the empirical performance of the method on several datasets. '
volume: 54
URL: https://proceedings.mlr.press/v54/rakhlin17a.html
PDF: http://proceedings.mlr.press/v54/rakhlin17a/rakhlin17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-rakhlin17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Alexander
family: Rakhlin
- given: Karthik
family: Sridharan
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1403-1411
id: rakhlin17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1403
lastpage: 1411
published: 2017-04-10 00:00:00 +0000
- title: 'Distribution of Gaussian Process Arc Lengths'
abstract: ' We present the first treatment of the arc length of the GP with more than a single output dimension. GPs are commonly used for tasks such as trajectory modelling, where path length is a crucial quantity of interest. Previously, only paths in one dimension have been considered, with no theoretical consideration of higher dimensional problems. We fill the gap in the existing literature by deriving the moments of the arc length for a stationary GP with multiple output dimensions. A new method is used to derive the mean of a one-dimensional GP over a finite interval, by considering the distribution of the arc length integrand. This technique is used to derive an approximate distribution over the arc length of a vector valued GP in $\mathbbR^n$ by moment matching the distribution. Numerical simulations confirm our theoretical derivations.'
volume: 54
URL: https://proceedings.mlr.press/v54/bewsher17a.html
PDF: http://proceedings.mlr.press/v54/bewsher17a/bewsher17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-bewsher17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Justin
family: Bewsher
- given: Alessandra
family: Tosi
- given: Michael
family: Osborne
- given: Stephen
family: Roberts
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1412-1420
id: bewsher17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1412
lastpage: 1420
published: 2017-04-10 00:00:00 +0000
- title: 'Distributed Adaptive Sampling for Kernel Matrix Approximation'
abstract: 'Most kernel-based methods, such as kernel regression, kernel PCA, ICA, or $k$-means clustering, do not scale to large datasets, because constructing and storing the kernel matrix $K_n$ requires at least $O(n^2)$ time and space for $n$ samples. Recent works (Alaoui 2014, Musco 2016) show that sampling points with replacement according to their ridge leverage scores (RLS) generates small dictionaries of relevant points with strong spectral approximation guarantees for $K_n$. The drawback of RLS-based methods is that computing exact RLS requires constructing and storing the whole kernel matrix. In this paper, we introduce SQUEAK, a new algorithm for kernel approximation based on RLS sampling that \emphsequentially processes the dataset, storing a dictionary which creates accurate kernel matrix approximations with a number of points that only depends on the effective dimension $d_eff(γ)$ of the dataset. Moreover since all the RLS estimations are efficiently performed using only the small dictionary, SQUEAK never constructs the whole matrix $K_n$, runs in linear time $\widetildeO(nd_eff(γ)^3)$ w.r.t. $n$, and requires only a single pass over the dataset. We also propose a parallel and distributed version of SQUEAK achieving similar accuracy in as little as $\widetildeO(\log(n)d_eff(γ)^3)$ time.'
volume: 54
URL: https://proceedings.mlr.press/v54/calandriello17a.html
PDF: http://proceedings.mlr.press/v54/calandriello17a/calandriello17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-calandriello17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Daniele
family: Calandriello
- given: Alessandro
family: Lazaric
- given: Michal
family: Valko
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1421-1429
id: calandriello17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1421
lastpage: 1429
published: 2017-04-10 00:00:00 +0000
- title: 'Binary and Multi-Bit Coding for Stable Random Projections'
abstract: 'The recent work [17] developed a 1-bit compressed sensing (CS) algorithm based on $α$-stable random projections. Although the work in [17] showed that the method is a strong competitor of other existing 1-bit algorithms, the procedure requires knowing $K$, the sparsity. Note that $K$ is the $l_0$ norm of the signal. Other existing 1-bit CS algorithms require the $l_2$ norm of the signal. In this paper, we develop an estimation procedure for the $l_α$ norm of the signal, where $0<α\leq2$ from binary or multi-bit measurements. We demonstrate that using a simple closed-form estimator with merely 1-bit information does not result in a significant loss of accuracy if the parameter is chosen appropriately. Theoretical tail bounds are also provided. Using 2 or more bits per measurement reduces the variance and importantly, stabilizes the estimate so that the variance is not too sensitive to chosen parameters.'
volume: 54
URL: https://proceedings.mlr.press/v54/li17c.html
PDF: http://proceedings.mlr.press/v54/li17c/li17c.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-li17c.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Ping
family: Li
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1430-1438
id: li17c
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1430
lastpage: 1438
published: 2017-04-10 00:00:00 +0000
- title: 'Spectral Methods for Correlated Topic Models'
abstract: 'In this paper we propose guaranteed spectral methods for learning a broad range of topic models, which generalize the popular Latent Dirichlet Allocation (LDA). We overcome the limitation of LDA to incorporate arbitrary topic correlations, by assuming that the hidden topic proportions are drawn from a flexible class of Normalized Infinitely Divisible (NID) distributions. NID distributions are generated by normalizing a family of independent Infinitely Divisible (ID) random variables. The Dirichlet distribution is a special case obtained by normalizing a set of Gamma random variables. We prove that this flexible topic model class can be learnt via spectral methods using only moments up to the third order, with (low order) polynomial sample and computational complexity. The proof is based on a key new technique derived here that allows us to diagonalize the moments of the NID distribution through an efficient procedure that requires evaluating only univariate integrals, despite the fact that we are handling high dimensional multivariate moments. In order to assess the performance of our proposed Latent NID topic model, we use two real datasets of articles collected from New York Times and Pubmed. Our experiments yield improved perplexity on both datasets compared with the baseline.'
volume: 54
URL: https://proceedings.mlr.press/v54/arabshahi17a.html
PDF: http://proceedings.mlr.press/v54/arabshahi17a/arabshahi17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-arabshahi17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Forough
family: Arabshahi
- given: Anima
family: Anandkumar
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1439-1447
id: arabshahi17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1439
lastpage: 1447
published: 2017-04-10 00:00:00 +0000
- title: 'Label Filters for Large Scale Multilabel Classification'
abstract: 'When assigning labels to a test instance, most multilabel and multiclass classifiers systematically evaluate every single label to decide whether it is relevant or not. This linear scan over labels becomes prohibitive when the number of labels is very large. To alleviate this problem we propose a two step approach where computationally efficient label filters pre-select a small set of candidate labels before the base multiclass or multilabel classifier is applied. The label filters select candidate labels by projecting a test instance on a filtering line, and retaining only the labels that have training instances in the vicinity of this projection. The filter parameters are learned directly from data by solving a constraint optimization problem, and are independent of the base multilabel classifier. The proposed label filters can be used in conjunction with any multiclass or multilabel classifier that requires a linear scan over the labels, and speed up prediction by orders of magnitude without significant impact on performance.'
volume: 54
URL: https://proceedings.mlr.press/v54/niculescu-mizil17a.html
PDF: http://proceedings.mlr.press/v54/niculescu-mizil17a/niculescu-mizil17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-niculescu-mizil17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Alexandru
family: Niculescu-Mizil
- given: Ehsan
family: Abbasnejad
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1448-1457
id: niculescu-mizil17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1448
lastpage: 1457
published: 2017-04-10 00:00:00 +0000
- title: 'Learning from Conditional Distributions via Dual Embeddings'
abstract: 'Many machine learning tasks, such as learning with invariance and policy evaluation in reinforcement learning, can be characterized as problems of learning from conditional distributions. In such problems, each sample x itself is associated with a conditional distribution $p(z|x)$ represented by samples $z_i_i=1^M$, and the goal is to learn a function f that links these conditional distributions to target values y. These problems become very challenging when we only have limited samples or in the extreme case only one sample from each conditional distribution. Commonly used approaches either assume that z is independent of x, or require an overwhelmingly large set of samples from each conditional distribution. To address these challenges, we propose a novel approach which employs a new min-max reformulation of the learning from conditional distribution problem. With such new reformulation, we only need to deal with the joint distribution p(z,x). We also design an efficient learning algorithm, Embedding-SGD, and establish theoretical sample complexity for such problems. Finally, our numerical experiments, on both synthetic and real-world datasets, show that the proposed approach can significantly improve over existing algorithms.'
volume: 54
URL: https://proceedings.mlr.press/v54/dai17a.html
PDF: http://proceedings.mlr.press/v54/dai17a/dai17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-dai17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Bo
family: Dai
- given: Niao
family: He
- given: Yunpeng
family: Pan
- given: Byron
family: Boots
- given: Le
family: Song
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1458-1467
id: dai17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1458
lastpage: 1467
published: 2017-04-10 00:00:00 +0000
- title: 'Sequential Multiple Hypothesis Testing with Type I Error Control'
abstract: 'This work studies multiple hypothesis testing in the setting when we obtain data sequentially and may choose when to stop sampling. We summarize the notion of a sequential p-value (one that can be continually updated and still maintain a type I error guarantee) and provide several examples from the literature. This tool allows us to convert step-up or step-down multiple hypothesis testing procedures in the fixed-horizon setting (which includes Benjamini-Hochberg, Holm, and Bonferroni) into sequential versions that allow the statistician to reject a hypothesis as soon as the sequential p-value reaches a threshold. We show that if the original procedure has a type I error guarantee in a certain family (including FDR and FWER), then the sequential conversion inherits an analogous guarantee. The conversion also allows for allocating samples in a data-dependent way, and we provide simulated experiments demonstrating an increased number of rejections when compared to the fixed-horizon setting.'
volume: 54
URL: https://proceedings.mlr.press/v54/malek17a.html
PDF: http://proceedings.mlr.press/v54/malek17a/malek17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-malek17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Alan
family: Malek
- given: Sumeet
family: Katariya
- given: Yinlam
family: Chow
- given: Mohammad
family: Ghavamzadeh
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1468-1476
id: malek17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1468
lastpage: 1476
published: 2017-04-10 00:00:00 +0000
- title: 'A Maximum Matching Algorithm for Basis Selection in Spectral Learning'
abstract: 'We present a solution to scale spectral algorithms for learning sequence functions. We are interested in the case where these functions are sparse (that is, for most sequences they return 0). Spectral algorithms reduce the learning problem to the task of computing an SVD decomposition over a special type of matrix called the Hankel matrix. This matrix is designed to capture the relevant statistics of the training sequences. What is crucial is that to capture long range dependencies we must consider very large Hankel matrices. Thus the computation of the SVD becomes a critical bottleneck. Our solution finds a subset of rows and columns of the Hankel that realizes a compact and informative Hankel submatrix. The novelty lies in the way that this subset is selected: we exploit a maximal bipartite matching combinatorial algorithm to look for a sub-block with full structural rank, and show how computation of this sub-block can be further improved by exploiting the specific structure of Hankel matrices.'
volume: 54
URL: https://proceedings.mlr.press/v54/quattoni17a.html
PDF: http://proceedings.mlr.press/v54/quattoni17a/quattoni17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-quattoni17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Ariadna
family: Quattoni
- given: Xavier
family: Carreras
- given: Matthias
family: Gallé
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1477-1485
id: quattoni17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1477
lastpage: 1485
published: 2017-04-10 00:00:00 +0000
- title: 'Value-Aware Loss Function for Model-based Reinforcement Learning'
abstract: 'We consider the problem of estimating the transition probability kernel to be used by a model-based reinforcement learning (RL) algorithm. We argue that estimating a generative model that minimizes a probabilistic loss, such as the log-loss, is an overkill because it does not take into account the underlying structure of decision problem and the RL algorithm that intends to solve it. We introduce a loss function that takes the structure of the value function into account. We provide a finite-sample upper bound for the loss function showing the dependence of the error on model approximation error, number of samples, and the complexity of the model space. We also empirically compare the method with the maximum likelihood estimator on a simple problem.'
volume: 54
URL: https://proceedings.mlr.press/v54/farahmand17a.html
PDF: http://proceedings.mlr.press/v54/farahmand17a/farahmand17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-farahmand17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Amir-Massoud
family: Farahmand
- given: Andre
family: Barreto
- given: Daniel
family: Nikovski
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1486-1494
id: farahmand17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1486
lastpage: 1494
published: 2017-04-10 00:00:00 +0000
- title: 'Convergence Rate of Stochastic k-means'
abstract: 'We analyze online (Bottou & Bengio, 1994) and mini-batch (Sculley, 2010) k-means variants. Both scale up the widely used Lloyd’s algorithm via stochastic approximation, and have become popular for large-scale clustering and unsupervised feature learning. We show, for the first time, that they have global convergence towards “local optima” at rate $O(1/t)$ under general conditions. In addition, we show that if the dataset is clusterable, stochastic k-means with suitable initialization converges to an optimal k-means solution at rate $O(1/t)$ with high probability. The k-means objective is non-convex and non-differentiable; we exploit ideas from non-convex gradient-based optimization by providing a novel characterization of the trajectory of the k-means algorithm on its solution space, and circumvent its non-differentiability via geometric insights about the k-means update.'
volume: 54
URL: https://proceedings.mlr.press/v54/tang17b.html
PDF: http://proceedings.mlr.press/v54/tang17b/tang17b.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-tang17b.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Cheng
family: Tang
- given: Claire
family: Monteleoni
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1495-1503
id: tang17b
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1495
lastpage: 1503
published: 2017-04-10 00:00:00 +0000
- title: 'Automated Inference with Adaptive Batches'
abstract: 'Classical stochastic gradient methods for optimization rely on noisy gradient approximations that become progressively less accurate as iterates approach a solution. The large noise and small signal in the resulting gradients makes it difficult to use them for adaptive stepsize selection and automatic stopping. We propose alternative “big batch” SGD schemes that adaptively grow the batch size over time to maintain a nearly constant signal-to-noise ratio in the gradient approximation. The resulting methods have similar convergence rates to classical SGD, and do not require convexity of the objective. The high fidelity gradients enable automated learning rate selection and do not require stepsize decay. Big batch methods are thus easily automated and can run with little or no oversight.'
volume: 54
URL: https://proceedings.mlr.press/v54/de17a.html
PDF: http://proceedings.mlr.press/v54/de17a/de17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-de17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Soham
family: De
- given: Abhay
family: Yadav
- given: David
family: Jacobs
- given: Tom
family: Goldstein
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1504-1513
id: de17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1504
lastpage: 1513
published: 2017-04-10 00:00:00 +0000
- title: 'Scalable Convex Multiple Sequence Alignment via Entropy-Regularized Dual Decomposition'
abstract: 'Multiple Sequence Alignment (MSA) is one of the fundamental tasks in biological sequence analysis that underlies applications such as phylogenetic trees, profiles, and structure prediction. The task, however, is NP-hard, and the current practice resorts to heuristic and local-search methods. Recently, a convex optimization approach for MSA was proposed based on the concept of atomic norm, which demonstrates significant improvement over existing methods in the quality of alignments. However, the convex program is challenging to solve due to the constraint given by the intersection of two atomic-norm balls, for which the existing algorithm can only handle sequences of length up to 50, with an iteration complexity subject to constants of unknown relation to the natural parameters of MSA. In this work, we propose an accelerated dual decomposition algorithm that exploits entropy regularization to induce closed-form solutions for each atomic-norm-constrained subproblem, giving a single-loop algorithm of iteration complexity linear to the problem size (total length of all sequences). The proposed algorithm gives significantly better alignments than existing methods on sequences of length up to hundreds, where the existing convex programming method fails to converge in one day.'
volume: 54
URL: https://proceedings.mlr.press/v54/zhang17b.html
PDF: http://proceedings.mlr.press/v54/zhang17b/zhang17b.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-zhang17b.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Jiong
family: Zhang
- given: Ian En-Hsu
family: Yen
- given: Pradeep
family: Ravikumar
- given: Inderjit
family: Dhillon
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1514-1522
id: zhang17b
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1514
lastpage: 1522
published: 2017-04-10 00:00:00 +0000
- title: 'Robust Causal Estimation in the Large-Sample Limit without Strict Faithfulness'
abstract: 'Causal effect estimation from observational data is an important and much studied research topic. The instrumental variable (IV) and local causal discovery (LCD) patterns are canonical examples of settings where a closed-form expression exists for the causal effect of one variable on another, given the presence of a third variable. Both rely on faithfulness to infer that the latter only influences the target effect via the cause variable. In reality, it is likely that this assumption only holds approximately and that there will be at least some form of weak interaction. This brings about the paradoxical situation that, in the large-sample limit, no predictions are made, as detecting the weak edge invalidates the setting. We introduce an alternative approach by replacing strict faithfulness with a prior that reflects the existence of many ’weak’ (irrelevant) and ’strong’ interactions. We obtain a posterior distribution over the target causal effect estimator which shows that, in many cases, we can still make good estimates. We demonstrate the approach in an application on a simple linear-Gaussian setting, using the MultiNest sampling algorithm, and compare it with established techniques to show our method is robust even when strict faithfulness is violated.'
volume: 54
URL: https://proceedings.mlr.press/v54/bucur17a.html
PDF: http://proceedings.mlr.press/v54/bucur17a/bucur17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-bucur17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Ioan Gabriel
family: Bucur
- given: Tom
family: Claassen
- given: Tom
family: Heskes
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1523-1531
id: bucur17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1523
lastpage: 1531
published: 2017-04-10 00:00:00 +0000
- title: 'Learning Graphical Games from Behavioral Data: Sufficient and Necessary Conditions'
abstract: 'In this paper we obtain sufficient and necessary conditions on the number of samples required for exact recovery of the pure-strategy Nash equilibria (PSNE) set of a graphical game from noisy observations of joint actions. We consider sparse linear influence games — a parametric class of graphical games with linear payoffs, and represented by directed graphs of n nodes (players) and in-degree of at most k. We show that one can efficiently recover the PSNE set of a linear influence game with $O(k^2 \log n)$ samples, under very general observation models. On the other hand, we show that $Ω(k \log n)$ samples are necessary for any procedure to recover the PSNE set from observations of joint actions.'
volume: 54
URL: https://proceedings.mlr.press/v54/ghoshal17b.html
PDF: http://proceedings.mlr.press/v54/ghoshal17b/ghoshal17b.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-ghoshal17b.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Asish
family: Ghoshal
- given: Jean
family: Honorio
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1532-1540
id: ghoshal17b
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1532
lastpage: 1540
published: 2017-04-10 00:00:00 +0000
- title: 'Non-Count Symmetries in Boolean & Multi-Valued Prob. Graphical Models'
abstract: 'Lifted inference algorithms commonly exploit symmetries in a probabilistic graphical model (PGM) for efficient inference. However, existing algorithms for Boolean-valued domains can identify only those pairs of states as symmetric, in which the number of ones and zeros match exactly (count symmetries). Moreover, algorithms for lifted inference in multi-valued domains also compute a multi-valued extension of count symmetries only. These algorithms miss many symmetries in a domain. In this paper, we present first algorithms to compute non-count symmetries in both Boolean-valued and multi-valued domains. Our methods can also find symmetries between multi-valued variables that have different domain cardinalities. The key insight in the algorithms is that they change the unit of symmetry computation from a variable to a variable-value (VV) pair. Our experiments find that exploiting these symmetries in MCMC can obtain substantial computational gains over existing algorithms.'
volume: 54
URL: https://proceedings.mlr.press/v54/anand17a.html
PDF: http://proceedings.mlr.press/v54/anand17a/anand17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-anand17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Ankit
family: Anand
- given: Ritesh
family: Noothigattu
- given: Parag
family: Singla
- given:
family: Mausam
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1541-1549
id: anand17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1541
lastpage: 1549
published: 2017-04-10 00:00:00 +0000
- title: 'Greedy Direction Method of Multiplier for MAP Inference of Large Output Domain'
abstract: 'Maximum-a-Posteriori (MAP) inference lies at the heart of Graphical Models and Structured Prediction. Despite the intractability of exact MAP inference, approximated methods based on LP relaxations have exhibited superior performance across a wide range of applications. Yet for problems involving large output domains (i.e., the state space for each variable is large), standard LP relaxations can easily give rise to a large number of variables and constraints which are beyond the limit of existing optimization algorithms. In this paper, we introduce an effective MAP inference method for problems with large output domains. The method builds upon alternating minimization of an Augmented Lagrangian that exploits the sparsity of messages through greedy optimization techniques. A key feature of our greedy approach is to introduce variables in an on-demand manner with a pre-built data structure over local factors. This results in a single-loop algorithm of sublinear cost per iteration and O(log(1/epsilon))-type iteration complexity to achieve epsilon sub-optimality. In addition, we introduce a variant of GDMM for binary MAP inference problems with a large number of factors. Empirically, the proposed algorithms demonstrate orders of magnitude speedup over state-of-the-art MAP inference techniques on MAP inference problems including Segmentation, Alignment, Protein Folding, Graph Matching, and Pairwise-Interacted Multilabel Prediction.'
volume: 54
URL: https://proceedings.mlr.press/v54/huang17a.html
PDF: http://proceedings.mlr.press/v54/huang17a/huang17a.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-huang17a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Xiangru
family: Huang
- given: Ian En-Hsu
family: Yen
- given: Ruohan
family: Zhang
- given: Qixing
family: Huang
- given: Pradeep
family: Ravikumar
- given: Inderjit
family: Dhillon
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1550-1559
id: huang17a
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1550
lastpage: 1559
published: 2017-04-10 00:00:00 +0000
- title: 'Scalable Greedy Feature Selection via Weak Submodularity'
abstract: 'Greedy algorithms are widely used for problems in machine learning such as feature selection and set function optimization. Unfortunately, for large datasets, the running time of even greedy algorithms can be quite high. This is because for each greedy step we need to refit a model or calculate a function using the previously selected choices and the new candidate. Two algorithms that are faster approximations to the greedy forward selection were introduced recently [Mirzasoleiman et al., 2013, 2015]. They achieve better performance by exploiting stochastic evaluation and distributed computation respectively. Both algorithms have provable performance guarantees for submodular functions. In this paper we show that divergent from previously held opinion, submodularity is not required to obtain approximation guarantees for these two algorithms. Specifically, we show that a generalized concept of weak submodularity suffices to give multiplicative approximation guarantees. Our result extends the applicability of these algorithms to a larger class of functions. Furthermore, we show that a bounded submodularity ratio can be used to provide data dependent bounds that can sometimes be tighter also for submodular functions. We empirically validate our work by showing superior performance of fast greedy approximations versus several established baselines on artificial and real datasets. '
volume: 54
URL: https://proceedings.mlr.press/v54/khanna17b.html
PDF: http://proceedings.mlr.press/v54/khanna17b/khanna17b.pdf
edit: https://github.com/mlresearch//v54/edit/gh-pages/_posts/2017-04-10-khanna17b.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'
publisher: 'PMLR'
author:
- given: Rajiv
family: Khanna
- given: Ethan
family: Elenberg
- given: Alex
family: Dimakis
- given: Sahand
family: Negahban
- given: Joydeep
family: Ghosh
editor:
- given: Aarti
family: Singh
- given: Jerry
family: Zhu
page: 1560-1568
id: khanna17b
issued:
date-parts:
- 2017
- 4
- 10
firstpage: 1560
lastpage: 1568
published: 2017-04-10 00:00:00 +0000