An Efficient Re-Scaled Perceptron Algorithm for Conic Systems
An Efficient Re-Scaled Perceptron Algorithm for Conic Systems
复制标题
圆锥系统的高效重缩放感知器算法
DOI：
10.2139/ssrn.937948
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
S. Vempala
中科院分区：
文献类型：
--
作者：
A. Belloni;R. Freund;S. Vempala
经典感知器算法是求解齐次线性不等式系统Ax > 0的初等算法，在学习理论中有许多重要的应用（例如[11,8]）。与该算法相关的一个自然条件度量是可行解锥的欧几里得宽度τ，感知器算法的迭代复杂度以1/τ2为界。Dunagan和Vempala[5]开发了一种重新缩放的感知器算法，改进了O（n ln(1/τ)）次迭代（高概率）的复杂度，理论上在τ中是有效的，特别是在位长度模型中是多项式时间的。我们将这些感知器方法的概念扩展到一般齐次二次系统Ax∈int K，其中K是一个正则凸锥。我们基于锥的深度分离预言器的概念，提供了对重尺度感知器算法的圆锥扩展，该算法本质上是计算强分离的证明。我们给出了重尺度感知器算法在理论上有效的一般条件，即多项式时间；这包括当K是半空间、二阶锥和正半定锥的叉积时的情况。
The classical perceptron algorithm is an elementary algorithm for solving a homogeneous linear inequality system Ax > 0, with many important applications in learning theory (e.g., [11,8]). A natural condition measure associated with this algorithm is the Euclidean width τ of the cone of feasible solutions, and the iteration complexity of the perceptron algorithm is bounded by 1/τ2. Dunagan and Vempala [5] have developed a re-scaled version of the perceptron algorithm with an improved complexity of O(n ln(1/τ)) iterations (with high probability), which is theoretically efficient in τ, and in particular is polynomial-time in the bit-length model. We explore extensions of the concepts of these perceptron methods to the general homogeneous conic system Ax ∈ int K where K is a regular convex cone. We provide a conic extension of the re-scaled perceptron algorithm based on the notion of a deep-separation oracle of a cone, which essentially computes a certificate of strong separation. We give a general condition under which the re-scaled perceptron algorithm is theoretically efficient, i.e., polynomial-time; this includes the cases when K is the cross-product of half-spaces, second-order cones, and the positive semi-definite cone.