An Efficient Re-Scaled Perceptron Algorithm for Conic Systems

Alexandre Belloni, Robert M. Freund, Santosh VempalaSSRN 2006 · DOI

TL;DR

This paper extends the "re-scaled perceptron" algorithm, originally designed for linear inequalities, to a broader class of "conic systems." The authors introduce a novel "deep-separation oracle" and demonstrate that their generalized algorithm can efficiently find solutions to these conic systems, offering a theoretically sound alternative to existing methods for problems like linear programming, second-order cone programming, and semidefinite programming.

What Problem Does This Paper Address?

The paper tackles the problem of finding a feasible solution to a "conic inclusion" system, which can be generally expressed as $Ax \in \text{int } K$, where $A$ is a linear operator, $x$ is a vector in a Euclidean space, and $K$ is a regular closed convex cone. This general form encompasses many important optimization problems, including linear programming (LP), second-order cone programming (SOCP), and positive semi-definite programming (SDP). While established methods like interior-point methods (IPMs) can solve these problems efficiently, they often require specialized barrier functions for the cone $K$. The classical perceptron algorithm, a simpler row-action method for linear inequalities ($K = \mathbb{R}_+^m$), has a theoretical complexity that can be exponential in the bit-length of the input. A previous work by Dunagan and Vempala introduced a "re-scaled perceptron" algorithm that achieved polynomial-time complexity for LP by iteratively improving the "width" of the feasible region. This paper aims to generalize this re-scaled perceptron approach to arbitrary conic systems, providing a unified and efficient algorithmic framework.

Methods

The core contribution of this paper is the extension of the re-scaled perceptron algorithm to conic systems. This involves several key innovations:

  • Conic Perceptron Algorithm: The paper first generalizes the standard perceptron algorithm to conic systems. This version requires an "interior separation oracle" for the feasibility cone $F = \{x \in X : Ax \in K\}$.
  • Deep-Separation Oracle: A crucial new concept introduced is the "deep-separation oracle." Unlike a standard separation oracle, which finds a hyperplane that separates a point from a set, a deep-separation oracle finds a separating hyperplane that is "deeply" violated by the point. This oracle is essential for the re-scaling step.
  • Re-scaled Conic Perceptron Algorithm: The paper then presents the re-scaled perceptron algorithm, which iteratively uses the deep-separation oracle to "re-scale" the conic system. This re-scaling process effectively increases the "width" of the feasible region, leading to improved convergence properties. The algorithm is structured in steps, including initialization, the conic perceptron phase, stopping criteria, a perceptron improvement phase (using the deep-separation oracle), and a re-scaling step.
  • Construction of Deep-Separation Oracles: A significant portion of the paper is dedicated to showing how to construct deep-separation oracles for specific classes of cones, such as the non-negative orthant, second-order cones, and positive semi-definite cones. They also provide a general methodology for constructing a deep-separation oracle for a feasibility cone $F$ if its dual cone $K^*$ has an efficiently computable deep-separation oracle.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The Power of "Deep" Separation: The key insight is that a "deep" separation oracle, which identifies constraints violated by a significant margin, is crucial for the re-scaling mechanism to effectively improve the geometric properties (width) of the feasible region. This is a stronger requirement than a standard separation oracle.
  • Unified Framework for Conic Optimization: The paper provides a unified algorithmic framework that can handle various types of conic optimization problems (LP, SOCP, SDP) by generalizing the re-scaled perceptron. This suggests a common algorithmic principle underlying these seemingly different problem classes.
  • Constructing Oracles is Key: The efficiency of the re-scaled perceptron algorithm hinges on the ability to efficiently construct deep-separation oracles for the specific cones involved. The paper demonstrates that for many important cones, these oracles can be constructed efficiently, often by leveraging properties of their dual cones.
  • Geometric Interpretation of Re-scaling: The re-scaling step can be interpreted as geometrically "stretching" the space in a way that makes the feasible region "wider," thereby accelerating convergence.

Key Results

  • Theoretical Efficiency: The re-scaled perceptron algorithm is shown to have a theoretical complexity that depends logarithmically on the desired precision (related to $1/\tau_F$, where $\tau_F$ is the width of the feasibility cone). Specifically, the number of iterations is bounded by $O(\log(1/\delta))$ with probability at least $1-\delta$, where $\delta$ is a small error parameter.
  • Oracle Complexity: The algorithm makes $O(T n^2 \ln(n))$ calls to a deep-separation oracle and $O(T n^2)$ calls to a separation oracle, where $T$ is the number of re-scaling steps.
  • Practical Oracle Construction: The paper provides explicit methods for constructing deep-separation oracles for common conic systems, including those involving the non-negative orthant, second-order cones, and positive semi-definite cones.
  • Comparison to Ellipsoid Method: The authors note that while the re-scaled perceptron algorithm is theoretically efficient, the ellipsoid method might have a superior complexity by a factor of $n \ln n$ in certain scenarios, especially when deep-separation oracles are significantly more expensive than interior separation oracles. However, they highlight the potential for acceleration and the independent interest of the re-scaling mechanism.

Limitations and Future Work

  • Oracle Cost: The overall efficiency of the algorithm is heavily dependent on the cost of computing the deep-separation oracle. For some complex cones, constructing this oracle can still be computationally intensive.
  • Practical Performance: While theoretically efficient, the paper focuses on worst-case complexity. The practical performance compared to highly optimized interior-point methods for specific problem classes (like SDP) is not extensively discussed.
  • Open Questions: The authors pose an open question about whether a more straightforward and efficient deep-separation oracle can be constructed for the case of $K = \mathcal{S}_+^k$ (positive semi-definite cone). They also suggest that the re-scaling mechanism might be exploitable in other algorithms.

Summary updated

BibTeX
@misc{belloni2006efficient,
  author = {Alexandre Belloni and Robert M. Freund and Santosh Vempala},
  title = {{An Efficient Re-Scaled Perceptron Algorithm for Conic Systems}},
  year = {2006},
  doi = {10.2139/ssrn.937948},
  howpublished = {SSRN},
}

Loading related content...

Figure