资源分类
》 资源 》论文》A provably efficient simplex algorithm for classification

A provably efficient simplex algorithm for classification

2020-01-13 | |  56 |   36 |   0

Abstract

We present a simplex algorithm for linear programming in a linear classification formulation. The paramount complexity parameter in linear classification problems is called the margin. We prove that for margin values of practical interest our simplex variant performs a polylogarithmic number of pivot steps in the worst case, and its overall running time is near linear. This is in contrast to general linear programming, for which no sub-polynomial pivot rule is known.

上一篇：Compressive neural representation of sparse, high-dimensional probabilities

下一篇：Multiple Choice Learning: Learning to Produce Multiple Structured Outputs

用户评价
全部评价

热门资源

  • Stratified Strate...

    In this paper we introduce Stratified Strategy ...

  • The Variational S...

    Unlike traditional images which do not offer in...

  • Learning to learn...

    The move from hand-designed features to learned...

  • A Mathematical Mo...

    Direct democracy, where each voter casts one vo...

  • Learning to Predi...

    Much of model-based reinforcement learning invo...