论文标题
结构化John Ellipsoid计算的更快算法
Faster Algorithm for Structured John Ellipsoid Computation
论文作者
论文摘要
计算John Ellipsoid是机器学习和凸优化的一个基本问题，其目标是用最大体积计算椭圆形，该椭圆形在给定的凸中心中心对称的多层poper，由矩阵$ a \ in \ MathBb in \ Mathbb {r}^n \ times d} $定义。在这项工作中，我们展示了两种更快的算法，用于近似约翰·埃利普斯（John Ellipsoid）。 $ \ bullet $用于稀疏矩阵$ a $，我们可以实现几乎输入稀疏时间$ \ mathrm {nnz}（a） + d^ω$，其中$ω$是矩阵乘法的指数。当前，$ω\约2.373 $。 矩阵$ a $的$ \ bullet $，带有小树宽$τ$，我们可以实现$nτ2$ time。 因此，我们显着改善了近似于中央对称多层的约翰椭圆形的最新结果[Cohen，Cousins，Lee和Yang Colt 2019]，该结果花费了$ ND^2 $时间。
Computing John Ellipsoid is a fundamental problem in machine learning and convex optimization, where the goal is to compute the ellipsoid with maximal volume that lies in a given convex centrally symmetric polytope defined by a matrix $A \in \mathbb{R}^{n \times d}$. In this work, we show two faster algorithms for approximating the John Ellipsoid. $\bullet$ For sparse matrix $A$, we can achieve nearly input sparsity time $\mathrm{nnz}(A) + d^ω$, where $ω$ is exponent of matrix multiplication. Currently, $ω\approx 2.373$. $\bullet$ For the matrix $A$ which has small treewidth $τ$, we can achieve $n τ^2$ time. Therefore, we significantly improves the state-of-the-art results on approximating the John Ellipsoid for centrally symmetric polytope [Cohen, Cousins, Lee, and Yang COLT 2019] which takes $nd^2$ time.
