1
$\begingroup$

I am conducting research on an algorithm called Parsimonious Online Learning with Kernels (POLK), which uses reproducing kernel hilbert spaces as a means for approximating a function.

Here is a link to the paper, and I have taken a screenshot of the two primary algorithms presented in the paper:

https://arxiv.org/pdf/1612.04111.pdf

enter image description here

enter image description here

The reason I am posting here, is that I am trying to implement the final step in KOMP (algorithm 1), where the H-norm of the difference in functionals is minimized over weight vector w.

My approach is to use gradient descent on the H-norm to achieve this minimization. The result does converge, but it converges to a maximum rather than a minimum. I am hoping that someone could double check my math, and that I am not making a major conceptual misstep in my approach.

Note: $$\tilde{f(\cdot)} = \Sigma_{n = 1}^{N} w_nK(x_n, \cdot)$$

Also note that I use w to represent the weight vector prior to removing an element from the dictionary, and $\bar{w}$ to represent the weight vector corresponding to the dictionary with an element removed.

\begin{align*} w &= argmin_{w \in R^{N-1}} \vert \vert \tilde{f(\cdot)} - w^Tk_D(\cdot) \vert \vert_H\\ &= argmin_{w \in R^{N-1}} \vert \vert \Sigma_{n = 1}^{N} w_nK(x_n, \cdot) - \Sigma_{n = 1}^{N-1} \bar{w_n}K(\bar{x_n}, \cdot) \vert \vert_H\\ &= argmin_{w \in R^{N-1}} \vert \vert <w^TK_D(\cdot) - \bar{w}^TK_{\bar{D}}(\cdot), w^TK_D(\cdot) - \bar{w}^TK_{\bar{D}}(\cdot)> \vert \vert_H\\ &= argmin_{w \in R^{N-1}} \vert \vert \Sigma_{i = 1}^{N} \Sigma_{j = 1}^{N} w_iw_jK(x_i, x_j) - 2 * \Sigma_{i = 1}^{N} \Sigma_{j = 1}^{N - 1} w_i \bar{w_j} K(x_i, \bar{x_j}) + \Sigma_{i = 1}^{N - 1}\Sigma_{j = 1}^{N - 1} \bar{w_i} \bar{w_j}K(\bar{x_i}, \bar{x_j}) \vert \vert_H\\ &= argmin_{w \in R^{N-1}} \Sigma_{i = 1}^{N - 1} \Sigma_{j = 1}^{N - 1} \bar{w_i}\bar{w_j}K(\bar{x_i}, \bar{x_j}) - 2 * \Sigma_{i = 1}^{N} \Sigma_{j = 1}^{N - 1} w_i \bar{w_j} K(x_i, \bar{x_j})\\ &= argmin_{w \in R^{N-1}} 2 * \bar{w_k} \Sigma_{i = 1}^{N - 1} \bar{w_i} K(\bar{w_k}, \bar{w_i}) - \bar{w_k}^2 K(\bar{w_k}, \bar{w_k}) - 2 * \bar{w_k} \Sigma_{i = 1}^{N}w_i K(x_i, \bar{x_k})\\ &= argmin_{w \in R^{N-1}} 2 * \bar{w_k} \Sigma_{i = 1, i \neq k}^{N - 1} \bar{w_i} K(\bar{w_k}, \bar{w_i}) + \bar{w_k}^2 K(\bar{w_k}, \bar{w_k}) - 2 * \bar{w_k} \Sigma_{i = 1}^{N}w_i K(x_i, \bar{x_k})\\ \cfrac{\partial \ell}{\partial \bar{w_k}} &= \cfrac{\partial}{\partial \bar{w_k}} 2 * \bar{w_k} \Sigma_{i = 1, i \neq k}^{N - 1} \bar{w_i} K(\bar{w_k}, \bar{w_i}) + \bar{w_k}^2 K(\bar{w_k}, \bar{w_k}) - 2 * \bar{w_k} \Sigma_{i = 1}^{N}w_i K(x_i, \bar{x_k})\\ &= 2 \Sigma_{i = 1, i \neq k}^{N-1} \bar{w_i}K(\bar{x_i}, \bar{x_k}) + 2 \bar{w_k}K(\bar{x_k}, \bar{x_k}) - 2 \Sigma_{i = 1}^{N} w_i K(x_i, \bar{x_k})\\ \bar{w_{k, t+1}} &= \bar{w_{k, t}} - \alpha \cfrac{\partial \ell}{\partial \bar{w_k}} \end{align*}

I realize that there are numerous details on the algorithm that are left out of my question, so if anything is not clear, I am happy to revise my question and provide more detail.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy