Summary
The paper mainly studies the problem of finding a maximum weight basis in a matroid $\mathcal{M}=(E,\mathcal{I})$ using two types of independence oracles "clean" and "dirty". The clean oracle determines whether a set $S \subseteq E$ is an independent set in $\mathcal{M}$, and the dirty oracle determines independence according to another matroid $\mathcal{M}_d=(E,\mathcal{I}_d)$. The dirty oracle is free but might be imprecise for $\mathcal{M}$. For measuring the error of $\mathcal{M}_d$ with respect to $\mathcal{M}$, the parameters $\eta_A$ and $\eta_R$ are defined, which intuitively are the number of elements that have to be added to/removed from a maximum-weight basis of $\mathcal{M}_d$ to reach a maximum-weight basis of $\mathcal{M}$.
The main result of the paper is an algorithm that computes a maximum-weight basis of $\mathcal{M}$ using at most $\min (n-r+k+\eta_A \cdot (k+1)+ \eta_R \cdot (k+1) \lceil \log_2 r_d \rceil, (1+1/k)n )$ calls to the clean oracle, where $n=|E|$, $k$ is a positive integer, and $r$ and $r_d$ are the ranks of $\mathcal{M}$ and $\mathcal{M}_d$, respectively. The authors also prove lower bounds that show any deterministic algorithm should have dependencies with respect to $n$, $r$, $\eta_A$, and $\eta_B$ that are similar to those of the proposed algorithm.
Strengths
* The authors provide interesting and nontrivial upper and lower bounds for a fundamental problem.
* The two-oracle model considered, which can be viewed as a learning-augmented model, is theoretically interesting.
* The paper is well-written, and the algorithms are presented in a logical sequence that is easy to follow. The warm-up algorithms introduced in section 2 are especially helpful in facilitating understanding of the techniques and challenges.
Weaknesses
* The parameter $k$ in the main result of the paper is intuitively used to determine how much we want to trust the dirty oracle. When
$k$ is set close to 0 to heavily favor the dirty oracle, if the errors $\eta_A$ and $\eta_R$ turn out to be high, the algorithm might use $\Omega(n \log n)$ calls to the clean oracle. This significantly exceeds the calls required by the optimal worst-case algorithm without predictions, which uses $n$ calls to the clean oracle. In this sense, the algorithm is not robust.
* The results lack empirical verification. Even basic proof-of-concept experiments would be valuable to assess whether this model could be practically applicable.
Questions
* Minor remarks:
* In lines 71-73 and 86-87, the wording was initially confusing to me. I think the way these results are stated later as the minimum or maximum of two values is easier to read.
* The error measures defined in lines 375-380 can be exponential in $n$.
Limitations
The authors state their theoretical results formally, describing all assumptions.