Can the ellipsoid method be used with a randomized separation oracle?

Question

Suppose we are trying to solve the following optimization problem: $$ \text{maximize } ~~ c\cdot y \\ \text{subject to } ~~ y\in S $$ where the region $S$ is described by an exponential number of constraints. We assume that $S$ is non-empty and convex, and that the problem has an optimal solution.

Suppose a separation oracle for $S$ was available, i.e., an oracle that given a vector $y$ does one of the following:

1. says that $y$ is feasible ($y \in S$).
2. says that $y$ is infeasible ($y \notin S$). In this case, it returns a violated constraint.

Then, we could have solved our problem with the following variant of the Ellipsoid method (called the sliding objective function technique): based on the oracle answer, a cut through $y$ is made to reduce the size of the current ellipsoid. If the oracle said that $y$ is infeasible, a feasibility cut is made with the returned violated constraint; otherwise, if the oracle said that $y$ is feasible, an optimality cut is made with respect to the objective function. Eventually, the returned solution is the vector with the highest objective value among all vectors deemed feasible by the oracle.

Now suppose that we only have access to a limited randomized version of the separation oracle. Given a vector $y$, it still returns one of the two options described above. When it says that $y$ is infeasible (option 2), it is always correct; but, when it says that $y$ is feasible (option 1), it may be incorrect, but we assume that it is right with high probability. In particular, assume that we know that the probability of success is $(1-\epsilon)$ for some small $\epsilon$.

What will happen if we use this randomized separation oracle inside this variant of the Ellipsoid method? Notice that an incorrect answer can only be returned when an optimality cut needs to be applied (only when the oracle says that $y$ is feasible), can we conclude that it only affects the optimiality?

Let $T$ be an upper bound on the number of iterations in any execution of the deterministic Ellipsoid method variant (the first one described) on our LP. If we used this randomized separation oracle once in each iteration, would it be reasonable to claim that the returned solution is an optimal solution with probability at least $(1-\epsilon)^T$?

[ intuitively, since each operation of the oracle is independent, the value $(1-\epsilon)^T$ gives a lower bound on the probability that we received a correct answer in all the iterations. ]

If so, can we increase the success probability of this Ellipsoid method variant to the same level as the success probability of the oracle (i.e., at least $(1-\epsilon)$) by operating it more than once at each iteration? Is there a way to relate the number of times we need to run the oracle in each iteration to $T$?

Answer 1

Yes, given your conditions the probability of a correct result is at least $(1-\epsilon)^T$.

This seems to follow from standard calculations, so maybe I am missing something. Here are the calculations so you can check.

Fix an instance of your problem. Consider the random experiment of running ellipsoid with the randomized oracle that you describe. Let r.v. $N$ be the number of queries to the oracle made by ellipsoid. For $t\ge 0$, let $X_t$ be the event that the oracle returns a correct answer in each of the first $\min(t, N)$ iterations.

1. First observe that, $(\forall t\ge 1)~\Pr[X_t | X_{t-1}] \ge 1-\epsilon]$.
   (Indeed, by assumption, in any single iteration, the oracle returns a correct answer with probability at least $1-\epsilon$. So, for all $t\ge 1$, $$\Pr[X_t ~|~ N \ge t \wedge X_{t-1}] \ge 1-\epsilon.$$ By definition of $X_t$, $$\Pr[X_t ~|~ N < t \wedge X_{t-1})] = 1.$$ So $$ \begin{aligned} \Pr[X_t ~|~ X_{t-1}] & {} = \Pr[N \ge t] \Pr[X_t ~|~ N \ge t \wedge X_{t-1}] \\ & ~~+ \Pr[N < t]\Pr[X_t ~|~ N < t \wedge X_{t-1}] \\ & {} \ge \Pr[N \ge t] (1-\epsilon) + \Pr[N < t] \\ & {} \ge 1-\epsilon, \end{aligned} $$ as claimed.)

2. It follows that $(\forall t\ge 0)~\Pr[X_t] \ge (1-\epsilon)^t$.
   (Indeed, by definition $\Pr[X_0] = 1$, so for $t\ge 1$ $$ \begin{aligned} \Pr[X_t] & {} \ge \Pr[X_t | X_{t-1}] \Pr[X_{t-1}]\\ & {} \ge (1-\epsilon) \Pr[X_{t-1}] && \text{(by Step 1 above)}\\ & {} \ge (1-\epsilon) (1-\epsilon)^{t-1} && \text{(inductively)}\\ & {} = (1-\epsilon)^t, \end{aligned} $$ as claimed.)

3. So $\Pr[X_T] \ge (1-\epsilon)^T$. Now suppose $X_T$ occurs. That is, the oracle doesn't fail within the first $\min(N, T)$ iterations. Then those first $\min(N, T)$ iterations are the same as they would be with a correct deterministic oracle. So (by definition of $T$) in this case the process returns a correct result. So $\Pr[\text{a correct result}] \ge \Pr[X_T] \ge (1-\epsilon)^T$. $~~~\Box$