An online passive-aggressive algorithm for difference-of-squares classification

Lawrence K. SaulNeurIPS 2021 · OpenReview

This paper, presented at NeurIPS 2021 by Lawrence K. Saul, introduces a clever way to bring the power of nonlinear classification to the fast-paced world of online learning. By leveraging a "difference-of-squares" model, the author extends the elegant "passive-aggressive" learning framework beyond simple linear boundaries.

The Challenge of Online Learning at Scale

In online learning, data arrives in a continuous stream and must be processed one example at a time. For simple linear models, the Passive-Aggressive (PA) algorithm is highly effective: it stays "passive" if it classifies an example correctly with enough confidence, but becomes "aggressive" when it fails, changing its weights by the absolute minimum amount required to fix the error.

However, linear models are often too simple for complex, real-world data. While kernel methods can add nonlinearity, they scale poorly to millions or billions of examples because they require storing a "budget" of previous examples. Conversely, deep neural networks are powerful but don't easily support the "minimal change" update rule that makes PA learning so robust and easy to use (specifically, avoiding the need to tune learning rates).

INFIMNIST dataset and the decline of linear separability

The author seeks a middle ground: a model more powerful than a linear one, but simple enough to allow for exact, efficient PA updates. This is particularly crucial for massive datasets like INFIMNIST (a 100-million example superset of MNIST with random distortions). As the dataset grows, the data becomes increasingly inseparable by linear hyperplanes, necessitating nonlinear approaches.

The Difference-of-Squares (DoS) Model

To bridge this gap, the author proposes the Difference-of-Squares (DoS) classifier.

Architecture of the Difference-of-Squares (DoS) model
  1. The Architecture: The model maps an input $x$ into two separate vectors, $h_+$ and $h_-$, using affine transformations (essentially $Wx + b$). It then predicts the label based on which vector has a larger squared magnitude: $y = \text{sign}(\|h_+\|^2 - \|h_-\|^2)$. This creates a quadratic decision boundary.
  2. The Update Rule: When the model makes a mistake, the algorithm solves a Quadratically Constrained Quadratic Program (QCQP) to find the smallest possible change to the transformation matrices that satisfies the correct classification margin.
  3. Tractable Non-convexity: While this optimization problem is technically non-convex, the author demonstrates it is tractable. It can be reduced to a simple one-dimensional search for a "step size," making the update almost as fast as a linear one.
  4. Model Alignment and Symmetry: The model is "over-parameterized," meaning many different weight settings result in the same classifier. This creates a problem for model averaging, a common trick to stabilize learning. To resolve this, the author uses techniques from Procrustes analysis and Lorentz transformations to "align" models before averaging them.

Key Insights and Results

  • Superior Accuracy: On the 100M example INFIMNIST task, DoS models significantly outperformed linear models. As the "rank" (the dimensionality of the internal vectors) increased, the error rates dropped further.
  • Computational Efficiency: The updates are mathematically simple enough to handle a continuous stream of 100 million examples on standard hardware without the overhead of kernel budgets.
  • The Importance of Alignment: The proposed "aligned averaging" technique was shown to be essential. Without recognizing the rotational and Lorentz symmetries of the parameter space, the averaged model would often "collapse" and fail to define a sensible decision boundary.

Limitations and Future Work

While highly effective, the approach has a few limitations. Curiously, the simplest DoS model (rank $d=1$) slightly underperformed the linear model, which the author suspects is due to the non-convexity of the objective function that larger models can more easily overcome. Furthermore, while PA learning for linear models has well-established "regret bounds" (theoretical guarantees on the number of mistakes), these have not yet been derived for the DoS model.

Ultimately, the DoS model acts as a natural bridge between purely linear models and fully quadratic ones, offering a sweet spot of capacity and computational efficiency. The author suggests it would be interesting to see if this "Lorentztron" approach could be applied to other types of non-convex but tractable optimization problems in machine learning.

Summary updated

Abstract

We investigate a low-rank model of quadratic classification inspired by previous work on factorization machines, polynomial networks, and capsule-based architectures for visual object recognition. The model is parameterized by a pair of affine transformations, and it classifies examples by comparing the magnitudes of vectors that these transformations produce. The model is also over-parameterized in the sense that different pairs of affine transformations can describe classifiers with the same decision boundary and confidence scores. We show that such pairs arise from discrete and continuous symmetries of the model’s parameter space: in particular, the latter define symmetry groups of rotations and Lorentz transformations, and we use these group structures to devise appropriately invariant procedures for model alignment and averaging. We also leverage the form of the model’s decision boundary to derive simple margin-based updates for online learning. Here we explore a strategy of passive-aggressive learning: for each example, we compute the minimum change in parameters that is required to predict its correct label with high confidence. We derive these updates by solving a quadratically constrained quadratic program (QCQP); interestingly, this QCQP is nonconvex but tractable, and it can be solved efficiently by elementary methods. We highlight the conceptual and practical contributions of this approach. Conceptually, we show that it extends the paradigm of passive-aggressive learning to a larger family of nonlinear models for classification. Practically, we show that these models perform well on large-scale problems in online learning.
BibTeX
@inproceedings{saul2021online,
  author = {Lawrence K. Saul},
  title = {{An online passive-aggressive algorithm for difference-of-squares classification}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=NX4fWKc0gaG},
}
Figure