Enhancing Kernel Flexibility via Learning Asymmetric Locally-Adaptive Kernels

Accuracy Comparison in Regression with EigenPro3.0 and RFMs

In response to your concerns regarding accuracy improvement, as acknowledged by the first reviewer, our algorithms showcase state-of-the-art accuracy in regression tasks. Notably, our results surpass even the performance of ResNet, a benchmark for high-level regression methods in small and medium-sized datasets.

We sincerely appreciate the advanced kernel methods you recommended. To address your main concern, we have conducted an additional comparative experiment with EigenPro 3.0 and Recursive Feature Machines (RFMs).

Table1: Performance of EigenPro3.0 and LAB RBF kernels on real datasets.

In our experimental setup, we train EigenPro3.0 for 50 iterations, while RFM for 5 iterations, aligning with the parameter setting outlined in their papers. As shown in the public code, RFMs use all training data points to compute the final decision function. That is, they use all training data as the support data.

Both EigenPro3.0 and RFM exhibit excellent capabilities in managing large-size kernel models; however, their dependence on symmetric kernel formulations poses a high requirement on large number of support data. While by utilizing locally adaptive bandwidth, our algorithm can significantly reduce the requirement of support data—essentially, the model complexity—while maintaining a high level of accuracy.

Moreover, we've observed that in RFMs, they learn a matrix $M$ in a generalization of the Laplace kernel $\mathcal{K}(x_i, x_j) = \exp(-\gamma\||x_i - x_j\||_M)$, where $\||x_i - x_j\||_M = (x_i - x_j)^\top M(x_i - x_j)$. That is, the matrix $M$ is designed to capture relationships among features.

In contrast, our proposed LAB RBF kernels $\mathcal{K}(x_i, x_j) = \exp(-\||\Theta_j\odot(x_i - x_j)\||_2^2)$ and corresponding learning algorithm aim at learning locally-adaptive bandwidths for each support data. Exploring a completely different mechanism, combining these two methods in the future could prove to be intriguing

Again, we appreciate your recommendation of these advanced methods, and we are committed to incorporating this comparative experiment into the revised version of our work.

Minor issues

1. The computation at line 4 of the algorithm, specifically evaluating $f_{\mathcal{Z},\Theta}(t) = K_{\Theta} (t,X_{sv})(K_\Theta(X_{sv},X_{sv})+\lambda I_N)^{-1}Y_{sv}$ is not time-consuming, especially when the number of support data is limited. In our experiments, we directly compute this inverse due to the manageable size of the support data. We agree that existing scalability techniques, while primarily designed for symmetric kernels, can be applied here to further speed-up the computation, opening new possibilities.

2. Distinguish from Prior Works: While previous works [1][2] and our study use the same definition of asymmetric kernels, $\mathcal{K}(x,t) = \langle \phi(x), \psi(t)\rangle$, our paper introduces the first formulation of asymmetric kernel ridge regression. In contrast to previous studies focusing on PCA and least square SVM, this results in distinct stationary solutions and applications. Furthermore, prior works employ manually designed asymmetric kernels such as the Kullback-Leibler Kernel and SNE Kernels (refer to [2] for details). While these kernels exhibit good performance on asymmetric data (e.g., directed graphs), their advantage on general data is not apparent. To address this limitation, our paper proposes a novel asymmetric kernel learning algorithm, demonstrating superior performance on general data.

3. In Eq. (6), since $(K(X,X)+\lambda I)$ is a square matrix, its inverse exists as long as it is full-rank.

---

We trust that our explanation, coupled with the additional experiment, sufficiently addresses your concerns regarding both accuracy and scalability in our experiments, and we would greatly appreciate it if you could consider raising the score accordingly. We are very willing to further discuss with you on equipping current techniques to our LAB RBF kernels or any other topics that might interest you.

Thank you for your valuable suggestions and recognition of our dynamic strategy and locally adaptive bandwidths.

Scalability is not Our Contribution

First of all, we wish to emphasize our central focus, as indicated by the title. Our paper aims to explore the application of asymmetric kernel learning in regression tasks and assess its advantages over symmetric kernels, rather than concentrating on large datasets or large kernel machines.

Our main contributions lie in (i) introducing the first asymmetric KRR model and (ii) presenting a novel asymmetric kernel learning algorithm. These two techniques collectively offer a fresh approach to learn flexible asymmetric kernels in regression tasks. Current investigations into asymmetric kernels continue to face a gap in terms of interpretable regression models and efficient kernel learning algorithms, adding to the novelty of this work.

We would like to clarify what we mean by scalability in the context of this paper. The introduction of locally-adaptive bandwidths largely enhance the flexibility of RBF kernels. This allows us to significantly reduce the need for support data, and the decrease in support data consequently benefits the scalability of the model. This is also what we want to emphasis in Table 3, with the reduction being more evident in the larger datasets.

Consider that we can reduce the requirement for support data. When coupled with existing acceleration techniques, as you suggested, it becomes feasible for us to effectively manage millions of data points. The feasibility, however, hinges on the computing infrastructure and the number of support vectors, aspects beyond the scope of this paper.

It's noteworthy that a majority of current solutions for large kernel machines are founded on symmetric kernels. We believe extending their approach to accommodate asymmetric kernels would be particularly intriguing.

Nevertheless, we value your comments and will carefully revise the paper to eliminate any potential ambiguity.

Dear reviewer PWHQ,

We sincerely appreciate your understanding and recognition of our work. We are delighted that these results have boosted your confidence in our approach.

The latest version of our paper is now accessible in the OpenReview system, and we hope that this updated version meets your standards. For your convenience, here we've outlined the key modifications:

• We have removed our ambiguous statement regarding scalability. Instead, in the revised version, we emphasize that learning flexible kernels can reduce the need for support data. This reduction in support data, in turn, significantly reduces model complexity, making it more efficient to deal with large-scale datasets. Please refer to the contributions in the end of introduction on page 4, the statements at the beginning of Section 4 on page 7, and the discussion about experimental results on larger datasets in Table 3 on page 8.
• EigenPro3.0 and RFMs have been introduced as new comparative methods. Please refer to Table 1 on page 7, and Table 3 on page 8 for details.
• A discussion on incorporating current accelerating methods for kernel machines into our methods has been added. Please refer to the line 15 on page 6.
• The definitions of N and M have been incorporated. Please refer to Table 1 on page 7.
• Additional discussions on current studies of asymmetric kernels in related works. Besides, ARD and RFMs are also included in relted works. Please refer to Section 5 on page 9.

Once again, thank you for your recognition and insights. In the following days, we will continue to revise our paper according to your suggestions and those provided by other reviewers.

Thank you for your attentive reading and valuable suggestions.

Coefficient of the Error Terms in Asymmetric KRR Model

Thanks for your recognization on the novelty of our asymmetric kernel ridge regression model. We are glad that you are interested in this model. It is one of our major technical contributions to deal with asymmetric kernels on regression tasks and also provids theoretical support for subsequent asymmetric kernel learning algorithm.

To address you concern on the coefficient of the error terms, it would be better to start at the LS-SVM form of our model, i.e. the model in Eq. (7).

The objective function in Eq. (7) primarily incorporates a regularization term $w^\top v$ and a error term $\sum_{i=1}^N e_i r_i$. As most of machine learning models, these two terms are adjusted by a trade-off hyper-parameter $\lambda$ varing with different datasets.

By substituting constraints in Eq. (7) to the objective function, we obtian the model in Eq. (4), whose corresponding objective function is represented as $\lambda w^\top v + \frac{1}{2}(\phi^\top(X)w-Y)^\top(\psi^\top(X)v-Y).$To enhance clarity, we delved deeper into the interpretation of $(\phi^\top(X)w-Y)^\top(\psi^\top(X)v-Y)$, outlining it as two loss terms and one mapping function’s distinctiveness term. That is, $2(\phi^\top(X)w-Y)^\top(\psi^\top(X)v-Y) = \||\psi^\top(X)v-Y\||_2^2 + \||\phi^\top(X)w-Y\||_2^2 - \||\psi^\top(X) v - \phi^\top(X) w\||_2^2.$ Therefore, the three terms $\||\psi^\top(X) v - \phi^\top(X) w\||_2^2$, $\||\psi^\top(X)v-Y\||_2^2$, and $\||\phi^\top(X)w-Y\||_2^2$ are not independent; instead, they are integrated as a whole and thus do not require a extra hyper-parameter tuning.

Thank you for this insightful question. We will make it clearer in the revised version.

Impact of the Initial Support Data Selection

Firstly, you are correct in pointing out the significant influence of support data selection on the algorithm. In light of this, we have introduced a dynamic strategy aimed at mitigating the impact of initial support data selection.

To address your concern, we explore three different approaches to initial data selection: two rational methods (Y-based and X-based) and one irrational method (Extreme Y).

• Y-based (utilized in the manuscript): data is sorted based on their labels, and support data is uniformly selected.
• X-based: k-means is applied to the training data to identify cluster centers, followed by the selection of data points closest to these centers.
• Extreme Y: data is sorted based on their labels, and those with the largest Y values are selected.

Table1: Performance of Alg.1 with different selection of initial support data.

The results indicate that the poor selection method does have a detrimental impact on our performance, particularly evident in the case of Yacht where we struggle to fit the data. In contrast, the other two sensible methods demonstrate good and comparable performance.

In order to further improve, we introduce a dynamic strategy at the end of Section 3. In this strategy, we dynamically incorporate hard samples into the support dataset. We then integrate these approaches with the proposed dynamic strategy to evaluate its effectiveness.

Table 2: Performance of Alg.1 with dynamic strategy

Based on these results, it is evident that the proposed dynamic strategy has a significantly positive impact on performance. It not only enhances accuracy but also reduces variance, resulting in more stable solutions. Even with the bad selection selection, the final performance is improved to a satisfactory level.

Why is the Number of Support Data is so Small?

In fact, the limitation in support data is not attributed to the termination condition. Instead, the constrained support data stems from the remarkable flexibility of LAB RBF kernels. This flexibility empowers our algorithm to represent intricate data patterns with a reduced number of support data.

In determining the termination condition, we prefer achieving a modest number of support data, given its advantages in computational efficiency and memory conservation, all while upholding accuracy.

Traditional symmetric kernels, lacking such flexibility, struggle to achieve the same efficiency as they apply a uniform kernel formula to all data points.

The example in Figure 1 in the manuscript precisely illustrates this point. Attempting to fit unevenly distributed data with a uniform bandwidth necessitates more support data to approximate local distributions, as depicted in (b) and (c). By leveraging the high flexibility of LAB RBF kernels, as demonstrated in (d), our algorithm perfectly tackles this challenge, resulting in advantages in both accuracy and model complexity.

---

We hope that our explanations and the additional experimental results adequately address your concerns regarding support data selection and the formulation of the asymmetric KRR model. We would greatly appreciate it if you could consider revising the score accordingly. Moreover, we are open to further discussions regarding the design of the asymmetric KRR model or any other topics that might interest you.

Dear reviewer aToc,

Just now, we have uploaded the revised papar in OpenReview system and sincerely hope it meets your standards. Here is a quick look of the key updates:

• We tried our best to better clarify the design of the asymmetric kernel ridge regression model in Eq.(4). Please review the reorgnized sentences in Section 2.2 on page 4.
• We added the discussion and the additional experiment on the selection of initial support data in Appendix F. We trust these additions will provide robust evidence for the effectiveness of our proposed dynamic strategy.

We're truly grateful for your valuable suggestions, which have played a pivotal role in elevating the quality of our paper. Any lingering concerns on your end? We're all ears and more than ready to tackle them before the discussion period wraps up.

We sincerely appreciate your valuable comments and highly recognition of our work.

About Convergence Properties

We agree with you regarding the significance of convergence properties in algorithmic discussions. Given that our optimization problem, as outlined in equation (9), is a non-convex unconstrained challenge, we have opted for the utilization of stochastic gradient descent (SGD) methods to efficiently address it. Consequently, the convergence analysis of SGD in the realm of general non-convex optimization is pertinent to our algorithm, e.g.[1]. For this reason, we chose not to delve into this topic in the manuscript. But we value your suggestions and intend to incorporate a discussion on it in the revised version.

[1] Fehrman, Benjamin, Benjamin Gess, and Arnulf Jentzen. "Convergence rates for the stochastic gradient descent method for non-convex objective functions." The Journal of Machine Learning Research 21, no. 1 (2020): 5354-5401.

Learning Behavior of LAB RBF Kenrels

The learning behavior of LAB RBF kernels, as you point out, is indeed both intriguing and notably distinct from existing kernels due to their inherently asymmetric nature. The loss of symmetry renders the analysis tools in traditional RKHS, or even in more general case e.g., reproducing kernel Kreïn spaces (RKKS) and reproducing kernel Banach spaces (RKBS), not applicable. Our ongoing work specifically addresses and explores these unique characteristics.

Notably, LAB RBF kernels, featuring trainable bandwidths, share a resemblance with multiple kernel learning whose corresponding functional space comprises a direct sum space of Hilbert spaces. Inspired by this correlation, our analysis of LAB RBF kernels aims to construct a sparse model within the direct integral space of Hilbert spaces. This work is not only interesting but also presents a notable challenge due to the complex nature of the space being explored.

Effects of Inaccurate Estimation of Bandwidths

We appreciate your insights into the crucial role that bandwidths play in the performance of LAB RBF kernels. It is precisely for this purpose, we propose the kernel learning algorithm to determine proper bandwidths for different data patterns.

Indeed there might be some challenges to determine good bandwidth in practice. For example, within our kernel learning algorithm, various factors during training, such as the choice of initial points, stopping criteria, learning rate, and batch size, may result in distinct bandwidth estimations.

In our experiments, these hyper-parameters are determined through cross-validation, detailed in Appendix C. And the influence of initialization is thoroughly addressed in Appendix E.

Here, to address you concern, we present extra experimental results that demonstrate their impact on the performance of our algorithm.

Impact of Maximal Iteration Number

1. Yacht dataset: 246 training data, batch size=32.

2. Pakinson dataset: 4700 training data, batch size=128.

Impact of Learning Rate

1. Yacht dataset

2. Pakinson dataset:

Impact of Batch Size

1. Yacht dataset

2. Pakinson Dataset:

These results underscore that the carefully selection of these hyperparameters enhances the final performance. Nevertheless, even under suboptimal hyperparameter settings, the performance remains commendable, albeit with varying bandwidth estimates. This highlights the robustness and insensitivity of our algorithm across a wide spectrum of hyperparameter choices.

---

We hope that our explanations, along with the additional experiments, effectively address your concerns regarding algorithm convergence and robustness. Furthermore, we welcome the opportunity for further discussions on the learning behavior of LAB RBF kernels if you are interested.

Dear reviewer gJwQ, We've just uploaded the revised paper onto the OpenReview system. Taking your insightful suggestions into account, we've made thorough revisions to the manuscript, where you can find that:

• On page 7, we added the discussion of convergence analysis in the end of Section 3.
• In the Appendix E, we added the extra experiments on the effects of hyper-parameters on final performance.

Once again, we appreciate these valuable suggestions from you, which have significantly contributed to enhancing the quality of our paper.