ML Anthology

A Near-Optimal Algorithm for Approximating the John Ellipsoid

Michael B. Cohen, Ben Cousins, Yin Tat Lee, Xin Yang
COLT 2019 pp. 849-873
/colt/2019/cohen2019colt-nearoptimal/

Abstract

We develop a simple and efficient algorithm for approximating the John Ellipsoid of a symmetric polytope. Our algorithm is near optimal in the sense that our time complexity matches the current best verification algorithm. Experimental results suggest that our algorithm significantly outperforms existing algorithms. We also provide the MATLAB code for further research.

PDF COLT Semantic Scholar

Cite

Text

Cohen et al. "A Near-Optimal Algorithm for Approximating the John Ellipsoid." Conference on Learning Theory, 2019.

Markdown

[Cohen et al. "A Near-Optimal Algorithm for Approximating the John Ellipsoid." Conference on Learning Theory, 2019.](https://mlanthology.org/colt/2019/cohen2019colt-nearoptimal/)

BibTeX

@inproceedings{cohen2019colt-nearoptimal,
  title     = {{A Near-Optimal Algorithm for Approximating the John Ellipsoid}},
  author    = {Cohen, Michael B. and Cousins, Ben and Lee, Yin Tat and Yang, Xin},
  booktitle = {Conference on Learning Theory},
  year      = {2019},
  pages     = {849-873},
  volume    = {99},
  url       = {https://mlanthology.org/colt/2019/cohen2019colt-nearoptimal/}
}