Random feature-based double Vovk-Azoury-Warmuth algorithm for online multi-kernel learning

• URL: http://arxiv.org/abs/2503.20087v2
• Date: Tue, 01 Apr 2025 18:53:42 GMT
• Title: Random feature-based double Vovk-Azoury-Warmuth algorithm for online multi-kernel learning
• Authors: Dmitry B. Rokhlin, Olga V. Gurtovaya,
• Abstract summary: We introduce a novel multi-kernel learning algorithm, VAW$2$, for online least squares regression in reproducing kernel Hilbert spaces (RKHS)<n>VAW$2$ leverages random Fourier feature-based functional approximation and the Vovk-Azoury-Warmuth (VAW) method in a two-level procedure.<n>A theoretical analysis yields a regret bound of $O(T1/2ln T)$ in expectation with respect to artificial randomness, when the number of random features scales as $T1/2$.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce a novel multi-kernel learning algorithm, VAW$^2$, for online least squares regression in reproducing kernel Hilbert spaces (RKHS). VAW$^2$ leverages random Fourier feature-based functional approximation and the Vovk-Azoury-Warmuth (VAW) method in a two-level procedure: VAW is used to construct expert strategies from random features generated for each kernel at the first level, and then again to combine their predictions at the second level. A theoretical analysis yields a regret bound of $O(T^{1/2}\ln T)$ in expectation with respect to artificial randomness, when the number of random features scales as $T^{1/2}$. Empirical results on some benchmark datasets demonstrate that VAW$^2$ achieves superior performance compared to the existing online multi-kernel learning algorithms: Raker and OMKL-GF, and to other theoretically grounded method methods involving convex combination of expert predictions at the second level.

Related papers

• A hierarchical Vovk-Azoury-Warmuth forecaster with discounting for online regression in RKHS [0.0]
  We study the problem of online regression with the unconstrained quadratic loss against a time-varying sequence of functions from a Reproducing Kernel Hilbert Space (RKHS)<n>We propose a fully adaptive, hierarchical algorithm, which learns both the discount factor and the number of random features.
  arXiv  Detail & Related papers  (2025-06-27T20:47:52Z)
• The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Models [71.5283441529015]
  In this work we consider generic Gaussian Multi-index models, in which the labels only depend on the (Gaussian) $d$-dimensional inputs through their projection onto a low-dimensional $r = O_d(1)$ subspace.<n>We introduce the generative leap exponent $kstar$, a natural extension of the generative exponent from [Damian et al.'24] to the multi-index setting.
  arXiv  Detail & Related papers  (2025-06-05T18:34:56Z)
• Enhanced Feature Learning via Regularisation: Integrating Neural Networks and Kernel Methods [0.0]
  We consider functions as expectations of Sobolev functions over all possible one-dimensional projections of the data.<n>This framework is similar to kernel ridge regression, where the kernel is $mathbbE_w ( k(B)(wtop x,wtop xprime))$, with $k(B)(a,b) := min(|a|, |b|)mathds1_ab>0$ the Brownian kernel, and the distribution of the projections $w$ is learnt
  arXiv  Detail & Related papers  (2024-07-24T13:46:50Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• Model-adapted Fourier sampling for generative compressed sensing [7.130302992490975]
  We study generative compressed sensing when the measurement matrix is randomly subsampled from a unitary matrix. We construct a model-adapted sampling strategy with an improved sample complexity of $textitO(kd| boldsymbolalpha|_22)$ measurements.
  arXiv  Detail & Related papers  (2023-10-08T03:13:16Z)
• Convergence analysis of online algorithms for vector-valued kernel regression [0.42970700836450487]
  We consider the problem of approximating the regression function from noisy vector-valued data by an online learning algorithm. We show that the expected squared error in the RKHS norm can be bounded by $C2 (m+1)-s/(2+s)$, where $m$ is the current number of processed data.
  arXiv  Detail & Related papers  (2023-09-14T15:10:47Z)
• A duality framework for analyzing random feature and two-layer neural networks [7.400520323325074]
  We consider the problem of learning functions within the $mathcalF_p,pi$ and Barron spaces. We establish a dual equivalence between approximation and estimation, and then apply it to study the learning of the preceding function spaces.
  arXiv  Detail & Related papers  (2023-05-09T17:41:50Z)
• Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs [60.40452803295326]
  We propose a new reward-free algorithm for learning linear Markov decision processes (MDPs) At the core of our algorithm is uncertainty-weighted value-targeted regression with exploration-driven pseudo-reward. We show that our algorithm only needs to explore $tilde O( d2varepsilon-2)$ episodes to find an $varepsilon$-optimal policy.
  arXiv  Detail & Related papers  (2023-03-17T17:53:28Z)
• Provably Efficient Convergence of Primal-Dual Actor-Critic with Nonlinear Function Approximation [15.319335698574932]
  We show the first efficient convergence result with primal-dual actor-critic with a convergence of $mathcalOleft ascent(Nright)Nright)$ under Polyian sampling. Results on Open GymAI continuous control tasks.
  arXiv  Detail & Related papers  (2022-02-28T15:16:23Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  We propose a model-free reinforcement learning algorithm inspired by the popular randomized least squares value iteration (RLSVI) algorithm. Our algorithm drives exploration by simply perturbing the training data with judiciously chosen i.i.d. scalar noises. We complement the theory with an empirical evaluation across known difficult exploration tasks.
  arXiv  Detail & Related papers  (2021-06-15T02:23:07Z)
• A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants [39.28675942566465]
  This paper develops a framework to study finite-sample convergence guarantees of a class of value-based asynchronous RL algorithms. As a by-product, we provide theoretical insights into the bias-variance trade-off, i.e., efficiency of bootstrapping in RL.
  arXiv  Detail & Related papers  (2021-02-02T15:48:19Z)
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
  adversary-resilient distributed optimization, in which. machines can independently compute gradients, and cooperate. Our algorithm is based on a new concentration technique, and its sample complexity. It is very practical: it improves upon the performance of all prior methods when no. setting machines are present.
  arXiv  Detail & Related papers  (2020-12-28T17:19:32Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  We study the problem of high-dimensional robust linear regression where a learner is given access to $n$ samples from the generative model $Y = langle X,w* rangle + epsilon$ We propose estimators for this problem under two settings: (i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance and (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  arXiv  Detail & Related papers  (2020-07-16T06:44:44Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  We study the learnability of halfspaces in the presence of Tsybakov noise. We give an algorithm that achieves misclassification error $epsilon$ with respect to the true halfspace.
  arXiv  Detail & Related papers  (2020-06-11T14:25:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.