An online passive-aggressive algorithm for difference-of-squares classification
Authors: Lawrence K. Saul
Venue: NeurIPS 2021 Poster (2021)
Keywords: Online learning
passive-aggressive updates
QCQP

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.

An online passive-aggressive algorithm for difference-of-square classification
Lawrence K. Saul
Department of Computer Science and Engineering University of California, San Diego 9500 Gilman Drive, Mail Code 0404 La Jolla, CA 92093-0404 saul@cs. ucsd.edu
Abstract
We investigate low-rank model of quadratic classification inspired by previous work on factorization machines, polynomial networks, and capsule-based architec- tures for visual object recognition. The model is parameterized by pair of affine transformations, and it classifies examples by comparing the magnitudes of vectors that these transformations produce. The model is also pere-paramttrizeed 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 pussive-agrressive 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 can be solved efficiently by elementary methods. We highlight the concep- tual and practical contributions of this approach. Conceptually, extends the paradigm of passive-aggressiee learning to a larger family of nonlinear models for classification. Practically, show that these models perform well on large-scale problems in online learning.
show that it
Introduction
As data sets grow in size and complexity, they create new opportunitics and challenges- large- scale applications of online learning (l] These challenges have been extensively studied and, for the most part, elegantly resolved for the simplest linear models classification (2]. For such models, particularly elegant approach is that of pagrive-aggressive learning 33 In this framework, model is only updated when fails to classify an example correctly with high confidence. When update is triggered, however, the model is changed by whatever minimum amount is required to achieve this goal. This approach neatly dispenses with the need to choose or adapt learning rates.
Given the appeal of such updates, it is of natural interest to extend this approach to a larger family of nonlinear models. Proceeding from the linear model, this can done most straightforwardly by the use of kernel methods [4+6]. But kernel methods do not scale effortlessly to the regime of online learning that we envision in this haper-where the examples are arriving in a streaming fashion from essentially unlimited source
g It is possible to adopt budgeted approach 19114
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

for kernel-based passive-ages aggressive updates [13 conserving memory at the expense of model capacity, but this approach necessarily entails further complexities.
Without the kernel trick, we must face the crux of the problem. Passive-aggressivee updates hinge on the ability perform fundamental calculation: when update is triggered, must compute the minimum change in model parameters that is required to fix the classifier's decision boundary. This is relatively simple calculation for linear models (with hyperplane decision boundaries), but an enormously complex one for (say) decision trees, ensemble methods, and neural nets with threshold or ReLU activation functions. The question is whether this is true for all nonlinear models.
This paper investigates a family of low-rank models for quadratic classification inspired by previous work on factorization machines [88 [9]. polynomial networks [20] [1]] and possule-based archi- tectures for visual object recognition 22 23 For models in this family, we show how to derive aagsive-agresssiv updates by solving quadratically constrained quadratic program (QCQP). The QCQP is nonconvex but tractable: it reduces to an elementary minimization over a bounded interval. In this way, we are able extend the framework of passive-aggresive learning to a larger family of nonlinear models. This is the paper's main contribution.
The organization of this paper is as follows. In section we review the main lines of work that motivated this study. In section B] we formulate our model, elucidate its symmetries, and derive the updates for pagsive-ag learning. In section 4 we provide experimental results a data set with 100M training examples. Finally, in section future work.
we conclude and suggest some directions for
2 Background and related work
aggresiee updates 3 emerged from a long line of work on incremental learning of linear classifiers (3) These updates are based on simple intuition. Suppose that an algorithm has access to a stream of labeled examples {(x, yt) he2, where x, E RD and y E { {-1, [-1,+1}. The goal of the algorithm is learn linear classifier parameterized by a weight vector E TR.. At the outset, the weight vector is initialized to the origin. Then, after the algorithm sees each example, the weight vector is updated by solving the following constrained optimization:
W
argmin WERn
ww,l such that J.w' 2 1.
(1)
The optimization is trivial if the algorithm already classifies the input x, correctly with at least unit margin: in this case, the algorithm responds passively, making no change at all to the weight vector. When this is not the case, however, the algorithm responds aggressively, changing w by the minimum amount required to achieve this goal. The optimization in eq. 4 has the closed-form solution:
max 1 N/wxx x.)
W++1 W. Ogli where
Or
|
This update is appealing in its simplicity and easily adapted to handle noisy labels or to learn separating hyperplane that does not pass through the origin (3]. Similar updates have been studied for problems in online regression 3 portfolio selection 34. nonnegative matrix factorization 351 and
active learning (36).
The above framework can also be generalized via the "kernel trick" 4 to learn nonlinear classifiers. This is done by substituting kernel function evaluations for dot products between training inputs. In this case, however, the kernelized algorithm will typically limit the number of examples that are used to construct the model's decision boundary 19
In this paper we also develop passive-aggressive updates for nonlinear model of classification. Our approach, however, not rooted in the use of kernel methods, but in low-rank quadratic models of classification. For practitioners, these models can provide natural bridge between purely linear and fully quadratic models of classification. Previous examples such models include so-called factorization machines [18 [9] and polynomial networks (of degree two) 20) 21). Though not the focus of this paper, it should be noted that factorization machines (and their variants) have been widely applied problems in collaborative filtering and click-through rate prediction (7
The specific form of our model is also motivated by so-called capsule architectures for visual object recognition 222 23 Like traditional neural nets, capsule-based architectures compute vectors of

---

h-
sum of squares
affine
transformation
sign
affine
transformation
sum of squares
h-
Figure 1: sffeerence-o-squurree (DoS) classifier visualized as a neural network with one layer of hidden units. The network uses pair of affine transformations map each input x into vectors h,, and h of hidden unit activities. Then it labels the input by comparing the squared magnitudes of these vectors.
hidden unit activities; unlike traditional neural nets, they the magnitudes of these vectors to encode the probability that an entity is present an image. This idea has mainly been developed
for deep architectures with multiple layers of interlinked capsules [23 52) although recently it
was explored for a simpler latent variable model of multiway classification
[53 Here we pursue this
simplification even further for problems of binary classification. Whereas the latent variable model in (53) is well suited for maximum likelihood estimation a batch setting, the model in this paper is much better suited to aassive-aggressin learning in online setting. We develop these ideas further in the next section.
Model
In this section we introduce the model at the heart of this paper. We begin by formulating the model as neural network (3.1) and elucidating the symmetries of its parameter space (3.2). Next we derive the passive-aggressive updates for online learning 3.3) and show how to average different models across time (3.4.
3.1 Difference-of-squares classification
The model we study is most easily visualized as the neural network in Fig. The network maps the input into hidden layer by pair of affine transformations: - A2 x b Then it predicts binary label y E {-1,+1} by comparing the magnitudes of the vectors produced in this way. More concretely, let h E Rd denote the vectors of hidden unit activities. The label is predicted as follows:
h4 A b
h_ A b
(4)
sign
(1 1-11?
(5)
Based on the form eq. (5). we refer this model as a difference-of difference-of--xuuaeee of-uuees (DoS) classifier. The dimensionalities of h4 and h- hyperparameters of the model, which for convenience set to be equal. Eq. (5) also makes plain the connection to capsule-based architectures 222 23 53], with h.
and h. playing the role of hidden "pose" vectors whose squared magnitudes determine how inputs are classified. It should noted that networks of this form are not universal function approximators because their decision boundary is necessarily quadratic. This is in contrast neural networks with non- non-polynon pol-oolllomial activation functions, which can approximate any decision boundary in the limit of infinitely many hidden units 57]
The DoS model may not universal approximator, with sufficiently many hidden units, can mimic any fully quadratic classifier. For example, consider classifier of the form
sign (x Px + +r)+
(6)

---

where the decision boundary is determined by the parameters P E Ru** E R" and E R. To prove the claim, we simply express P the difference of positive semidefinite matrices P, and P-. In particular, P = Pt P-, then eq. (6) can be recast in the form of eqs. (35 by setting
r + 1
A
b =
S+
where + = S S_S+. From the mapping in eq. 77. we also see the potential of this parameterization. Suppose that the imput is high dimensional but that the matrix P is of low rank. Then the matrices S satisfying + S + can be short and wide as opposed to square, and the matrices A+ in eq. 7 will have many fewer rows than columns. Such DoS model, with many fewer parameters, may be easier to estimate (robustly) than a fully quadratic classifier.
DoS models differ slightly in form and motivation from the low-rank models of quadratic classification provided by factorization machines [8. by quadratic surface
In factorization machines, the decision boundary is modeled
(Pt) +
Σ
q.a; +r.
where the so-called interaction matrix P+ a low-rank positive semidefinite (PSD) matrix that can be expressed the product of smaller factors. There two differences between eq. (6) for DoS models and eq. (8) for factorization machines: first, the interaction matrix in factorization machines is restricted to be PSD, and second, the decision boundary in factorization machines is only computed from the off-diagonal terms of this interaction matrix. The first of these differences can be viewed as purposeful form of regularization for the sorts of extremely sparse prediction problems, such as collaborative filtering and thrruhhh rate prediction, to which factorization machines have been widely applied [19 (7 the second does not have any effect if the input is a vector of binary elements (because / x4 if æ; E {0, 1)). As shown by eqs. 7 however, these restrictions are not shared by DoS classifiers. In the latter, they overcome by associating separate low-rank matrices (namely, A+) to the classes of positive and negative examples.
Before proceeding, we adopt more unified notation in DoS models for the parameters A+ and b. We do so by working in an augmented input space; specifically we define
x 1
U= [A+ by], V
[A b.).
so that the vector z has exactly one more row than the input x, and the matrices U and V have exactly column than the matrices A,, and A. In this notation, the model's decision boundary simplifies to
sign (Z
y sign (|U2|| |2
(10)
The first expression in eq. (10) provides the most efficient way to compute the label E (-1, but the second makes plain the model's symmetries. We explore these symmetries in the next section.
3.2 Symmetries of the model
Eq. 10p shows that the model's decision boundary and confidence scores only depend on its pa- rameters through the difference U U From this observation deduce two important symmetries. First, the model's predictions are invariant to orthogonal transformations of the form
U QU, + AV,
(11)
(12)
where S2 and A are (independently chosen) d x d orthogonal matrices, satisfying Ω 0 Second, the model's predictions invariant Lorentz transformations (or boosts") of the form
ATA
+ U cosh y - V sinh p
(13)
V V cosh p U sinh yp
(14)
where yp E R. (Lorentz transformations are symmetry of spacetime in the theory of special relativity (58). Both symmetries reveal that the model is over-parameterizze:; by this mean

---

that models with different parameters may describe classifiers with the same decision boundary and confidence scores. This property commonly observed in deep neural networks with ReLU hidden units [59] and rotational symmetries in particular are characteristic of many models of matrix factorization and low-dimensional embedding [60].
The orthogonal and Lorentz transformations in eqs. tries of the DoS parameter space. Note in particular that the former do not change the Frobenius norms of the matrices U and V. while the latter do. From eqs. (33 it is possible, in fact, to compute the Lorentz transformation that yields the model parameters minimum norm:
reflect fundamentally different symme-
argmin +
|| cosh ip V sinh fll
||V cosshpp U Usinh & (1(
(15)
As shorthand notation, we define the matrix inner product (U, = Eij VijVay Then the solution to eq. (1)) takes the simple form:
2(U. V)
80 taan-
(16)
| + IVE.
We omit the derivation of this result, which obtained by zeroing the derivative of the bracketed expression in eq. (15). The result will be needed in section 3.4 when we discuss how to average different models across time.
3.3 Passive-aggressive updates for online learning
We consider learning in the online setting where labeled examples arrive one at a time and are subsequently discarded. Let (U,, V.) denote the model parameters before the example (x,, yr) arrives at time I. We explore passive-aggressive approach, in which at each time step, the algorithm updates its model by solving the following optimization:
min
U. || +IV U.V
such that y/ (1|U2.||2 (|U2z)/=-1/Vzll1 21.
(17)
Suppose that the example (X,, W/ is already classified correctly and with high confidence. Then the algorithm does not change the model: i.e., U = U, and V = Vt. On the other hand, when this is not the case, the algorithm performs the minimal update to correct this failure.
The optimization in eq. (17) quadratically constrained quadratic program (QCQP). This QCQP not convex due to the difference of squared terms that appears its constraint. It is, however, tractable (61-63): nonconvex QCQPs with single constraint be efficiently solved by so-called S S-procedure from nonlinear control theory [64] 65). This general procedure is beyond the scope of this study, but for the problem of interest in eq. [17 the solution can be obtained and justified by more elementary methods.
We start by presenting the solution as a fail accompli. The optimization over matrices (U, V) in eq. (I7) reduces, in the end, to determining a step size a analagous to the one that appears in eq. (2). For DoS models, the step size is found by solving the following one me-dimensional optimization:
||,z1|| + (1+ BeU
] 12 v
ag argmin
|
(18)
(.1))
yov
This minimization convex, and practice it is easily solved by standard methods (e.g., golden section search). Finally, given the step size a2, the updates]for U and V take the simple form:
(UZZ))Z
U U,
(19)
1/1
11-0p at
||z,|2
at
(V,z,)zz
V = V
(20)
1/t
+ 04
|
We emphasize that these updates very nearly simple to implement as the one for linear classifiers in eq. (2). At the same time, however, they provide access to a much richer family of models.
'These updates assume that neither U,æ]| nor || Viz is equal to zero. The assumption holds in practice, as such precise cancellations do not occur when the model parameters are initialized with random values.
5

---

Next we briefly justify the form of these updates. The calculation that follows is a special case of a more general treatment [66] for nonconvex but tractable QCQPs; treatments of even greater Note that if an update is required for the example (Xt, y1)) follows (by continuity) that the solution to eq. (17) will satisfy the margin constraint with equality. We therefore start by forming the Lagrangian
generality are also available 665 67 68
C(U, V, = ||U -.-U,112 + +IVV-V + A (v+ - ||Uz + ||zz1l)).
(21)
The next step is to eliminate the matrices U and V. By setting their partial derivatives to zero, we find that these matrices satisfy
U =U- U.(1I- U1(I112121 >anzi)) =U,
Up U.
AZ
1+
(22)
1 Al1zel1
V = Vi (V((++ IZI
)
vo 1
Xz,zz
(23)
1+ Al|zz|1?
To obtain the rightmost expressions in eq. (2 23 p. we have inverted the matrices = λz,z, using
the -MorrannMorrioon formula and assuming that | * ||z]|_ (We will verify this assumption in the course of finding a solution.) Given these expressions for U and V, it remains only to determine the Lagrange multiplier X. To do so, we simply enforce the constraint y1 = =|U22]|| - V2, _| 23) into this constraint, we obtain the nonlinear equation:
Substituting eqs.
y1
1 (1=
1- 1- 112
)
U22,11
(1
1 1Z
1/
(24)
To simplify what follows, we make the elementary change of variables v yeA11ze11? With this change, we can rewrite eq. (24) as
d [1--)/)) yn ||U + T ynu
|V v
0 du
(25)
Finally we observe that the derivative in eq. 25 is negative at 0= and vanishes for some v E (0, 1) when 3/2 (1|,,,,12 - In this way, recover the minimization prescribed by eq. (18). Likewise, obtain the passive- aggressive updates in eqs. 20) by substituting this solution for the step size into eqs. 23
1V?), < 1; this inequality is, of course, precisely what triggers the update.
3.4 Model averaging
Passive-aggressive updates will not converge to stable solution if there is no model that perfectly classifies the training examples, and they may converge very slowly even when there is. This may not matter if the model is to be indefinitely deployed in an online setting (e.g., when the examples are drawn from a nonstationary or adversarial distribution (69)) But it does matter the ultimate goal is to train and deploy a single fixed model.
For linear classifiers, it is known that stable result can be obtained by averaging models across time 28 29 70 Let O,, denote the model parameters obtained after m intervals of training (where each interval corresponds to some period of natural interest a single update, an epoch, a second,
a minute, etc). In the online setting, an averaged model é,,. = 1 Em O₂ can be computed at the end of each interval. This type of averaging has simple intuition for linear models where the parameters specify a separating hyperplane. For example, consider two models whose separating hyperplanes parallel. Averaging their parameters, we obtain another model whose separating hyperplane is sandwiched in the middle. For linear classifiers, this a sensible result.
The situation is more complicated for mver-aarameterized models, and a simple example shows why. Consider two DoS models with parameters O, (U, V) and e_ ( U, V); also consider the model with the averaged parameter θ = 1/2 (+ + θ_). Note that the models e and θ_ specify exactly the same classifier, whereas the model é (0, 0) does not specify decision boundary at all. In this case, the naive average has clearly not yielded a sensible result. What has gone wrong?
The problem arises in large part due to the symmetries of the model's parameter space. The continuous symmetries, particular, define low-dimensional manifolds of functionally equivalent classifiers, and these manifolds are not convex. This lack of convexity can lead to nonsensical results when

---

unaligned average
aligned average
[ (
Lorentz invariance
rotational invariance
8
(0++0b)
4 4 46;
8
The DoS model is over peeapaammeteiieed in the sense that different parameters and O' generate classifiers with the same decision boundary and confidence scores. This is most evidently true when and O' are related by a continuous symmetry of the model's parameter space, such as a Lorentz transformation (lop) or rotation (hottom). Let θ O be one such pair of parameters, and let e2 0 be another (left). Suppose we desire a model that represents, in some meaningful sense, the average of the models defined by O and 2 Due to the model's 's symmetries, the midpoint {() + (2) may yield a nonsensical result for this average (middle), However, the midpoint (0 + +02) will define a sensible average if O and O are appropriately aligned (right).
Figure 2:
intermediate models constructed by linear interpolation. The problem is illustrated in Fig. 2 for the particular symmetries of DoS models. The figure also depicts a natural solution to this problem: it is to align the parameters of different models before performing their average. Intuitively, by first aligning these parameters, we compensate for the invariances of the model's parameter space. The alignment can also be viewed as form of continuous needed to compare or interpolate between different overparameterized models in a meaningful way.
-emeeery-breaking [60]; this symmetry-breaking is
perform this aligned average as follows. Suppose that we wish compute DoS model Ô that is intermediate between two other DoS models θ (U1, V1) and O (U2, V2). We do this in three steps:
More concretely,
Account for the model's 's invariance under Lorentz transformations. In particular, compute the boost ii in eq. 155) that yields the minimum-norm model O (U,, Vi) equiva- lent to θ (U,, J. Also compute the boost ;22 that yields the minimum-norm model
0 (U,, V2 equivalent to O (U2, V2).
2. Account for the model's 's invariance under orthogonal transformations. In particular, compute the matrices Ω and A that solve the orthogonal Procrustes problems 771:
Ω = argmin QU; - U' 11 such that Q Q I 1I such that Q =I
(26)
Q
argmin QV
(27)
Intuitively, 52 and A are the orthogonal transformations that best align U/2 with U/ and V with V₁. These matrices have closed-for foredd-fomm solutions that are casily obtained from the singular value decompositions (SVDs) (72) of the matrices U Ug, V,. and V/. Set O = (NU,, AV2), and note that by construction the models O and 0₂ define the same classifier.
3. Compute Ô by averaging the newly aligned parameters O and O², as opposed to the original (unaligned) parameters: i.c., for unweighted average, set θ 1/4 (O) θ%
We can also extend this procedure to average multiple DoS models across time. To do so, we note that the unaligned average θ,, 1 Em O₁ may be computed incrementally by setting
é m (1 θ θm-1 + + m
(28)

---

original
distortions
40
O
/
number linearly separable pairs
linearfy Inseparable pairs
2
30
3
4
20
5
6
(20 7E
7
8
g
100K
200K
300K
400K
500K
number of training examples
Figure 3: Left: The INFIMNIST data set 7 generates new digit images by distorting training examples from the original MNIST data set [73]. Right: Fewer pairs of digits remain linearly separable more examples are added to the training set. The inset shows when (and which) pairs of digits become linearly inseparable function of the number of training examples.
For the aligned average, we simply replace the terms m and @m in eq. (28 by their equivalent but aligned counterparts @ and O from the above procedure.
The additional computations for these aligned averages do not entail much extra cost. The more costly step the one that accounts for the model's invariance under orthogonal transformations. However, the cost of this step is small for two reasons. First, the model's parameter matrices typically short and wide; thus in solving the orthogonal Procrustes problems of eqs. 27) fairly cheap to compute and perform SVDs of the d x matrices U U? and ViV Second, in order to obtain stable result, is not necessary average over all of the models estimated throughout the course of training. In practice, this average can be performed over the models estimated at regular but much longer intervals (e.g., once per several thousand training examples).
Experimental results
We experimented on the INFIMNIST data set of handwritten digit images [7], a purposefully con- structed superset of the original MNIST data set [73]. The first 10K images of this superset are those of the MWIST test set, and the next 60K images those of the MNIST training set. The remaining images- about one trillion them hhee-were
were programmatically generated by distorting the 60K images of the MNIST training set; Fig. 3 (left). Our experiments set aside the first 10K images test and used the next 100M images (without reshufflig)) as training examples for online learning.
The MNIST data has been extensively benchmarked. For the original 60K training examples, it is well known that most pairs of digit classes are linearly separable. This situation changes, however, when the training data is augmented with more examples described above. Fig. (right) shows the number linearly separable pairs of digits as function of the number of INFIMNIST training examples. Note that only only pair of digits (O versus 1) remains linearly separable when the training set contains as few as 500K examples. This suggests role for models of higher capacity.
Our experimental setup" was straightforward. We trained linear and DoS models using the updates, respectively, from eqs. (2) and 20). We initialized the parameters of the linear model with zero values and those of the DoS models with small random values. Specifically,
sampled the elements of and from mero-mean normal distribution whose variance was inversely proportional to the number of elements in these matrices. (Note that the DoS models require nonzero initialization to break the symmetry between different hidden units.) We computed ten-way error rates from the
IIn total we purchased several hundred CPU-hours on externaly managed cluster of Intel Xeon Gold 6132 processors. Much of this expended prototyping, debugging, and other intermediate non-results.

---

INFIMNIST
INF INNIISST
20
20
linear
linear
cumulative erro rate (%)
Do5 (d:1)
Do5 (d=1)
Do5 (d=2)
10
10
Do5 (d=4)
moving error rate (9)
Do5
Do5 (d=8)
Do5 (d=4)
Do5 (d=16)
Do5 (d-16)
1
20M
40M
60M
80M
100M
0.5
20M
40M
60M
80M
100M
number of training examples
number training examples
Figure 4: Cumulative and moving error rates (%) on training examples for different models of INFIMNIST digits. The latter were computed non-overlapping sliding windows of 50K examples.
majority votes of 45 } (10- 9) pairwise classifiers. There were no other sources of randomness in the experiments other than the seed for the random number generator. Though not shown here, we verified on the first 10M examples that the results varied little across five different values of this seed,
Fig. 4 compares the cumulative and moving error rates on training examples from different models. The moving error rates were computed on non-overlapping sliding windows of 50K examples. The results are shown for the linear model as well as DoS models with hidden vectors h of dimensionality E {1, 4, 8, 16). It clear that the DoS models with higher capacity learn more accurate classifiers. In addition, as one might expect, the error rates stabilize more quickly for smaller models. For the largest model, the error rates still decreasing after 100M examples, showing that even this stage they are still improving.
Fig. compares the test error rates from models sampled intervals of 50K training examples. The error rates of non-averaged models (left) are extremely variable, especially for the smaller models. However, the results stabilize quickly when these models are averaged across time (right). In addition, it is clear that the averaged models (right) generalize much better than the non-averaged ones (left). It required some extra computation in these experiments to average different DoS models (see section 3.4), but these averaging steps were only performed once per 50K training examples. Thus the extra cost was essentially negligible.
Overall the results show that DoS models low rank can learn much more accurate classifiers than linear models. In addition, these improvements
obtained from online updates that are nearly as simple to implement; compare eqs. (99 20) to eq. (2). Our results provide further evidence for the benefits of low-rank models of quadratic classification, and they consistent with previous results, on the original MNIST data set, that factorization machines can learn much more accurate classifiers than purely linear models 77.. This paper is the first, however, to demonstrate the viability of passive-aggressive updates for these types of models.
It is curious that the linear model slightly outperforms the DoS model with rank-one (d=1) 1) matrices, even though the latter contains the former as a special case. We do not entirely understand this effect, but we did observe it repeatedly in experiments. Presumably this performance gap can be traced to the different objective functions for these models. Both the linear and DoS models can be viewed as attempting to minimize objective function based on the sum of hinge losses. For the linear model, however, this objective function is convex in the model parameters, while for the DoS models, is not. It seems that DoS models with larger capacity easily overcome this non-convexity surpass the linear model, while the DoS model with rank-one matrices is not able to do so. should be kept in mind, though, that the performance gap between the linear and rank-one DoS model is far smaller than the gap between both these models and DoS models of higher rank.
Analogous behavior has been observed in neural network classifiers: those with barely more capacity than a linear model may not always improve on (say) logistic regression, while those with large numbers of hidden units do without any difficulty.

---

INFIMNIST
INFIMNIST
20
20
WITH MODEL AVERAGING
10
10
WITHOUT MODEL AVERAGING
test error rate (%)
test error rate
linear
linear
Do5 (d-1)
Do5 (d-=]]
Do5 (d:2)
Do5 (d=2)
Do5 (d-4)
Do5 [dlm]
DoS (d-8)
Do5 (d-8)
Do5 (d:16)
Do5 (d:16)
0
20M
40M
60M
80M
100M
0
20M
40M
60M
80M
100M
number of training examples
number training examples
Figure 5: Test error rates (%) for different models of INFIMNIST digits as a function of the number of training examples. The models on the right were averaged across time; those on the left were not.
5 Conclusion
In this paper we have investigated family of low-rank models for quadratic classification. Like factorization machines and polynomial networks, these models provide natural bridge between purely linear and fully quadratic classifiers. The DoS models in this paper were trained by passive- aggressive updates; these updates do not require the tuning of learning rates, and they are only slightly more complicated than the passive-aggress aggressive updates already in for linear models. For all of these reasons, the models in this paper should provide a useful addition to the practitioner's toolbox.
These models also raise several questions that are deserving of further theoretical study. Many formal results are available for passive-aggressivy learning of linear classifiers, including regret bounds on the cumulative number of mistakes [3]. It remains to show whether these bounds can be transferred to DoS classifiers. It would also interesting to derive some sort (Lorentzroon?) convergence theorem for the realizable setting.
In pursuing this work, realize that any technological advance carries the risk of negative societal impacts. There may be settings (c.g., battlefields, markets, networks) where better online algorithms could be exploited by adversaries overcome static or slowly evolving defenses. More generally, any classifier of sensitive data can be misapplied, deployed with bias, or deliberately put to misuse 777.79]. By raising awareness of these negative impacts, however, we can hope to forestall them.
We conclude by observing that the fields of machine learning and optimization are inextricably linked. The simplest linear models 880 are powered by least-squares methods and singular value decompositions 72). With extra machinery, these models can be made more robust 883 interpretable [86] even extended nonlinear settings [87] these generalizations
often formulated as convex quadratic or semidefinite programs [88]. In machine learning as a whole, optimizations that once seemed exotic are now commonplace. In the study of passive-aggressive learning algorithms, this paper has found a role for nonconvex but tractable QCQPs. It seems likely that other useful models, yet to be formulated, can benefit from these methods.
Acknowledgements
We are grateful to the anonymous reviewers and NeurlPS area chairs for numerous suggestions to improve this manuscript. The paper's experiments performed the Triton Shared Computing Cluster (TSCC) at UC San Diego and supported by an allowance from the author's home department.
Funding Transparency Statement
There was funding in direct support of this work, and the author did not have financial relationships with entities that could be perceived to influence the contents of this paper.
10

---

References
[1] L. Bottou and Y. LeCun. Large scale online learning. In S. Thrun, L. Saul, and B. Schölkopf, editors, Advancey in Neural Information Processing Systems 16, pages 217-224. MIT Press. 2004.
[2] N. Resa-Bianchi and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006,
[3] K. Crammer, O. Dekel, J. Keshet, S. Shalev-Shwartz, and Y. Singer. Online passive-aggressive algorithms. Journal of Machine Learning Research, 7:551-585, 2006.
M. A. Aizerman, É. M. Braverman, and L. I. Rozonoér. Theoretical foundations of the potential function method pattern recognition learning. Automation and Remote Control, 25:821-837, 1964.
V. N. Vapnik. Statistical Learning Theory. Wiley, 1998.
B. Schölkopf and A. Smola. Learning with Kernels: Support Vector Machines, Regularization, Opti- mization and Beyond. MIT Press, 2001.
[7] G. Loosli, S. Cani, and L. Bottou. Training invariant support vector machines using selective sampling. In L. Bottou, O. Chapelle, D. DeCoste, and J. Weston, editors, Large Scale Kernel Machines, pages 301-320 MIT Press, 2007.
[8] Lu, S. C. H. Hoi, J. Wang. P. Zhao, and Z.-Y. Liu. Large scale online kernel learning. Journal of Machine Learning Research, 17(47):1 1-44)) 2016.
[9] K. Crammer, J. Kandola, and Y. Singer. Online classification on a budget. In S. Thrun, L. K. Saul, and
B. Schölkopf, editors, Advances in Neural Information Processing Systems 16, pages 225-232. MIT Press, 2004.
[10] J. Weston, A. Bordes, and L. Botton. Online (and offline) even tighter budget. In Proceedings of the Sth International Conference Al and Statistics (AISTATS-05), pages 413-420, 2005.
[11] G. Cavallanti, N.Cesa-Bianchi, and C. Gentile. Tracking the best hyperplane with simple budget perceptron, Machine Learning, 69(2):143-167, 2007.
[12] O. Dekel, S. S.-Shwartz, and Singer. The forgetron: kernel-based pereeptron on a budget. SIAM Journal on Computing, (7(5))1342-13333 2008.
[13] F. Orabona, Keshet, and Caputo. Bounded kernel-based online leamming. Journal of Machine Learning Research, 10(9)):2643-22) 2666, 2009.
[14] Z. Wang, K. Crammer, and S. Vucetic. Breaking the curse of kernelization: Budgeted stochastic gradient descent for large-scale SVM training. Journal of Machine Learning Research, 13(100))310333131 2012.
[15] Z. Wang and S. Vucetic. Online sussive-aggressive algorithms on a budget. In Proceedings of the 13th International Conference on Al and Statistics (AISTATS- 10), pages 998-915,7 2010.
[16] J. Lu, P. Zhao, and S. C. H. Hoi. Online sparse passive aggressive learning with kemels. In Proceedings of the 2016 SIAM International Conference Data Mining (SDM-16), pages 675-683, 2016.
[17] C.-H. Wu, H. H.-S. Lu, and H.-M. Hang. Budgeted passive-aggressive learning for online multiclass classification. IEEE Access, 8:227420-201 2274372 2020.
[18] S. Rendle. Factorization machines. In Proceedings of the IEEE International Conference on Data Mining, pages 995-1000. IEEE, 2010.
[19] S. Rendle. Factorization machines with libfm.. ACM Transactions Intelligent Systems and Technology (TIST), 3(3) 2012.
[20] R. Livni, S. Shalev-Shwartz, and O. Shamir. On the computational efficiency of training neural networks. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 27, pages 855 864. Curran Associates, Inc., 2014.
[21] M. Blondel, M. Ishihata, A. Fujino, and N. Ueda. Polynomial networks and factorization machines: New insights and efficient training algorithms. In Proceedings of the 33rd International Conference on Machine Learning (ICML-16), pages 850-858, 2016.
[22] G. E. Hinton, A. Krizhevsky, and S. D Wang. Transforming auto-encoders. In Proceedings of the International Conference Artificial Neural Networks (ICANN-II), pages 44-51. 51. Springer, 2011.
11

---

[23] S. Sabour, N. Frosst. and G. E. Hinton. Dynamic routing between capsules. In I. Guyon, U. V. Luxburg.
S. Bengiio, H. Wallach, R. Fergus, S. Vishwanathan, and Garnett, editors, Advances in Neural Information Processing Systems 30. pages 3856-3866. Curran Associales, Inc., 2017.
[24] F. Rosenblatt. The perceptron: A probabilistic model for information storage and organization in the brain. Psychological Review, 65:386-49P 407, 1958.
[25] A. B. J. Novikoff. On convergence proofs perceptrons. In Proceedings of the Symposium the Mathematical Theory of Automata, volume XII, pages 615-622, 1962.
[26] N. Littlestone. Mistake bounds and logarithmic linear-threshold learning algorithms. PhD thesis, UC Santa Cruz, 1989.
[27] J. Kivinen and M. Warmuth. Exponentiated gradient versus gradient descent for linear predictors. Informa- tion and Computation, 132(1):1 64, 1997.
[28] Y. Freund and R. E. Schapire. Large margin classification using the perceptron algorithm. Machine Learning, 37:277-296 1999.
[29] C. Gentile. A new approximate maximal margin classification algorithm. Journal of Machine Learning Research, 2:213-242, 2001.
[30] M. Herbster. Learning additive models online with fast evaluating kernels. In Proceedings of the 14th Annual Conference on Computational Learning Theory, pages 444 460, 2001.
[31] J. Kivinen, A. J. Smola, and R. C. Williamson. Online learning with kernels. IEEE Transactions on Signal Processing. 52(8):2165 2176, 2002.
[32] Y. Li and P. M. Long. The relaxed online maximum margin algorithm. Machine Learning, 46(1-3):311-387, 2002.
[33] K. Crammer and Y. Singer. Ultraconeevvative online algorithms for multiclass problems. Journal of Machine Learning Research, 3:951-991, 2003.
[34] B. Li, P. Zhao, S. C. H. Hoi, and V. Gopalkrishnan. PAMR: Passive aggressive mean reversion strategy for portfolio selection. Machine Learning, 87(2):221-255 258, 2012.
[35] M. Blondel, Y. Kubo, and N. Ueda. Online gassive-aggreste algorithms for nonnegative matrix fac- torization and completion. Proceedings of 17th International Conference on Al and Statistics (AISTATS-14) pages 96-104, 2014.
[36] J. Lu, P. Zhao, and S. C. H. Hoi. Online passive-aggressiee active learning. Machine Learning, 103:141- 183, 2016.
[37] Y. Juan, Y. Zhuang, W.-S, Chin, and C.-J. Lin, Field-aware factorization machines for CTR prediction. In Proceedings of the 10th ACM Conference on Recommender Systems (RecSys- 16)), pages 43-50, 2016.
[38] Y. Juan. D. Lefortier, and O. Chapelle. Field-aware factorization machines in real-world online advertising system. In Proceedings of the 26th International Conference on World Wide Web Companion, pages 680-688, 2017.
[39] Y. Sun, J. Pan, A. Zhang, and A. Flores. Fm2: Field-matrixes factorization machines for recommender systems. In Proceedings of the Web Conference (WWW-21), pages
2021.
[40] M. T. Bahadori. Spectral capsule networks, 2018. Workshop at the International Conference Learning Representations (ICLR-18).
[41] K. Duarte. Y. Rawat, and M. Shah. Videocapsulenet: A simplified network for action detection. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi and R. Gamett, editors, Advances in Neural Information Processing Systems 31, pages 7610-7619. Curran Associates, Inc., 2018
[42] G. E. Hinton, S. Sabour, and N. Frosst. Matrix capsules with EM routing. In Proceedings of the International Conference on Learning Representations (ICLR- 18), 2018
[43] Dilin Wang and Qiang Liu. An optimization view on dynamic routing between capsules, 2018, Workshop at the Interaatinnal Conference on Learning Representations (18L
12

---

[44] L. Zhang, M. Edraki, and G.-J. Qi. Cappronet: Deep feature learning via orthogonal projections onto capsule subspaces. In S. Bengio. H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Prucessing Syxtems 31. pages 5814-5823. Curran Associates, Inc., 2018.
[45] K. Ahmed and L. Torresani. STAR Caps: Capsule networks with straight-through attentive routing. In STAR-Caps:
H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché Buc, F. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 9101-911 10. Curran Associates, Inc., 2019.
[46] T. Hahn, M. Pyeon, and G. Kim. Self-routing capsule networks. In H. Wallach, H. Larochelle, A. Beygelz- imer, F. d' Alché Buc, E. Fox, and R. Gareett, editors, Advances in Neural Information Processing Systems 32, pages 7658-7667. Curran Associates, Inc., 2019.
[47] T. Jeong, Y. Lee, and H. Kim. Ladder capsule network. In Proceedings of the 36th International Conference on Machine Learning (ICML-19), pages 3071-3079, 2019.
[48] A. Kosiorek, S. Sabour, Y. W. Tch, and G. E. Hinton. Stacked capsule autoencoders. In H. Wallach, H. Larochelle, A. Beygelzimer. F. d' Alché Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 15512 15522. Curran Associates, Inc., 2019.
[49] Zhang Xinyi and Lihui Chen. Capsule graph neural network. In Proceedings of the International Conference on Learning Representations (ICLR-19), 2019.
[50] Y. Qin, N. Frosst, S. Sabour, C. Raffel, G. Cottrell, and G. E. Hinton. Detecting and diagnosing adversarial images with class-conditional capsule reconstructions, In Proceedings of the International Conference on Learning Representattons (ICIR-20), 2020.
[51] Y.HH. H. Tsai, N. Srivastava, H. Goh, and R. Salakhutdinov. Capsules with inverted dot-product attention routing, In Proceedings of the International Conference on Learning Representations (ICLR-20), 2020.
[52] S. R. Venkataraman, S. Balasubramanian, and R. R. Sarma. Building deep equivariant capsule networks. In Proceedings of the International Conference Learning Representations (ICLR-20) 20), 2020.
[53] L. K. Saul, An EM algorithm for capsule regression. Neural Computation, 33(1):1944-22) 2021.
[54] G. Cybenko. Approximation by superpositions of sigmoidal function. Mathematics of Control, Signals, and Systems, 2(4):303-314, 1989.
[55] K. Hornik, Approximation capabilities of multilayer feedforward networks. Neural Networks, 4(2):251- 257, 1991.
[56] Leshno, V. Ya, A. Pinkus, and S. Schocken. Multilayer feedforward networks with a nonpolynomial activation function can approximate any function, Neural Networks, 666):861-867, 1993.
[57] A. Pinkus. Approximation theory of the MLP model in neural networks. Acta Numerica, 1:143-195, 1999.
[58] E. F. Taylor and J. A. Wheeler. Spacetime Physics. W. H. Freeman, 1992.
[59] L. Dinh, R. Pascanu, S. Bengio, and Y. Bengio. Sharp minima can generalize for deep nets. In Proceedings of the 34th International Conference on Machine Learning (ICML-17), pages 1019-1028 2017.
[60] R. Bamler and S. Mandt. Improving optimization for models with continuous symmetry breaking. In Proceedings of the 35th International Conference Machine Learning (ICML-18), pages 423-432 2018.
[61] F., Feron. Nonconvex quadratic programming, semidefinite relaxations and randomization algorithms in information and decision systems. In T. F. Djaferis and I. C. Sehick, editors, System Theory, pages 255-274. Springer, 2000.
[62] Y. and S. Zhang. New results on quadratic minimization. SIAM Journal on Optimization, 14(1):245-267, 2003.
[63] Z.-Q. Luo, W.-K. Ma, A. So, Y. Ye, and S. Zhang. Semidetinite relaxation of quadratic optimization problems. IEEE Signal Processing Magazine, 27(3):20-34, 2010.
[64] S. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan. Linear Matrix Inequalities in System and Control Theory, volume 15 of Studies in Applied Mathematics. SIAM, 1994.
[65] 1. Pólik and T. Terlaky. A survey of the s-lemma. SIAM Review, 49(3):371-418, 2007.
13

---

[66] J. Park and S. Boyd. General heuristics for nonconvex quadratically constrained quadratic programming. 2017. arXiv preprint 1
[67] J. J. Moré. Generalizations of the trust region problem. Optimization Methods and Software, 2(3-4):189- 209, 1993.
[68] J.-M. Feng, G.-X. Lin, R.-L. Sheu, and Y. Xia. Duality and solutions for quadratic programming over single non-homogeneous quadratic constraint. Journal of Global Optimization, 54(2):275-293, 2012.
[69] J. Ma, I., K. Saul, S. Savage, and G. M. Voelker, Identifying suspicious URLs: application of large- scale online learning. In Proceedings of the 26th Annual International Conference Machine Learning (ICML-09), pages 681-688, 2009.
[70] O. Shamir and T. Zhang. Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes. Proceedings of 30th International Conference on Machine Learning (ICML-13), pages 71-79, 2013.
[71] P. H. Schönemann. generalized solution the orthogonal procrustes problem. Psychometrika, 31:1-10. 1966.
[72] R. Horn and C. R. Johnson. Matrix Analysis. Cambridge University Press, 2012.
[73] Y. LeCun, L. Bottou, Y. Bengio, and Haffner. Gradient-based learning applied document recognition. Proceedings of the IEEE, 86(1 (6(11)22278-324 1998.
[74] C. Liu, T. Zhang, P. Zhao, J. Zhou, and J. Sun. Locally linear factorization machines. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI-17), pages 2294-2300, 2017.
[75] D. B. Rubin and D. T. Thayer. EM algorithms for ML. factor analysis. Psychometrika, 47(1):69-76, 1982.
[76] D. Bartholomew, M. Knott, and I. Moustaki. Latent Variable Models and Factor Analysis: A Unified Approach. Wiley, 2011.
[77] J. Buolamwini and T. Gebru. Gender shades: intersectional accuracy disparities in commercial gender classification. Proceedings of the 1st Conference on Fairness, Accountability and Transporency (FACCT- 18), pages 77-91, 2018
[78] Raji. Gebru, M. Mitchell, J. Buolamwini, Lee, Denton. Saving face: investigating the ethical concerns of facial recognition auditing. In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society (AIES-20), pages 145-151, 2020.
[79] R. Berk, H. Heidari, S. Jabbari, M. Kears,, and A. Roth. Fairness in criminal justice risk assessments: the state of the art. Sociological Methods & Research, 30(1):3-44, 2021.
[80] S. Weisherg. Applied Linear Regression. Wiley, 2013.
[81] Hotelling. Analysis of complex of statistical variables into principal components. Journal of Educational Psychology, 24:417-441 1933.
[82] Jolliffe, Principal Component Analysis. Springer, 2002.
[83] C. Cortes and V. Vapnik. Support- networks. Machine Learning, 20:273 297, 1995.
[84] A. J. Smola and B. Schölkopf. A tutorial on support vector regression. Statistics and Computing. 14:19 1491992222, 2004.
[85] E. J. Candes, X. Li, Y. Ma, and J. Wright. Robust principal component analysis? Journal of the ACM, 58(3):1 37, 2009.
[86] R. Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society Series B, (8())2267-888 1996.
[87] K. Q. Weinberger and I.. K. Saul. Unsupervised learning of image manifolds by semidefinite programming. International Journal of Computer Vision, 70:77-90, 2006.
[88] S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
14


Reviews:
[{"review_id": "R4ZElTeMltc", "reviewer": "Reviewer_Tg7a", "summary": "In the setting of online learning, this paper investigates difference-of-squares models with the aim of devising conceptually simple and efficient passive-aggressive algorithms. Starting from the background on online passive-aggressive linear classification, the authors present the difference-of-squares model, by highlighting its symmetries. For this model, the update step and the averaging step are justified in detail. Experimental results on the InfiMinst dataset corroborate the interest of this quadratic passive-aggressive approach, especially in comparison with the standard, linear approach.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, this paper is very well-written, well-motivated, and well-organized. The key issues related to the nonconvexity and over-parameterization of difference-of-squares models are examined in detail, and the solutions are elegant. Finally, the (preliminary) experimental results look promising. \n \nI have only minor comments, in order to further improve this paper:\n* In the Supplementary Material, it would be nice to provide more details about the “S-procedure” used to solve the nonconvex QCQP problem (16). \n* At the end of Section 3.4, it would be relevant to give a brief comment about the runtime complexity of the three-step model averaging method (I think that it is dominated by the computation of singular value decompositions). \n* As indicated by the authors, the lack of regret analysis is a limitation. To this point, I think that they are two main directions of research: mistake-bounds in the realizable case (i.e. the “Lorentztron” analysis), and regret-bounds in the agnostic case (involving the choice of an appropriate surrogate loss for such difference-of-squares models).\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, most of the limitations of this study have been pointed out by the authors. Societal impacts are not applicable in the present context.", "review_text": "", "extra_scores": {"ethical_concerns": "Not Applicable.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "QUnjGQ_jtMi", "reviewer": "Reviewer_15ax", "summary": "The authors proposed a low rank model for quadratic classification formulated as a neural network, which they called Difference-of-Squares (DoS). Albeit not a universal approximator, such as neural networks, the proposed model can compete with any fully quadratic classifier. The ablation study involved using the INFIMNIST dataset and the DoS model was compared against a linear classifier. There has also been a bizarre outcome presented, i.e. linear model outperforming the DoS with dimensionality=1. Many thanks to the authors for mentioning this and being honest that they do not know why this is happening.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The DoS model authors presented is based on a neural net formulation albeit \"constrained\" to a quadratic classification. The mathematical formulation of the problem has been robust and detailed and has clearly reflected upon the symmetries of the model in that the decision boundary and confidence scores only depend on its parameters through the difference U^TU-V^TV. This implies that the model is invariant to orthogonal transformations and also invariant to Lorentz transformations.\nFurthermore, the learning process considers a passive-aggressive updates for online learning whereby the labelled examples arrive one at a time. The purpose is the model parameters/weights to be updated at a Δ that is enough to classify the initially wrongly classified point.\n\nAlthough the approach is convincing the experimental setup is slightly lacking, not only in terms of datasets considered but on how it has been presented. For instance, would worse results for d=1 for DoS be evidenced across other datasets too? This would have allowed to check the consistency of the outputs beyond one dataset (this is just a limitation not a deal-breaker).\n\nPerhaps a table would have helped to summarise the main findings and be more reflective on the importance of the findings. I think the conclusion could be split into another section \"Discussion\" as it is currently too long and it contains discussion either way.\n\nLastly, I was hooked initially that the paper will have some associations with Capsule Networks, but I ended up wondering, what has the purpose been of mentioning them? Just their viewpoint invariant capabilities?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I have mentioned the limitations above. I think they mainly refer to the experimental setup, conclusion/discussion and mentioning capsule networks but not being more specific.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}, {"review_id": "5UpIYY-6nf", "reviewer": "Reviewer_ymSV", "summary": "Passive Aggressive Algorithms are a very important class for algorithms for large-scale learning. This paper makes some modeling contributions. ", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Passive Aggressive Algorithms are a very important class for algorithms for large-scale learning. These are not very popular but recently there has been a lot of activity to improve and extend these models. The present paper extends these ideas to nonlinear models without taking recourse to Kernels. Instead, their work is motivated by capsule networks for visual object recognition. I liked the motivation and problem formulation. While the authors claim that their work contributes to understanding low-rank models for quadratic classification and provide a \"natural bridge between purely linear and fully quadratic classifiers\", I don't see why this work is significant in the absence of any theoretical results. Further experimental results are very limited and unless otherwise, they compare results with other online algorithms it is very difficult to make sense of these. Also, the computational costs involved in this too not very clear. I should say that the passive-aggressive update that the authors derived is pretty neat. But so what? After all this, there are no theoretical insights? At least some bounds on the cumulative loss of the algorithms? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "There are no ethical concerns. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4.5 hours"}, "extra_text": {}}, {"review_id": "4e1e5y7sZSZ", "reviewer": "Reviewer_HDQ3", "summary": "The paper investigates a family of low-rank models for quadratic classification inspired by so-called capsule networks for visual object recognition. For models in this family, it shows how to derive passive-aggressive updates by solving a quadratically constrained quadratic program (QCQP).", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I am not an expert on online learning so I cannot evaluate the significance of this work. But the methods proposed here look useful to me.  A potential drawback of this work is that the authors only validate their method on a single dataset. Therefore, I am not sure the approach proposed here generalizes well to other datasets. I, therefore, refer to other reviewers on the evaluation of the significance of this work.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See my comments in \"Main Review\".", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper introduces a new  passive-aggressive algorithms where the hypothesis function is a difference of squares (quadratics). Previously, only linear models had been considered with the passive-aggressive framework. The resulting model is non-convex, but tractable, since the authors show the model parameters can be updated using a 1-dimensional convex optimization problem over the interval (0, 1).  The authors then study the symmetries in the resulting model, and develop a specialized averaging scheme which is non-trivial given nonlinear manifold for which the model presents. These are the strengths of the paper, and I believe that the ideas present in the paper on using difference of squares models, extending the passive-aggressive framework to new model and averaging will be useful and interesting to the community.

The paper has some weakness for which I would like to see the authors make some small adjustments for the camera ready:
1) A lack of mention of comparison to other quadratic based models. As such, I would kindly request the authors to also mention factorization machines, and other related quadratic models. 
2) Insufficient numerics. Currently the numerics compare the DoS (difference of squares) model to a linear model, and ultimately show the DoS model is more expressive, without overfitting. There are also experiments highlighting the benefits on the new form of averaging. But  additional experiments that could disentangle the benefits of using DoS model, from the passive-aggressive framework, and also contrast to other quadratic models (such a factorization machines) would really enrich the paper. So I kindly request that the authors consider including some additional numeric insights along these lines in the camera ready paper.
3)  The authors also highlight how the DoS model can interpolate data, and thus this could be used as a simple case study for the interpolation of DNNs. But no details, or hints as to how or why this makes sense were developed. Perhaps the authors could tone down this claim? 

Finally, the reviews where divided on the paper, but ultimately the reviewers in favor raised more concrete points, which after my own reading of the paper I agreed with.
Decision: Accept (Poster)