Title: Near-Optimal Streaming Ellipsoidal Rounding for General Convex Polytopes
We give near-optimal algorithms for computing an ellipsoidal rounding of a convex polytope whose vertices are given in a stream. The approximation factor is linear in the dimension (as in John's theorem) and only loses an excess logarithmic factor in the aspect ratio of the polytope. Our algorithms are nearly optimal in two senses: first, their runtimes nearly match those of the most efficient known algorithms for the offline version of the problem. Second, their approximation factors nearly match a lower bound we show against a natural class of geometric streaming algorithms. In contrast to existing works in the streaming setting that compute ellipsoidal roundings only for centrally symmetric convex polytopes, our algorithms apply to general convex polytopes. We also show how to use our algorithms to construct coresets from a stream of points that approximately preserve both the ellipsoidal rounding and the convex hull of the original set of points. more »« less
Makarychev, Yury; Manoj, Naren Sarayu; Ovsiankin, Max
(, Proceedings of Thirty Fifth Conference on Learning Theory, PMLR)
Po-Ling Loh and Maxim Raginsky
(Ed.)
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
Brandenburg, Marie-Charlotte; De_Loera, Jesus; Meroni, Chiara
(, American Mathematical Society)
We study the structure of the set of all possible affine hyperplane sections of a convex polytope. We present two different cell decompositions of this set, induced by hyperplane arrangements. Using our decomposition, we bound the number of possible combinatorial types of sections and craft algorithms that compute optimal sections of the polytope according to various combinatorial and metric criteria, including sections that maximize the number of -dimensional faces, maximize the volume, and maximize the integral of a polynomial. Our optimization algorithms run in polynomial time in fixed dimension, but the same problems show computational complexity hardness otherwise. Our tools can be extended to intersection with halfspaces and projections onto hyperplanes. Finally, we present several experiments illustrating our theorems and algorithms on famous polytopes.
Many streaming algorithms provide only a high-probability relative approximation. These two relaxations, of allowing approximation and randomization, seem necessary - for many streaming problems, both relaxations must be employed simultaneously, to avoid an exponentially larger (and often trivial) space complexity. A common drawback of these randomized approximate algorithms is that independent executions on the same input have different outputs, that depend on their random coins. Pseudo-deterministic algorithms combat this issue, and for every input, they output with high probability the same "canonical" solution. We consider perhaps the most basic problem in data streams, of counting the number of items in a stream of length at most n. Morris’s counter [CACM, 1978] is a randomized approximation algorithm for this problem that uses O(log log n) bits of space, for every fixed approximation factor (greater than 1). Goldwasser, Grossman, Mohanty and Woodruff [ITCS 2020] asked whether pseudo-deterministic approximation algorithms can match this space complexity. Our main result answers their question negatively, and shows that such algorithms must use Ω(√{log n / log log n}) bits of space. Our approach is based on a problem that we call Shift Finding, and may be of independent interest. In this problem, one has query access to a shifted version of a known string F ∈ {0,1}^{3n}, which is guaranteed to start with n zeros and end with n ones, and the goal is to find the unknown shift using a small number of queries. We provide for this problem an algorithm that uses O(√n) queries. It remains open whether poly(log n) queries suffice; if true, then our techniques immediately imply a nearly-tight Ω(log n/log log n) space bound for pseudo-deterministic approximate counting.
Alaluf, Naor; Ene, Alina; Feldman, Moran; Nguyen, Huy L; Suh, Andrew
(, 47th International Colloquium on Automata, Languages, and Programming)
We study the problem of maximizing a non-monotone submodular function subject to a cardinality constraint in the streaming model. Our main contributions are two single-pass (semi-)streaming algorithms that use $$\tilde{O}(k)\cdot\mathrm{poly}(1/\varepsilon)$$ memory, where $$k$$ is the size constraint. At the end of the stream, both our algorithms post-process their data structures using any offline algorithm for submodular maximization, and obtain a solution whose approximation guarantee is $$\frac{\alpha}{1+\alpha}-\varepsilon$$, where $$\alpha$$ is the approximation of the offline algorithm. If we use an exact (exponential time) post-processing algorithm, this leads to $$\frac{1}{2}-\varepsilon$$ approximation (which is nearly optimal). If we post-process with the algorithm of Buchbinder-Feldman '19, that achieves the state-of-the-art offline approximation guarantee of $$\alpha=0.385$$, we obtain $0.2779$-approximation in polynomial time, improving over the previously best polynomial-time approximation of $0.1715$ due to Feldman'18. One of our algorithms is combinatorial and enjoys fast update and overall running times. Our other algorithm is based on the multilinear extension, enjoys an improved space complexity, and can be made deterministic in some settings of interest.
Ben-Eliezer, Omri; Jayaram, Rajesh; Woodruff, David P.; Yogev, Eylon
(, Journal of the ACM)
We investigate the adversarial robustness of streaming algorithms. In this context, an algorithm is considered robust if its performance guarantees hold even if the stream is chosen adaptively by an adversary that observes the outputs of the algorithm along the stream and can react in an online manner. While deterministic streaming algorithms are inherently robust, many central problems in the streaming literature do not admit sublinear-space deterministic algorithms; on the other hand, classical space-efficient randomized algorithms for these problems are generally not adversarially robust. This raises the natural question of whether there exist efficient adversarially robust (randomized) streaming algorithms for these problems. In this work, we show that the answer is positive for various important streaming problems in the insertion-only model, including distinct elements and more generally F p -estimation, F p -heavy hitters, entropy estimation, and others. For all of these problems, we develop adversarially robust (1+ε)-approximation algorithms whose required space matches that of the best known non-robust algorithms up to a poly(log n , 1/ε) multiplicative factor (and in some cases even up to a constant factor). Towards this end, we develop several generic tools allowing one to efficiently transform a non-robust streaming algorithm into a robust one in various scenarios.
Makarychev, Yury, Manoj, Naren Sarayu, and Ovsiankin, Max. Near-Optimal Streaming Ellipsoidal Rounding for General Convex Polytopes. Retrieved from https://par.nsf.gov/biblio/10518029. Proceedings of the Symposium on Theory of Computing . Web. doi:10.1145/3618260.3649692.
Makarychev, Yury, Manoj, Naren Sarayu, & Ovsiankin, Max. Near-Optimal Streaming Ellipsoidal Rounding for General Convex Polytopes. Proceedings of the Symposium on Theory of Computing, (). Retrieved from https://par.nsf.gov/biblio/10518029. https://doi.org/10.1145/3618260.3649692
Makarychev, Yury, Manoj, Naren Sarayu, and Ovsiankin, Max.
"Near-Optimal Streaming Ellipsoidal Rounding for General Convex Polytopes". Proceedings of the Symposium on Theory of Computing (). Country unknown/Code not available: ACM. https://doi.org/10.1145/3618260.3649692.https://par.nsf.gov/biblio/10518029.
@article{osti_10518029,
place = {Country unknown/Code not available},
title = {Near-Optimal Streaming Ellipsoidal Rounding for General Convex Polytopes},
url = {https://par.nsf.gov/biblio/10518029},
DOI = {10.1145/3618260.3649692},
abstractNote = {We give near-optimal algorithms for computing an ellipsoidal rounding of a convex polytope whose vertices are given in a stream. The approximation factor is linear in the dimension (as in John's theorem) and only loses an excess logarithmic factor in the aspect ratio of the polytope. Our algorithms are nearly optimal in two senses: first, their runtimes nearly match those of the most efficient known algorithms for the offline version of the problem. Second, their approximation factors nearly match a lower bound we show against a natural class of geometric streaming algorithms. In contrast to existing works in the streaming setting that compute ellipsoidal roundings only for centrally symmetric convex polytopes, our algorithms apply to general convex polytopes. We also show how to use our algorithms to construct coresets from a stream of points that approximately preserve both the ellipsoidal rounding and the convex hull of the original set of points.},
journal = {Proceedings of the Symposium on Theory of Computing},
publisher = {ACM},
author = {Makarychev, Yury and Manoj, Naren Sarayu and Ovsiankin, Max},
}
Warning: Leaving National Science Foundation Website
You are now leaving the National Science Foundation website to go to a non-government website.
Website:
NSF takes no responsibility for and exercises no control over the views expressed or the accuracy of
the information contained on this site. Also be aware that NSF's privacy policy does not apply to this site.
An official website of the United States government
