{'fraction_non_alphanumeric': 0.037868436463009955, 'fraction_numerical': 0.012687878196369315, 'mean_word_length': 4.421375661375661, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 2, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Projective Quadratic Regression for Online Learning

This paper considers online convex optimization (OCO) problems - the paramount framework for online learning algorithm design. The loss function of learning task in OCO setting is based on streaming data so that OCO is a powerful tool to model large scale applications such as online recommender systems. Meanwhile, real-world data are usually of extreme high-dimensional due to modern feature engineering techniques so that the quadratic regression is impractical. Factorization Machine as well as its variants are efficient models for capturing feature interactions with low-rank matrix model but they can't fulfill the OCO setting due to their non-convexity. In this paper, We propose a projective quadratic regression (PQR) model. First, it can capture the import second-order feature information. Second, it is a convex model, so the requirements of OCO are fulfilled and the global optimal solution can be achieved. Moreover, existing modern online optimization methods such as Online Gradient Descent (OGD) or Follow-The-Regularized-Leader (FTRL) can be applied directly. In addition, by choosing a proper hyper-parameter, we show that it has the same order of space and time complexity as the linear model and thus can handle high-dimensional data. Experimental results demonstrate the performance of the proposed PQR model in terms of accuracy and efficiency by comparing with the state-of-the-art methods.


Introduction
In the setting of online learning, the training data arrive in a streaming fashion and the system should provide a response immediately. Specifically, online learning is performed in a sequence of consecutive rounds indexed by time t. At round t, the learner updates a learning variable using simple calculations that are usually based on a single sample only. Online learning is a powerful tool for a wide range of applications such as online rating, news feeding, and ad-click prediction. The paramount framework for online learning is online convex optimization (OCO) (Hazan 2016;Shalev-Shwartz 2012) which can be solved by many stateof-the-art online optimization algorithms such as Online Meanwhile, in real-world applications, the feature dimension could be extremely high. Therefore, traditional linear models are still the most popular model in such scenario. However, linear models fail to utilize the interaction between features so that lots of artificial feature engineering work is needed. Quadratic regression captures first-order information of each input feature as well as second-order pairwise feature interactions. However, it is usually unacceptable in terms of space complexity when dealing with high-dimensional data because the model size is of order O(d 2 ) with d-dim features. Factorization Machine (FM) (Rendle 2010) is an efficient mechanism for capturing up to second-order feature information with a low-rank matrix in factorized form. It only needs O(md) space with rank m. FM achieves state-of-the-art performance in various applications (Juan, Lefortier, and Chapelle 2017;Li et al. 2016;Lu et al. 2017;Nguyen, Karatzoglou, and Baltrunas 2014;Rendle et al. 2011;Zhong et al. 2016;Chen et al. 2019b;2019a) and has recently regained significant attention from researchers (Blondel et al. 2016a;2016b;He et al. 2017;Xu et al. 2016). Unfortunately, the vanilla FM (Rendle 2010) and its variants (Blondel et al. 2016a;Cheng et al. 2014;Juan, Lefortier, and Chapelle 2017;Lu et al. 2017) are nonconvex formulations and unable to fulfill the fundamental requirements demanded in OCO. Several convexified FM formulations (Blondel, Fujino, and Ueda 2015;Lin et al. 2018;Yamada et al. 2017) are proposed to address this weakness but the computation cost is high and thus impractical in highdimensional problems.
The above formulations are all based on the low-rank assumption of the feature-interaction matrix and thus to reduce the number of learning variables. However, the question is whether we really need the low-rank assumption? Is there any other way to save parameters? Our answer is that we don't need the low-rank assumption and we can save param- This intuition is based on our observation that the frequencies of different features occurring in real-world datasets vary a lot. For instance, figure 1 shows the numbers of occurrences of different features in two public datasets, i.e. MovieLens 1 and Avazu 2 respectively. It is shown that a large number of features scarcely occur in the datasets, while only a few features frequently occur. So we separate the features into two categories: high frequent features and low frequent features. We assume that the high frequent features are more important so that their interaction are more valuable. To this background, we propose a Projective Quadratic Regression (PQR) model. Specifically, for high frequent features, we adopt the full quadratic form. Within low frequent features, we just ignore their interactions. We then use a set of sharing parameters for high and low frequent feature interactions. In fact, we can rewrite the global bias, the feature weight vector and the feature interaction matrix into an augmented symmetric matrix. The intuiton of sharing parameters we mentioned above is equivalent to restricting the feasible set to be a subset of symmetric matrices. We show that the feasible set are actually convex and then satisfy the first requirement of OCO. Then we rewrite the loss function into a convex function with respect to the augmented matrix and thus fulfill the second requirement of OCO. Based on this scheme, the resulting formulation of PQR can seamlessly meet the aforementioned requirements of the OCO framework. Moreover, due to its convexity, most optimization algorithms such as FTRL can be directly applied to PQR model and theoretical analyses such as regret bounds and convergence rates are still valid. In addition, by choosing a proper hyper-parameter, this kind of matrices can be rep-1 https://grouplens.org/datasets/movielens/ 2 https://www.kaggle.com/c/avazu-ctr-prediction/data resented by O(d) parameters so that it has the same space complexity with linear models.
We conduct extensive experiments on real-world datasets to evaluate the empirical performance of PQR. As shown in the experimental results in both online rating prediction and online binary classification tasks, PQR outperforms state-ofthe-art online learning algorithms in terms of both accuracy and efficiency, especially for high-dimensional problems.

Contribution
• PQR model captures first-order feature information as well as second-order pairwise feature interaction. It is a convex formulation so that it fulfills the requirements of online convex optimization setting and the optimal solution is theoretically guaranteed.
• Optimization algorithms for convex models can be applied directly to PQR and all the theoretical analyses are still valid.
• PQR is a general framework and can be applied to many other tasks such as batch and stochastic settings besides online learning.
• PQR is efficient in terms of space complexity and computation cost. It has the same order of space and time complexity with linear model with a proper hyper-parameter.
• We evaluate the performance of the proposed PQR model on both online rating prediction and online binary classification tasks. Experimental results show that PQR outperforms state-of-the-art online learning methods.

Method
In this section, we first introduce preliminaries in online learning and then turn to the development of the proposed projective quadratic regression (PQR) model for online convex problem. The PQR model is essentially a quadratic regression model with a constraint on the feasible set. The idea behind this model is sharing parameters. We prove the convexity of PQR so that it fits into the online learning setting and state-of-the-art online optimization algorithms can be applied directly.

Online Convex Optimization
The online learning algorithms are built upon the assumption that the training instances arrive sequentially rather than being available prior to the learning task. The paramount framework for online learning is Online Convex Optimization (OCO) (Hazan 2016;Shalev-Shwartz 2012). It can be seen as a structured repeated game between a learner and an adversary. At each round t ∈ {1, 2, . . . , T }, the learner is required to generate a decision point θ t from a convex set S ⊆ R n . Then the adversary replies to the learner's decision with a convex loss function f t : S −→ R and the learner suffers the loss f t (θ t ). Specifically, the online learning setting can be described as follows.
For index t = 1, 2, . . . , T , the learner chooses learning parameters θ t ∈ S, where S is convex. Then the environment responds with a convex function f t : S −→ R and the output of the round is f t (θ t ).
The regret is defined by The goal of the learner is to generate a sequence of decisions {θ t |t = 1, 2, . . . , T } so that the regret with respect to the best fixed decision in hindsight is sub-linear in T , i.e. lim T →∞ regret T /T = 0. The sub-linearity implies that when T is large enough, the learner can perform as well as the best fixed decision in hindsight.
Based on the OCO framework, many online learning algorithms have been proposed and successfully applied in various applications (DeMarzo, Kremer, and Mansour 2006;Li and Hoi 2014;Zhao and Hoi 2013). Follow-The-Regularized-Leader (FTRL) (McMahan et al. 2013) is one of the most popular online learning algorithms, which is summarized in Algorithm 1 and the regret bound of FTRL is shown in Theorem 1 (Hazan 2016).

Algorithm 1: Follow-The-Regularized-Leader
Input: η > 0, regularization function R, and convex set S Theorem 1. The FTRL Algorithm 1 attains the following bound on regret If an upper bound on the local norms is known, i.e. ||g t || F ≤ G R for all time t, then we can further optimize over the choice of η to obtain

Quadratic Regression
The general quadratic regression is a combination of linear model with pairwise feature interaction. Given an input feature vector x ∈ R d , the predictionŷ can be obtained with the following formula: where b ∈ R is the bias term, w is the first-order feature weight vector and A ∈ R d×d is the second-order feature interaction matrix. Clearly we only need the upper triangle of the matrix so that we can assume the matrix is symmetric, i.e., A = A T ∈ R d×d . Then we rewrite the bias term b, the first-order feature weight vector w and the second-order feature interaction matrix A into a single matrix C: Therefore, the predictionŷ can be represented by a quadratic form with extended feature vectorx = (x T , 1) T . In fact, we can define the quadratic regression model bŷ where S is the set of all (d+1)×(d+1) symmetric matrices. Clearly,ŷ is linear and thus convex in C. Under this setting, we can show that the composition of any convex function and the quadratic regression form is still convex in C. Actually we have Proof. Consider λ ∈ [0, 1] and C 1 , C 2 ∈ K. By the convexity of K, C = λC 1 + (1 − λ)C 2 ∈ K. Then by the linearity ofŷ and convexity of f , we have

Projective Quadratic Regression
The major problem of quadratic regression is that the feasible set contains all symmetric matrices which is too large and impractical in real-world applications. Existing formulations are usually based on the low-rank assumption. The vanilla FM is just decomposing the matrix into a product of a low-dimensional matrix and its transpose. But this formulation makes it a non-convex model. Several convexified FM formulations (Lin et al. 2018;Yamada et al. 2017) are based on the same assumption and adding low-rank constraint by restricting the nuclear norm of the candidate matrix. However, it introduces operations such as singular value decomposition and the overall computation cost is actually high and thus it is impractical in real applications with large and high-dimensional datasets.
The main idea of our proposed projective quadratic regression model is to restrict the feasible set to a subset of symmetric matrices. It is not based on low-rank assumption but the intuition of sharing parameters. This is based on the assumption that the frequencies of different features occurring vary a lot as shown in Figure 1. We then separate the features into two categories: high frequent features and low frequent features. We assume that the high frequent features are more important so that their interaction are more valuable. Therefore, for high frequent feature interactions, we adopt the full quadratic form. And within low frequent features, we just ignore their interactions. Finally, we use a set of sharing parameters for high and low frequent feature interactions.
We denote I = {1, 2, . . . , d} as the index set of all features where d is the dimension of the feature space. The separation of high and low frequent features can be defined as follows.
Definition 1. A feature separation is a bi-partition of index set I, i.e., where H is the set of indices of all high frequent features while L for low frequent features.
In practice, we have various ways to separate the high and low frequent features. For example, we can sample the training data and calculates the features counts. Then we can choose the top-k features as the high frequent features and the rest as low frequent features. Another way may be setting a threshold, any feature whose occurrence is greater than the threshold can be considered as a high frequent feature, and otherwise a low frequent feature. In this paper, we use the top-k method where k is a hyper-parameter and can be called the order of the model. After separating the indices, i.e., I = H ∪ L, the key idea of PQR is using the following matrix to catch feature interactions: where p i,j and q i are learning parameters.
Definition 2. Given a separation I = H∪L, the matrix with the form in (7) can be called a PQR matrix with respect to this separation. The PQR matrix can be denoted as A (H,L) .
Let us assume that the size of H is k, i.e., |H| = k. So |L| = d − k. Without losing generality, if we assume H = {1, 2, . . . , k} and L = {k + 1, k + 2, . . . , d}, then the matrix looks like in Figure 2. We can easily see that there are 1 2 k(k +1) learning parameters for the PQR matrix. Combining with the linear part of the model, the space complexity of learning parameters is of the order O(k 2 + d). In particular, if we choose k in the order of O( √ d), the PQR model have the same order of computation cost as linear models. The computation cost is summarized in Table 1.
Now we can show that the PQR model fulfills the OCO framework. For a given separation I = H ∪ L, Let where A (H,L) is the PQR matrix. We then have

Proposition 3. T (H,L) is a convex set for any separation
Proof. It is easy to verify that T (H,L) is closed under addition and scalar multiplication. By the definition of convex set, T (H,L) is convex.
Now we define our projective quadratic regression model (PQR) as a quadratic regression model with restriction the feature-interaction matrices to be the PRQ matrices. In summary, the proposed PQR model can be represented bŷ

s.t. C ∈ T (H,L)
By Proposition 2 and 3, we can see that PQR model (9) fulfills the OCO setting.
Examples There are two important examples: online rating prediction and online binary classification.
In the online rating prediction task, at each round, the model receives a pair of user and item sequentially and then predicts the value of the incoming rating correspondingly. Denote the instance arriving at round t as (u t , i t , y t ), where u t , i t and y t represent the user, item and the rating (a number from 1 to 5) given by user u t to item i t . The user feature and item feature (still denoted by u t and i t to save notation) can be represented by a concatenation of one-hot vectors. The input feature vector x t is constructed as a concatenation of u t and i t . Upon the arrival of each instance, the model predicts the rating withŷ t = 1 2x t Cx t , wherex t = [x T t , 1] T . The convex loss function incurred at each round is the squared loss: The online binary classification task is usually applied to the click-through-rate (CTR) prediction problem. In this task, the instances are denoted as (x t , y t ) indexed by t ∈ [1, 2, . . . , T ], where x t is the input feature vector and y t ∈ {−1, 1} is the class label. At round t, the model predicts the label with sign(ŷ t ) = sign( 1 The loss function is a logistic loss function: Implementation Details We first calculate the separation I = H ∪ L. We can achieve this by sampling the data, calculating the feature counts and selecting top-k features as H and the rest as L. Then we find that PQR model is actually a set of rules to cross features. If x is a feature vector, we can Actually we have the following definition. Definition 3. Given a feature vector x and a separation I = H ∪ L, the vectorx defined in (12) is called the PQR expansion of x. Therefore, the PQR model on a dataset is essentially equivalent to the linear model with respect the associated PQR expansions of this dataset. We list the implementation detail of online rating and online binary classification in Algorithm 2 by following the FTRL-Proximal algorithm in (McMahan et al. 2013).
More Explanation on PQR Like vanilla FM, the idea behind the PQR model is matrix factorization. In fact, the PQR matrix with respect to I = H ∪ L, can be considered as a decomposition in the following form where P is (k + 1) × d matrix and M is a (k + 1) × (k + 1) matrix. M is symmetric and its diagonals are zeros. Namely, M i,j = M j,i and M i,i = 0. So it has 1 2 k(k + 1) parameters which represents the feature-interaction learning parameters. The matrix P is a projection matrix which maps the original feature vector into a lower dimensional space. Specifically, P x is a permutation of where i l ∈ H with l = 1, 2, . . . , k and x L = j∈L x j .
The key idea is that the projection matrix P is determined by the separation I = H ∪ L, so we don't need to learn it. That is also the reason why we name the proposed model as projective quadratic regression model.

Related Work
Vanilla FM The vanilla Factorization Machine (Rendle 2010) defines the interaction matrix A = V V T where V is a d×m matrix with m d and optimized on thin matrix V . It considers both the first and the second order information of features and learns the feature interactions automatically. It yields state-of-the-art performance in various learning tasks and its space complexity and computation cost are acceptable. However, it is a non-convex formulation and cannot fit into the online convex optimization setting. Moreover, the global optimal solution is not guaranteed by gradient based optimization algorithms. The bad local minima and saddle points may affect the performance and it is difficult to study how to select a good initial point theoretically.
CFM The Convex FM (CFM) introduced by Yamada et al. (Yamada et al. 2017) is a convex variant of the widely used Factorization Machines. It employs a linear + quadratic model and regularizes the linear term with the l 2 -norm and the quadratic term with the nuclear norm. It outperforms the vanilla FM on some applications. However, it is impractical in high-dimensional datasets due to high computation cost.
CCFM The Compact Convexified FM (CCFM) model invented by X. Lin et al. (Lin et al. 2018) is another convex model. By rewriting the bias term b, the first-order feature weight vector w and the second-order feature interaction matrix A into a single matrix C and restricting the feasible set by intersecting a nuclear ball, this formulation fits OCO setting. However, the computation cost is very high since at each iteration, a singular value decomposition operation is needed, which is unbearable in a real application.
DiFacto The Difacto introduced by M. Li et al. (Li et al. 2016) is a variant of Factorization Machines. It is not a convex model but it also use the information of frequency of feature occurrence. In DiFacto, the features are allocated embedding vectors with different ranks based on the occurrence frequency. Namely, higher frequency features corresponds to embedding vectors with larger ranks. The pairwise interaction between features with different ranks is obtained by simply truncating the embedding with high rank to a lower rank. Such truncations usually lead to worse performance. In fact, DiFacto reduces the computational burden of FM by sacrificing the performance.

Experiments
In this section, we evaluate the performance of the proposed PQR model on two popular machine learning tasks: online rating prediction and online binary classification.

Experimental Setup
We compare the empirical performance of PQR with stateof-the-art variants of FM in the online learning setting. We construct the baselines by applying online learning approaches to the existing formulations of FM: vanilla FM (Rendle 2010), CFM (Yamada et al. 2017), and DiFacto (Li et al. 2016). We also compare with LR model (linear regression of online rating prediction and logistic regression for online binary classification) since it is still popular in the high-dimensional sparse datasets. We skip CFM for highdimensional datasets due to its high computation cost. For optimization method, We apply the state-of-the-art FTRL-Proximal algorithm (McMahan et al. 2013) with 1 + 2 regularization for LR and PQR. Specifically, the implementation of PQR-FTRL can be seen in Algorithm 2. For vanilla FM, we just applied the online gradient descent with 1 regularization. To summarize, the compared models are: The vanilla FM and DiFacto are non-convex models so that we need to randomly initialize the learning parameters to escape local minimum. And results are different for each trial run. Therefore, we repeat the same experiment for 20 times. Finally, the average and standard deviation of 20 scores (RMSE, AUC or LogLoss) are reported. On the other hand, LR, CFM and PQR are convex models. So we can initialize the learning parameters as zeros (like in Algorithm-1 and Algorithm-2). As long as the input data (train/test) are the same, the output scores are the same and thus there is no need for repetition. Moreover, for PQR model, we also test different orders (k values) for each dataset.
Datasets For the online rating prediction task, we use the typical MovieLens datasets, including MovieLens-100K (ML100K), MovieLens-1M (ML1M) and MovieLens-10M (ML10M); For the online binary classification task, we select high-dimensional sparse datasets including Avazu, Criteo 3 , and KDD2012 4 . These three high-dimensional datasets are preprocessed and can be downloaded from the LIBSVM website 5 . The statistics of the datasets are summarized in Table 2. All these datasets are randomly separated into train(80%), validation(10%) and test(10%) sets. In our experiments, the training instances are fed one by one to the model sequentially.

Online Rating Prediction
We use Movie Lens datasets for this task. For ML100K and ML1M, we use gender, age, occupation, and zipcode as the user feature and the movie genre as the item feature. We perform the standard discretization, use one-hot representation for each feature, and then concatenate them together. For ML10M, since there is no demographic information of users, we just use the user ids as the user feature instead. The rank of FM is selected from the set of {2, 4, 8, 16, 32, 64, 128, 256, 512}. The coefficient of regularization term and the learning rate are tuned in a range [0.0001, 10]. We list the RMSE of all compared algorithms in Table 3. From our observation, PQR achieves higher prediction accuracy than all the baselines, which illustrates the advantage of PQR.

Online Binary Classification
In many real applications, feature vectors are usually extremely high-dimensional hence sparse representation is used instead, i.e., only nonzero key-value pairs are stored.
We demonstrate the performance of PQR as well as other approaches for this case using high-dimensional sparse datasets: Avazu, Criteo, and KDD2012. Due to the highdimensionality, CFM is impractical. So we compare PQR with LR, vanilla FM and DiFacto in two aspects: accuracy (measured by AUC and LogLoss) and efficiency (measured by training time and model size).
The rank for vanilla FM and DiFacto is selected from the set of {4, 8, 16, 32, 64}. The coefficient of regularization term and the learning rate are selected in a range of [0.0001, 10]. We list the results in Table 4. In most cases, PQR outperforms the baseline algorithms in both accuracy and efficiency. The accuracy demonstrates that PQR has better expressiveness than linear model and low-rank FM models. The efficiency illustrates the theoretical computation cost of PQR model. Finally, for FM, there is no theory about how to choose a proper rank. However, the order of PQR has a clear meaning which is good for parameter tuning.

Conclusion and Future Work
In this paper, we propose a projective quadratic regression (PQR) model under the online learning settings. It meets the requirements in online convex optimization framework and the global optimal solution can be achieved due to its convexity. In addition, we show that the computation cost of PQR can be low if we choose a suitable order. Finally, we demonstrate its effectiveness by comparing with stateof-the-art approaches. For future work, a more scientific approach to select the order for PQR is an attractive direction.