Tight Bounds for Volumetric Spanners and Applications
Authors: Aditya Bhaskara, Sepideh Mahabadi, Ali Vakilian
NeurIPS 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main contribution in this paper is to show that a simple local search algorithm yields volumetric spanners with parameters that improve both lines of prior work by Hazan and Karnin [2016] and Woodruff and Yasuda [2023]. Our arguments also allow us to study the case of having a general ℓp norm bound on the coefficients. Thus, we obtain a common generalization with the results of Awerbuch and Kleinberg [2008] on barycentric spanners (which correspond to the case p = ). Further our results can be plugged in, following the same approach of Woodruff and Yasuda [2023], to obtain improvements on a range of matrix approximation problems in these settings.One application we highlight is the following. Volumetric spanners turn out to be closely related to another well-studied problem, that of finding the minimum volume enclosing ellipsoid (MVEE) for a given set of points, or more generally, for a given convex body K. This is a classic problem in geometry [Welzl, 1991, Khachiyan and Todd, 1990]. The celebrated result of Fitz John (e.g., see [Ball, 1992]) characterized the optimal solution for general K. Computationally, the MVEE can be computed using a semidefinite programming relaxation [Boyd et al., 2004], and more efficient algorithms have subsequently been developed; see [Cohen et al., 2019]. Coresets for MVEE (defined formally below) were used to construct well-conditioned spanning subsets in the recent work of Woodruff and Yasuda [2023]. We give a result in the opposite direction, and show that the local search algorithm for finding well-conditioned spanning sets can be used to obtain a coreset of size O(d/ϵ). This quantitatively improves upon prior work, as we now discuss. |
| Researcher Affiliation | Collaboration | Aditya Bhaskara University of Utah bhaskaraaditya@gmail.com Sepideh Mahabadi Microsoft Research Redmond smahabadi@microsoft.com Ali Vakilian Toyota Technological Institute at Chicago (TTIC) vakilian@ttic.edu |
| Pseudocode | Yes | Algorithm 1 Procedure Local Search-NR |
| Open Source Code | No | The paper does not include any explicit statement about releasing code or a link to a source-code repository. |
| Open Datasets | No | The paper is theoretical and does not use or describe any specific datasets for training or evaluation. It refers to abstract 'sets of vectors' but not concrete public datasets. |
| Dataset Splits | No | The paper is theoretical and does not mention any data splits for validation or other purposes. |
| Hardware Specification | No | The paper is theoretical and does not describe any specific hardware used for experiments. |
| Software Dependencies | No | The paper does not specify any software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithmic properties and bounds. It does not describe an experimental setup with hyperparameters or system-level training settings. |