The self-concordant perceptron is efficient on a sub-family feasibility instances

Adrien Chan-Hon-Tong

Strict linear feasibility or linear separation is usually tackled using efficient approximation/stochastic algorithms (that may even run in sub-linear times in expectation). Howeve…