Dual Space Gradient Descent for Online Learning
One crucial goal in kernel online learning is to bound the model size. Common approaches employ budget maintenance procedures to restrict the model sizes using removal, projection, or merging strategies. Although projection and merging, in the literature, are known to be the most effective strategies, they demand extensive computation whilst removal strategy fails to retain information of the removed vectors. An alternative way to address the model size problem is to apply random features to approximate the kernel function. This allows the model to be maintained directly in the random feature space, hence effectively resolve the curse of kernelization. However, this approach still suffers from a serious shortcoming as it needs to use a high dimensional random feature space to achieve a sufficiently accurate kernel approximation. Consequently, it leads to a significant increase in the computational cost. To address all of these aforementioned challenges, we present in this paper the Dual Space Gradient Descent (DualSGD), a novel framework that utilizes random features as an auxiliary space to maintain information from data points removed during budget maintenance. Consequently, our approach permits the budget to be maintained in a simple, direct and elegant way while simultaneously mitigating the impact of the dimensionality issue on learning performance. We further provide convergence analysis and extensively conduct experiments on five real-world datasets to demonstrate the predictive performance and scalability of our proposed method in comparison with the state-of-the-art baselines.
The paper introduces a new algorithm for kernel-based online learning, where (a) the number of support vectors is controlled by discarding the least significant ones, and (b) information of the discarded support vectors is partially retained by maintaining a random projection of them in a lower-dimensional space.  Regret bounds are derived in terms of the "budget" of retained support vectors and the dimensionality of the random projections.  Experiments show that compared to previous methods, the new algorithm obtains a very good trade-off between prediction accuracy and memory use.       
The rebuttal answered all my technical questions, in particular the one about probability and expectations in Theorems 1(ii) and 3.  My scores (which were given assuming the technicalities can be fixed) remain the same.  *** Original review below ***  The algorithm is as far as I know an original and intuitively appealing combination of techniques previously introduced in this quite active subarea.  I quite like it.  The theoretical results do not feel that exciting.  The regret bounds seem more or less what one might expect, and there is no comparison to bounds for other algorithms.  I understand that there are no directly comparable bounds since you have both budget size and dimensionality of random projections as significant parameters, but still some discussion would be nice.  The dependence on budget B in your bounds could perhaps be pointed out more explicitly.  The experiments are compelling.  The relevant competing algorithms are included, and the data sets are sufficiently varied.  Detailed comments:  Algorithm 1: On line 4, you include all indices in I_t, even when alpha_t is zero.  Is this really intended?  On the other hand, b is increased only for non-zero alpha_t.  You also fail to mention where b is decreased, but it would seem if you really do this as written then the arg min in Algorithm 2 might just catch a lot of zeros and not actually free up any budget.  Theorem 1: I did not find a definition for sigma_mu in [15].  There was sigma_P where P is a distribution.  But what is mu here, anyway?  Theorem 2: "the following statement guarantees" seems wrong  line 169: "where" should be "were"?  Experiments: Is it reasonable to use the same values for hyperparameters such as B for all the algorithms?  Would it make any difference in the results if each algorithm was individually tuned?  line 232: Pegasos is not mentioned anywhere else as far as I can see  line 257, "due to additional exponential operators":  Another factor that causes more computation in Logit than in Hinge is that the gradient is always non-zero.  reference [15]: "Infomration"  Appendix, proof of Theorem 2: To get to (4) you need the previous bound to hold for all j, but if I understand correctly the current bound is just for a fixed j.  Proof of Theorem 2, last chain of inequalities: To get here you seem to need E[alpha^2 beta^2] \leq E[alpha^2] E[beta^2] , which seems intutively reasonable but would require a proof.  Similar issue appear in proof of Theorem 6 (top of page 5).  page 5, lines 7 and 8: The term with 8A^2 seems to have a factor 1/lambda missing.  Proof of Theorem 7: There is no "Lemma 2" here.  Appendix, Section 3: Your use of O notation is a bit sloppy.  In particular, from f_1 = O(g_1) and f_2 = O(g_2) one cannot conclude f_1-f_2 = O(g_1-g_2).