<p><em>Yes, given your conditions the probability of a correct result is at least <span class="math-container">$(1-\epsilon)^T$</span>.</em></p>
<p>This seems to follow from standard calculations, so maybe I am missing something.  Here are the calculations so you can check.</p>
<p>Fix an instance of your problem.  Consider the random experiment of running ellipsoid with the randomized oracle that you describe.  Let r.v. <span class="math-container">$N$</span> be the number of queries to the oracle made by ellipsoid.  For <span class="math-container">$t\ge 0$</span>, let <span class="math-container">$X_t$</span> be the event that the oracle returns a correct answer in each of the first <span class="math-container">$\min(t, N)$</span> iterations.</p>
<ol>
<li><p>First observe that, <span class="math-container">$(\forall t\ge 1)~\Pr[X_t | X_{t-1}] \ge 1-\epsilon]$</span>.<br />
(Indeed, by assumption, in any single iteration, the oracle returns a correct answer with probability at least <span class="math-container">$1-\epsilon$</span>. So, for all <span class="math-container">$t\ge 1$</span>,
<span class="math-container">$$\Pr[X_t ~|~ N \ge t \wedge X_{t-1}] \ge 1-\epsilon.$$</span>
By definition of <span class="math-container">$X_t$</span>,
<span class="math-container">$$\Pr[X_t ~|~ N &lt; t \wedge X_{t-1})] = 1.$$</span>
So
<span class="math-container">$$
\begin{aligned}
\Pr[X_t ~|~ X_{t-1}]
&amp; {} = \Pr[N \ge t] \Pr[X_t ~|~ N \ge t \wedge X_{t-1}]
\\ &amp; ~~+ \Pr[N &lt; t]\Pr[X_t ~|~ N &lt; t \wedge X_{t-1}] \\
&amp; {} \ge \Pr[N \ge t] (1-\epsilon) + \Pr[N &lt; t] \\
&amp; {} \ge 1-\epsilon,
\end{aligned}
$$</span>
as claimed.)</p>
</li>
<li><p>It follows that <span class="math-container">$(\forall t\ge 0)~\Pr[X_t] \ge (1-\epsilon)^t$</span>.<br />
(Indeed, by definition <span class="math-container">$\Pr[X_0] = 1$</span>, so for <span class="math-container">$t\ge 1$</span>
<span class="math-container">$$
\begin{aligned}
\Pr[X_t] &amp; {} \ge \Pr[X_t | X_{t-1}] \Pr[X_{t-1}]\\
&amp; {} \ge (1-\epsilon) \Pr[X_{t-1}] &amp;&amp; \text{(by Step 1 above)}\\
&amp; {} \ge (1-\epsilon) (1-\epsilon)^{t-1} &amp;&amp; \text{(inductively)}\\
&amp; {} = (1-\epsilon)^t,
\end{aligned}
$$</span>
as claimed.)</p>
</li>
<li><p>So <span class="math-container">$\Pr[X_T] \ge (1-\epsilon)^T$</span>.  Now suppose <span class="math-container">$X_T$</span> occurs.  That is, the oracle doesn't fail within the first <span class="math-container">$\min(N, T)$</span> iterations.  Then those first <span class="math-container">$\min(N, T)$</span> iterations are the same as they would be with a correct deterministic oracle.  So (by definition of <span class="math-container">$T$</span>) in this case the process returns a correct result.  So <span class="math-container">$\Pr[\text{a correct result}] \ge \Pr[X_T] \ge (1-\epsilon)^T$</span>.  <span class="math-container">$~~~\Box$</span></p>
</li>
</ol>

CC BY-SA 4.0
2023-01-08T08:51:46.373Z
My real goal was to understand how to relate the success probability of the oracle to the success probability of the ellipsoid method in order to (as you wrote in one of your earlier comments) increase the success-probability of this *randomized ellipsoid method* by calling the oracle more times in each iteration. I hope it's okay to ask if you could elaborate on why you wrote $O(\log(T))$ times? Is there a calculation that explains why it should work? All I managed to prove was that $\log_{\epsilon}[1-(1-\epsilon)^{\frac{1}{T}}]$ times would be sufficient, but not to directly relate it $T$.
eden hartman
CC BY-SA 4.0
2023-01-08T12:31:41.507Z
Consider replacing the oracle, say $A(y)$, by an oracle $A_d(y)$ that does the following: it calls $A(y)$ repeatedly, returning the violated constraint if/when $A(y)$ returns one, or if that doesn't happen within $d$ calls to $A(y)$, returns "feasible".  Then the probability that $A_d(y)$ incorrectly says "feasible" in a given call is at most $1-\epsilon^d$.  So, using $A_d$ instead of $A$, overall failure probability is at most $1-(1-\epsilon^d)^T \le 1 - (1-T\epsilon^d) = T\epsilon^d$, which is small if $d \gg \log(T)/\log(1/\epsilon)$.
Neal Young
CC BY-SA 4.0
2023-01-08T12:35:59.530Z
Furthermore, in an iteration when $y\not\in S$, the expected number of calls that $A_d(y)$ makes to $A(y)$ is at most $1/(1-\epsilon) = 1+O(\epsilon)$.  Note that each iteration of the other kind (where $y\in S$ and $A_d(y)$ makes $d$ calls to $A(y)$) is one in which ellipsoid adjusts the cost estimate, so presumably there are not so many of those iterations (and if for some reason there were, you could modify ellipsoid to use binary search for the cost instead, and then there wouldn't be).  So perhaps using $A_d$ won't slow ellipsoid down much.
Neal Young
CC BY-SA 4.0
2023-01-08T12:42:03.160Z
BTW if you are interested in actually solving LP's like this in practice, there are probably more practical (faster) algorithms (e.g. using column generation or lagrangian-relaxation, depending on the type of your LP).
Neal Young
CC BY-SA 4.0
2023-01-08T20:05:39.040Z
Thank you, your answers (and questions) have been really helpful.  I'll look into the practical algorithm as well.
eden hartman
CC BY-SA 4.0
2023-01-08T05:36:29.267Z
2023-01-08T05:36:29.267Z
Neal Young
<p>Suppose we are trying to solve the following optimization problem:
<span class="math-container">$$
\text{maximize  }  ~~ c\cdot y
\\
\text{subject to  } ~~ y\in S
$$</span>
where the region <span class="math-container">$S$</span> is described by an exponential number of constraints.
We assume that <span class="math-container">$S$</span> is non-empty and convex, and that the problem has an optimal solution.</p>
<p>Suppose a <em>separation oracle</em> for <span class="math-container">$S$</span> was available, i.e., an oracle that given a vector <span class="math-container">$y$</span> does one of the following:</p>
<ol>
<li>says that <span class="math-container">$y$</span> is feasible (<span class="math-container">$y \in S$</span>).</li>
<li>says that <span class="math-container">$y$</span> is infeasible (<span class="math-container">$y \notin S$</span>). In this case, it returns a violated constraint.</li>
</ol>
<p>Then, we could have solved our problem with the following variant of the Ellipsoid method (called the <a href="https://link.springer.com/book/10.1007/978-3-642-78240-4" rel="nofollow noreferrer"><em>sliding objective function technique</em></a>): based on the oracle answer, a cut through <span class="math-container">$y$</span> is made to reduce the size of the current ellipsoid.
If the oracle said that <span class="math-container">$y$</span> is infeasible, a <em>feasibility cut</em> is made with the returned violated constraint; otherwise, if the oracle said that <span class="math-container">$y$</span> is feasible, an <em>optimality cut</em> 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.</p>
<p>Now suppose that we only have access to a limited <strong>randomized</strong> version of the separation oracle. Given a vector <span class="math-container">$y$</span>, it still returns one of the two options described above.
When it says that <span class="math-container">$y$</span> is infeasible (option 2), it is always correct; but, when it says that <span class="math-container">$y$</span> 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 <span class="math-container">$(1-\epsilon)$</span> for some small <span class="math-container">$\epsilon$</span>.</p>
<p>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 <span class="math-container">$y$</span> is feasible), can we conclude that it only affects the optimiality?</p>
<p>Let <span class="math-container">$T$</span> 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 <span class="math-container">$(1-\epsilon)^T$</span>?</p>
<p>[ intuitively, since each operation of the oracle is independent, the value <span class="math-container">$(1-\epsilon)^T$</span> gives a lower bound on the probability that we received a correct answer in all the iterations. ]</p>
<p>If so, can we increase the success probability of this <em>Ellipsoid method variant</em> to the same level as the success probability of the oracle (i.e., at least <span class="math-container">$(1-\epsilon)$</span>) 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 <span class="math-container">$T$</span>?</p>

CC BY-SA 4.0
2023-01-06T22:49:10.917Z
@NealYoung Thank you for your response! I edited the question, hope it's a bit more clear now. Your second comment may provide a solution to my problem. In practice, there is a randomized alg that I want to use as-is as a part of my separation oracle implementation, but I wasn't sure what the consequences would be. Furthermore, I tried to understand how the success probability of the oracle would affect the success probability of the ellipsoid method. Can you explain why $O(\log T(S))$ times should be enough? can we give a lower bound on the probability that an optimal solution will be found?
eden hartman
CC BY-SA 4.0
2023-01-07T10:13:58.283Z
@NealYoung The separation oracle may say that **the vector $y$ is infeasible**. Suppose we use the Central-Cut Ellipsoid Method ["Geometric Algorithms and Combinatorial Optimization" by  Grötschel et al.], then in each iteration, the oracle is given the center of the current ellipsoid (desceibed by the vector $y$)  and it needs to determine whether it is feasible. Accordingly, a cut is made and a smaller ellipsoid is considered. The ellipsoid variant I used for optimization is the 'sliding objective function technique' in which if a feasible vector was found then an optimality cut is made.
eden hartman
CC BY-SA 4.0
2023-01-07T16:41:16.237Z
@NealYoung I edited the question again and added more details about the specific variant of the ellipsoid method that I used.  Your questions and observations have been very helpful to me. Thank you.
eden hartman
CC BY-SA 4.0
2023-01-07T19:48:12.697Z
If the oracle says that $y$ is feasible, and it is not, then the optimality cut might yield an ellipsoid that has an empty intersection with $S$, so all following solutions will be infeasible. In this case, your algorithm might return a solution that is infeasible, and better than all feasible solutions.
Erel Segal-Halevi
CC BY-SA 4.0
2023-01-07T21:01:20.257Z
@NealYoung (1) the answer is option (b) $k$ is an upper bound (I'll try to clarify this in the question). (2) I'm not sure what you mean by *cost queries*. The oracle only answers the quation "does $y$ belong to $S$?" if the answer is NO then we can be sure that indeed $y \notin S$, but if the answer is YES we can only be sure that $y \in S$ with high probability.
eden hartman
CC BY-SA 4.0
2023-01-07T21:08:53.317Z
To clarify, you mention that "an optimality cut" is added.  I assume that during the execution the actual polytope for ellipsoid is $S_\lambda = \{x \in S : c\cdot x \ge \lambda\}$, where $c\cdot x\ge \lambda$ is the "optimality cut", and $\lambda$ is increased if $S_\lambda$ is found to be feasible, and decreased otherwise (similar to binary search).  So it is possible that the query point $y$ could be in $S$, but not in  the current $S_\lambda$.  So then the correct answer would be "infeasible", but (perhaps?) your oracle could say "feasible" (even though $c\cdot y < \lambda$)
Neal Young
CC BY-SA 4.0
2023-01-07T23:36:22.313Z
@NealYoung I can see why you say that it is similar to binary search, but I think the main difference is that according to the ellipsoid variant we use $\lambda$ never supposed to decreases. In your notations, we should start with some known feasible point (which we can find with the "regular" ellipsoid method), this point gives us a lower bound on $\lambda$ and then, I think, that if $S_{\lambda}$ is infeasible we should simply say that $\lambda$ is optimal and to stop the process (if $S_{\lambda}$ is feasible we can proceed as you described).
eden hartman
CC BY-SA 4.0
2023-01-07T23:54:18.797Z
@ErelSegal-Halevi I think you're right! It seems that in the case that there was a mistake in (at least) one of the ellipsoid iterations, then that the result would actually be an infeasible solution that has a higher objective value than the objective values of all feasible solutions (i.e., an objective value higher than the real optimal objective value). Thank you. Now, assuming that you are correct, the only remaining question is with what probability such an event will occur .
eden hartman
<optimization><randomized-algorithms><linear-programming><oracles><convex-optimization>
Can the ellipsoid method be used with a randomized separation oracle?
eden hartman
# Can the ellipsoid method be used with a randomized separation oracle?

(Asked by: username_0 on 2023-01-06)

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*](https://link.springer.com/book/10.1007/978-3-642-78240-4)): 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$?

**Tags:** optimization, randomized-algorithms, linear-programming, oracles, convex-optimization
> **Comments:**
> **username_0**: @NealYoung Thank you for your response! I edited the question, hope it's a bit more clear now. Your second comment may provide a solution to my problem. In practice, there is a randomized alg that I want to use as-is as a part of my separation oracle implementation, but I wasn't sure what the consequences would be. Furthermore, I tried to understand how the success probability of the oracle would affect the success probability of the ellipsoid method. Can you explain why $O(\log T(S))$ times should be enough? can we give a lower bound on the probability that an optimal solution will be found?  
> **username_0**: @NealYoung The separation oracle may say that **the vector $y$ is infeasible**. Suppose we use the Central-Cut Ellipsoid Method ["Geometric Algorithms and Combinatorial Optimization" by  Grötschel et al.], then in each iteration, the oracle is given the center of the current ellipsoid (desceibed by the vector $y$)  and it needs to determine whether it is feasible. Accordingly, a cut is made and a smaller ellipsoid is considered. The ellipsoid variant I used for optimization is the 'sliding objective function technique' in which if a feasible vector was found then an optimality cut is made.  
> **username_0**: @NealYoung I edited the question again and added more details about the specific variant of the ellipsoid method that I used.  Your questions and observations have been very helpful to me. Thank you.  
> **username_1**: If the oracle says that $y$ is feasible, and it is not, then the optimality cut might yield an ellipsoid that has an empty intersection with $S$, so all following solutions will be infeasible. In this case, your algorithm might return a solution that is infeasible, and better than all feasible solutions.  
> **username_0**: @NealYoung (1) the answer is option (b) $k$ is an upper bound (I'll try to clarify this in the question). (2) I'm not sure what you mean by *cost queries*. The oracle only answers the quation "does $y$ belong to $S$?" if the answer is NO then we can be sure that indeed $y \notin S$, but if the answer is YES we can only be sure that $y \in S$ with high probability.  
> **username_2**: To clarify, you mention that "an optimality cut" is added.  I assume that during the execution the actual polytope for ellipsoid is $S_\lambda = \{x \in S : c\cdot x \ge \lambda\}$, where $c\cdot x\ge \lambda$ is the "optimality cut", and $\lambda$ is increased if $S_\lambda$ is found to be feasible, and decreased otherwise (similar to binary search).  So it is possible that the query point $y$ could be in $S$, but not in  the current $S_\lambda$.  So then the correct answer would be "infeasible", but (perhaps?) your oracle could say "feasible" (even though $c\cdot y < \lambda$)  
> **username_0**: @NealYoung I can see why you say that it is similar to binary search, but I think the main difference is that according to the ellipsoid variant we use $\lambda$ never supposed to decreases. In your notations, we should start with some known feasible point (which we can find with the "regular" ellipsoid method), this point gives us a lower bound on $\lambda$ and then, I think, that if $S_{\lambda}$ is infeasible we should simply say that $\lambda$ is optimal and to stop the process (if $S_{\lambda}$ is feasible we can proceed as you described).  
> **username_0**: @ErelSegal-Halevi I think you're right! It seems that in the case that there was a mistake in (at least) one of the ellipsoid iterations, then that the result would actually be an infeasible solution that has a higher objective value than the objective values of all feasible solutions (i.e., an objective value higher than the real optimal objective value). Thank you. Now, assuming that you are correct, the only remaining question is with what probability such an event will occur .  

---

## 1 answers

### Answer by username_2 on 2023-01-08. Score: 2 | Accepted answer

*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$

> **Comments:**
> **username_0**: My real goal was to understand how to relate the success probability of the oracle to the success probability of the ellipsoid method in order to (as you wrote in one of your earlier comments) increase the success-probability of this *randomized ellipsoid method* by calling the oracle more times in each iteration. I hope it's okay to ask if you could elaborate on why you wrote $O(\log(T))$ times? Is there a calculation that explains why it should work? All I managed to prove was that $\log_{\epsilon}[1-(1-\epsilon)^{\frac{1}{T}}]$ times would be sufficient, but not to directly relate it $T$.  
> **username_2**: Consider replacing the oracle, say $A(y)$, by an oracle $A_d(y)$ that does the following: it calls $A(y)$ repeatedly, returning the violated constraint if/when $A(y)$ returns one, or if that doesn't happen within $d$ calls to $A(y)$, returns "feasible".  Then the probability that $A_d(y)$ incorrectly says "feasible" in a given call is at most $1-\epsilon^d$.  So, using $A_d$ instead of $A$, overall failure probability is at most $1-(1-\epsilon^d)^T \le 1 - (1-T\epsilon^d) = T\epsilon^d$, which is small if $d \gg \log(T)/\log(1/\epsilon)$.  
> **username_2**: Furthermore, in an iteration when $y\not\in S$, the expected number of calls that $A_d(y)$ makes to $A(y)$ is at most $1/(1-\epsilon) = 1+O(\epsilon)$.  Note that each iteration of the other kind (where $y\in S$ and $A_d(y)$ makes $d$ calls to $A(y)$) is one in which ellipsoid adjusts the cost estimate, so presumably there are not so many of those iterations (and if for some reason there were, you could modify ellipsoid to use binary search for the cost instead, and then there wouldn't be).  So perhaps using $A_d$ won't slow ellipsoid down much.  
> **username_2**: BTW if you are interested in actually solving LP's like this in practice, there are probably more practical (faster) algorithms (e.g. using column generation or lagrangian-relaxation, depending on the type of your LP).  
> **username_0**: Thank you, your answers (and questions) have been really helpful.  I'll look into the practical algorithm as well.  

---

