Seeing future data improves greedy set selection for limited memory
Optimal Polynomial-Query Approximation for Consistent Submodular Maximization with Short Lookahead
Data Structures and AlgorithmsMachine Learning
Summary
The paper studies how to keep a small group of items that maximizes value as new items arrive one by one. Normally, without knowing what's coming next, the best you can do is about 58.6% as good as the perfect choice after seeing all items. The authors show that if the algorithm can look a little bit into the future, it can do about 63.2% as well, which is the best possible. They also give specific algorithms that balance how many items are changed at each step and how many future items are seen, offering a clearer understanding of this trade-off.
What this means in practice
- •For database system engineers: Implement storage policies that maintain valuable subsets of data elements as new data arrives with limited edits and partial future insight.
- •For real-time recommendation teams: Improve item selection for recommendations by using short-term prediction of incoming content to maintain high-quality sets efficiently.
A theory result. No direct application yet.
Authors
Vaneet Aggarwal
Abstract
Elements arrive one at a time, and after each arrival an algorithm holds a set of at most $k$ arrived elements. Its goal is a held set whose value under a monotone submodular function is close to the best value that $k$ arrived elements can achieve. The recourse of an update is the number of elements inserted into or removed from the held set, and we require it to be bounded independently of $k$ and of the number $n$ of arrivals. With evaluations only on sets of arrived elements and polynomially many of them, the best ratio a randomized algorithm can achieve is $2-\sqrt{2}\approx0.5858$. We show that seeing future arrivals raises the best ratio for polynomially many evaluations to $1-1/e\approx0.6321$, for deterministic and for randomized algorithms; no algorithm with polynomially many evaluations exceeds $1-1/e$, even when all elements are available at once. For every $\varepsilon>0$, a deterministic algorithm that sees the next $\lceil\varepsilon k/3\rceil$ arrivals keeps a set of value at least $1-1/e-\varepsilon$ times the optimum at every time, changes $O(\varepsilon^{-3})$ elements per arrival and makes $(n+1)^{O(\varepsilon^{-2})}$ evaluations. With the whole arrival sequence known in advance, a deterministic algorithm attains the same ratio with $O(\varepsilon^{-2})$ changes per arrival. A randomized algorithm with the same short lookahead makes $O(n^2k)$ evaluations, changes $O(\varepsilon^{-2})$ elements per arrival, and attains the same ratio in expectation at each fixed time. The main tool is a greedy algorithm with an explicit guarantee for each of its partial solutions combined with each initial segment of the known future arrivals. A second tool moves between two such solutions one element at a time while keeping the value high, and the deterministic algorithm times each move using upper bounds on the optimum from failed searches.