A deterministic rescaled perceptron algorithm

• 成果类型: Article
• 署名作者: Pena, Javier; Soheili, Negar
• 署名单位: Carnegie Mellon University; University of Illinois System; University of Illinois Chicago; University of Illinois Chicago Hospital
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-015-0860-y
• 发表日期: 2016
• 页码: 497-510
• 关键词: relaxation method; systems; MODEL

摘要

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.