The algorithm for randomized variable elimination including a search for 'r' is given below as in from the Stracuzzi and Utgoff (2004) paper for reference.
The explanation of RVErS algorithm is presented below as in from the Stracuzzi and Utgoff (2004) paper as:
"Randomized variable elimination including a binary search for r (RVErS — “reverse”) begins by
computing tables for kopt(n, r) for values of r between rmin and rmax. Next an initial hypothesis is
generated and the variable selection loop begins. The algorithm chooses the number of variables
to remove at each step based on the current value of r. Each time the bound on the maximum
number of successful selections is exceeded, rmax reduces to r and a new value is calculated as
r = (rmax+rmin) / 2. Similarly, when the bound on consecutive failures is exceeded, rmin increases to r and
r is recalculated. The algorithm also checks to ensure that the current number of variables never
falls below rmin. If this occurs, r, rmin and rmax are all set to the current number of variables.
RVErS terminates when rmin and rmax converge and c1 * E(n, r, k) consecutive variable selections fail.
The choice of when to adjust r is important. The selection process must be allowed to fail a
certain number of times for each success, but allowing too many failures will decrease the efficiency
of the algorithm. We bound the number of failures by c1 * E(n, r, k) where c1 > 1 is a constant.
This allows for the failures prescribed by the cost function along with some amount of “bad luck”
in the random variable selections. The number of consecutive successes is bounded similarly by
c2* (r −E(n, r, k)) where c2 > 0 is a constant. Since E(n, r, k)) is at most r, the value of this
expression decreases as the expected number of failures increases. In practice c1 = 3 and c2 = 0.3
appear to work well."