An Iterative Geometric Approach to Optimizing Separating Hyperplanes

Technical Summary: An Iterative Geometric Approach to Optimizing Separating Hyperplanes

Problem Statement
The paper addresses the problem of computing the maximum-margin separating hyperplane for a binary-labeled, linearly separable dataset. This is equivalent to solving the hard-margin Support Vector Machine (SVM) optimization problem, a convex quadratic program. While standard solvers (e.g., SMO, interior-point methods) solve this problem directly over the entire dataset, the paper investigates a specific scenario: given an initial, feasible (but non-optimal) separating hyperplane, can the optimal solution be reached more efficiently through a sequence of iterative geometric refinements? The goal is to improve the margin continuously while strictly maintaining linear separability at every step.

Methodology
The proposed method is an iterative algorithm that transforms a current separating hyperplane $H_i$ into a new hyperplane $H_{i+1}$ with a larger margin. The process relies on local information (the "active set") rather than the global dataset. The algorithm proceeds as follows:

1. Active Set Identification: For the current hyperplane $H_i$, the algorithm identifies the active set $A_i$, consisting of the samples from both classes closest to the hyperplane.
2. Local Optimization: An existing SVM solver is applied exclusively to the active set $A_i$ to compute its local maximum-margin separating hyperplane, denoted $H^*_i$, with normal vector $w^*_i$.
3. Convergence Check: If the current hyperplane $H_i$ coincides with $H^*_i$, the algorithm terminates, as a hyperplane optimal for its active set is proven to be globally optimal (Lemma 1).
4. Geometric Re-alignment: If $H_i \neq H^*_i$, the algorithm re-aligns $H_i$ toward $H^*_i$. This is achieved by interpolating the normal vector: $w_i(\alpha) = (1-\alpha)w_i + \alpha w^*_i$. The rotation occurs around a pivot point $m$, defined as the midpoint of a selected pair of oppositely labeled support vectors from $A_i$.
5. Margin Expansion and Blocking: The parameter $\alpha$ is increased from 0 to 1. During this rotation, the margin with respect to the active set increases strictly monotonically. However, the rotation is constrained by "blocking samples" outside the active set that might cross the margin hyperplanes. The algorithm calculates the maximum admissible $\alpha$ ($\alpha_{actual}$) such that no new sample violates the separation constraint.
6. Iteration: The hyperplane is updated using $\alpha_{actual}$. If $\alpha_{actual} < 1$, a new sample (or set of samples) has become active (a "blocking sample"), and the process repeats with the updated active set. If $\alpha_{actual} = 1$, the global optimum is reached.

Key Contributions

• Iterative Geometric Technique: The paper introduces a novel algorithm that decomposes the global optimization problem into a sequence of smaller subproblems defined by active sets. Unlike traditional methods that minimize a global objective function, this approach performs geometric transformations (rotations) of the hyperplane to maximize the margin.
• Theoretical Findings:
  • Local-Global Optimality: The paper formalizes the condition that if a separating hyperplane is optimal with respect to its active set, it is globally optimal.
  • Geometric Margin Relationship: It derives a relationship showing that the margin of the interpolated hyperplane is proportional to the cosine of the angle between the current normal vector and the optimal normal vector of the active set ($\gamma(\alpha) = \gamma^* \cos \theta(\alpha)$).
  • KKT Interpretation: The work provides a geometric interpretation of the Karush–Kuhn–Tucker (KKT) conditions in the context of SVMs, linking the separation of projected convex hulls to optimality.
• Experimental Evaluation: The method was implemented in Python using NumPy and CVXPY and tested on linearly separable pairs of MNIST digits.

Experimental Results
The experiments compared the proposed iterative refinement method against a baseline global solver (CVXPY with OSQP) on MNIST digit pairs (ranging from ~2,000 to ~12,000 samples).

• Small Datasets (~2,000 samples): The proposed method was slower than the direct global solver, requiring approximately 10 times more computation time in some cases. The overhead of solving multiple subproblems outweighed the benefits.
• Large Datasets (~12,000 samples): The method became competitive. When the time to compute the initial feasible hyperplane was included, the method was faster in 6 out of 10 training set experiments. When the initial hyperplane was assumed to be pre-existing, the refinement phase alone outperformed the baseline in 8 out of 10 experiments.
• Active Set Size: The active sets remained significantly smaller than the total dataset size (average active set size was roughly half the number of support vectors), validating the strategy of solving reduced subproblems.
• Convergence: The algorithm consistently reached the optimal solution in all experiments, with iteration counts ranging from 84 to 778.

Significance and Claims
The paper claims that the proposed approach is particularly beneficial in scenarios where finding a feasible separating hyperplane is computationally easier than computing the optimal one directly, or when a feasible hyperplane is already available. The method does not replace existing SVM solvers but offers an alternative framework that exploits feasibility and active-set geometry.

The authors are modest regarding the method's universality. They acknowledge that the method does not outperform direct optimization on smaller datasets and that the computational complexity depends heavily on the chosen solver for the active set subproblems. Furthermore, the paper notes that theoretical questions remain open, specifically regarding whether the chosen re-alignment direction guarantees the fastest possible margin increase and whether the method is guaranteed to terminate in a finite number of iterations for all cases. The work is presented as a geometric perspective on maximum-margin optimization that provides new insights into the relationship between local and global optima.