Revisiting Area Convexity: Faster Box-Simplex Games and Spectrahedral Generalizations
Authors: Arun Jambulapati, Kevin Tian
NeurIPS 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We investigate different aspects of area convexity [She17], a mysterious tool introduced to tackle optimization problems under the challenging ℓ geometry. We develop a deeper understanding of its relationship with more conventional analyses of extragradient methods [Nem04, Nes07]. We also give improved solvers for the subproblems required by variants of the [She17] algorithm, designed through the lens of relative smoothness [BBT17, LFN18]. Leveraging these new tools, we give a state-of-the-art first-order algorithm for solving box-simplex games (a primal-dual formulation of ℓ regression) in a d n matrix with bounded rows, using O(log d ϵ 1) matrix-vector queries. Our solver yields improved runtimes for approximate maximum flow, optimal transport, min-mean-cycle, and other basic combinatorial optimization problems. We also develop a near-linear time algorithm for a matrix generalization of box-simplex games, capturing a family of problems closely related to semidefinite programs recently used as subroutines in robust statistics and numerical linear algebra. |
| Researcher Affiliation | Collaboration | Arun Jambulapati Simons Institute jmblpati@berkeley.edu Kevin Tian University of Texas at Austin kjtian@cs.utexas.edu Work completed at the University of Washington. Work completed at Microsoft Research. |
| Pseudocode | Yes | Algorithm 1: Conceptual Box Simplex(A, b, c, Ograd, Oxgrad) [...] Algorithm 2: Grad Step Oracle(z, v, α, β) [...] Algorithm 3: XGrad Step Oracle(z, v, y, α, β) |
| Open Source Code | No | The paper does not provide any statement about making its source code available or a link to a code repository for the described methodology. |
| Open Datasets | No | The paper is theoretical, focusing on algorithm design and runtime complexity, rather than empirical studies on specific datasets. Therefore, it does not mention training on publicly available datasets. |
| Dataset Splits | No | The paper is theoretical and focuses on algorithm design and analysis. It does not describe experiments with dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and discusses algorithm complexity and runtime, but it does not specify any hardware used for running experiments. |
| Software Dependencies | No | The paper focuses on theoretical algorithm design and analysis. It does not mention any specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and describes algorithms and their complexity. It does not include specific experimental setup details such as hyperparameters, optimization settings, or training configurations. |