A deterministic rescaled perceptron algorithm

作者：Pena Javier^*; Soheili Negar

来源：Mathematical Programming, 2016, 155(1-2): 497-510.

DOI：10.1007/s10107-015-0860-y

• Separation oracle
• Perceptron algorithm
• Rescaling
• Cone width

The perceptron algorithm is a simple iterative procedure for finding a point in a convex cone . At each iteration, the algorithm only involves a query to a separation oracle for and a simple update on a trial solution. The perceptron algorithm is guaranteed to find a point in after iterations, where is the width of the cone . We propose a version of the perceptron algorithm that includes a periodic rescaling of the ambient space. In contrast to the classical version, our rescaled version finds a point in in perceptron updates. This result is inspired by and strengthens the previous work on randomized rescaling of the perceptron algorithm by Dunagan and Vempala (Math Program 114:101-114, 2006) and by Belloni et al. (Math Oper Res 34:621-641, 2009). In particular, our algorithm and its complexity analysis are simpler and shorter. Furthermore, our algorithm does not require randomization or deep separation oracles.

• 出版日期2016-1