High-Probability Kernel Alignment Regret Bounds for Online Kernel Selection

Abstract

In this paper, we study data-dependent regret bounds for online kernel selection in the regime online classification with the hinge loss. Existing work only achieves $O(\Vert f\Vert ^2_{\mathcal {H}_{\kappa }}T^\alpha ), \frac{1}{2}\le \alpha <1$ O ( ‖ f ‖ H κ 2 T α ) , 1 2 ≤ α < 1 regret bounds, where $\kappa \in \mathcal {K}$ κ ∈ K , a preset candidate set. The worst-case regret bounds can not reveal kernel selection improves the performance of single kernel leaning in some benign environment. We develop two adaptive online kernel selection algorithms and obtain the first high-probability regret bound depending on $\mathcal {A}(\mathcal {I}_T,\kappa )$ A ( I T , κ ) , a variant of kernel alignment. If there is a kernel in the candidate set matching the data well, then our algorithms can improve the learning performance significantly and reduce the time complexity. Our results also justify using kernel alignment as a criterion for evaluating kernel function. The first algorithm has a O ( T / K ) per-round time complexity and enjoys a $O(\Vert f\Vert ^2_{\mathcal {H}_{i^*}} \sqrt{K\mathcal {A}(\mathcal {I}_T,\kappa _{i^*})})$ O ( ‖ f ‖ H i ∗ 2 K A ( I T , κ i ∗ ) ) high-probability regret bound. The second algorithm enjoys a $\tilde{O}(\beta ^{-1} \sqrt{T\mathcal {A}(\mathcal {I}_T,\kappa _{i^*})})$ O ~ ( β - 1 T A ( I T , κ i ∗ ) ) per-round time complexity and achieves a $\tilde{O}(\Vert f\Vert ^2_{\mathcal {H}_{{i^*}}}K^{\frac{1}{2}}\beta ^{\frac{1}{2}} T^{\frac{1}{4}}\mathcal {A}(\mathcal {I}_T,\kappa _{i^*})^{\frac{1}{4}})$ O ~ ( ‖ f ‖ H i ∗ 2 K 1 2 β 1 2 T 1 4 A ( I T , κ i ∗ ) 1 4 ) high-probability regret bound, where $\beta \ge 1$ β ≥ 1 is a balancing factor and $\kappa _{i^*}\in \mathcal {K}$ κ i ∗ ∈ K is the kernel with minimal $\mathcal {A}(\mathcal {I}_T,\kappa )$ A ( I T , κ ) .