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^{\omega}$, where $\omega$ is exponent of matrix multiplication. Currently, $\omega \approx 2.373$. $\bullet$ For the matrix $A$ which has small treewidth $\tau$, we can achieve $n \tau^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.
翻译：计算约翰 Ellipsoid 是机器学习和 convex优化中的一个基本问题, 目的是用最大体积来计算电子流, 最大体积存在于一个由矩阵 $A\ in\ mathbb{R ⁇ n\ time d} 美元定义的某个 convex 中央对称多元体 。 在这项工作中, 我们展示了两种关于约合 John Ellipsoid 的更快的算法 。 $\ bull$ 。 对于稀薄的矩阵 $A 来说, 我们可实现几乎输入的宽度时间 $\ mathrm{nz} (A) + d ⁇ omega} $, 其中, $\ omga$ 是矩阵倍增的缩放。 目前, $\ omga\ approx 2. 373 美元 。 $\ balllet $ 对于有小树with $\ tau $, 我们可以达到$\ tau2 美元的时间。 因此, 我们大大改进了对 John Ellips 的 Exlipsylsylsyal $ co, co co, co- col- coltimesldslus.
相关内容
微信扫码咨询专知VIP会员