A near-optimal algorithm for approximating the John Ellipsoid

Michael B. Cohen, Ben Cousins, Yin Tat Lee, Xin Yang
Proceedings of the Thirty-Second Conference on Learning Theory, PMLR 99:849-873, 2019.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v99-cohen19a, 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 = {Proceedings of the Thirty-Second Conference on Learning Theory}, pages = {849--873}, year = {2019}, editor = {Beygelzimer, Alina and Hsu, Daniel}, volume = {99}, series = {Proceedings of Machine Learning Research}, month = {25--28 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v99/cohen19a/cohen19a.pdf}, url = {https://proceedings.mlr.press/v99/cohen19a.html}, 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. } }
Endnote
%0 Conference Paper %T A near-optimal algorithm for approximating the John Ellipsoid %A Michael B. Cohen %A Ben Cousins %A Yin Tat Lee %A Xin Yang %B Proceedings of the Thirty-Second Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2019 %E Alina Beygelzimer %E Daniel Hsu %F pmlr-v99-cohen19a %I PMLR %P 849--873 %U https://proceedings.mlr.press/v99/cohen19a.html %V 99 %X 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.
APA
Cohen, M.B., Cousins, B., Lee, Y.T. & Yang, X.. (2019). A near-optimal algorithm for approximating the John Ellipsoid. Proceedings of the Thirty-Second Conference on Learning Theory, in Proceedings of Machine Learning Research 99:849-873 Available from https://proceedings.mlr.press/v99/cohen19a.html.

Related Material