Streaming Algorithms for Ellipsoidal Approximation of Convex Polytopes

Yury Makarychev, Naren Sarayu Manoj, Max Ovsiankin
Proceedings of Thirty Fifth Conference on Learning Theory, PMLR 178:3070-3093, 2022.

Abstract

We give efficient deterministic one-pass streaming algorithms for finding an ellipsoidal approximation of a symmetric convex polytope. The algorithms are near-optimal in that their approximation factors differ from that of the optimal offline solution only by a factor sub-logarithmic in the aspect ratio of the polytope.

Cite this Paper

BibTeX
@InProceedings{pmlr-v178-makarychev22a, title = {Streaming Algorithms for Ellipsoidal Approximation of Convex Polytopes}, author = {Makarychev, Yury and Manoj, Naren Sarayu and Ovsiankin, Max}, booktitle = {Proceedings of Thirty Fifth Conference on Learning Theory}, pages = {3070--3093}, year = {2022}, editor = {Loh, Po-Ling and Raginsky, Maxim}, volume = {178}, series = {Proceedings of Machine Learning Research}, month = {02--05 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v178/makarychev22a/makarychev22a.pdf}, url = {https://proceedings.mlr.press/v178/makarychev22a.html}, abstract = {We give efficient deterministic one-pass streaming algorithms for finding an ellipsoidal approximation of a symmetric convex polytope. The algorithms are near-optimal in that their approximation factors differ from that of the optimal offline solution only by a factor sub-logarithmic in the aspect ratio of the polytope.} }
Endnote
%0 Conference Paper %T Streaming Algorithms for Ellipsoidal Approximation of Convex Polytopes %A Yury Makarychev %A Naren Sarayu Manoj %A Max Ovsiankin %B Proceedings of Thirty Fifth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2022 %E Po-Ling Loh %E Maxim Raginsky %F pmlr-v178-makarychev22a %I PMLR %P 3070--3093 %U https://proceedings.mlr.press/v178/makarychev22a.html %V 178 %X We give efficient deterministic one-pass streaming algorithms for finding an ellipsoidal approximation of a symmetric convex polytope. The algorithms are near-optimal in that their approximation factors differ from that of the optimal offline solution only by a factor sub-logarithmic in the aspect ratio of the polytope.
APA
Makarychev, Y., Manoj, N.S. & Ovsiankin, M.. (2022). Streaming Algorithms for Ellipsoidal Approximation of Convex Polytopes. Proceedings of Thirty Fifth Conference on Learning Theory, in Proceedings of Machine Learning Research 178:3070-3093 Available from https://proceedings.mlr.press/v178/makarychev22a.html.

Related Material