More Like this

1. From Sampling to Optimization on Discrete Domains with Applications to Determinant Maximization

   Anari, Nima; Vuong, Thuy-Duong (July 2022, Proceedings of Thirty Fifth Conference on Learning Theory)

   Loh, Po-Ling; Raginsky, Maxim (Ed.)

   We establish a connection between sampling and optimization on discrete domains. For a family of distributions $$\mu$$ defined on size $$k$$ subsets of a ground set of elements, that is closed under external fields, we show that rapid mixing of natural local random walks implies the existence of simple approximation algorithms to find $$\max \mu(\cdot)$$. More precisely, we show that if $$t$$-step down-up random walks have spectral gap at least inverse polynomially large, then $$t$$-step local search finds $$\max \mu(\cdot)$$ within a factor of $$k^{O(k)}$$. As the main application of our result, we show that $$2$$-step local search achieves a nearly-optimal $$k^{O(k)}$$-factor approximation for MAP inference on nonsymmetric $$k$$-DPPs. This is the first nontrivial multiplicative approximation algorithm for this problem. In our main technical result, we show that an exchange inequality, a concept rooted in discrete convex analysis, can be derived from fast mixing of local random walks. We further advance the state of the art on the mixing of random walks for nonsymmetric DPPs and more generally sector-stable distributions, by obtaining the tightest possible bound on the step size needed for polynomial-time mixing of random walks. We bring the step size down by a factor of $$2$$ compared to prior works, and consequently get a quadratic improvement on the runtime of local search steps; this improvement is potentially of independent interest in sampling applications. 

   more » « less
2. No Dimensional Sampling Coresets for Classification

   Alishahi, Meysam; Phillips, Jeff M (July 2024, Proceedings of the 41st International Conference on Machine Learning (ICML))

   We refine and generalize what is known about coresets for classification problems via the sensitivity sampling framework. Such coresets seek the smallest possible subsets of input data, so one can optimize a loss function on the coreset and ensure approximation guarantees with respect to the original data. Our analysis provides the first no dimensional coresets, so the size does not depend on the dimension. Moreover, our results are general, apply for distributional input and can use iid samples, so provide sample complexity bounds, and work for a variety of loss functions. A key tool we develop is a Radamacher complexity version of the main sensitivity sampling approach, which can be of independent interest. 

   more » « less
3. Testing Determinantal Point Processes

   Gatmiry, Khashayar; Aliakbarpour, Maryam; Jegelka, Stefanie (January 2020, Annual Conference on Neural Information Processing Systems (NeurIPS 2020))

   null (Ed.)

   Determinantal point processes (DPPs) are popular probabilistic models of diversity. In this paper, we investigate DPPs from a new perspective: property testing of distributions. Given sample access to an unknown distribution q over the subsets of a ground set, we aim to distinguish whether q is a DPP distribution or ϵ-far from all DPP distributions in ℓ1-distance. In this work, we propose the first algorithm for testing DPPs. Furthermore, we establish a matching lower bound on the sample complexity of DPP testing. This lower bound also extends to showing a new hardness result for the problem of testing the more general class of log-submodular distributions 

   more » « less
4. Coreset Clustering on Small Quantum Computers

   https://doi.org/10.3390/electronics10141690  

   Tomesh, Teague; Gokhale, Pranav; Anschuetz, Eric R.; Chong, Frederic T. (July 2021, Electronics)

   null (Ed.)

   Many quantum algorithms for machine learning require access to classical data in superposition. However, for many natural data sets and algorithms, the overhead required to load the data set in superposition can erase any potential quantum speedup over classical algorithms. Recent work by Harrow introduces a new paradigm in hybrid quantum-classical computing to address this issue, relying on coresets to minimize the data loading overhead of quantum algorithms. We investigated using this paradigm to perform k-means clustering on near-term quantum computers, by casting it as a QAOA optimization instance over a small coreset. We used numerical simulations to compare the performance of this approach to classical k-means clustering. We were able to find data sets with which coresets work well relative to random sampling and where QAOA could potentially outperform standard k-means on a coreset. However, finding data sets where both coresets and QAOA work well—which is necessary for a quantum advantage over k-means on the entire data set—appears to be challenging. 

   more » « less
5. Subset Selection and Summarization in Sequential Data

   Elhamifar, E.; De Paolis Kaluza, M. C. (January 2017, Neural Information Processing Systems)

   Subset selection, which is the task of finding a small subset of representative items from a large ground set, finds numerous applications in different areas. Sequential data, including time-series and ordered data, contain important structural relationships among items, imposed by underlying dynamic models of data, that should play a vital role in the selection of representatives. However, nearly all existing subset selection techniques ignore underlying dynamics of data and treat items independently, leading to incompatible sets of representatives. In this paper, we develop a new framework for sequential subset selection that finds a set of representatives compatible with the dynamic models of data. To do so, we equip items with transition dynamic models and pose the problem as an integer binary optimization over assignments of sequential items to representatives, that leads to high encoding, diversity and transition potentials. Our formulation generalizes the well-known facility location objective to deal with sequential data, incorporating transition dynamics among facilities. As the proposed formulation is non-convex, we derive a max-sum message passing algorithm to solve the problem efficiently. Experiments on synthetic and real data, including instructional video summarization, show that our sequential subset selection framework not only achieves better encoding and diversity than the state of the art, but also successfully incorporates dynamics of data, leading to compatible representatives. 

   more » « less