Michael Kapralov, Ameya Velingker, Amir Zandieh
2019-02-27
The Discrete Fourier Transform (DFT) is a fundamental computational primitive, and the fastest known algorithm for computing the DFT is the FFT (Fast Fourier Transform) algorithm. One remarkable feature of FFT is the fact that its runtime depends only on the size
of the input vector, but not on the dimensionality of the input domain: FFT runs in time irrespective of whether the DFT in question is on or for some , where . The state of the art for Sparse FFT, i.e. the problem of computing the DFT of a signal that has at most nonzeros in Fourier domain, is very different: all current techniques for sublinear time computation of Sparse FFT incur an exponential dependence on the dimension in the runtime. In this paper we give the first algorithm that computes the DFT of a -sparse signal in time in any dimension , avoiding the curse of dimensionality inherent in all previously known techniques. Our main tool is a new class of filters that we refer to as adaptive aliasing filters: these filters allow isolating frequencies of a -Fourier sparse signal using samples in time domain and runtime per frequency, in any dimension . We also investigate natural average case models of the input signal: (1) worst case support in Fourier domain with randomized coefficients and (2) random locations in Fourier domain with worst case coefficients. Our techniques lead to an time algorithm for the former and an time algorithm for the latter.
Yuko Kuroki, Liyuan Xu, Atsushi Miyauchi, Junya Honda, Masashi Sugiyama
2019-02-27
We study the problem of stochastic combinatorial pure exploration (CPE), where an agent sequentially pulls a set of single arms (a.k.a. a super arm) and tries to find the best super arm. Among a variety of problem settings of the CPE, we focus on the full-bandit setting, where we cannot observe the reward of each single arm, but only the sum of the rewards. Although we can regard the CPE with full-bandit feedback as a special case of pure exploration in linear bandits, an approach based on linear bandits is not computationally feasible since the number of super arms may be exponential. In this paper, we first propose a polynomial-time bandit algorithm for the CPE under general combinatorial constraints and provide an upper bound of the sample complexity. Second, we design an approximation algorithm for the 0-1 quadratic maximization problem, which arises in many bandit algorithms with confidence ellipsoids. Based on our approximation algorithm, we propose novel bandit algorithms for the top-k selection problem, and prove that our algorithms run in polynomial time. Finally, we conduct experiments on synthetic and real-world datasets, and confirm the validity of our theoretical analysis in terms of both the computation time and the sample complexity.
Anisur Rahaman Molla, William K. Moses Jr
2019-02-27
We consider cooperation among insects, modeled as cooperation between mobile robots on a graph. Within this setting, we consider the problem of mobile robot dispersion on graphs. The study of mobile robots on a graph is an interesting paradigm with many interesting problems and applications. The problem of dispersion in this context, introduced by Augustine and Moses Jr., asks that
robots, initially placed arbitrarily on an node graph, work together to quickly reach a configuration with exactly one robot at each node. Previous work on this problem has looked at the trade-off between the time to achieve dispersion and the amount of memory required by each robot. However, the trade-off was analyzed for \textit{deterministic algorithms} and the minimum memory required to achieve dispersion was found to be bits at each robot. In this paper, we show that by harnessing the power of \textit{randomness}, one can achieve dispersion with bits of memory at each robot, where is the maximum degree of the graph. Furthermore, we show a matching lower bound of bits for any \textit{randomized algorithm} to solve dispersion. We further extend the problem to a general -dispersion problem where robots need to disperse over nodes such that at most robots are at each node in the final configuration.
Zonglei Bai, Yongzhi Cao, Hanpin Wang
2019-02-25
In this paper, we give a sampling algorithm for the Potts model using Markov chains. Based on the sampling algorithm, we give \emph{FPRAS}es for the Potts model and the number of
-colorings of the graph.
Bruno Ordozgoiti, Aristides Gionis
2019-02-27
We propose a new variant of the k-median problem, where the objective function models not only the cost of assigning data points to cluster representatives, but also a penalty term for disagreement among the representatives. We motivate this novel problem by applications where we are interested in clustering data while avoiding selecting representatives that are too far from each other. For example, we may want to summarize a set of news sources, but avoid selecting ideologically-extreme articles in order to reduce polarization. To solve the proposed k-median formulation we adopt the local-search algorithm of Arya et al. We show that the algorithm provides a provable approximation guarantee, which becomes constant under a mild assumption on the minimum number of points for each cluster. We experimentally evaluate our problem formulation and proposed algorithm on datasets inspired by the motivating applications. In particular, we experiment with data extracted from Twitter, the US Congress voting records, and popular news sources. The results show that our objective can lead to choosing less polarized groups of representatives without significant loss in representation fidelity.
Changye Wu, Julien Stoehr, Christian P. Robert
2018-10-10
Hamiltonian Monte Carlo samplers have become standard algorithms for MCMC implementations, as opposed to more basic versions, but they still require some amount of tuning and calibration. Exploiting the U-turn criterion of the NUTS algorithm (Hoffman and Gelman, 2014), we propose a version of HMC that relies on the distribution of the integration time of the associated leapfrog integrator. Using in addition the primal-dual averaging method for tuning the step size of the integrator, we achieve an essentially calibration free version of HMC. When compared with the original NUTS on several benchmarks, this algorithm exhibits a significantly improved efficiency.
Ainesh Bakshi, Nadiia Chepurko, David P. Woodruff
2019-02-27
We study the Maximum Independent Set problem for geometric objects given in the data stream model. A set of geometric objects is said to be independent if the objects are pairwise disjoint. We consider geometric objects in one and two dimensions, i.e., intervals and disks. Let
be the cardinality of the largest independent set. Our goal is to estimate in a small amount of space, given that the input is received as a one-pass turnstile stream. We also consider a generalization of this problem by assigning weights to each object and estimating , the largest value of a weighted independent set. We provide the first algorithms for estimating and in turnstile streams. For unit-length intervals, we obtain a -approximation to and in poly space. We also show a matching lower bound. For arbitrary-length intervals, we show any -approximation to , and thus also , requires space. To this end, we introduce a new communication problem and lower bound its information complexity. In light of the lower bound we provide algorithms for estimating for arbitrary-length intervals under a bounded intersection assumption. We also study the parameterized space complexity of estimating and , where the parameter is the ratio of maximum to minimum interval length. For unit-radius disks, we obtain a -approximation to and in space, which is closely related to the hexagonal circle packing constant.
Mingda Qiao, Gregory Valiant
2019-02-12
We consider a model of selective prediction, where the prediction algorithm is given a data sequence in an online fashion and asked to predict a pre-specified statistic of the upcoming data points. The algorithm is allowed to choose when to make the prediction as well as the length of the prediction window, possibly depending on the observations so far. We prove that, even without any distributional assumption on the input data stream, a large family of statistics can be estimated to non-trivial accuracy. To give one concrete example, suppose that we are given access to an arbitrary binary sequence
of length . Our goal is to accurately predict the average observation, and we are allowed to choose the window over which the prediction is made: for some and , after seeing observations we predict the average of . This particular problem was first studied in [Dru13] and referred to as the "density prediction game". We show that the expected squared error of our prediction can be bounded by and prove a matching lower bound, which resolves an open question raised in [Dru13]. This result holds for any sequence (that is not adaptive to when the prediction is made, or the predicted value), and the expectation of the error is with respect to the randomness of the prediction algorithm. Our results apply to more general statistics of a sequence of observations, and we highlight several open directions for future work.
Hans Raj Tiwary, Victor Verdugo, Andreas Wiese
2019-02-27
Linear programming is a powerful method in combinatorial optimization with many applications in theory and practice. For solving a linear program quickly it is desirable to have a formulation of small size for the given problem. A useful approach for this is the construction of an extended formulation, which is a linear program in a higher dimensional space whose projection yields the original linear program. For many problems it is known that a small extended formulation cannot exist. However, most of these problems are either
-hard (like TSP), or only quite complicated polynomial time algorithms are known for them (like for the matching problem). In this work we study the minimum makespan problem on identical machines in which we want to assign a set of given jobs to machines in order to minimize the maximum load over the machines. We prove that the canonical formulation for this problem has extension complexity , even if each job has size 1 or 2 and the optimal makespan is 2. This is a case that a trivial greedy algorithm can solve optimally! For the more powerful configuration integer program, we even prove a lower bound of . On the other hand, we show that there is an abstraction of the configuration integer program admitting an extended formulation of size . In addition, we give an -approximate integral formulation of polynomial size, even for arbitrary processing times and for the far more general setting of unrelated machines.
Rishabh Iyer, Jeff Bilmes
2019-02-26
We are motivated by large scale submodular optimization problems, where standard algorithms that treat the submodular functions in the \emph{value oracle model} do not scale. In this paper, we present a model called the \emph{precomputational complexity model}, along with a unifying memoization based framework, which looks at the specific form of the given submodular function. A key ingredient in this framework is the notion of a \emph{precomputed statistic}, which is maintained in the course of the algorithms. We show that we can easily integrate this idea into a large class of submodular optimization problems including constrained and unconstrained submodular maximization, minimization, difference of submodular optimization, optimization with submodular constraints and several other related optimization problems. Moreover, memoization can be integrated in both discrete and continuous relaxation flavors of algorithms for these problems. We demonstrate this idea for several commonly occurring submodular functions, and show how the precomputational model provides significant speedups compared to the value oracle model. Finally, we empirically demonstrate this for large scale machine learning problems of data subset selection and summarization.
