<p>The strong separation problem is polynomially equivalent to the strong containment problem (and the latter is known to be equivalent to the general LP problem). The equivalence of separation and containment is proved in Theorem (6.4.1) in the Grötschel, Lovász, Schrijver book:
<a href="https://www.zib.de/groetschel/pubnew/paper/groetschellovaszschrijver1988.pdf" rel="nofollow noreferrer">https://www.zib.de/groetschel/pubnew/paper/groetschellovaszschrijver1988.pdf</a></p>

CC BY-SA 3.0
2018-04-08T18:20:27.720Z
The separation problem in your question is "given two sets of linearly separable points, find a linear separator". The separation problem for linear programs is "given a polytope described by linear constraints, and a point outside of it, find a violated constraint". They don't seem obviously the same. But, more importantly, the reductions in GLS (based on the ellipsoid method) do *not* run in strongly polynomial time. They do not imply that a strongly poly separation oracle gives a strongly poly LP solver. In fact an LP in standard form has a trivial strongly poly separation oracle.
Sasho Nikolov
CC BY-SA 3.0
2018-04-08T18:21:59.200Z
Hmm. So the problem is still open as far as we know?
Aryeh
CC BY-SA 3.0
2018-04-08T18:26:11.630Z
I don't know. Linear separability of points is a particular LP. Maybe there is some (strongly polynomial time) reduction of a general LP to this form. I will ask a friend who may know.
Sasho Nikolov
CC BY-SA 3.0
2018-04-08T18:57:01.710Z
Many thanks! It'd be good to resolve this...
Aryeh
CC BY-SA 3.0
2018-04-08T13:24:42.660Z
2018-04-08T13:24:42.660Z
Aryeh
<p><strong>Second version, hopefully correct.</strong></p>

<p>I claim that solving the feasibility problem <span class="math-container">$\exists? x: Ax \le b$</span> reduces in strongly polynomial time to finding a linear separator. Then it's easy to reduce linear programming to the feasibility problem.</p>

<p>Let us first reduce the strict feasibility problem <span class="math-container">$\exists? x: Ax &lt; b$</span> to finding a linear separator. Towards this, notice that you can reduce to the special case <span class="math-container">$b=0$</span>: just transform the constraints to 
<span class="math-container">$$
Ax + tb &lt; 0, \\
t &lt; 0 
$$</span>
If <span class="math-container">$Ax &lt; b$</span> is feasible for some <span class="math-container">$x$</span>, then <span class="math-container">$(x, -1)$</span> is feasible for the problem above. Conversely, if <span class="math-container">$(x, t)$</span> is feasible for the problem above, then <span class="math-container">$\tilde{x} = -x/t$</span> is feasible for <span class="math-container">$A\tilde{x} &lt; b$</span>. 
This reduction just adds a row and a column to <span class="math-container">$A$</span>, and a new variable <span class="math-container">$t$</span>. </p>

<p>Assume then that you are given the problem <span class="math-container">$Ax &lt; 0$</span>. 
Create a data set which has one point labeled red for every row of <span class="math-container">$A$</span>, and is equal to that row. It also contains the origin <span class="math-container">$0$</span>, labeled blue. Any hyperplane <span class="math-container">$H$</span> separating the red-labeled points from the blue-labeled origin gives a solution to <span class="math-container">$Ax &lt; 0$</span>: just take the normal of <span class="math-container">$H$</span> in the direction of the origin to be <span class="math-container">$x$</span>. </p>

<p>The final step is to reduce the feasibility problem <span class="math-container">$Ax \le b$</span> to the strict feasibility problem <span class="math-container">$Ax &lt; b$</span>. We argue that given an oracle for the strict feasibility problem, we can solve the feasibility problem. Let <span class="math-container">$S$</span> be an inclusion-maximal set of constraints such that the system <span class="math-container">$\forall i \in S: (Ax)_i &lt; b_i$</span> is feasible: we can find <span class="math-container">$S$</span> in at most <span class="math-container">$m$</span> calls to the oracle (assuming <span class="math-container">$A$</span> is <span class="math-container">$m\times n$</span>). If <span class="math-container">$S$</span> contains <em>all</em> constraints, we are done. Otherwise, it is not hard to see that, if <span class="math-container">$Ax \le b$</span> is feasible, then for any <span class="math-container">$i \not \in S$</span> the constraint <span class="math-container">$(Ax)_i \le b_i$</span> must be satisfied with equality for all feasible <span class="math-container">$x$</span>. Use one (or more) of these constraints to eliminate one (or more) of the variables, and recurse on the remaining variables. </p>

<p>This equivalence between finding a linear separator and linear programming is surely well-known, but I do not know what the right reference is. For example, I have seen something like the final reduction above attributed to Chvatal. </p>

CC BY-SA 3.0
2018-04-10T08:49:06.567Z
what is $'\exists ?'$ symbol?
Turbo
CC BY-SA 3.0
2018-04-10T19:58:13.483Z
@Turbo Make a wild guess :) It just indicates that this is a decision problem asking if there exists such an $x$.
Sasho Nikolov
CC BY-SA 4.0
2018-10-05T04:57:47.873Z
@NealYoung I think I have fixed the answer.
Sasho Nikolov
CC BY-SA 4.0
2018-10-05T13:50:18.280Z
Seems right to me. [I've deleted my comments on your first draft, as they no longer apply.]
Neal Young
CC BY-SA 4.0
2018-04-08T20:36:52.400Z
2018-10-06T19:52:20.790Z
2018-10-06T19:52:20.790Z
Sasho Nikolov
<p>Given <span class="math-container">$m$</span> binary labeled points in <span class="math-container">$\mathbb{R}^d$</span>, it is well-known that in general it's NP-hard to find a hyperplane that minimizes sample error. A brute-force search considers all <span class="math-container">$O(m^d)$</span> sample point <span class="math-container">$d$</span>-tuples which span all candidate hyperplanes, and the dimension <span class="math-container">$d$</span> is the hardness parameter (see the <a href="https://dl.acm.org/citation.cfm?id=207282" rel="nofollow noreferrer">paper</a> by Höffgen et al.)</p>
<p>What about the <em>realizable</em> case? Here two natural algorithms come to mind: the Perceptron and Linear Programming. The Perceptron has runtime quadratic in inverse margin. Since we currently don't know of any strongly polynomial LP solvers, all current methods depend, in the worst case, on the configuration of the labeled points -- i.e., the runtime also depends on the margin.</p>
<p>Question: Is there a strongly polynomial algorithm for finding a consistent hyperplane?</p>
<p>Edit (04-Oct-2018). I had accepted an answer but there is a problem with it, so as of now the status of the question is unknown. Is consistent hyperplane as hard as general LP?</p>
<p>Edit 2 (06-Oct-2018). Status: solved!</p>

CC BY-SA 3.0
2018-03-09T11:56:36.473Z
A strongly polynomial algorithm for finding a consistent hyperplane would yield a strongly polynomial algorithm for the separation problem; this would imply a strongly polynomial algorithm for linear programming.
Gamow
CC BY-SA 3.0
2018-03-09T11:58:20.170Z
Thanks! I’ll be happy to accept an answer with references.
Aryeh
CC BY-SA 3.0
2018-04-08T10:13:00.220Z
@SashoNikolov This is a partial reference, will try to follow up with something more substantial: http://homepages.cae.wisc.edu/~linderot/classes/ie418/lecture14.pdf
Aryeh
<cc.complexity-theory><machine-learning><linear-programming><lg.learning>
Complexity of finding a consistent hyperplane
Aryeh
# Complexity of finding a consistent hyperplane

(Asked by: username_0 on 2018-03-09)

Given $m$ binary labeled points in $\mathbb{R}^d$, it is well-known that in general it's NP-hard to find a hyperplane that minimizes sample error. A brute-force search considers all $O(m^d)$ sample point $d$-tuples which span all candidate hyperplanes, and the dimension $d$ is the hardness parameter (see the [paper](https://dl.acm.org/citation.cfm?id=207282) by Höffgen et al.)

What about the *realizable* case? Here two natural algorithms come to mind: the Perceptron and Linear Programming. The Perceptron has runtime quadratic in inverse margin. Since we currently don't know of any strongly polynomial LP solvers, all current methods depend, in the worst case, on the configuration of the labeled points -- i.e., the runtime also depends on the margin.

Question: Is there a strongly polynomial algorithm for finding a consistent hyperplane?

Edit (04-Oct-2018). I had accepted an answer but there is a problem with it, so as of now the status of the question is unknown. Is consistent hyperplane as hard as general LP?

Edit 2 (06-Oct-2018). Status: solved!

**Tags:** cc.complexity-theory, machine-learning, linear-programming, lg.learning
> **Comments:**
> **username_1**: A strongly polynomial algorithm for finding a consistent hyperplane would yield a strongly polynomial algorithm for the separation problem; this would imply a strongly polynomial algorithm for linear programming.  
> **username_0**: Thanks! I’ll be happy to accept an answer with references.  
> **username_0**: @SashoNikolov This is a partial reference, will try to follow up with something more substantial: http://homepages.cae.wisc.edu/~linderot/classes/ie418/lecture14.pdf  

---

## 2 answers

### Answer by username_2 on 2018-04-08. Score: 7 | Accepted answer

**Second version, hopefully correct.**

I claim that solving the feasibility problem $\exists? x: Ax \le b$ reduces in strongly polynomial time to finding a linear separator. Then it's easy to reduce linear programming to the feasibility problem.

Let us first reduce the strict feasibility problem $\exists? x: Ax < b$ to finding a linear separator. Towards this, notice that you can reduce to the special case $b=0$: just transform the constraints to
$$
Ax + tb < 0, \\
t < 0
$$
If $Ax < b$ is feasible for some $x$, then $(x, -1)$ is feasible for the problem above. Conversely, if $(x, t)$ is feasible for the problem above, then $\tilde{x} = -x/t$ is feasible for $A\tilde{x} < b$.
This reduction just adds a row and a column to $A$, and a new variable $t$.

Assume then that you are given the problem $Ax < 0$.
Create a data set which has one point labeled red for every row of $A$, and is equal to that row. It also contains the origin $0$, labeled blue. Any hyperplane $H$ separating the red-labeled points from the blue-labeled origin gives a solution to $Ax < 0$: just take the normal of $H$ in the direction of the origin to be $x$.

The final step is to reduce the feasibility problem $Ax \le b$ to the strict feasibility problem $Ax < b$. We argue that given an oracle for the strict feasibility problem, we can solve the feasibility problem. Let $S$ be an inclusion-maximal set of constraints such that the system $\forall i \in S: (Ax)\_i < b\_i$ is feasible: we can find $S$ in at most $m$ calls to the oracle (assuming $A$ is $m\times n$). If $S$ contains *all* constraints, we are done. Otherwise, it is not hard to see that, if $Ax \le b$ is feasible, then for any $i \not \in S$ the constraint $(Ax)\_i \le b\_i$ must be satisfied with equality for all feasible $x$. Use one (or more) of these constraints to eliminate one (or more) of the variables, and recurse on the remaining variables.

This equivalence between finding a linear separator and linear programming is surely well-known, but I do not know what the right reference is. For example, I have seen something like the final reduction above attributed to Chvatal.

> **Comments:**
> **username_3**: what is $'\exists ?'$ symbol?  
> **username_2**: @Turbo Make a wild guess :) It just indicates that this is a decision problem asking if there exists such an $x$.  
> **username_2**: @NealYoung I think I have fixed the answer.  
> **username_4**: Seems right to me. [I've deleted my comments on your first draft, as they no longer apply.]  

---

### Answer by username_0 on 2018-04-08. Score: 2

The strong separation problem is polynomially equivalent to the strong containment problem (and the latter is known to be equivalent to the general LP problem). The equivalence of separation and containment is proved in Theorem (6.4.1) in the Grötschel, Lovász, Schrijver book:
<https://www.zib.de/groetschel/pubnew/paper/groetschellovaszschrijver1988.pdf>

> **Comments:**
> **username_2**: The separation problem in your question is "given two sets of linearly separable points, find a linear separator". The separation problem for linear programs is "given a polytope described by linear constraints, and a point outside of it, find a violated constraint". They don't seem obviously the same. But, more importantly, the reductions in GLS (based on the ellipsoid method) do *not* run in strongly polynomial time. They do not imply that a strongly poly separation oracle gives a strongly poly LP solver. In fact an LP in standard form has a trivial strongly poly separation oracle.  
> **username_0**: Hmm. So the problem is still open as far as we know?  
> **username_2**: I don't know. Linear separability of points is a particular LP. Maybe there is some (strongly polynomial time) reduction of a general LP to this form. I will ask a friend who may know.  
> **username_0**: Many thanks! It'd be good to resolve this...  

---

