The self-concordant perceptron is efficient on a sub-family feasibility instances
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2019
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915798544547840 |
|---|---|
| author | Chan-Hon-Tong, Adrien |
| author_facet | Chan-Hon-Tong, Adrien |
| contents | Strict linear feasibility or linear separation is usually tackled using efficient approximation/stochastic algorithms (that may even run in sub-linear times in expectation). However, today state of the art for solving exactly/deterministically such instances is to cast them as a linear programming instances. Inversely, this paper introduces a self-concordant perceptron algorithm which tackles directly strict linear feasibility with interior point paradigm. This algorithm has the same worse times complexity than state of the art linear programming algorithms but it complexity can be characterized more precisely eventually proving that it binary complexity is low on a sub-family of linear feasibility. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1901_08525 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | The self-concordant perceptron is efficient on a sub-family feasibility instances Chan-Hon-Tong, Adrien Data Structures and Algorithms Strict linear feasibility or linear separation is usually tackled using efficient approximation/stochastic algorithms (that may even run in sub-linear times in expectation). However, today state of the art for solving exactly/deterministically such instances is to cast them as a linear programming instances. Inversely, this paper introduces a self-concordant perceptron algorithm which tackles directly strict linear feasibility with interior point paradigm. This algorithm has the same worse times complexity than state of the art linear programming algorithms but it complexity can be characterized more precisely eventually proving that it binary complexity is low on a sub-family of linear feasibility. |
| title | The self-concordant perceptron is efficient on a sub-family feasibility instances |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/1901.08525 |