Open Problems:73

Suggested by	Edo Liberty
Source	Baltimore 2016
Short link	https://sublinear.info/73

A tad more open-ended than the usual open problems from this website, this one arises from the following observation. While streaming algorithms are often motivated by the constraints due to “big data,” in practice this data is not static: however, most streaming algorithms use the structure and regularities encountered in the stream to compute solutions or results only available at the end of the streaming, in hindsight.

In practice, however, one often needs to be online as well: that is, to maintain a “good as of now” solution as the stream goes, and to combine the usual memory constraints of the streaming setting with the objectives of the standard online analysis setting. (Note that, in contrast to the majority of the machine learning literature, one cannot in general make the assumption of stochasticity; the performance thus has to be compared in the adversarial setting, or an intermediate, better suited model has to be developed.)

Question: Which model can capture this real-world need for a combination of streaming and online competitivity constraints, and what algorithms can then one obtain in this model?

Note: For some work in this direction, one can consult [LibertySS-16].