Accelerating Matroid Optimization through Fast Imprecise Oracles
Authors: Franziska Eberle
Felix Hommelsheim
Alexander Lindermayr
Zhenwei Liu
Nicole Megow
Jens Schlöter
Venue: NeurIPS 2024 poster (2024)
Keywords: matroid optimization
weak-strong models
learning-augmented algorithms
algorithms with predictions
query minimization
robustness
Primary area: optimization
TL;DR: We study matroid basis problems in a two-oracle model, where we have access to a fast but potentially imprecise and to a slow but precise independence oracle.

Abstract: Querying complex models for precise information (e.g. traffic models, database systems, large ML models) often entails intense computations and results in long response times. Thus, weaker models which give imprecise results quickly can be advantageous, provided inaccuracies can be resolved using few queries to a stronger model. In the fundamental problem of computing a maximum-weight basis of a matroid, a well-known generalization of many combinatorial optimization problems, algorithms have access to a clean oracle to query matroid information. We additionally equip algorithms with a fast but dirty oracle. We design and analyze practical algorithms which only use few clean queries w.r.t. the quality of the dirty oracle, while maintaining robustness against arbitrarily poor dirty oracles, approaching the performance of classic algorithms for the given problem. Notably, we prove that our algorithms are, in many respects, best-possible. Further, we outline extensions to other matroid oracle types, non-free dirty oracles and other matroid problems.

Accelerating Matroid Optimization through Fast Imprecise Oracles
Franziska Eberle Technical University of Berlin Germany f. eberle@tu-berlin.de
Felix Hommelsheim
Alexander Lindermayr University of Bremen Germany
University of Bremen Germany Thommels@uni-breem
linderal Gundera@ummi-rreeen de
Zhenwei Liu University of Bremen Germany
Nicole Megow University of Bremen Germany amego=@uni-bremen de
Jens Schlöter
Centrum Wiskunde Informatica
The Netherlands
zhenwei@uni Surinireenn-eeennnneme de
jens. wwh.oter@cwii.cc.
Abstract
Querying complex models for precise information (e.g. traffic models, database systems, large MI models) often entails intense computations and results in long response times. Thus, weaker models that give imprecise results quickly can be ad- vantageous, provided inaccuracies can be resolved using few queries to stronger model. In the fundamental problem of computing a maximun-weight basis of a matroid, well-known generalization of many combinatorial optimization prob- lems, algorithms have access to clean oracle to query matroid information. We additionally equip algorithms with fast but dirty oracle. We design and ana- lyze practical algorithms that only use few clean queries w.r.t. the quality of the dirty oracle, while maintaining robustness against arbitrarily poor dirty oracles, ap- proaching the performance of classic algorithms for the given problem. Notably, we prove that our algorithms are, in many respects, best-possible. Further, we outline extensions to other matroid oracle types, non-free dirty oracles and other matroid problems.
Introduction
We study the power of awo-oracle model [1, 4, 34, 36] for fundamental matroid optimization problems, which generalize many problems in combinatorial optimization.
The two-oracle model is an emerging technique for augmenting a problem where algorithms access information via oracles. The idea is abstract from subroutines, such as Neuronal Network (NN) inference graph algorithms, which compute required information from underlying models. Al- ready today the size of such models can be arbitrarily large, and they are expected to grow further in the near future. Thus, computing precise results for each oracle query can be (too) expensive. To mitigate these costs, we assume to have access to second oracle that is less expensive but gives possibly imprecise answers. Such oracle can be an efficient heuristic to leverage this fast dirty oracle to obtain enough information in order to query the expensive clean oracle little possible. This model has been successfully applied to, e.g., clustering [4, 34), sorting [1], priority queues [5], or data labeling [36].
smaller NN. The goal is
We study this model in the context of matroid optimization. Matroids play central and unifying role in combinatorial optimization as numerous classic problems can be framed as matroid basis problems, e.g., problems in resource allocation and network design. A matroid M (E, I) is
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

downward-closed set system with certain augmentation property. It is represented by ground set E of elements and family I C 2 of independent sets, A basis an inclusion-wise maximal independent set, and all bases of matroid have the same size, which is the rank of the matroid; we give formal definitions later. prominent matroid is the graphic matroid in which, given an undirected graph, every subset of edges that induces an acyclic subgraph is independent.
Since [Z] can be exponential in n =- [E], algorithms operating on matroids are given access to oracles. The independence oracle answers for query S C E' whether S E I. Given a weight we 2 0 for every e E E, a classic goal in matroid optimization is to find a basis of M of maximum total weight. In his seminal work, Edmonds [18] showed that the greedy algorithm, which greedily adds elements in order of non-increasing weight, solves this problem using an optimal number of oracle calls, and, vice versa, that matroids are the most general downward-closed set systems for which this algorithm is correct. For graphic matroids, this greedy algorithm corresponds to the classic algorithm of Kruskal [15] for computing minimum-weight spanning tree in an edge- weighted graph, which is commonly taught in undergraduate algorithm classes.
To motivate the two-oracle model for matroid optimization, we continue with the special case of computing a minimum spanning tree in a large network. This problem arises, e.g., ensure con- nectivity in a telecommunication network or as a subroutine to approximate a cheap tour between certain points of interest in road network. Here, the elements E correspond to the edges of the network. The clean oracle for this graphic matroid has to decide whether a set of edges is cycle- free. While this doable in time linear in the query size, it can be prohibitively expensive for huge queries. However, there are several ways to design a dirty oracle of reasonable quality:
Networks, especially telecommunication networks, often evolve over time, In this case, the dirty oracle could quickly return cached results of the previous (now outdated) network.
If the network is clustered into many highly connected components that are only loosely connected each other, such as road networks are clustered around big cities, the dirty oracle can check the query for each (city) component individually. Since there may only be few highways between the cities, this can be quite close to the clean answer.
The dirty oracle could operate in a sparsified subnetwork, e.g., by restricting it to only major roads or data links.
We initiate the study of the following two-oracle model for general matroid problems: In addition to the clean oracle of a given matroid M = (E, I), an algorithm has access to fast dirty oracle. For simplicity, we assume that this oracle belongs to a matroid Ma = (E, Ia) and answers for query S whether S E Ig In fact, the former assumption is not necessary, and we will adapt our results to weaker dirty-oracle variants such as arbitrary downward-closed set systems. We emphasize that the algorithm has no knowledge about the relationship between the dirty oracle and the true matroid M. Finally, we assume for now that calling the dirty oracle free and discuss mitigations later. Since calling the dirty oracle is free, our goal is to minimize the number of clean-oracle calls required to solve the underlying matroid problem.
Our work neatly aligns with the celebrated framework of Gtarning-augmente algorithms [30], which is receiving tremendous attention [29]. Here, an algorithm has access to a groblem-speciffe prediction and yields good performance when the prediction is accurate (consistency) and does not perform too bad when given arbitrary predictions (robustess)). Ideally, the performance degrades gracefully with the prediction's 's quality, measured by an error function (smoothness). The type of performance thereby depends on the problem, and could be, e.g., a quality guarantee of the computed solution of an optimization problem, or the running time of an algorithm. The latter is intricately related to the goal of the two-oracle model: the overall running time highly depends on the number of clcan-oracle calls. From this perspective, the consistency of algorithm in the two-oracle model is the worst-case number of clean-oracle calls it uses when the dirty oracle is perfect, i.c., M MM. while the robustness is the worst-case number of clean oracles independent of the quality of the dirty oracle.
More generally, we can interpret algorithms for one model also in the other model and vice versa: On the one hand, our two-oracle model fits into the learning-augmentee considering an optimal solution w.r.t. the dirty oracle as possibly imprecisely predicted solution. On the other hand, a predicted solution B. C can used to construct the dirty oracle Ma- = setting.
algorithm framework by
(F, 2Ba). Thus, our main results are also applicable in the

---

1.1 Our results
In this paper, we design optimal algorithms in the two-oracle model for the problem of finding maximum-wen weight basis (defined later) of matroid.
1. Two-oracle algorithms: For any integer 2 1, there is an algorithm which computes a maximum-weight basis of matroid M using most
min + k + VI (k+ + 1) + nR +k+ + 1)[logg ral, (1+ )
many oracle calls to M (see Theorem 3.8).
Here, r is the rank of the matroid, i.c., the size of any basis, and ra the rank of Ma. In terms algorithms, algorithm has consistency of at most robustness of at most (1 + 1 n,. Moreover, the bound our algorithm smoothly degrades w.r.t. the quality of the dirty oracle, measured by error measures 7A and Ma (the prediction errors). Intuitively, 7A and 7R denote the number of elements that have to be added to and removed from sekiimum-weighh clean basis; give
of
+ & and
maximum- weight basis of Ma. respectively, to reach formal definition later. Our algorithm has a tuning parameter to regulate the level of robustness against dirty oracle of bad quality; beneficial feature when the quality of the dirty oracle can be roughly estimated. In Section 2, we present slightly improved bounds for the case of unit weights.
Observe that, given dirty oracle of reasonable quality, our algorithm significantly improves upon the greedy algorithm whenever the rank r is not too small (due to the dependence on n r), which is always the case for, e.g.. graphic matroids in sparse networks like road or telecommunication networks. We further show that this dependence is best possible for any deterministic algorithm for any rank Moreover, our algorithm is optimal w.r.t. to the dependence 1A and ma:
2. Tight lower bounds: For every rank every deterministic algorithm requires at least n--r- - + 7) and at least r 7) flog, ral clean-oracle calls to compute basis a matroid (Appendix B).
Yet we present an algorithm which bypasses the dependence on n n--rb by leveraging the slightly more powerful clean rank oracle (see Section 4.1 for the definition). Note that any algorithm requires at least n clean rank oracle calls in the traditional setting for this problem in the worst case.
3. Rank oracles: There is an algorithm which computes basis of matroid M using at most 2 nA [loga (n [ + n [log2 T'dl and at most n+1 1 calls to the rank oracle of M (Section 4.1).
Finally, we initiate the study of extensions, with which we hope to foster future research.
4. Costly oracles: In this model, every dirty-oracle call incurs cost I, and every clean-oracle call costs > 1. We are interested in minimizing the total cost. We illustrate that this model requires new algorithmic techniques compared our main setting (see Section 4.2).
5. Matroid intersection:
We give two different approaches on how our techniques can be incor- porated in textbook algorithms for reducing the number of clean-oracle calls in the fundamental matroid intersection problem using dirty oracles (see Section 4.3).
All omitted proofs are deferred to the appendix.
1.2 Further related work
Noisy oracles, two-oracle model, imprecise predictions. Optimization in the presence of im- precise oracles is a fundamental problem and has been studied extensively, also for submodular optimization [25, 26, 27, 28, 35], which is connected to matroid optimization via the submodular- ity of rank functions. The majority of previous work assumes access only to a single noisy oracle, where the noise usually is of stochastic nature. Only recently, a two-oracle model as in our work has been studied from a theoretical perspective. Bai and Coester [1] consider sorting with a clean and dirty comparison operator. They minimize the number of clean-compaaison-oprraaaee give guarantees that smoothly degrade with the number of wrong dirty-comparison answers. Similar strong and weak oracles have also been considered by Bateni et al. [4] for the Minimum Spanning
calls and
3

---

Tree problem and clustering, and by Benomar and Coester [5] in the context of priority queues. In contrast to our model, they consider oracles for accessing the distance between two points and not for deciding cycle freeness (graphic matroid). Besides these explicit results on two-oracle models, explorable uncertainty with predictions [20, 21] can also interpreted as such model.
Two- and multistage problems. All algorithms presented in this paper also solve the following two-stage problem: Given maximum- weight basis Ba for first-stage matroid Ma (dirty matroid), compute a maximum-weight basis B for a second stage matroid M (clean matroid) with minimum [B4 where B denotes the symmetric difference of Ba and B, and minimize the number of oracle calls to M. Two- (or multi-) stage problems of this type have been studied extensively, mostly for graph problems [2, 3. 12, 13, 19. 22, 23, 33] but also for matroids [8, 9, 14, 24]. Most of these works consider a combined objective optimizing the quality of the second stage solution and the distance between the first- and second-stage solutions. contrast, we insist on an optimal second- stage solution and minimize the number of clean-oracle calls. Furthermore, to our knowledge, all previous work on matroid problems in these models assumes that the matroid stays the same for all stages but the weights of the elements change, whereas we assume the opposite. Blikstad et al. [7] consider the somewhat similar problem of dynamically maintaining a basis of a matroid, but in a different oracle model.
1.3 Preliminaries
Matroids. A matroid M a tuple/ E, I) consisting of a finite ground set E of n elements and a family of independent sets I C 2 with 0 E I that satisfy the following properties: (i) I is downward-clle cloose,, i.c., A E I implies B E I for all B C A and (ii) if A, B E I with |A| > [B] then there exists E A \ B s.t. B + and X - e when we remove e E X from X S E.) An important notion are bases, which are the (inclusion-wise) maximal elements of I: for fixed matroid, we denote the set of bases by B. For a dirty matroid Ma. we refer to the set of bases by Ba- A circuit is a minimal dependent set of elements. The main results of this paper consider the problem of finding maximum weight basis, ie., given matroid M = (E,I) and weights we for all e E E, the goal is to find a basis B E B maximizing Ecer We- The greedy algoritmm solves this problem by iteratively adding elements in non-increasing order of their weight to the solution if possible, i.e., if the solution stays independent in M [18]. Given a weighted ground set, we always assume that the elements of F = {ei,-..; Cn) are indexed according to the weight order, i.c., i S j implies We, 2 Wey, with ties broken arbitrarily. Given that, for any i and S S E we define Sg: = {ez E S J S i} (Szi analogously).
I. (We write X + E when we add
E X to X C E
Requirements on algorithms and optimal solutions. For all considered problems, we require algorithms to execute clean queries (oracle calls) until the answers to these queries reveal sufficient information to solve the given problem, e.g., find a maximum-weight basis for the clean matroid. More precisely, the queries executed by the algorithon algorithm together with the answers must be a certificate that a third party with only access to the clean matroid and without any additional knowledge can use in order to find a provable solution. In particular, an optimal algorithm that knows the answers to all clean queries upfront has to execute queries in order to satisfy the certificate requirement.
We refer to the robustness of an algorithm, when bounding the maximum number of clean-oracle calls the algorithm needs for any input instance, independently of the quality of the dirty oracle.
Definition of our error measure. We define error measure that quantifies the quality of the dirty oracle w.r.t. the clean oracle. We define the error measure for the case that the dirty oracle is a matroid and describe in the next section how this extends to arbitrary downward-closed
systems. Let 8 be the set of maximum-weight bases of M and BY be the set of maximum-weigh bases of Ma. (In the unweighted case, B B and B3 = Ba.) We first define for every S B2 the sets A(S), R(S) as any cardinality-wise smallest set A C EXS and R C S, respectively, such that SUAD B and S R B' for some B, B' E B
These sets describe the smallest number of additions/removals necessary to transform S into a su- perset/subset of some maximum- distance from S to B Our final error measure is defined as the largest modification distance of any weiit basis of Ma. that is, ?A maxses; [A(S) and πjR maxses; R[S)).
basis of M. We call [A(S)] + R(S) the modification
Assume both oracles are matroids. follows from standard matroid properties that, for any dirty basis Bg, there are modification sets A, R with |A| = IA(Ba). R = RR (2)) and B& RU A E B.

---

Hence r Fd 7AA 77.- Also, for all S1, E Ba. IA(S)) - [A(S)) if and only if (R(S1)] = [R(S))].
1.4 Discussion of the model
Computing a dirty basis upfront. For all our results on computing a (maximun-weight basis, it suffices to first compute imaximum-weight dirty basis and afterwards switch exclusively using the clean oracle. A similar observation can be made for the results of Bai and Coester [1] on sorting, where would possible to initially compute a tournament graph for the dirty comparator and afterwards switch to only using the clean comparator without increasing the number of clean- comparator calls. In Section 4, we observe that separating the usage the dirty and clean oracles in this way does not work anymore if dirty- calls also incur costs.
Counting wrong answers as error measure. Bai and Coester [1] use the number of wrong dirty- comparator answers as error measure. While this is meaningful error measure for sorting, a similar error measure for our problem does not seem accurately capture the quality of the dirty oracle. Consider an instance with unit weights, where we have Ba C B. This can lead to an exponential number of wrong dirty oracle answers, but the dirty oracle still allows us to compute a clean basis. For this reason, we use the modification distance error measure instead.
Relaxing requirements on the dirty oracle. We illustrate how to extend the error definition of Sec- tion 1.3 to arbitrary downward-cled -closed set systems in the unweighted case: For every inclusion-we seslssio-wwise maximal set S of the dirty oracle we compute A(S) and R(S) as before. The addition and removal стror are then defined analogously by replacing B with the set of all inclusion- maximal inde- pendent sets (instead of all maximum sets in the unweighted case). Then, all our results in this paper also carry over to this more general setting. Using an error definition with respect to some greedy al- gorithm on weighted downward-closed set systems, one can also obtain the same result for arbitrary weighted downward-clen -lloeed set systems. However, for clarity, we only prove our statements for the case that the dirty oracle is matroid.
1.5 Organization of the paper
We begin in Section 2 with gentle introduction to our techniques and algorithms by studying the simpler problem of computing any basis a matroid. Then, we extend these ideas in Section 3 and present our main algorithmic results. Finally, in Section 4, we demonstrate how to generalize and adapt our approach to other settings and problems. Many proofs for these sections are deferred to the appendix. In Appendix B, also included detailed section our lower bounds.
2 Warm-up: computing an unweighted basis
The goal of this section is to give a gentle introduction to our algorithmic methods, which we extend in the next sections. Consider the basic problem of finding any basis of matroid. Note that without the dirty oracle, we need exactly n elean-orack, calls find and verify any basis in the worst-case.
In the following, we assume that we are given an arbitrary basis Ba of the dirty matroid Ma. which can be computed without any call to the clean oracle. We first analyze the so-called simple algorithm: If Ba E I, we set B to By- Otherwise, we set B to the empty set. Next, for each element e E E B, we add it to B if B + I and output B at the end.
The idea of the simple algorithm to only use the dirty basis Ba is independent the clean matroid, we then can easily augment it to clean basis. Otherwise, we abandon it and effectively run the classic greedy algorithm. Formalizing this sketch proves the following lemma.
Lemma 2.1. The simple algorithm computes a clean basis using at most n + clean-oracle calls. Further, if Ba E B, it terminates using at most n + clean- oracle calls.
Surprisingly, in Appendix B, we will see that this simple algorithm achieves a best-possible trade-off between optimizing the cases Ba E B and Bg & B at the same time.
5

---

2.1 An error-dependent algorithm
The simple algorithm discards the dirty basis Ba if it is not independent in M. This approach may be wasteful, especially if removing just one element from Ba, such as in the case of a circuit, leads independence. This seems particularly drastic if the clean and dirty oracle are relatively "close", i.e., the error measured by the modification distance is small. This suggests a refinement with a more careful treatment of the dirty basis Ba- We propose a binary search strategy to remove elements from Ba until it becomes independent. A key feature is that this allows for an error- dependent performance guarantee bounding the number of claan-oracle calls by TA and MR. the smallest numbers of elements to be added and removed to turn a dirty basis into a basis of the clean matroid.
We define the error-dependent algorithum: First, set B to Ba and fix an order of the elements in B. Repeatedly use binary search find the smallest index s.t. Bei & I and remove e; from B until B E I. Then add each element e E E' \ Bg to B if B + e E I and output the final set B.
Lemma 2.2. The error-dependent algorithm computes a clean basis using at most ni - r ++++++ MR
[loggra ra] clean-orucle calls.
Proof. The algorithm simulates finding a maximal independent subset of Ba w.r.t. the clean ma- troid, and augments the resulting set to clean basis. Hence, the correctness follows from matroid properties. We remove [R(Ba)] S mR elements from Ba. Hence, the removal loop is executed (R(Ba) times. In each iteration, we use most 1 + [log2 ral clean queries (one for checking B E and at most [log, ra] for the binary search). Thus, the removing process uses at most [R( + flog2 ral) clean queries. Augmenting B uses algorithm uses at most (R(Ba)((1 + [log2 ral) + n Ta + 1 oracle calls. We conclude using (a) S nn and ra AJ + ?A.-
ra clean queries. Combined, our
2.2 An error-dependent and robust algorithm
The error-dependen algorithm has a good bound on the number of clean- oracle calls (less than n) when 7l and !JR are small. However, in terms of robusiness-i.e. the maximum number of oracle calls for any instance, regardless of the dirty-oracle quality-this algorithm performs asymptotically worse than the gold standard achieved by the classic greedy algorithm. This is the case when the dirty basis is equal to E, but the clean matroid is empty: the error-dependent algorithm executes n binary searches over narrowing intervals, using logz log,(n!) O(n log n) clcan-oracle calls. By look- ing closer at the crror-dependent algorithm, the special structure of this example can be explained + ΠA are essentially also done by the greedy algorithm. Hence,
because queries charged to they are in a sense already robust. Motivated by the greedy algorithm, another extreme variant of the removal process would be go linearly through B, and greedily remove elements. This gives an optimal robustness, but is clearly bad if n is small.
For our main result in the unweighted setting, we combine both extremes into a robustification framework and achieve a trade-off using the following key observation. we have to remove many elements (π8 is large), some elements must be close to each other. In particular, if the next removal is close to the last one (in terms of the fixed total order), a linear search costs less than a binary search. Based on this, after removal, we first check the next (log(Ta)) elements of Ba linearly for other removals before executing a binary search. This bounds the number of binary searches by O (og(ta)) ). each incurring cost of [log2(ra)]. However, the linear search also incurs some cost. Thus, we further parameterize this idea (see Algorithm 3), and obtain the following main result.
Theorem 2.3. For every k E N4, there is an algorithm that, given dirty matroid Ma of rank ra with unknown TJл and nn, computes a basis of a matroid M of rank r with at most min(n - r + k MI + nn (k- + 1)[lo ra]. (1 + 1
& )m oracle calls to M.
3 Computing a maximum-weight basis
Consider the weighted setting. Recall that Bi and B* denote the sets of maximum-weight bases of the dirty and clean matroid, respectively. We assume that we are given maximum-weigh basis Bg E By. which can be computed without any clean-oracle calls. The main difficulty compared to the unweighted setting is as follows: In the unweighted setting, the error-dependent algorithm first

---

2. add
1. remove
2. add
3. remove 4. add 1. remove
C4
e5
c
e
e1
22
e3
64
C6
e7
es
6g
(a) Modification to an arbitrary clean basis.
(b) Modification to a maximum-weight weightt clean ba- sis. Adding ez is necessary for its high weight. Element es is only blocking after adding to Ba ca. hence cannot be detected earlier.
Figure I: A matroid with elements e (displayed as circles) ordered left-to-right by non- increasing weight. The elements of the maximum-weige dirty basis Bd are filled.
computes an arbitrary maximal independent set B' C Ba and then easily augments B' to a clean basis. In the weighted setting, however, there clearly can be independent sets B' S Ba that are not part of any maximum-weight basis; hence we need to be more careful. Finding such a special independent subset of Ba only by removing elements from Ba and testing its independence seems difficult: Ba itself could be independent, but not part of any maximum-weet weight basis. However, even in this case, Ba can be very close to a maximum- -weggtt basis w.r.t. VIA and 77- Therefore, we cannot avoid carefully modifying Ba since strategies like the greedy algorithm would use too many queries.
Thus, we alternatingly add and remove elements to and from Ba. Intuitively, we want to ensure, as the greedy algorithm, that we do not miss adding elements with large weight. Thus, we try to add them as soon as possible. However, even if they are part of every basis in 8", this might result in dependent current solution unless we now remove elements, which were not detectable before. An example of such situation is given in Figure 1. This observation rules out simple two-stage algorithms as used the unweighted case.
We now present our algorithm. Its full description is shown in Algorithm 1. Given elements F. = (ei..... } in non-decreasing order of their weight, maintains a preliminary solution, which initially is set to the dirty basis Bg. It modifies this solution over n iterations and tracks modifications in the variable sets A C E E (added elements) and R C Ba (removed elements). In every iteration f, the algorithm selects elements to add and remove such that at the end of iteration é its preliminary solution (Ba) R) A satisfies two properties, which we define and motivate now.
Property (i) requires that the preliminary solution (Ba \ R) U A up to e, should be a maximal subset of some maximum-weight basis. For the sake of convenience, we introduce the matroid M = (E, ),,, where I" is the set of all subsets of B". Then, we can use the following definition.
Definition 3.1. A set S is k-safe if Sek E I and for every e E Ega \Sex it holds that S e & I".
In other words, set k--afe if a basis of the truncated matroid of the kth prefix of E. Using this definition, Property (i) requires that at the end of iteration É, the current solution (Ba \, R) U A is E-safe. Establishing this property in every iteration will give us that the final solution is n-safe, and, thus, maximum weight basis of M. This works because the algorithm does not modify its solution for the εth prefix of E after the εth iteration.
To establish Property (i) after every iteration without using too many clean queries, it also maintains Property (di): at the end of every iteration the current solution is independent, i.e., (Ba) \ R) UA e I.
We now give some intuition on how our algorithm achieves this. Initially, say for E = 0, before Line 2 Property (i) is fulfilled trivially. For Property (ii), before Line the algorithm greedily adds weight elements of Bg to R that close a circuit in the smallest prefix of (B, \ R? U A (Lines 2-4). This subroutine can be implemented via binary search. To guarantee both properties at the end of iteration f, first observe that Property (ii) holds as long as A and R have not changed in this iteration. However, this might be necessary to establish Property (i). Intuitively, our algorithm wants to act like the classic greedy algorithm to ensure Ê-safeness. Thus, it checks whether e, should be in the solution by considering its solution for Ege. Clearly, if e E Ba \ R or e E R, there is nothing to modify (Line 6), because the current solution is independent due to Property (ii) for the previous iteration. Similarly, if ez & B, and the current solution for Esg together with es is independent, we add e, to our solution (Lines 6-7). However, by adding element, Property (ii) can become false due to an introduced circuit, which we have to break (Lines 8-10). Finally, there might be the situation that eg E Bg has been added to R in an earlier iteration, so E R. In this
7

---

Algorithm 1: Find a wexxighu--wigghh basis
Input: dirty basis Ba F., matroid M (F, Z)
A <- 0: R t- 0 (added removed )
2 while (Ba] \ R) UUA & do
Find the smallest index i s.t. ((Ba) R) ( A) $ I via binary search
R R e;
for L f 1 t0 do
ee & Ba and ((Ba), R)UA+ ei) E then
A +te eg
if Ba \ R) UAA & I then
Find the smallest index i s.t. ((Ba) \ R) U A) $ I via binary search
10
R + R +
return (Ba) ARRAAA
case, clearly do not want to even consider adding ey again, queries for verifying this addition cannot be bounded by our error measure. Indeed, removing and re-adding an element cannot be part of any minimal modification distance. Thus, our algorithm skips such elements (Line 6). To justify this, we prove that removing element is always necessary, in the sense that there always is a circuit that eg breaks and that cannot be broken by removing elements in later iterations by Lines 8-10. This follows from classic matroid properties for circuits. Formally, we prove in Appendix C:
Lemma 3.2 (Property (ii)). At the start (end) of each iteration of Line 5, it holds (Ba (R)
Lemma 3.3 (Property (i)). At the end of every iteration of Line 5, (Ba \ R) U A is E-safe.
Since there are at most elements in R, the algorithm clearly terminates, and we conclude as fol- lows.
Corollary 3.4. Algorithm I terminates with n-safe set.
remains to bound the number of clean queries. Fix A and R to their final sets. Assume that elements non-increasingly ordered by their weight; among elements of equal weight, elements of Bd come before elements of E Ba. For such an ordering, the algorithm modifies Ba to a closest basis of 1
Lemma 3.5. It holds that |A| S Пa and | nn-
To conclude, we use charging scheme and Lemma 3.5 derive the following bound; for details, we refer to Appendix C.
Lemma 3.6. Algorithm computes a max-weight basis with at most n n-r+1+21a + (ra)) clean queries.
We complement this algorithmic result by a lower bound. It proves that our error-dependent guaran- tees in the unweighted case are not possible in the weighted case. Hence, it separates both settings.
Lemma 3.7. Every deterministic algorithm for finding maximum-weight basis executes strictly more than n r + 1)A + 1R [logg(ra)] + clean-oracle calls in the worst-case.
Application of the robustification framework. As in the unweighted case, our algorithm may perform poorly when the dirty oracle is of low quality, i.c., 1J and are large. We extend the ideas for robustifying the error-dependent algorithm (cf. Section 2.2) and combine them with the concepts developed above. The key idea for robustifying Algorithm 1 is to start a binary search only after a sufficient number of linear search steps. However, as observed above (cf. Figure 1), we cannot remove all blocking elements in one iteration. While the simple argument that the linear search partitions B2 still holds, does not cover total removal cost, because later addition can create removal at a previously checked position. To overcome this, we observe that in Algorithm 1, immediate removal of every detected element from the current solution is not necessary; we just need to decide whether in iteration element e, should be part of the solution.

---

Algorithm 2: Find a maximum-weight basis (robustified)
Input: dirty basis Ba, matroid [F, integer
A < 0: R t 0; dmax <- m
2 q < 0; LS <- true {linear search counter / flag)
for l 1 to do
er & Ba then if ((Ba \ (R) E I then A+ A ex and LS +- true
else if Ba RR R and LS = true then
g + q ++111111
if (BB \ RjU A) <e $ I then R R+ and
if L dmax or (q
and (Ba) \ RRRACC I) then q k and LS false
10
else if k[log2 ral then
11
Find the smallest index i s.t. ((B,) RR) g) $ I via binary search
12
R + R + e and q +-
13
return (Ba RUUA
In our robustified algorithm (Algorithm 2) we exploit this as follows. While in Algorithm we linearly check prefixes of E Ba for additions, we now linearly check prefixes of E for additions (Lines 4-5) and removals (Lines 6-8). However, for the sake of good error-dependency. we count these removal checks (cf. increment counter in Line 7) and execute binary search only if we checked enough elements B₃ linearly (Lines 10-12). Then, we can again bound the total cost for the binary searches using density argument. Whenever we remove an element, we charge the previous cost of the linear searches to this removal error and reset q, which ce-activates the linear search. However, if the current solution is already independent, do not want to search for removal errors at all (cf. Lines 2 and in Algorithm 1). Unfortunately. doing such a check after every addition and removal already rules out robustness close n. Thus, slightly delay this check w.r.t. the counter q, and stop the removal search accordingly (Line 9). Finally, whenever an element added, make sure that the linear search is running that we start it again (Line 5), as new circuit could have been introduced in our solution. Formalizing this sketch proves our main theorem.
Theorem 3.8. For any E N4, there is an algorithm that, given a dirty matroid Ma of rank va with unknown AJa and qjs computes a maximum- basis of a matroid M of rank with at most min r + AA (k 1) + qn (k + 1) [log ral, (1 + {) oracle calls to M.
4
Extensions and future work
4.1 Rank oracles
Another common type of matroid oracles is the rank oracle: Given any S C E, a rank oracle returns the cardinality of maximum independent contained S, denoted by r(S). Since r(S) |S| if and only if S E I, our algorithmic results for independence oracles directly transfer. Moreover, for the unweighted setting, we can even reduce the number of oracle calls using rank oracle, implying that some lower bounds do not translate. For example, given B₃ can compute its rank r (Ba) to obtain 7e = Ba - r (Ba) and decide whether to remove elements via binary search or immediately switch to the greedy algorithm. Further, can improve the dependency on 77. if 7) is small can find the elements to be added via binary search. Hence, we get the following result.
Proposition 4.1. There is an algorithm that computes clean basis with most min {n 1,2 ? [lgg ral min {ЛΛ [Tog2(n ra)l; n - -ra] clean rank-oracle calls.
The full discussion
rank oracles can be found in the appendix. For future work it would be interesting to see if the error-dependency and the worst-case bound can be improved, and if rank oracles can be used to improve the results for the weighted setting.

---

4.2 Dirty independence oracle with cost
We consider the generalized setting where a dirty-oracle call has cost and a clean-orach call has cost > 1 with the objective to minimize the total cost. Lemma B.1 translates to this setting, giving a lower bound p(n r + 1). Note that the previous results assume that p > in this setup.
The main takeaway of this generalization is that it can be beneficial for an algorithm to delay dirty- oracle calls for clean-oracle calls, depending on p and This contrasts the previous sections, where we can meet lower bounds by computing a dirty basis upfront.
To see this, we consider two algorithms and assume for simplicity that Ma M. The first algo- rithm starts with E and removes elements via binary search until it reaches an independent set. only uses clean-orack, calls of total cost p(n - r) [log2 (n)] p. The second algorithm computes a dirty basis and verifies it, incurring a total cost of n + p(n - r + 1). as Ma = -M. Thus, for small p and large r, the first algorithm incurs less cost than the second algorithm, which is optimal among the class of algorithms which only initially use dirty- calls. Specifically, having access to rank oracles, one can compute the value of upfront using one clean-oracle call and, thus, select the better algorithm.
4.3 Matroid intersection
In the matroid intersection problem, we are given two matroids M = (E,I) ()) and 2 = I9), and we seek a maximum set of elements X S E that is independent in both matroids, i.c., X E I' nIa
The textbook algorithm for finding such a maximum independent set is to iteratively increase the size of a solution one by one using an augmenting path type algorithm until no further improvement possible. This algorithm has a running time of O(r²n) [17]. There are faster algorithms known for matroid intersection, which run in time (nr3//4) [6] and in time O(n ++(()) for the special case of two partition matroids [11]. (In partition matroid M = (E, I), the elements are partitioned into classes C2 with capacities k, and a set C E independent
and only if IC; n S| S k; holds for each C..) Here, we focus on improving the running time of the simple textbook algorithm by (i) using dirty oracles calls in each of the augmentation steps and (ii) by computing a warm-start solution using an optimal dirty solution, i.e. feasible solution of certain size dependent on the error.
Matroid intersection via augmenting paths. Our error measure is as follows: We define 7/2 (F E I F & I'} and nh2 = {F E I3 F & I to be the number of different sets which are independent in the dirty matroid but not independent in the clean matroid. In order to simplify the setting, we assume here that (i) the dirty matroids are supersets of the clean matroids, i.e., I2 C Z] and I C Iz. and (ii) that the clean matroids are partition matroids. We note that in general the intersection of two partition matroids can be reduced to finding a maximum b b-matching.
Proposition 4.2. There is an algorithm that computes an optimum solution for matroid intersection using most (r 1) (2 + (m + 112) ([ogg(n)] 2)) clean-oracle calls.
Matroid intersection via warm-starting. We show how to exploit the dirty matroids to obtain a good starting solution that independent both clean matroids. The idea of warm-starting using predictions has been used for other prediction models in [10, 16, 31] for problems like weighted bipartite matching or weighted matroid intersection. These results are tailored to the weighted setting and do not directly translate to improvements in the unweighted case. As етror measure we adjust the removal error for matroid intersection: Let S = maxx, [Sal and define S = (Sa E IA n Z2 |Sal = si} to be the set of optimum solutions to the dirty matroid in- tersection problem. We define 7/- maxs,es; ming,ericze {|Sa \ Scl S. C Sz).
Our algorithm computes an optimal solution to the dirty matroid, then greedily removes elements until obtain feasible solution for the clean matroid. By observing that this reverse greedy algorithm is a 2- 2-approximation in the number of elements to be removed, T/. we obtain the follow- ing result.
Proposition 4.3. There is algorithm that computes feasible solution Sy E It n of size |S 2 8 - 22,, using at most 2 + 2n,, (1+ [n)g) clean-oracle calls.
10

---

Acknowledgments and Disclosure of Funding
We thank Kevin Schewior for initial discussions the topie of this paper.
This research is supported by the German Research Foundation (DFG) through grant no. 517912373 and by the University of Bremen with the 2023 Award for Outstanding Doctoral Supervision. Further, the first author is funded by the Deutsche Forschungsgemeinschaatt (DFG, German Re- search Foundation) under Germany's Excellence Strategy The Berlin Mathematics Research Center MATH+ (EXC-2046/1, project ID: 390685689).
References
[1]
Xingjian Bai and Christian Coester. Sorting with Predictions. In: NeurIPS. 2023.
[2] Evripidis Bampis, Bruno Escoffier, Michael Lampis, and Vangelis Th. Paschos. Multistage Matchings. In: SWAT. Vol. 101. LIPles. Schloss Dagstuhl- Leibnniz-Zentrum für Informatik, 2018, 7:1-7:13.
[3] Evripidis Bampis, Bruno Escoffier, Kevin Schewior, and Alexandre Teiller. Online Multistage Subset Maximization Problems. In: Algorithmica 83.8 (2021), pp. 2374-2399.
[4] MohammadHossein Bateni, Prathamesh Dharangutte, Rajesh Jayaram, and Chen Wang. Met- ric Clustering and MST with Strong and Weak Distance Oracles. In: COLT. Vol. 247. Pro- ceedings of Machine Learning Research. PMLR, 2024, pp. 498-58 5500.
[5] Ziyad Benomar and Christian Coester. Learning-Augmentie Priority Queues, In: CoRR 04422406.04793 (2024).
[6] Joakim Blikstad. Breaking O(nr) for Matroid Intersection. In: ICALP. Vol. 198. LIPIcs. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2021, 31:1-31:17.
[7] Joakim Blikstad, Sagnik Mukhopadhyay, Danupon Nanongkai, and Ta-Wei Tu. Fast Algo- rithms via Dynamic-Orade Matroids. In: STOC. ACM, 2023, pp. 1229-1242.
[8] Niv Buchbinder, Shahar Chen, and Joseph Naor. Competitive Analysis via Regularization. In: SODA. SIAM, 2014, pp. 436-444.
[9] Niv Buchbinder, Shahar Chen, Joseph Naor, and Ohad Shamir. Unified Algorithms for Online Learning and Competitive Analysis. In: COLT. Vol. 23. JMLR Proceedings. JMI..org, 2012, pp. 5.1-5.18.
[10] Justin Y. Chen, Sandeep Silwal, Ali Vakilian, and Fred Zhang. Faster Fundamental Graph Algorithms via Learned Predictions. In: ICML. Vol. 162. Proceedings of Machine Learning Research. PMLR, 2022, pp. 3583-3602.
[11] Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum Flow and Minimum-Cost Flow in Almost-Linear Time. In: FOCS. IEEE, 2022, pp. 612-623.
[12] Markus Chimani, Niklas Troost, and Tilo Wiedera, Approximating Multistage Matching Prob- lems. In: Algorithmica 84.8 (2022), pp. 2135-2153.
[13] Markus Chimani, Niklas Troost, and Tilo Wiedera. A general approximation for multi- stage subgraph problems. In: LAGOS. Vol. 223. Procedia Computer Science. Elsevier, 2023,
pp. 334-342
[14] Edith Cohen, Graham Cormode, Nick G. Duffield, and Carsten Lund. the Tradeoff be- tween Stability and Fit. In: ACM Trans. Algorithms 13.1 (2016), 7:1-7:24.
[15] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. fourth. MIT Press, 2022.
[16] Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Faster Matchings via Learned Duals. In: NeurlPS. 2021, pp. 10393-10406.
[17] Jack Edmonds. Submodular functions, matroids, and certain polyhedra, combinatorial struc- tures and their applications, R. Guy, H. Hanani, N. Sauer, and J. Schonheim, eds. In: New York (1970), pp. 69-87.
[18] Jack Edmonds. Matroids and the greedy algorithm. In: Math. Program. 1.1 (1971), pp. 127-
136.
[19] David Eisenstat, Claire Mathieu, and Nicolas Schabanel. Facility Location in Evolving Met- rics. In: ICALP (2). Vol. 8573. Lecture Notes in Computer Science. Springer, 2014, pp. 459-
470.
11

---

[20] Thomas Erlebach, Murilo S. de Lima, Nicole Megow, and Jens Schlöter. Sorting and Hyper- graph Orientation under Uncertainty with Predictions. In: IJCAI. ijeai.org, 2023, pp. 5577- 5585.
[21] Thomas Erlebach, Murilo Santos de Lima, Nicole Megow, and Jens Schlöter. Learning- Augmented Query Policies for Minimum Spanning Tree with Uncertainty. In: ESA. Vol. 244.
LIPlcs. Schloss Dagstuhl Leibniz-Zentrrmm für Informatik, 2022, 49:1-49:18.
[22]
Till Fluschnik, Rolf Niedermeier, Carsten Schubert, and Philipp Zschoche. Multistage s-t Path: Confronting Similarity with Dissimilarity in Temporal Graphs. In: ISAAC. Vol. 181.
LIPlcs. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2020, 43:1 43:1-43:16.
[23] Dimitris Fotakis, Loukas Kavouras, and Lydia Zakynthinou. Online Facility Location in Evolving Metrics. In: Algorithms 14.3 (2021), p. 73.
[24]
Anupam Gupta, Kunal Talwar, and Udi Wieder. Changing Bases: Multistage Optimization for Matroids and Matchings. In: ICALP (1). Vol. 8572. Lecture Notes in Computer Science. Springer, 2014, pp. 563-575.
[25] Avinatan Hassidim and Yaron Singer. Submodular Optimization under Noise. In: COLT.
Vol. 65. Proceedings of Machine Learning Research. PMLR, 2017, pp. 1069-1122.
[26] Elad Hazan and Satyen Kale. Online submodular minimization. In: J. Mach. Learn. Res. 13 (2012), pp. 2903-2922.
[27] Lingxiao Huang, Yuyi Wang, Chunxue Yang, and Huanjian Zhou. Efficient Submodular Op-
timization under Noise: Local Search is Robust. In: NeurIPS. 2022.
[28] Shinji Ito. Submodular Function Minimization with Noisy Evaluation Oracle. In: NeurIPS.
2019. pp. 12080-12090.
[29] Alexander Lindermayr and Nicole Megow. Repository of papers on algorithms with predic- tions. http: / alllarl aagorrthtswwitthe tetth-preiiciions www.iiiiiiinnnuubbb.oee.ee io/ [Accessed: (October 21, 2024)]. 2024.
[30] Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with Predictions. In: Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press, 2020, pp. 646-662.
[31] Shinsaku Sakaue and Taihei Oki.
-Bssed Framework for Warm- Starting Algorithms with Predictions. In: NeurlPS. 2022.
[32] Alexander Schrijver. Combinatorial Optimization Polyhedra and Efficiency. Algorithms and Combinatories. Springer, 2003.
[33] Hadas Shachnai, Gal Tamir, and Tami Tamir. A Theory and Algorithms for Combinatorial Reoptimization. In: LATIN. Vol. 7256. Lecture Notes in Computer Science. Springer, 2012, pp. 618-630.
[34] Sandeep Silwal, Sara Ahmadian, Andrew Nystrom, Andrew McCallum, Deepak Ramachan- dran, and Seyed Mehran Kazemi. KwikBucks: Correlation Clustering with Cheap-Weak and Expensive-Strong Signals. In: ICLR. OpenReview.net, 2023.
[35] Yaron Singer and Avinatan Hassidim. Optimization for Approximate Submodularity. In: NeurIPS. 2018, pp. 394-405.
[36] Chicheng Zhang and Kamalika Chaudhuri. Active Learning from Weak and Strong Labelers.
In: NIPS. 2015, pp. 703-711.
12

---

Appendix
A Proofs omitted from Section
A.1 Proof of Lemma
Lemma 2.1. The simple algorithm computes clean basis using + 1 clean-oracle calls. Further, if Ba E B. it terminates using at most n r + Alean-oracle calls.
Proof. The correctness follows easily from matroid properties. If the dirty oracle is perfectly correct, i.c. Ba E B, then we only need to use one clean-oracle call check whether Ba and n n- calls for checking the maximality. If Ba & Z, we start from the empty set and check whether to add each of the elements. Thus, the algorithm uses at most + clean-oracle calls in any case.
A.2 Proofs omitted from Section 2.2
give the formal description of the algorithm discussed Section 2.2 Algorithm
Algorithm 3: Find a basis (robustified)
Input: dirty basis Ba, matroid M (E, I), integer B 4 0 and S + Bu
Fix an order for S (ei,...,eral
3 while S * 9 do Re-index the elements in from 1 to [S], keeping the relative order Find the smallest index i E mi....,.ii(])]) h 1}} with B U Sgs & I via linear search such an exists then
L B - BUS. Sci-1 and 8 S
S Sgg and go to next iteration of Line 3.
B USSUEE then if ir 2 and S + and go to next iteration of Line
L
Find the smallest index (k....,min fin [logz ral, [S]}} with B U Sgg I via linear search
if there is no such index then Find the smallest index i E {k[log2 ral + 1,..., |S|} with U U.g $ I via binary search (guaranteed exist)
12
13
B
BUS and S S Sex
14
for E E B, do
B I then
16
B - B +
return B
This algorithm is essentially the same the error-dependent algorithm from Section 2.1 but uses a robust way of finding removals. The parameter i measures the trade-off between linear searches and binary searches. Note that each linear search has two parts (Line 5 and Line 10). Between the two parts, we insert a check B UUS U E (Line 8), which is necessary to prevent using too many queries when there this check if there actually are elements to check in the second part.
further removals necessary. small detail here is that we only have to do
Theorem 2.3. For every k N4, there is an algorithm that, given dirty matroid Ma of rank ra with unknown TJA and TJR, computes a basis a matroid M of rank with at most min r + MA + TR (k + log, Tal. (1 + _ mm oracle calls to M.
Proof. We analyze Algorithm 3. Observe that the algorithm finds maximal independent subset of Ba the clean matroid and greedily tries to add remaining elements, similar to the error- dependent algorithm. Hence, the conrectness follows in the proof of Lemma 2.2.
13

---

It remains to bound the number of creale calls. We first prove the error-dependent upper bound. Note that the algorithm removes (R) I T7 elements from B,. and then adds [A(B,)] < пл elements. For every removed element, the algorithm uses at most k 6eoog2 r'dl clean-oracle calls due to the two linear searches, [log2 ra] calls in the binary search, and one extra query for the check between the two linear searches. Once we have a solution B U S that is not necessarily maximum but feasible, which we do not know yet, we need to use at most & additional queries until we verify that this solution is indeed feasible: We have up to k queries of linear search in Line 5 and one query in Line After removing elements, the algorithm makes n - ra queries in Line 15, Thus, the total number of clean-oracle calls is most R Ba) ((: + 1) [log ral + + Td- By plugging in rd
7R + 7A = r, we proof the stated upper bound of
n
+ 7 + na 1) [ogg ra]-
Second, prove the robust upper bound that is independent of 14 and 77. To this end, we partition Ba = {ei...., } into segments separated by the removed elements. Each segment (except the last one, which treat separately below) contains exactly removed element the end. If linear search (Lines 5 and 10) finds the element to be removed, we call the corresponding segment short. Otherwise, say it is long.
Let the total length of short segments be Lshont The cost of short segment is equal to its length, plus one for the check between the two linear searches in Line 8 if its length is at least k. Thus, the total cost of all short segments at most (1 + Lshort.
Let the total length of long segments be Liong- In long segment, there are exactly & &[log2 ra queries done by the linear searches (Lines 5 and 10), one query due Line 8 and most floga I' many queries by the binary search in Line 12. Thus, the total cost of a long segment is at most Liig
(Ie + 1) [log2 ra] + 1. Moreover, there can be most k[logg ru rul+1 the total cost of all long segments is at most (1 + ;. Lrong.
many long segments. Therefore,
Finally, let Lis be the length of the last segment, where no elements removed. If this does not exist we set Liss = O. When the algorithm considers this segment, the condition that B USS E I in Line 8 is in Line 8, there are two cases. If [S] < k - 1, then we do not query B USS E I and terminate the while-loop. Before that, we use exactly Tiatt many oracle calls in Line 5. Otherwise, that is |S|| 2 k, we use k 1 oracle calls in Line 5 and one query in Line 8, which evaluates true and terminates the while-loop. Since k < |S| S
because no further elements
removed afterwards. Regarding the other condition
Lias,, we conclude that in both cases we use at most Liast many oracle calls during the last segment.
Therefore, the total number of queries done in Lines 3-13 is most
1 k.
(Istoot + [ongg)
Lsuaa S (
rd-
Together with the n Ta oracle calls in Line 15, we conclude that the total number of oracle calls is most
(1 T ra s
1 1)) n.
rd +
1 1
This concludes the proof of Theorem 2.3.
B Lower bounds
We present lower bounds on the worst-case number of clean queries required by any deterministic algorithm. Note that all lower bounds hold even if the dirty oracle indeed follows a matroid. First, we show that, even if M .Ma, the worst-case number of clean queries is at least n + 1. The following lemma also shows that this is best-possible number of queries for instances with M Ma and the best-possible worst-case bound of n queries cannot be achieved at the same time.
Lemma B.1. For every rank > 1, no deterministic algorithm can use less than n r + clean queries, even if M = Ma Further, for any algorithm that uses exactly n - + 1 clean queries whenever M MM. there is at least instance where it uses at least + clean queries.
14

---

Proof. Consider arbitrary n and with r n. We give clean matroid M such that the statement of the lemma holds for the instance defined by M and the dirty matroid M2 = M. Let E (e1,...,, En) denote the ground set of elements. We define M = Ma as a partition matroid with two classes of elements C1 = (G-1)..,,.-11) and C2 = [er...... en Each set C F. with |snc]| I r-1 and |SnC2| Σ is independent in M MMa and we denote the set of independent sets by I and the set of bases by B. Each basis of this matroid completely contains C₁ and exactly one member of C2. Thus, the rank of M is indeed r. We show that even if the algorithm knows that the underlying matroid is a partition matroid (but it does not know the exact classes), it needs at least n r 1 queries.
As we require algorithms to show some certificate for a clean basis (see Section 1.3), every feasible algorithm has to verify that (i) some B E BB = B is independent in M and that (ii) B U {e} is not independent in M Ma for every e E F. \ B.
Consider the instance defined above. To prove (i), an algorithm has to make the oracle call B E I as calls to supersets of B will return false and calls to sets A with B g A cannot prove that B is independent.
Let denote the element of C2 that is part of the basis B selected by the algorithm. To prove (ii), the algorithm has to verify that the elements (e....., Cn \ {e} are all part of the same class as e and that this class has capacity one. Otherwise, the queries by the algorithm would not reveal sufficient information to distinguish between the matroid M and a potential alternative matroid M' that has third class with capacity one. However, B would not be basis for M', the queries by the algorithm must reveal sufficient information to distinguish M and M.
To prove that an element e' is part of the same class e, an algorithm has to execute query A E I with Inc. C2 = {e', e"} for an element e" that is already known to be in the same class as e. This is because queries A E I with either [An n C2l 1, |A n C2l 2 3 or e' & A would always give the same answer even for the potential alternative matroid M' which e' forms a class of capacity one on its own.
In total, this leads to least n - 1 oracle calls. Further, consider the robustness case that the algorithm is given an instance with a dirty matroid as described above and a clean matroid whose only independent set is the empty set. By the above arguments, in order use only n n- queries for the case M MM, the algorithm has to query some B E Ba. But this query does not help the algorithm to find out that the only clean basis is the empty set, i.e., still needs n more queries to show the fact.
The next lemma gives a lower bound that justifies the linear dependency on 7) in our algorithmic results. In fact, it prohibits improvements over the linear dependency unless the error grows quite large. But even then, we complement the result with a different lower bound that grows stronger with increasing number of errors.
Lemma B.2, For every AA 2 1, there is no deterministic algorithm that uses less than
+ AA
if S 7A T-T2
1 + loga
if
n-rd
nA
clean queries in the worst-case, even if knows Aa upfront.
We prove the lemma by dividing the two different lower bounds into two lemmas, Lemma B.3 and Lemma B.4, which we prove individually.
Lemma B.3, For every number of addition errors nA with 1 S nA S D-TA, there is no deterministic algorithu that uses less than n - r + 17 clean queries in the worst-case even if the algorithu knows the value of 1A upfront and π7 O.
Proof. For the statement of the lemma, we assume that the algorithm has full knowledge of ΠA- However, we still require that the queries of the algorithm be used as certificate for third party without knowledge of 1 to find a provable clean basis. Nevertheless, the assumption that the algorithm knows 17. still restricts the query answers that can be returned by an adversary.
Fix пл E (1,..., ==)
}]. Consider a problem instance with the ground set of elements E = tei....,enl Let Ma be a partition matroid with two classes of elements C1 {Ei,.... Era and
15

---

C2 = fera+1..... ent. Each set S S E with E E Cil S rd and En C2l = 0 is independent in Ma. Thus, C₁ is the only basis.
Consider an arbitrary algorithm for the instance. Depending on the algorithm's oracle calls, the adversary will create a clean partition matroid M (F, with the three classes of elements C1 = {ei...., err J. C2 and Cz. The elements of N ;= {erath..... en will be distributed to C2 and C3 depending on the algorithm's actions, and the class capacities will be ra for C₁, 0 for C2 and 7) for C3. The adversary will assign exactly 7]4 elements to C3. so the only basis of the clean matroid will be C1 C3 and the addition error will be indeed 17A1-
The adversary starts out with empty C2 and C3 and later on adds elements to these sets in a consistent manner. We distinguish between two types of oracle calls by the algorithm: (i) queries to sets S C E with ((S n N) A Cal 2 2 and (ii) queries to sets S S E with (SSN) \ Cal = 1 for the current Cz, which is initially empty. All other oracle calls only contain elements of (E \ () C.. For such queries the adversary has to return true.
For queries of type (ii), the queried set S C E' contains a single element e E (S N) C3 for the current Cz. e has already been fixed as a member of C2. the oracle call returns false. Otherwise, the adversary returns true and adds the single element of (S n N) C3s to Cg. After VA elements of N have been fixed as members of Ca, the adversary starts to return false on all type-(ii) and assigns the single element E NS) \ C3 to C2 instead.
Before we move on to tipe-(i) queries, we give some intuition on the strategy of the adversary for type-(ii) queries. The adversary is designed to reveal the elements C3 that lead to addition errors as fast as possible if the algorithm executes type-(ii) queries. If the algorithm would only execute type-(ii) queries, then after 74 such queries the algorithm would have identified C3- Since the algorithm knows 7A. it then also knows that none of the remaining elements of N \ C33 can be added to the basis Ci U C'3 and, thus, has also identified C2. However, in order to query certificate that proves to a third party without knowledge of V)A that the elements of C2 can indeed not be added, the algorithm will still require |C2] additional queries. Therefore, revealing C3 fast will lead to [C2 +Ca]| = n - r + 7A queries if the algorithm only executes type-(ii) queries. If the adversary would instead reveal the elements of C2 first, then the algorithm that only executes type-(ii) queries could use the knowledge of 7a to conclude after n r queries that C₁ U C3 must be an independent set, otherwise the number of errors would be too small. In contrast to the previous case, the algorithm can prove this efficiently with a single query to C1 U Cg. Thus, revealing C2 first would allow the algorithm to save queries.
For queries of type (i), the adversary will use a different strategy. If the adversary would also start by returning true for type-(i) queries, then every element of N \ C33 that is part of the query would have to be added to Cg. Since there are at least two such elements by definition of type-(i) queries, single query would prove membership of C3 for at least two elements. This would allow to reduce the number of queries below n - r + 7JA-
Instead, we define the adversary to return false as long as this is possible. To make this query result consistent with the clean matroid, the adversary has to add one of the queried elements to C2. If S C2 * (1 already holds for the queried set S and the current set C2, then the adversary can return false without adding a further element to C2. Otherwise, we define the adversary to select two elements e e2 of NS \ (C's U C2). These elements must exist by definition of type-(i) queries and as we assume S n C2 = 0. The adversary will later on add one of e and e2 to C2 depending the algorithms actions. Assume without loss of generality that e1 is the element that appears first (or at the same time as e2) in another later oracle call. Once e appears in this second query, the adversary adds e to C2. If C2 already contains ra 7A elements, then the adversary has to add it to C3 instead and answer the query accordingly.
To show the lower bound, we consider two cases: (1) n -'d 7A elements are added to C2 before TA elements are added to C3 and (2) 7 elements are added to C3 before n rd 7A elements are added to C2. If we show that the algorithm in both cases needs at least lemma follows.
+ 7 queries, the
Case 1. First, assume the algorithm queries in such a way that n - - 7 elements are assigned to C2 before 7 elements are assigned to C3. Since this is the case, an element is only added to C2 if there was a type-(i) query for which the adversary selected {c,e'} with e & e' to potentially add to C2. By definition of the adversary, each such element e afterwards added to C2 while appearing in
16

---

a second query after the type-(i) query. Thus, must appear in at least two queries. Note that these two queries are distinct for each C2 because the assignment of is fixed immediately once e appears in a second query after being selected by the adversary as part of the pair {e, in the type- (i) query. In particular, for e' to also be added to C2, it would need to be selected by the adversary in another type-(i) query and appear in another query afterwards. Since |C2| = n -d T] this leads to total number of queries of least 2- (n Td 7A). As 1] I 22 we have 2- (n Id 174) 2 Td = n + 17.. there exist elements that are never selected by the adversary in response to a type-(i) query, then the ad adversary must add those elements to C3s as C2 is already full. Since the algorithm knows aJ.. it potentially knows that this is the case and can prove that these elements are in C3 with single additional query to C1 U C3.
2- (n- - ra) (n 1 ra))
Case 2. Next, assume the algorithm queries in such way that 7/4 elements are added C3 before n - 17A elements are added to C2. Then, the algorithm must have executed TA type-(ii) queries to sets S where the unique element of (5 NNN) \ C3 was added to C3 afterwards.
Each element e E C2 must appear in a query to a set S for which each other member is either part of C1 or C3 (or eventually added to Cz). As the algorithm knows 174, it might be able to conclude that none of the elements in C' can be added to the independent set C1 UC; without actually querying them. However, the queries of the algorithm must be certificate for third party without knowledge of リ/А- Thus, despite knowing that none of these elements can be added, the algorithm still has to prove it using type-(ii) queries. This leads to a total of at least n Ta 7} + AI n r 7 queries.
Since the previous lemma only holds for errors of at most n- we complement it with the following lower bound for large errors.
Lemma B.4. For every number of removal errors na with < qA, there is no deterministic algo- rithm that uses less than 1 + [log2 ("mx")] queries in the worst-case, even if the algorithm knows the value of na upfront.
Proof. The idea is similar to Lemma B.6. Consider an instance with the dirty matroid Ma = (F, Ia) for the ground set of elements Cn). Let Ma be a partition matroid with the two classes J.
C = (ei...., } and C2 = {Eratl,.... Tn.). Each set I with / nCI S Ta and // n Cgl < 0 is independent in Ma. Thus, C₁ is the only dirty basis.
Fix a number of addition errors 7A 2 1. The adversary will create a clean matroid M = (E, by selecting 17.1 elements from C2 and add to C1 instead. Formally, the clean matroid will be a partition matroid with the two classes Ci = C₁ U A and C22- = C2 \ A for some set A S C2 with |A = 7A- The capacities for the classes are ra + 7741 and 0, respectively.
Firstly, the algorithm has to query Ci, otherwise cannot know whether there's some element in Ci that should be removed (it does not know 77n) Then, the adversary has to identify the set A (or equivalently C2 \ A) in order to execute final query to the clean basis C₁ U A. In order to do so, it has to use queries of the form Dj U D2 where D, C C1 and D2 C C2. The adversary has ((Cal) choices to decide A, and each of the queries by the algorithm can rule out at most one half of these choices (the adversary can always choose to answer "yes" or "no" depending on which preserves more choices). Thus the algorithm needs at least [log, ((Cal) = [logz 9A nA
queries. Note that this bound is weaker than that in Lemma B.3 when 7) is small compared to n Td.
We show that there exists an improved algorithm in terms of the error dependency if n.. = 0 and VA 2 (n - ra) + 1 (cf. Lemma B.5). Hence, a distinction depending on 1J4 in the lower bound (as in Lemma B.2) is indeed necessary.
Lemma B.5. For problem instances with 7R 0 and nA 2 (n-ra) + there exists algoritium that executes strictly less than n - + TA clean queries in the worst-case.
Proof. Let B be basis of the given dirty matroid Ma. Let N = fei.... Cn-ra) r denote the elements of \\ indexed an arbitrary order. Note that |N| 2 1 as qı = and 7 2 Consider the following algorithm:
17

---

1. If | 2 2. continue with Step 2. Otherwise, query B U [ef E I for the single element e N. Add to if this query returns true. Afterwards, terminate.
2. Pick two arbitrary distinct elements e, of N and execute the oracle call B fe, EI. Remove both elements from N.
3. If the oracle call returns true, then add {e, to B.
4. Otherwise, query BU(e} E I. If this returns true, add e to B. Otherwise, query BU(e'} E
I. If this returns true, add e' B.
5. If N is empty now, then terminate. Otherwise, go to Step 1.
We show that this algorithm satisfies the asserted statement.
Assume for now that | is even and, thus, no queries are executed in Step 1. We call one execution of Steps to 5 an iteration. Let k; with i E {0, 1, 2 denote the number of iterations in which i many elements have been added B. Then, the number of queries executed by the algorithm is at most 3 (Ko + k2) + k2g
Since (n rd) 74 elements of N are not part of the basis B computed by the algorithm, must have kg + l1 = (n - rz) MA as ko iterations identify two such elements each and & iterations identify two equalities, we obtain ko + k1 + K2 = n-r2 Hence, the number of queries executed by the algorithm is at most
such element each. Similarly, we have kn 2 122 7JΛ- By combining the
(Ni + k2) + K2
n ld
+ 2kg + + S
n rd
+ 2(2kk + ti1)
2
11 - ld
n2 Td +2
11 - Td
+ 2( rd 11A) <
2
2
4
nl Ta 2 = n1 - 7/A - 2.
The last inequality uses our assumed lower bound on 17A-
We note that there is a straightforward example which shows that this analysis is tight, where in particular kn 0 and the algorithm alternatingly adds two and one elements.
Finally, if | is odd, we have one additional query in Step I of the algorithm. Thus, the number of queries is in this case at most + 7/4
Finally, we justify the logarithmic error-dependency on the removal error me in our algorithmic results for small nj.
Lemma B.6. For every TR 2 L. there is no deterministic algorithm that uses less than
1+ [logz (ma) clean queries in the worst-case even if the algorithm knows the value of nR upfront. Further, if nR < 2 for some fixed k 2 0, the bound is at least n r r+ [ ra k)]
Proof. Consider an instance with the dirty matroid Ma = Ia) for the ground set of elements (c.. Let Ma be a partition matroid with the two classes C1 (eI..... e and C2 (Eryti, ). Each set I with / n Cil S ra and C < 0 is independent in Ma. Thus, Ci the only dirty basis.
Fix a number of removal errors 7/ 2 1. The adversary will create a clean matroid M = (F,, Z) by selecting TΙ elements to remove from C1 and add to O2 instead. Formally, the clean matroid will be a partition matroid with the two classes C₁ = C1 R and C% C2 U R for some set R C C with [R] TR. The capacities for the classes are ra - TJ and 0, respectively.
Consider an arbitrary deterministic algorithm. For each e E C2 = C₁ \ R, the algorithm has to query set S with $ n C2 {e) and S {e) C C₁, this is the only way of verifying that the elements in C2 cannot be added to the basis. Even if the algorithm knows that 77 = 0. still has to queries.
prove this by using such queries. This leads to at least
ra
For the elements in R, the algorithm has to do the same. However, does not know which elements of C₁ belong to R and which do not. Instead, the algorithm has to iteratively query subsets of C₁
18

---

until it has sufficient information to identify the set R. Note that queries to sets containing members of Cj and C2 always return false independent of whether the queried members of C belong to R or not, which means that such queries do not reveal any information helpful for identifying R.
We can represent each such algorithm for identifying R. as a search tree. A vertex in the search tree represents the current state of the algorithm and is labeled by the set P. S C11 of elements that still could potentially belong to R given the information already obtained by the algorithm and family of subsets S, such that each S E S, is guaranteed to contain at least one member of R given the algorithm's 's information. For the root of the search tree, we have P. = C1 and S, = {C1}- }- As the algorithm executes queries to sets S - C1. it gains more information about which elements could potentially belong to R. Thus, each vertex v in the search tree has (up-to) two successors r', v" with different labels Per and P." depending on the answer to the query executed by the algorithm while being the state represented by v. The algorithm can only terminate once reaches a state in the search tree with P.. = 1). because only then it has identified the set R = Pu. We refer to such vertices as leaves. Since, depending on the query results returned by the adversary, each subset of S SC C1 with |S| = Me could be the set R, there are at least ((()) = (Mx) leaves.
The search tree representing the algorithm has maximum out-degree of two and at least (+r) leaves, which implies that the depth of the search tree is at least [log, (-H) Since the adversary can select the query results in such a way that it forces the algorithm to query according to a longest
root-leaf-path, this implies that the algorithm needs at least [log2 (m queries to identify R.
In total, the algorithm has to execute at least for any positive integer n, & with lo S n. If nu is small compared to rdd, say, nn I ra for some constant & 2 0, then loga (x)) 2 nR (log2 ra- k).
+ 1 + [log2 (1)) queries. Note that (*) n
26
C Proofs omitted from Section 3
Lemma 3.2 (Property (ii).. At the start (end) of each iteration of Line 5, it holds (Ba) \ RUUAII
Proof. At the beginning of the first iteration, (Ba) [Ba)AR E I by the condition in Line 2. It suffices to show if (Ba) \ R) U E I holds before iteration E = j. then it also holds before iteration f = j ++ +1. If in iteration { = j. the condition in Line 6 is not satisfied, then A, R do not change and done. The remaining case is that e, is added to A. If then (Ba) \ R) U A E I, Line 8 evaluates false and we done. Otherwise, that is. (Ba) R) A & I, we execute the binary search in Line 9 and add an element to R. To conclude also this case, we argue that at the end of this iteration we have that (Ba) \ R) U A E I. Adding ej our solution, which by induction hypothesis was independent before, creates at most one (in this case exactly one) circuit in our solution (cf. Theorem 39.35 in [32]). Since the binary search in Line detects exactly this unique circuit, an element of the circuit is added to R, which breaks the circuit and makes (Ba \ R) U A independent again.
Lemma 3.3 (Property (i)). At the end of every iteration of Line 5, (Ba) \ R) U A is E-safe.
Proof. First, we introduce some notations. Let Ap. R3 be the sets represented by the variables A, R at the end of iteration (equivalently at the beginning of iteration + 1). We prove by induction over the iterations of Line 5 that the statement holds at the end of every iteration. First, note that every set is O-safe, thus, this also applies to our solution before the first iteration of Line 5. Let E {1, (1). We write B- (Ba) \ R Ar for our preliminary solution after iteration f- 1, and B' = (Ba) ( Re) U A for the solution after iteration f. By induction hypothesis, we can assume that B is (L - 1))-safe, and we now prove that B' is Ê-safe. To this end, we distinguish three cases concerning clement eg.
In the first case we assume that e, & B3. Then, the algorithm makes one more query (Line 6). If Bge + Ge & I, it must hold that E-safe, and since this case B = B', we are done. Otherwise, that is, Bee + ce E I, we add e to A and, thus, Bee + ee = B' We now prove that B' is part of a maximum-weiee that Bee-1 C B*. Such a basis exists because B is (e - -)-e by assumption. If e E B then also B C B", and we are done. Otherwise, that is, eg & B", there must be circuit C in B" eg.
basis, which implies that B' is f-safe. Let B* be some optimal basis such
19

---

Moreover, C' must contain some other element eN with to > L, because B'ee E I due to Lemma 3.2. By the ordering of the elements, Wer 2 Wex and therefore 8 + Eg is a maxinum-weight basis. Further, it contains B'gg. Thus, we conclude B² I
For the second case, suppose that e, BB Re-1. Thus, the condition in Line 6 evaluates false, and we have B = B'. Thus, B'= = Bee-1 + cg, and we can prove analogously to the previous case that BZgg in included in a maximum-weit weight basis.
Finally, it remains the case where eg E Re-1- In this case, ej is added to R in some earlier iteration l' < l, and, thus, eg & B'. Also, B = B' because Eg E Bd. We show that B' + is dependent, which implies that B' is Ê-safe. To this end, we prove for q = ....... l - 1 the invariant that ((Ba) \ Ry) U At) + Gg contains a eircuit C' such that eg E C and that e the element with the largest index in C. Note that the invariant holds at the time eg is added to R in iteration e' due to Lines 3 and 10. Suppose the invariant holds for q = j-- -
I, witnessed by circuit C₁. We now prove the invariant for j. q If Ci S ((Baa) \ R₂) U Az) Eg. we are done. Otherwise, the algorithm must have added element e, E C1 to R in iteration j. By Lines 2 and 9, e, is the element with largest index in circuit C2 in (Ba)
1 As er has the largest index in C1 by induction hypothesis and ej E C1, we conclude j < L. Thus, eg & C2. Since Ej E C1 n C2 and eg E C1 \ C2. there exists circuit C3 S. (C1 UC1UCC
{ej} such that et Css (cf. Theorem 39.7 in [32]). In particular, C3 S ((Ba) \ R₂) U Aj)gt-1 + eg and eg has the largest index in Cz. This makes C3 a witness for the invariant for q = J. and, thus, concludes the proof.
L
Lemma 3.5. It holds that |A| S na and | 7R-
Proof. Let A A(Ba), R = R(Ba) be some minimum modification sets for Ba and 1 (Ba U A.) R". We choose A and R such that |R +*I A is minimized. By definition, I" E B", and we have [A** S RR and |A*| S AA.
Let / denote the solution computed by the algorithm. If all elements have distinct weights, it is well known that maximum- weight basis is unique. Since is n-safe by Corollary 3.4, no elements can be added to I while maintaining independence in M Hence. I = I" Further, since RnA = 0, we have R = R²| and |A| |.A%. which asserts the statement in this case. The same argumentation holds if some elements have the same weight and I = I' holds.
Hence, assume from now I + 1 for the sake of contradiction. Let K be the number of distinct weights. We partition E according to weight into weight classes of elements with the same weight. We use subscript i on any set of elements to refer to the subset of elements of the ith weight class, Since I is n-safe by Corollary 3.4, both I and 1s have maximum weight. Using again the observation that An R 0, we have that
R& - |A = RT - 1477 and |4,1 1471
(I)
for every E [ss].
We now either find new modification sets R and A with IRAR* P |RAR* or show 1" & B*; a contradiction in both cases. In the former case, we udditionally require that
Re = Rt', |4^| = | and 7* e B".
(2)
That is, R and A are minimum modification sets.
Let be the weight class of the largest weight such that + 1. Since [4|| [47, we have 1 \ 4 # 0.
If there exists an element e E (T; T²) n A there exists an element el E T, 1 with 8 = T ee'' E B" due to the basis exchange property (cf. Theorem 39.6 in [32]) Ife' E ((Ba), (R) setting R. == R e' and A == A"
we obtain 7. = (Ba \ R³) U Ā' B However, this contradicts our assumption that A and Re are minimum modification sets for Ba since [ [A* < | + |Aa) Thus, e' E A, \ Ir. Therefore, setting R := R and A- == A - e + d' implies (2) and contradicts our minimality assumption on |R A R + IA A A since e' A A".
Otherwise, it must hold that A C A,, and there must exist an element e E (T; 1,) ((B)) R:). If A = A,, there must exist an element e' ((Ba), R.) n R such that I" e + é' E B" by
20

---

the basis exchange property. Setting R = R - c' + e and A = A in this case implies (2) and contradicts again our minimality assumption on |R A + A A Therefore, A _ A, and, in Observe that for all 1 S S 1, we have by our choice of i that 1 I-- In the prefix P U U (Ba);, algorithm guarantees that the largest independent set P has size [P| R.|. This implies P R & I, which contradicts our assumption that I* is a basis.
particular, | < |Aa. Due to (1) and (2), | < R
Lemma 3.6. Algorithm computes a max-weight basis with at most n n-r+1++++ 21A + ( clean queries.
Proof. The correctness follows from Corollary 3.4. It remains to bound the number of clean queries. Note that we use clean-oracle calls only in Lines 2,3,6,8 and 9.
In Lines and 9, each removal incurs binary search, which costs at most (rog) queries. Since every binary search increments the size of R. the total number of queries used in these lines is at most [log2 (ra)] [R]. In Line 2, the number of queries is equal to the number of elements added to R in Line 4 plus final one where the condition evaluates false, which we charge extra. Similarly, we charge the queries in Line 8 to the removals Line 10 if Line holds and to the added element in Line 7 otherwise. In Line 6, we have that each E \ Ba incurs a query, hence the total number n rd.
Summarized, the total number of clean queries is at most [log, . [R] + + + 1 |A| +n Ta- Using r Fa + AAA- 1RR and Lemma 3.5, we conclude the proof.
Lemma 3.7. Every deterministic algorithm for finding maximum-weight basis executes strictly more than n - r + TIA + VRR [Tog)(ra)] + clean-oracle calls in the worst-case.
Proof. Consider the ground set of elements E = fei...., En} with weights We; + i for all e; E E. Let the dirty matroid Ma be a partition matroid that is defined by the two classes C = {eI...., ) and C2 = {ee) with capacities n - 2 and 1, respectively. That is, each set I S E with | S n - and [2nC2] I is independent in Ma. Then, Ba = E\ {en-1) } is the only dirty
fesiium--eigght basis. Furthermore, if M .Ma, then the only way of verifying that B& is indeed a maximum -wiihtt clean basis is to query Ba and {ei,..., - The first query is necessary to prove independence and the second query is necessary to prove that B3 is maximum- weight basis. Note that querying Ba and E would also suffice to prove that Ba is a basis, but it would not exclude the possibility that fci,..... , } is also a basis with strictly more weight. Thus, c2-1) the queries Ba and E are not a certificate for proving that By is a maximum- weight basis.
Consider arbitrary deterministic algorithm. We prove the statement by giving an adversary that, depending on the algorithms clean-oracle calls, creates a clean matroid M that forces the algorithm to execute strictly more clean-oracle calls than the bound of the lemma.
First, we can observe that if .M- MMa, we have n r 7A + [log)(r)] 77 1 11= This means that if the algorithm starts by querying anything but Ba or P := {ei...., ..i....,,n.... cn the adversary can just use Ma as the clean matroid. By the argumentation above, the algorithm then has to also query Ba and P. leading to 3 > 2 queries. Thus, it only remains to consider algorithms that start by querying either Ba or P.
The algorithm queries P first. In this case, the adversary will return false. Note that this answer is consistent with the dirty matroid Ma. This implies that the algorithm has to query Ba next, as the adversary can otherwise select M = .Ma, which again forces the algorithm to also query Ba. Thus, the algorithm would execute
Case I:
queries.
Consider the case where the second query of the algorithm goes to Bg. We define the adversary to return that Ba is not independent.
Instead, the adversary will select clean partition matroid that is defined by the three classes C/
fei..... en-2) {ē} for an element ē E {ei...., cn-2) > that is selected by the adversary in response to the further crean-oracle calls by the algorithm, C% = {ē, en } and C²²- = (ea). The capacities will be n - 3, 0 and 1, respectively. This implies w/2 = 1 as the element e induces a removal error, and 7 = as e is still not part of any maximum- weight basis, and n - r = 2. The bound of the lemma then becomes n nA + [ra]] nR + 1 = 3 [loga(ra)) (ra)].
21

---

(14-)) [log2 (ra - 1)] oracle calls to find the element é. If we pick r.a as a sufficiently large power of two, we get [log2 (ra 1)] = [log2 ra].
Following the proof of Lemma B.6, the adversary can force the algorithm to use [log2
Note that queries containing en-1 do not contribute to finding é as they always return false. This implies that the algorithm needs additional query containing Cn-1 to prove that (Ba \. (ā)) U {ea-1} is not independent in the clean matroid. Combined with the two queries to Ba and P and the [log2 ral queries for finding é, this already leads to 3 (ra)) queries. Any additional query would imply that the algorithm executes strictly more queries than the bound of the lemma.
The algorithm however needs one additional query to verify that Ba \ {é} is independent. Note that the query Ba \ {o} could in principle be executed during the search for However, the adversary would only answer true to query of form Ba {e} for any E Ba if is the only remaining choice for ē since returning true to that query would reveal e = é, which the adversary never does. However, if e is the only remaining choice for E, then algorithm already knows E, which means that the query is not counted within the [log, Ta - 1| = [log, Tal for finding E. In total, this leads to 4 + [log2 ral > 3 ++ [log2 ral queries.
Case 2: The algorithm queries By first. Then, the adversary will return true, which is consistent with the dirty matroid. In order to avoid three queries in case that the adversary chooses .M = .Ma, the algorithm has to query P next. The adversary will answer that P is indeed independent and choose E as the only basis of the clean matroid. Afterwards, the algorithm has to query also E to prove that E is indeed independent. This leads to a total of three queries. However, we have n = 0. 7A and 7R = 0, which implies n r 7I + [log (Ta)] .R + 1 =1 2<33 3.
Theorem 3.8. For any h E N,, there is an algorithm that, given dirty matroid Ma of rank va with unknown 1JA and ijn computes a sekiimmm-weggtt basis of a matroid M of rank r with at most min(n r + k 7A (k- 1) + 7R (k + 1) [oog ral, (1 + mm) oracle calls to M.
Proof. To prove this theorem, we consider Algorithm 2. It is not hard to see that the correctness of Algorithm follows from the correctness of Algorithm 1. We now prove the stated bound on the number of clean-oracle calls.
The algorithm uses clean-oracle calls only in Lines 5, 8, 9, and 11. We separately prove the error- dependent bound and the robustness bound.
Proof of the error-dependent bound. and 11:
We start by bounding the number of queries in Lines 5, 9,
In Line 5, each element E E \ Ba incurs query and the total number of such queries is Td-
n
In Line 11, the binary search is incurred by elements in R. Thus, the total number of such queries is at most RR] [2][log2 ra]-
To bound the number of queries in Line 9, we observe that whenever g reaches k 1, we execute one such query, unless f = dmaxx because then we know that ((Ba R) U A) = (Ba) U and the independence follows because the condition in Line 10 evaluated false. Therefore, it suffices to bound how often reaches k - 1. Note that q can be decreased to 0 only in Lines 8, 9, and 12. Lines 8 and 12 correspond to an element in R. and Line 9 sets the variable LS to false which must have been set to true by Line 2 or Line 5 (in which case we added element to A). Hence, we conclude that the number of times q reaches A 1. which upper bounds the number of queries executed in Line 9, is at most [ + |A| +1.
In total, the number of clean queries in Lines 5, 9, and 11 is at most rd + [ logg ral + [R] + [A] +1
(3)
remains to bound the number of queries executed in Line 8. To this end, we first show q S A: when the algorithm terminates. This follows from the fact that at the end of the algorithm we have a feasible solution by Corollary 3.4. Assume for contradiction that g 2
at the end of the algorithm. Then at some previous iteration, we entered Line 9, Consider the iteration with largest
22

---

index in which we entered Line 9. Note that the st-temntment in Line 9 has to be false as otherwise was set 0 again. But, in particular, this implies that the current solution (B, ()) JA in this iteration is not independent and hence the algorithm must enter Line 8 or Line 11 at some later iteration in order to output an independent solution. This implies that q is set to again, a contradiction.
Observe that is increased by 1 before each query executed in Line 8 and the number of times is increased is at most the total decrease of g plus As shown before, can only be decreased by k - 1 in Line 9 which happens at most |A| + times, or decreased by at most & 6flog, r'l in Lines 8 or 12, which happens [R] times. To be more precise, Line 9 is executed at most |A|] (rather than |A| + 1) times if > 0 at the end of algorithm. This follows from the fact that q implies LS true at the end of the algorithm, which means Line is not executed after the last execution of Line 5.
(the value of q at the end of the algorithm).
To finally bound the number of queries in Line 8 we distinguish whether & q > 0 holds the end of the algorithm. If q > O at the end of the algorithm, then the number of queries executed in are caused by the final at most k - 2 increases of at the end of the algorithm after the last reset of q. If O, then there are no final queries after the last reset of q. However, as argued above, Line 9 is potentially
Line 8 most [A| (k 1) + |R]] k log2 ra] + 2. where the additive
executed [| + 1) times instead of only |A| times. Thus, the number of queries in Line 8 in that case is at most (IAA) + 1)- (k- 1) + R k (logg ra]. In both cases, the number of queries in Line is at most
|A| (A- 1) + R| A <logg Tal + +
We conclude the target bound the number of clean queries by summing up Equation (3) and Equation (4), plugging in + |A| [ = r and using Lemma 3.5, which also holds for Algorithm
n ra + [R] [og, ra] +|
R
|A| 1 + ||| (A: 1) + [R] -[loog ra] k:
= n Tu + [R] + A 1 +
R|
(l + 1) [log2 r21 + k
(r |A| + [R|) + R +
|A| 1 + R (At + 1) [log2 ral + k
= n rd + |4| . 1k+1)+
(k + 1) flgg2 ral + &
n r + N (k (/+1) 1) + 7R (k: + logg ral + k.
Proof of the robustness bound. Let Qa denote the set of queries of Line 5 that trigger the execu- tion of A <- A + et, i.e., QA contains the queries that detect an addition error. Let QN denote the queries of Line 5 that do not trigger the execution of A + A + et and let QR denote the set of all remaining queries.
First, observe that each query in QN is incurred by a distinct element of E (Ba U A). Thus, we have |QN| = n Td -A] [A].
Next, continue by bounding |Qal and 1Qz)- To this end, we partition Qn into segments T, A segment T; contains the queries of Qn that occur after the i'th reset of variable but before reset i i+1 1. We resef to refer to execution of Line 2, 8, 9 or 12 that sets the variable q 0. Since we count the execution of Line as a reset, segment Ti contains the queries of QR that take place between the execution of Line and the first execution of Line 8, or 12 (if such an execution exists).
For segment T,, let q; denote the current value of variable g at the final query of the segment. We distinguish between long, short and tiny segments:
A segment T, is long if it contains queries executed in Line 11.
A segment T; is tiny if it satisfies S k - 1.
A segment is T; is short if it is neither long nor tiny.
First, consider the long segments. Let hong denote the index set of the long segments and let Liong = Eierue 9:- Each long segment T, contains k [[og, r'l queries of Line 8 since qi must increase to at least this value in order to trigger queries in Line 1I and q is reset afterwards. Additionally, the segment must contain a query of Line 9 as qi increases to a value larger than & - 1. Finally, T; contains up-to [log, ra] queries of Line 11. Thus, a long segment T, contains at most (k + Tauss
1) logg ra] + queries. The number of long segments is at most x[ogg rel
as each long segment T;
23

---

has = = [oog ra]. By using that the total number of long segments is also at most R| (since each execution of Line 11 finds a distinct removal error), we get that the total number queries over all long segments is
Loong k kllogg Til
( (1++t) Limng g Htnng!
1 (1+1²) Liong + |Rangl
[Ti
((++1))log2aal)))
where Rkon S R denotes the set of removal errors that where added to R in Line 12.
Next, consider the short segments. As before let shon denote the index of the short segments and Lane 9:. A short segment T; contains exactly qi queries of Line 8. Furthermore, it
let Lihont = Eie Laues
must contain a query of Line 9 since it is not tiny and, thus, has 2 A 1. This implies that T; contains qi conclude that the total number of queries over all short segments most
(1 + 1 )q: queries. As T; is tiny, we have (1 4. )g: (1 t)g. We can
Σ TE Lato
TTIS
1
Σ 2 = 1 EEL
T:
Finally, consider the tiny segments. As before let Iuay denote the index set of the tiny segments and let Luny Eiem,, %. Observe that each tiny segment T, either ends with the reset in Line 14 or ends even before the reset because the algorithm terminates before qi reached value - 1. The latter case can happen at most once in the final segment. Since each reset in Line sets the LS flag to false and the flag is only set to true again Line when an addition error detected, the number of tiny segments is most + |A].
Each tiny segment contains most qi + queries (up-to qi in Line and up-to one in Line 9). Let I denote the index of the final segment and let Liing = Eie V(t) 9r- Without the final segment, we get.
Σ
Til= = Σ (a: + 1) Iiin + Hunyl 11 Luiy +AA. 1E
1
VEllsy Met
can combine the bound for the queries of these tiny segments with a bound for [Qal. Since each query of Qa detects an addition error in Line 5, we have [Qal IA]. Furthermore, we have Lunyy + | = k |A| as there are [A| tiny segments that are not the final one and each such segment T. has qi = k 1. Putting it together we achieve the following combined bound:
1 1)) (Luny + IA)).
Σ
++ Luny |A| |||
It remains to consider the final segment T,. If this segment does not query in Line 9, then have [T, qt- In this case, we can combine all previous bounds and use that Loong + Lihoo + Liiyy +
A x ra + |A| R conclude that the total number of queries is at most:
[Qwl + 1nl + 1Q QN1+
Σ
T
Σ
I
Σ
+
VE JANK
VE Ainy M0
1
S rd |A|
1
(Iriny + [Al + Lshon + Liong) + | + qe
k
< rd -AA|
[
(rr + |A| |A| | l) |Ronng
k
(1+ 1 n.
1 (n
|A|
|A|
R
+
|Roogg))
to
Note that the last inequality holds because |A| < n Td-
If T, executes query in Line 9, then we have [T.] implies < dmaa for the current index E when the query is executed and for dmaa = max Bg i.
+ 1. On the other hand, the query in Line
This means that the variable q is increased at most r. R 1 times and, thus, Liong + Lshoet
24

---

Luny + + |A| I + |A|
|Rongl - 1. Plugging these inequalities into the calculations above
yields the same result:
1Q + 1Q + 1Qx1 1Q +
Σ
T7 +
I
Σ
|QA+ 1Qx+++10 17
Ve Luny
In - |A| +
1+ k
(Iriny + |A/ + Lshort + Ltong) + RRongl + +
Sn
-
| +
+ k:
(ra + |A| - Rlang!
1) + |Rong! +
+
(n
ra
|4| + ra + |4| - Riong
1 |Riong + 1)
+
nh.
This concludes the proof of Theorem 3.8.
D Proofs omitted from Section 4
D.1 Discussion omitted from Section 4.1
Another commonly used type of matroid oracle is the rank oracle: given any S C F, rank oracle returns the cardinality of maximum independent set contained in S, denoted by r(S). We show in this section that rank oracle can be much more powerful than an independence oracle for our problem. First note that since r(S) = |S] if and only if E I. our previous results for independence oracles immediately translate. Moreover, we can even reduce the number of oracle calls using rank oracle. We briefly discuss key ideas for the unweighted case below. would be interesting to see whether these ideas also be used for the weighted case.
We start by adapting the simple algorithm from Section Assume w.L.o.g. B& + 0. If + |Bal (Ba & Σ), we run the greedy algorithm. Otherwise, we check whether r(E) = Ba If holds, we can conclude B. E and are done. (This is the main difference compared the simple algorithm with an independence oracle.) If not, we greedily try to add each element E E. \ Ba using in total n
queries. Thus, every case the algorithm does at most n + 1 clean-oracle calls. Moreover, unlike the simple algorithm with an independence oracle, it only does 2 oracle calls if Ba E B. In particular, this shows that Lemma B.I does not hold for rank oracles anymore.
|Bal S
Using the same idea, we can improve the number of oracle calls whenever B, E B for the error- dependent algorithm from Section 2.1 to 2. Furthermore, we can also improve its worst-case number of queries from On log, 11) to + 1. Recall that this bad case happens when nR is large. However, now we can simply compute r r(Ba) and obtain nr |Ba r(Ba). Depending on m7- we then decide whether to remove elements via binary-search immediately switch to the greedy algorithm. In particular, achieving this worst-case guarantee of + does not affect the error-dependent bound on the number of oracle calls.
Finally, we can improve the dependency on ПJ. Recall that in the error-dependent algorithm, we iteratively augment an independent set B with 1a many elements from E' \ Ba to a basis. But with rank oracle, we can find these elements faster via binary search: find the first prefix (E \ Ba)s which satisfies r U (E) ()) > r(B), and add (E Ba)= to B. Doing this exhaustively incurs at most A [log (n rr)] clean-oracle calls. Thus, whenever 77 Tlog (n-ra)T+ this strategy gives an improved error-dependent bound over considering elements in E Ba linearly. Furthermore, this condition can be easily checked with the rank oracle. Note that this contrasts Lemma B.2.
n-Td
To conclude the discussion, obtain the following proposition.
Proposition 4.1. There is an algorithm that computes clean basis with at most min {n + 1, 2 - 7R [loga ral + min {NA [log2(n ra)l, - -ra} clean rank-oracle calls.
25

---

D.2 Proofs omitted from Section 4.3
In the matroid intersection problem we are given two matroids M =E,IT) and M = on the same set of elements E and we seek to find maximum set of element X C E such that X I n nzZ i.e., is independent in both matroids. For i {1, we define r3 to be the rank of matroid I
D.2.1 Matroid intersection via augmenting paths
The textbook algorithm for finding such a maximum independent set is to iteratively increase the size of a solution by one and eventually reach point in which no improvement is possible; in that case we also get certificate: U S E with |X] 2 ru)) + +22(E) U). Given some feasible solution X E I' nI?, in every iteration the algorithm executes the following steps.
1. Construct the directed bipartite exchange graph DXX) for sets
E \ X, where for \ X there is an edge (z, 3) if X r E I and there is
X and
every æ E X and y E E an edge (y. if X x x y I?2 Compute sets Y1 = {y E X y E I'}
X
and X22 = l X
2. If 1 = 0 terminate with certificate U = F. Yf 0 terminate with certificate U = 0. Otherwise, compute a shortest path between any vertex Y1 and any vertex of Y2.
3. If no such path exists, terminate with the certificate U S E elements for which there exists directed path in D(X) to some element of Y2. Otherwise, augment X along P. that is, X + XAP, and continue with the next iteration.
We call the path found in step 2 an augmenting path. The running time of this classic algorithm is O(r²n) [17]. where
[E] and progress concerning the running times for matroid intersection, culminating in the currently best running time of (nrr3/4) for general matroids [6] and time O(n for special cases, e.g., the intersection of two partition matroids [11].
min(ri,r2). Recently, there has been a lot of significant
Here, we focus on improving the running- time of the simple textbook algorithm for matroid intersec- tion, by (i) using dirty oracles calls each of the augmentation steps or (ii) by using warm-starting ideas, i.e., by computing feasible solution of certain size dependent on the error using an optimal dirty solution.
Formally, additionally to the input for matroid intersection we are also given two dirty matroids M) (E,I)) and M3 = (E,I)). Our goal is to improve the classic textbook algorithm from above by using dirty-oracle calls. We attempt the following approach: Given feasible solution X (for the clean oracles), we do one iteration of the above algorithm using the dirty oracles. If there is an augmenting path, which is also an augmenting path for the clean matroids, solution and go to the next iteration. Otherwise, we found an augmenting path using dirty oracles, which is not an augmenting path for the clean matroids. In this case we do binary search to find the error, update our dirty matroids and start the algorithm again. Finally, if there is no augmenting path in the dirty matroid, we need to augment the solution using clean-oracle calls, as we do not benefit from using the dirty oracle anymore. To avoid this situation, throughout this section we assume that the dirty matroids are supersets of the clean matroids, i.e., I I3 and I C Iz.
augment
Further, in step of the augmenting path algorithm it is crucial that the path from Y1 to Y2 is a path without chords', as otherwise the computed solution may not be feasible. Note that in step 2 we compute a shortest path, which is always a path without chords. Therefore, if we use the dirty need to verify in each step that the
oracles to compute shortest path w.r.t. the dirty oracles, computed path has no chords for the clean matroids as well. To avoid such a situation, we restrict to the case that the clean matroids are partition matroids, for those matroids find an augmenting path without chords, but just any augmenting path. We note that in general the intersection of two partition matroids can be reduced finding maximum b-matching.
do not need to
Therefore, from now on we assume that the clean matroids are partition matroids and that the dirty matroids are supersets of the clean matroids. Our algorithm works follows. We assume that we
A chord of some s-t path P is an edge such that P + e admits an s-t path P' that is strictly shorter than P.
26

---

are given a feasible solution for the clean matroid and wish to increase its size by one if possible. Additionally, we are given two lists Fi and F2 of false dirty queries for M. and Ma respectively, i.e. two list of sets F C E' for which we have already queried that F' not independent in M or M². respectively (but it was independent in the respective dirty matroid), For each iteration, we use the following algorithm.
Algorithm 4: Augmenting path via dirty oracles
Input: A feasible solution X E I' nI and two lists of false dirty queries F2
1 Compute augmenting path P in D (X)
if there is no such path P then
3 L return X (in this case X is optimal)
if P is augmenting puth clean matroids then X' < XAP, Fi F1, F-
if P is not an angmenting path for clean matroids then find the first edge on P such that e & D(X) via binary search. Add corresponding set to F1 or F3 and go to Line 1.
Here, DJ (X) is the bipartite exchange graph for the dirty matroids My and Ma in which we have excluded the list of false queries F. More formally, for every X and y E \ X there is an edge (I. y) in D (X) if X - x + y E I, and X - x & Fi and there is an edge (y, x) in D (X) if X + L and X x + & F2.
Next, we analyze this augmenting path algorithm. In order to define an error measure, let 1/1 = ( (F e Ia F & I'} and n22 = {F E Iž FF & I2} be the number of different sets which are independent in the dirty matroid but not independent in the clean matroid. We now show the following result, which is stronger than Proposition 4.2.
Proposition D.1. Let L and M2 be two partition matroids and M2 and M3 be two dirty matroids such that M' and M2 are supersets of M and M², respectively. Given feasible solution X E I 2 of value k there is an algorithm that either returns a solution of value k+ 1 or outputs that X is maximum using most 2 + (1 + 12)) ([ogg(n)) + 2) clean-oracle calls.
Moreover, there is an algorithm that computes an optimum solution for matroid intersection using at most (r + 1). (2 + (m + m2) [[]o + 2)) clean-oracle calls.
Proof. We first prove that the solution output by the algorithm feasible. If there is no augmenting path in D (X). then there is no augmenting path in D(X) since the dirty matroids are supersets of the clean matroids and in Fi and F22 we only save queries which are not independent the clean matroid. Once we find augmenting path P in D (X), we always verify it using two claan- calls: We query if X P is independent in MM and in MM2. Hence, we only augment X if the augmenting path P is also matroids, we do not need to verify that P is an augmenting path without chords and hence XAP is an independent set in both clean matroids.
augmenting path in D(X). Since both clean matroids partition
remains to prove that we use at most 2 + (1) + 72) [ogg(n)] clean-oracle calls. As described above, after finding an augmenting path P in DJ (X), we verify it using two clean-oracke calls: We query if X P is independent in Mi and in M2. If is independent, we are done. This check needs 2 clean-oracle calls. Otherwise, one of the queries tells us that X AP is not independent, i.e.. one of the edges in P corresponds to a resulting set X. such that X, is independent in, say M2; but not independent in M In particular, in this case Line 7 is executed.
We now show the following: Whenever Line 7 is executed, we add to Fi or F2 an additional set and can find such set using most log2(n) many clean- calls. Since [F [Fzl S m n22 by definition, this shows the desired bound.
The exchange graph D(X) is a subgraph of the exchange graph D (X) since the dirty matroids are supersets the clean matroid and by definition of Fi and F2. Hence, if P = e, E2, .., Ep is an augmenting path in DF (X) but not an augmenting path D(X), there must be an edge e; E P which is not in D(X). Let e; be the first such edge. In order to find e,, we simply do binary search:
27

---

In each iteration, we have two pointers and r, satisfying 0 S f S i and S S p. for which we know that the first l edges of P are also in ((X) and among the edges Et+1...., E, there must be we simply query if XA P is independent in both clean matroids. If yes, then we set E = = 1. nf, We repeat this until we found es. This binary search algorithm finds the first edge e. E P which not in (X) using at most [loga (n)] many clean-oracle calls, where n is the number of elements E]. The additional +2 the bound appears since whenever we compute a new candidate augmenting path P. we first test if it is also an augmenting path in ( using 2 clean-oracle calls. Therefore, we obtain the bound of at most 2 + (m + 722 ([log2 [n)] + 2) clean-oracle calls.
an edge which is not in D(X). Then, for P = 61, f........11.1.
no, we set r r = _
We obtain the final bound of (r+1)-(2+ (m) - ((log)(())g) - clean-oracle calls for computing an optimum solution for matroid intersection as follows: In each iteration we increase the size of the current solution by one or prove that there is no improvement possible (and hence the solution is optimal). Therefore, there are most + 1 iterations, which proves the bound.
D.2.2 Matroid intersection via warm-starting using dirty solution
In this subsection we consider the task of using a solution to the dirty matroid intersection instance as a "warm-start" for the clean matroid intersection instance. In particular, we compute maximal subset of the dirty solution using only few clean-oracle calls, which again will depend on the error of the dirty matroids. Similar approaches for warm-starting using predictions have been used in [10, 16, 31] for problems like weighted bipartite matching or weighted matroid intersection. We show here that this is also possible using dirty matroids.
Before we start with the algorithm, let us define our error measure for this subsection. Here, we are just interested in the removal error: for a given maximum solution Sa for the dirty matroid intersec- tion, we compute the shortest distance to obtain feasible solution to the clean matroid intersection problem. Then, the error is simply the maximum value of this shortest distance among all maximum solutions Sa for the dirty matroid intersection. More formally, let S = maxg,ez]nzz [Sal and define S = {Sa E I nIZ | |Sal = +g} to be the set of optimum solutions to the dirty matroid intersection problem. We define 7)r maxs ming,eIInze {Sa S. S. S Sa).
Our algorithm works as follows. We first compute maximum solution Sa E Id nI3 using some algorithm for matroid intersection. Then, via binary search we greedily remove elements to first obtain a solution which in Z', and then do the same obtain a solution which is also in I We will then show that this solution satisfies |S 2 |Sal -2,, and that we use at most 2 2+ +- (1 [logz (n)]) many clean-oracle calls to compute Sy
Algorithm 5: Obtaining warm-start solution
Input: Two dirty and clean matroids. solution Sa Z} nz3
Compute
2 for i 1,2 do
S. E I then
L go to Line 2 with i = 2 or return S. = Sa if = 2
else
sort elements Sa in arbitrary order e1, E2, E|Sal
find the first element ej E Sa such that (cI, e--13 } E It and fei, eg} & I via binary search. Set Sa = Sa ej and go to Line 3
Proposition 4.3. There is an algorithm that computes feasible solution S. E I nI of size SS 5 2n, using at most 2 + 2n, (1 [Iog)(n)]) clean-oracle calls.
Proof. Feasibility clear since we check in Line for both matroids whether the solution is indeed feasible. We first prove that we remove at most 2/// many elements from S. to obtain a feasible solution Sy E I n I By the definition of the error Th. there is some set S. E I² n I with S. S. Sa of size |Sal Tr- Hence, there is some set R, such that Sa \ R. E I' and some set R such that S₂) \ R2 E I where [R]] S nr and R S Tr- Therefore, S. = S2 \ (R). (R) E I'nZ2
28

---

and 2 2 Saal-2n, Note that since M and M are matroids, the set R,, can be found by greedily removing elements from Sa such that Sa \ Ry E I' and, afterwards, the set Ry be found by greedily removing elements from Sa \ Ry such that (Sa R2,) Ry E I Since Algorithm computes such a set, we conclude that Line 5 is executed at most 21,, times.
Next, show that whenever Line 5 is executed, We fix some i E {1, Let c1, 22.... E|S,l be any order the elements. To find the first element Ej E Sa such that fei,...,j-i E I' and (ei,...,e}) & I', the algorithm performs a binary search. By folklore results, whenever Line is executed, we have previously executed a clean query in Line 3. Finally, we additionally need 2 clean-oracle calls, Line 5 is executed for both matroids even if there is
use at most [1o] many clean-oracle calls.
most floge (n)] many clean-oracle calls do so. Furthermore,
error at all. Therefore, we use at most 2 + 27,- (1 + [loga (n)] many clean-oracle calls.
29

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our results are mentioned in full detail in Section 1.1 and the main result (Maximum- Weight Basis) appears in the abstract; in Section 1.2 we further relate exist- ing results. The rest of the paper is dedicated to proving these results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
fine to include aspirational goals motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We have clearly stated the necessary assumptions in the respective theorem statements and mention generalizations, which require algorithmic ideas.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, a facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't it acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
30

---

Answer: [Yes]
Justification: We have clearly stated the necessary assumptions in the respective theorem statements. While we give (some) proof sketches in the main parts, the formal proofs to all our theoretical results can be found in the appropriate section in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results,
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proof's provided in appendix or supplemental material. Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, if the contribution is specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature the contribution. For example
(a) the contribution primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
31

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (uttps://nips.c cc/ haaai///uuides//eeeubbbiiss wtwpeeeuubbssssooooooooooo
onPolicy) for more details.
While we encourage the release of code and data, understand that this might not be possible, so No is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g,, for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / //nips. hpppplc/guiideeeeeepppppppppeaee /tteggguddds//eeeubmiieeeeee SroodeeumiissionP....
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question:
Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
32

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative етrоr rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: /tt////eurrre /tt///nurs...// ittehi/e/ehccccciieeeieeeeee
Answer: [Yes]
Since our research does neither involve human subjects or participants nor any datasets, the research process did cause harm. Since do directly train ML models, but rather analyze a theoretical framework within which ML models can be used for matroid optimization, do not anticipate negative societal impact potential harmful consequences.
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Since do not directly train ML models, but rather analyze theoretical framework within which ML models can be used for matroid optimization, we do not anticipate direct societal impact.
Guidelines:
33

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular upplications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e-g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: Since we do not train a ML model but analyze theoretical framework of how decrease their query time or how to incorporate them into pre-existing algorithms, our paper does not directly pose such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: As the paper is purely theoretical, we are not using existing assets. Where applicable, we do cite the relevant papers with related and / similar models.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
34

---

The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license. copyright information, and terms of use in the pack- age should be provided. For popular datasets, anperswithcode com /ataaset has curated licenses for some datascts. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors are encouraged reach out to the asset's ss creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, tion, or other labor should be paid at least the minimum wage the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
35

---

Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do include any information that would break anonymity (if applicable), such as the institution conducting the review.
36


Reviews:
[{"review_id": "Ia2Io9cOkU", "reviewer": "Reviewer_2QVw", "summary": "The paper explores the concept of 2-oracle algorithms for matroid optimisation problems. The underlying idea is to equip algorithms with a second, somewhat \"weaker\" oracle. The second oracle is also permits the algorithm to query matroid information (similar to the first oracle) but only gets imprecise answer (different from the first oracle). Therefore the second oracle is also called \"fast\" as the assumption is that its use is cheaper than the use of the first oracle. In this context the problem of computing a maximum-weight basis for a matroid is investigated. The main result obtained is the existence of an algorithm for computing a maximum-weight basis with a prescribed number of oracle calls. Some related tools and aspects like error-depdent and robust algorithms are also considered.", "questions": "- While matroid optimisation is closely related to combinatorial optimisation it is not clear why this paper is submitted to NeurIPS as the connection to neural computing is not that obvious; so this should be justified better\n\n- The paper speaks of \"robust\" algorithms and of \"robustifying\" error-dependent algorithms in a sense of dealing with errors from the second oracle; but robust optimisation has been studied widely in the combinatorial optimisation community is usually concerned with uncertainty in the costs or times given as input; so these two meaning of \"robust\" may easily be mixed up and may be confusing for the reader", "limitations": "n/a", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The main results are established in form of formal theorems that come with a proofs; I did not check the proofs in detail but they look solid (the proof techniques look standard and adequate for this purpose); thus the soundness of the material appears good\n\n- While this is not the first paper that studies the power of 2-oracle algorithms its study in the context of matroid optimisation appears to be original; thus the novelty of the paper is good", "weaknesses": "- The paper is not easy to read; at the end of the introduction (i.e. Section 1) there should be an outline of the organisation of the paper to give the reader orientation\n\n- The organisation of the paper is poor: the 9 pages text consist of 4 pages introduction (Section 1), 1.5 pages warm-up (computing an \"unweighted\" basis) (Section 2), 2 pages computing a max-weighted basis (Section 3) and 1.5 pages future work (Section 4); the way how the material is organised is really unfriendly for the reader\n\n- The main results require a long list of lemmas (which are given in the paper or its appendix); so this might be tedious for the reader to follow the line of proof\n\n- The presentation of the material in the paper is at most fair; changing this may require quite some rewriting of the paper", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### Justification for Conference Fit\n\nAmong the major topics of NeurIPS, our paper fits very well under \"Optimization\" and \"Machine Learning\".\nWhile we do not develop new ML methods, we instead design potential applications for ML-learned information. We theoretically analyze their potential for classic optimization problems in the context of learning-augmented algorithm design, which has been quite successfully established in AI venues, including NeurIPS (examples: Bai and Coester, 2023; Purohit, Svitkina and Kumar, 2018) and ICML (examples: Choo et al., 2023; Lykouris and Vassilvitskii, 2018), over the last five to eight years.\nWe refer to reference [26] in our submission for an almost complete list of papers in this area, many of which are published at NeurIPS or AI conferences in general. \nIn fact, an important use case of this area is to guide the development of ML methods: Which information should ML methods learn in order to improve widely used optimization algorithms? \n\n1. *Bai, X., and Coester, C. \"Sorting with predictions\", NeurIPS 2023*\n2. *Choo, D., et al. \"Active causal structure learning with advice\", ICML 2023*\n3. *Purohit, M., Svitkina, Z., and Kumar, R., \"Improving Online Algorithms via ML Predictions\" NeurIPS 2019*\n4. *Lykouris, T., and Vassilvtiskii, S. \"Competitive Caching with Machine Learned Advice\", ICML 2018*\n\n### Term \"robust\" and its use in robust optimization\n\nIndeed, robust optimization is a classical field of optimization concerned with worst-case guarantees in the face of uncertainty in the input, either in the objective function (cost) or constraints.\nIn the field of learning-augmented algorithms this phrase has been adopted to explicitly refer to worst-case guarantees with respect to the uncertainty about the predictions, which are part of the input.\n\n\n### Weak presentation\n\nWe regret that the reviewer finds the paper difficult to read. \nThe page limit imposes serious constraints on presenting the technical material,  but a full version will allow us to provide more details and illustrations.\nAs is common in theoretical papers, we aimed to present our technical results in a clear manner by breaking complex proofs into several lemmas, allowing readers to maintain an overview without needing to delve into all the details in the main body of the paper. \nWe are unclear about the specific concerns regarding the paper’s organization.\nWe hope that any issues with the organization of the sections do not significantly impact the evaluation of the scientific merits of the paper.\nWe will add an overview at the end of Section 1 as requested.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9kCgVizQ5M", "reviewer": "Reviewer_KsE6", "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}$.\nThe 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.", "questions": "* Minor remarks:\n  * 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.\n  * The error measures defined in lines 375-380 can be exponential in $n$.", "limitations": "The authors state their theoretical results formally, describing all assumptions.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The authors provide interesting and nontrivial upper and lower bounds for a fundamental problem. \n* The two-oracle model considered, which can be viewed as a learning-augmented model, is theoretically interesting.\n* 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 \n$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.\n* The results lack empirical verification. Even basic proof-of-concept experiments would be valuable to assess whether this model could be practically applicable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### Question Regarding Worst-case Guarantee (claimed n log n bound)\n\nOur wording in lines 71-73 might have been misleading and we will change it. Our robustness guarantee, and thus the overall guarantee of the algorithm, is at most 2n (when k=1, which is the smallest value of k for which the stated guarantee holds). In a revision, we will use the standard minimum expression for combining the error-dependent guarantee and the robustness guarantee.\n\n### Question/comment about the error measures defined in lines 375-380 to be potentially exponential in n\n\nYes, this is correct. If this is undesirable, we can adapt it to the number of \"wrong\" edges (at most rn) in the exchange graph constructed to find the alternating paths, which can be defined as follows: taking the max over all independent sets X, how many pairs (x,y) with X-x+y are dependent but judged as independent by the dirty oracle.\nWith this new definition, we can obtain the same results with only a minor modification in the analysis.\n\n### Empirical Verification\n\nWe are happy to add experiments in a full version. Our work provides theoretical results with proofs that hold true without experimental verification. It has become increasingly common in the field of learning-augmented algorithm design to omit experimental verification for purely theoretical results, even when publishing at AI venues.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0LXRFL5RjE", "reviewer": "Reviewer_rC5n", "summary": "This paper aims to solve fundamental matroid optimization problems, specifically, computing a maximum-weight basis of a matroid, a complex combinatorial optimization problem, To this end, the author proposes a two-oracle model, which uses fast but dirty oracle to reduce the time to call clean oracles. Then, the author proposes the algorithm to compute the maximum-weight basis and gives the upper bound of the oracles calls needed. Finally, the author also discusses advanced settings like different kinds of oracles and other matroid optimization problem.", "questions": "Perhaps it will be beneficial to include more figures as illustrations? For example, you can give an example of the algorithm walkthrough as a toy example. Also, it can also be helpful for the readers to understand the new proposed concept like k-safe and modification example.", "limitations": "I think the author has stated the limitations as he/she clearly stated the necessary assumptions in the respective theorem.", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "1. The theoretical technique of this paper seems strong, the paper gives a theorem and detailed proof of the bound of the cost to call oracles.\n\n2. The two-model design is superior to traditional methods which require n+1 clean calls, this seems to be a huge increase.\n\n3. The extended result in the Section 4 is interesting, it helps to show that the algorithm is generalizable and can be suitable for different settings.", "weaknesses": "1. The organization of this paper is very confusing, for example, the author includes a large part of the preliminary in its introduction rather than an independent section. Moreover, the author includes many extended results and propositions in its final section 4, but doesn't include a conclusion.\n\n2. The paper studies combinatorial optimization problems which can be hard to comprehend for readers with not much background knowledge, while the paper is not self-contained enough. The preliminary in Section 1.3 alone is not enough to grasp an intuitive concept of that.\n\n3. This paper doesn't include any empirical experiment.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### Organization of the Paper and Figures\n\nWe regret that space constraints prevent us from providing a more gentle introduction to the well-established field of matroid optimization. In a full version, we will include more figures and examples for our algorithms to better illustrate our results.\n\n### Empirical Verification\n\nWe are happy to add experiments in a full version. Our work provides theoretical results with proofs that hold true without experimental verification. It has become increasingly common in the field of learning-augmented algorithm design to omit experimental verification for purely theoretical results, even when publishing at AI venues.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "h92OmDDK12", "reviewer": "Reviewer_AWmg", "summary": "The paper studies the problem of finding a maximum-weight basis of a matroid in a learning-augmented setting, where there are two different oracles that the algorithm can query to check whether a set is independent: An exact oracle that always gives correct answers (but may be slow), and a dirty oracle that may give incorrect answers. Formally, the answers of the dirty oracle correspond to some other \"dirty\" matroid (or more generally, downward closed set system) that ideally is close to the true matroid. In the setting considered, queries to the dirty oracle are free, and the goal is to minimize the number of queries to the exact oracle to find a maximum weight basis.\n\nThe quality of the dirty oracle is parametrized by two error measures, corresponding roughly to the numbers of elements that would need to be added/removed to move from a max-weight basis for the dirty matroid to a max-weight basis for the true matroid. The main result is an algorithm whose number of clean queries interpolates (as a function of the error parameters) between n-r+k (where n is the number of items in the ground set and r the size of any basis, and $k\\ge 1$ is an algorithm parameter that can be chosen) and $n(1+1/k)$. One should note that without dirty queries, the problem requires n exact queries. The dependence on the error in the interpolation is shown to be asymptotically optimal.\n\nIf the algorithm has access to rank queries rather than just independence queries (rank queries return the rank of a set, i.e., the size of the maximal independent subset) the guarantees can be improved to a quantity interpolating beetween 2 and n+1 exact queries depending on the input.\n\nAn extension of the main results includes an application to the matrix intersection problem.", "questions": "Please elaborate on the size of n-r in typical settings, in relation to the first possible weakness above.", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- Essentially tight bounds.\n- Non-trivial algorithms. They are not overly complicated, but getting everything right requires some care.\n- Clear presentation. The simpler algorithm for the unweighted setting is helpful before diving into the unweighted setting.", "weaknesses": "- In order for the improvement of the algorithm for independence queries to be a super-constant factor requires n-r is sub-linear in n. It is not clear how realistic this is. The authors hint at graphic networks in sparse graphs having high rank -- does this mean $r=\\Omega(n)$ or even $r = n - o(n)$? The result in the case of rank queries avoids this issue though.\n- Significant work is required for the robustness result, i.e., to ensure the number of clean queries is simultaneously bounded by a function of the error parameters and by a quantity slightly larger than n. However, the trivial approach of running two algorithms in parallel would achieve a similar result, losing only a factor of 2, so the improvement over this trivial approach is relatively small.\n- The extension to matroid intersection seems relatively weak (strong assumptions and an error measure that can be exponentially large in n in the first setting). Since this is only an extension rather than a main result, this does not affect the main contribution though.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### Dependence on n-r\n\nIndeed, our results on independence oracles cannot avoid the dependence on n-r, though this can be mitigated by using a stronger oracle type, such as a rank oracle.\nNevertheless, improvements over the greedy guarantee are possible, e.g. for graphic matroids of sparse graphs.\nIn the graphic matroid of a connected graph $G=(V,E)$, we have $n = |E| \\ge |V|-1$ and $r = |V|-1$. If the graph is sparse and satisfies $|E| = |V|-1 + x$ for an $x \\in o(|V|)$, then $n-r$ is asymptotically smaller than the greedy guarantee of $n$. Likely more realistic is a value $x \\le c \\cdot |V|$ for some constant $c$. While this does not give an asymptotic improvement over the greedy algorithm, saving a constant factor can be significant in practice.\n\n\n### Our Robustness Approach vs Standard Approach\n\nIt is correct that the standard approach in learning-augmented algorithms, which involves running two algorithms alternatingly (in parallel), guarantees a simple robustness by losing a factor of 2 in robustness _and_ consistency.\nOur more complex algorithm can achieve a robustness of 2n and at the same time the optimal consistency of n-r+1 (when k=1).\nMoreover, we can achieve a better-than-2 robustness while only losing an additive constant in the consistency, which is not possible with the standard approach.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The reviewers remark that claims appear to be well substantiated with proofs [2QVw, KsE6], the manuscript presents strong results [rC5n, AWmg] and is well-written/clear/logically [KsE6, AWmg], but the writing/organization/readability of the paper could still be improved [2QVw, rC5n], the complexity improvement for independence queries hinge on the rank of the matroid r to grow with larger element cardinality $n$ such that $n-r$ would grow sublinearly [AWmg], limited improvement over trivially running two algorithms in parallel [AWmg] and requiring strong assumptions for the extension to matroid intersection [AWmg].

Apart from answering reviewer questions, the rebuttal expresses the intention to add a full version, not bound by page limits, which features more details and illustrations [response to 2QVw], a gentle introduction to matroid optimization [response to rC5n], some empirical verification [responses to KsE6, rC5n], clarifications of how $2$-oracle matroid optimization relates to neural networks [response to 2QVw] and that "robust" refers in this context to worst-case guarantees over inputs [response to 2QVw].

The overall recommendation is to accept this submission with the agreed upon changes during the discussion phase. While the improvements might not be particularly substantial, there is not really much room for improvement as the bounds are tight [AWmg], the work comprehensively studies a relevant problem and the proofs as well as presentation appear to be generally of high quality although the writing might be a bit dense at times.
Decision: Accept (poster)