MohammadHossein Bateni, Lin Chen, Hossein Esfandiari, Thomas Fu, Vahab S. Mirrokni, Afshin Rostamizadeh
2019-04-30
In the era of big data, learning from categorical features with very large vocabularies (e.g., 28 million for the Criteo click prediction dataset) has become a practical challenge for machine learning researchers and practitioners. We design a highly-scalable vocabulary compression algorithm that seeks to maximize the mutual information between the compressed categorical feature and the target binary labels and we furthermore show that its solution is guaranteed to be within a
factor of the global optimal solution. To achieve this, we introduce a novel re-parametrization of the mutual information objective, which we prove is submodular, and design a data structure to query the submodular function in amortized time (where is the input vocabulary size). Our complete algorithm is shown to operate in time. Additionally, we design a distributed implementation in which the query data structure is decomposed across machines such that each machine only requires space, while still preserving the approximation guarantee and using only logarithmic rounds of computation. We also provide analysis of simple alternative heuristic compression methods to demonstrate they cannot achieve any approximation guarantee. Using the large-scale Criteo learning task, we demonstrate better performance in retaining mutual information and also verify competitive learning performance compared to other baseline methods.
Sayan Bandyapadhyay, Saeed Mehrabi
2019-04-30
Let
and each be a set of orthogonal line segments in the plane. A line segment \emph{stabs} a line segment if . It is known that the problem of stabbing the line segments in with the minimum number of line segments of is NP-hard. However, no better than -approximation is known for the problem. In this paper, we introduce a constrained version of this problem in which every horizontal line segment of intersects a vertical line. We study several versions of the problem, depending on which line segments are used for stabbing and which line segments must be stabbed. We obtain several NP-hardness and constant approximation results for these versions. Our finding implies, the problem remains NP-hard even under the extra assumption on input, but small constant approximation algorithms can be designed.
Holden Lee, Oren Mangoubi, Nisheeth K. Vishnoi
2019-02-21
Given a sequence of convex functions
, we study the problem of sampling from the Gibbs distribution for each epoch in an online manner. This problem occurs in applications to machine learning, Bayesian statistics, and optimization where one constantly acquires new data, and must continuously update the distribution. Our main result is an algorithm that generates independent samples from a distribution that is a fixed TV-distance from for every and, under mild assumptions on the functions, makes poly gradient evaluations per epoch. All previous results for this problem imply a bound on the number of gradient or function evaluations which is at least linear in . While we assume the functions have bounded second moment, we do not assume strong convexity. In particular, we show that our assumptions hold for online Bayesian logistic regression, when the data satisfy natural regularity properties. In simulations, our algorithm achieves accuracy comparable to that of a Markov chain specialized to logistic regression. Our main result also implies the first algorithm to sample from a -dimensional log-concave distribution where the 's are not assumed to be strongly convex and the total number of gradient evaluations is roughly as opposed to implied by prior works. Key to our algorithm is a novel stochastic gradient Langevin dynamics Markov chain that has a carefully designed variance reduction step built-in with fixed constant batch size. Technically, lack of strong convexity is a significant barrier to the analysis, and, here, our main contribution is a martingale exit time argument showing the chain is constrained to a ball of radius roughly poly for the duration of the algorithm.
Karl Däubel
2019-04-03
The Ring Loading Problem emerged in the 1990s to model an important special case of telecommunication networks (SONET rings) which gained attention from practitioners and theorists alike. Given an undirected cycle on
nodes together with non-negative demands between any pair of nodes, the Ring Loading Problem asks for an unsplittable routing of the demands such that the maximum cumulated demand on any edge is minimized. Let be the value of such a solution. In the relaxed version of the problem, each demand can be split into two parts where the first part is routed clockwise while the second part is routed counter-clockwise. Denote with the maximum load of a minimum split routing solution. In a landmark paper, Schrijver, Seymour and Winkler [SSW98] showed that , where is the maximum demand value. They also found (implicitly) an instance of the Ring Loading Problem with . Recently, Skutella [Sku16] improved these bounds by showing that , and there exists an instance with . We contribute to this line of research by showing that . We also take a first step towards lower and upper bounds for small instances.
Amjad Ibrahim, Simon Rehwald, Alexander Pretschner
2019-04-30
Recent formal approaches towards causality have made the concept ready for incorporation into the technical world. However, causality reasoning is computationally hard; and no general algorithmic approach exists that efficiently infers the causes for effects. Thus, checking causality in the context of complex, multi-agent, and distributed socio-technical systems is a significant challenge. Therefore, we conceptualize an intelligent and novel algorithmic approach towards checking causality in acyclic causal models with binary variables, utilizing the optimization power in the solvers of the Boolean Satisfiability Problem (SAT). We present two SAT encodings, and an empirical evaluation of their efficiency and scalability. We show that causality is computed efficiently in less than 5 seconds for models that consist of more than 4000 variables.
Hayim Shaul, Dan Feldman, Daniela Rus
2018-01-22
In machine learning, classifiers are used to predict a class of a given query based on an existing (classified) database. Given a database S of n d-dimensional points and a d-dimensional query q, the k-nearest neighbors (kNN) classifier assigns q with the majority class of its k nearest neighbors in S. In the secure version of kNN, S and q are owned by two different parties that do not want to share their data. Unfortunately, all known solutions for secure kNN either require a large communication complexity between the parties, or are very inefficient to run. In this work we present a classifier based on kNN, that can be implemented efficiently with homomorphic encryption (HE). The efficiency of our classifier comes from a relaxation we make on kNN, where we allow it to consider kappa nearest neighbors for kappa ~ k with some probability. We therefore call our classifier k-ish Nearest Neighbors (k-ish NN). The success probability of our solution depends on the distribution of the distances from q to S and increase as its statistical distance to Gaussian decrease. To implement our classifier we introduce the concept of double-blinded coin-toss. In a doubly-blinded coin-toss the success probability as well as the output of the toss are encrypted. We use this coin-toss to efficiently approximate the average and variance of the distances from q to S. We believe these two techniques may be of independent interest. When implemented with HE, the k-ish NN has a circuit depth that is independent of n, therefore making it scalable. We also implemented our classifier in an open source library based on HELib and tested it on a breast tumor database. The accuracy of our classifier (F_1 score) were 98% and classification took less than 3 hours compared to (estimated) weeks in current HE implementations.
Wojciech Czerwiński, Wojciech Nadara, Marcin Pilipczuk
2019-04-30
Treedepth, a more restrictive graph width parameter than treewidth and pathwidth, plays major role in the theory of sparse graph classes. We show that there exists a constant
such that for every integers and a graph , if the treedepth of is at least , then the treewidth of is at least or contains a subcubic (i.e., of maximum degree at most ) tree of treedepth at least as a subgraph. As a direct corollary, we obtain that every graph of treedepth is either of treewidth at least , contains a subdivision of full binary tree of depth , or contains a path of length . This improves the bound of of Kawarabayashi and Rossman [SODA 2018]. We also show an application for approximation algorithms of treedepth: given a graph of treedepth and treewidth , one can in polynomial time compute a treedepth decomposition of of width . This improves upon a bound of stemming from a tradeoff between known results. The main technical ingredient in our result is a proof that every tree of treedepth contains a subcubic subtree of treedepth at least .
Xue Chen, Eric Price
2019-04-30
We consider the problem of locating a signal whose frequencies are "off grid" and clustered in a narrow band. Given noisy sample access to a function
with Fourier spectrum in a narrow range , how accurately is it possible to identify ? We present generic conditions on that allow for efficient, accurate estimates of the frequency. We then show bounds on these conditions for -Fourier-sparse signals that imply recovery of to within from samples on . This improves upon the best previous bound of . We also show that no algorithm can do better than . In the process we provide a new bound on the ratio between the maximum and average value of continuous -Fourier-sparse signals, which has independent application.
Yicheng Xu, Rolf H. Möhring, Dachuan Xu, Yong Zhang, Yifei Zou
2019-01-15
Hard-capacitated
-means (HCKM) is one of the fundamental problems remaining open in combinatorial optimization and data mining areas. In this problem, one is required to partition a given -point set into disjoint clusters with known capacity so as to minimize the sum of within-cluster variances. It is known to be at least APX-hard and for which most of the work is from a meta heuristic perspective. To the best our knowledge, no constant approximation algorithm or existence proof of such an algorithm is known. As our main contribution, we propose an FPT( ) algorithm with performance guarantee of for any HCKM instances in this paper.
Aleksandrs Slivkins
2019-04-15
Multi-armed bandits a simple but very powerful framework for algorithms that make decisions over time under uncertainty. An enormous body of work has accumulated over the years, covered in several books and surveys. This book provides a more introductory, textbook-like treatment of the subject. Each chapter tackles a particular line of work, providing a self-contained, teachable technical introduction and a review of the more advanced results. The chapters are as follows: Stochastic bandits; Lower bounds; Bayesian Bandits and Thompson Sampling; Lipschitz Bandits; Full Feedback and Adversarial Costs; Adversarial Bandits; Linear Costs and Semi-bandits; Contextual Bandits; Bandits and Zero-Sum Games; Bandits with Knapsacks; Incentivized Exploration and Connections to Mechanism Design.
