Summary
The authors studied monotone submodular maximization under a cardinality constraint in a dynamic model where predictions of insertions and deletions are given. In submodular maximization, a ground set of elements and a function assign a value to any subset of these elements. A function is submodular if adding an element to a smaller set contributes more value than adding it to a larger set. A function is monotone if its value always increases with the set size. In the dynamic model, elements are inserted and removed, and only elements that are inserted but not deleted can be selected. The error $\eta$ is defined as the number of elements whose actual insertion or deletion time differs from the prediction by at least ww. The goal is to find, after each update, a subset of size at most k from the current elements that maximizes the value of the monotone submodular function while minimizing the number of query calls.
Previous works on dynamic monotone submodular maximization under cardinality constraints (without predictions) achieve a 1/2 approximation factor using O(polylog(n)) or O(k⋅polylog(k)) query calls. There are also works on dynamic monotone submodular maximization with predictions under matroid constraints, which is a generalization of cardinality constraints, achieving a ∼0.32 approximation factor. In this paper, the authors design an algorithm for dynamic monotone submodular maximization under cardinality constraints using predictions that achieve a 1/2 approximation factor with only $O(poly(log(\eta),log(w),log(k)))$. When the predictions are poor, the algorithm’s complexity is as bad as the algorithm without predictions, having O(polylog(n)) query complexity since $\eta$ would become $\theta(n)$.
They use precomputation to compute a solution based on predictions for each time and leverage previous works on the dynamic model and delete-robustness model to update their solution according to real insertions and deletions. They also run experiments, comparing their query complexity with the dynamic algorithm. The results show that when prediction errors are small, their algorithm requires significantly fewer query calls. However, when the predictions are poor, the query complexity is comparable to that of the dynamic algorithm.
Strengths
Recently, many learning-augmented algorithms have been developed for dynamic and online models. They are interesting because, in real applications, we sometimes have an idea of how elements will change, raising the question of how we can improve our algorithms by leveraging these predictions. In this work, the authors improved the query complexity, eliminating the dependency on n and reducing the dependency on k to only logarithmically. It is interesting how query complexity can be improved using predictions, and it would be even more interesting if the approximation factor could also be improved.
Weaknesses
There were different algorithms for this problem without using predictions: one using O(polylog(n)) (first algorithm) and the other using O(k⋅polylog(k)) (second algorithm) query calls. Since the authors' algorithm has polylog(k) in its query complexity, if k is as large as $\theta(n^\epsilon)$ where $\epsilon$ is a constant, their algorithm is not better than the first algorithm. If k is small, the second algorithm is not that bad. Still, in the second case, the authors' algorithm is slightly better, but we should note that they also have O(n⋅polylog(n)) for precomputation.
## Comments for the authors:
- Line 37: cited [30] twice
- Some sentences are too long and make it hard to read. For example, look at the sentences from lines 60 to 63, and the next sentence.
Questions
I see that you mentioned Chen and Peng [10] proved that a dynamic algorithm for this problem needs poly(n)poly(n) query complexity, but does their approach apply when we have good predictions? I understand this question may be difficult and don’t expect the authors to answer it, but if they can answer affirmatively, it makes their result much stronger.