4
$\begingroup$

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 https://dl.acm.org/citation.cfm?id=207282).

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!

|cite|improve this question
$\endgroup$
  • 5
    $\begingroup$ 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. $\endgroup$ – Gamow Mar 9 '18 at 11:56
  • 3
    $\begingroup$ Thanks! I’ll be happy to accept an answer with references. $\endgroup$ – Aryeh Mar 9 '18 at 11:58
  • $\begingroup$ @SashoNikolov This is a partial reference, will try to follow up with something more substantial: homepages.cae.wisc.edu/~linderot/classes/ie418/lecture14.pdf $\endgroup$ – Aryeh Apr 8 '18 at 10:13
7
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ what is $'\exists ?'$ symbol? $\endgroup$ – Turbo Apr 10 '18 at 8:49
  • 1
    $\begingroup$ @Turbo Make a wild guess :) It just indicates that this is a decision problem asking if there exists such an $x$. $\endgroup$ – Sasho Nikolov Apr 10 '18 at 19:58
  • 1
    $\begingroup$ @NealYoung I think I have fixed the answer. $\endgroup$ – Sasho Nikolov Oct 5 '18 at 4:57
  • 1
    $\begingroup$ Seems right to me. [I've deleted my comments on your first draft, as they no longer apply.] $\endgroup$ – Neal Young Oct 5 '18 at 13:50
2
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Apr 8 '18 at 18:20
  • $\begingroup$ Hmm. So the problem is still open as far as we know? $\endgroup$ – Aryeh Apr 8 '18 at 18:21
  • 1
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Apr 8 '18 at 18:26
  • $\begingroup$ Many thanks! It'd be good to resolve this... $\endgroup$ – Aryeh Apr 8 '18 at 18:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.