We present a generalization of the adversarial linear bandits framework, where the underlying losses are kernel functions (with an associated reproducing kernel Hilbert space) rather than linear functions. We study a version of the exponential weights algorithm and bound its regret in this setting. Under conditions on …
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,695 papers · 148 categories
Trend · papers per month
9 results for “eigendecay”
Near-Interpolators: Rapid Norm Growth and the Trade-Off between Interpolation and Generalizationstat.ML
Near-interpolating models grow norms quickly, affecting generalization.
problem Understanding the trade-off between interpolation and generalization in near-interpolating models.
method Random matrix theory and eigendecay analysis of data covariance matrix.
result Near-interpolating models exhibit rapid norm growth and worse generalization trade-offs.
Sketching accelerates structured prediction methods for large datasets.
problem Scaling surrogate kernel methods for large datasets.
method Sketching approximations applied to input and output feature maps.
result Achieves close-to-optimal rates with reduced sketch size.
A new algorithm tackles adversarial linear contextual bandits using kernelized loss functions.
problem Online learning in adversarial linear contextual bandits with flexible loss functions.
method Proposes a computationally efficient algorithm using an optimistically biased estimator for reproducing kernel Hilbert space loss functions.
result Achieves near-optimal regret guarantees under polynomial and exponential eigendecay assumptions.
We derive optimal statistical and computational complexity bounds for exp-concave stochastic minimization in terms of the effective dimension. For common eigendecay patterns of the population covariance matrix, this quantity is significantly smaller than the ambient dimension. Our results reveal interesting connections…
New learning rates derived for Tikhonov-regularized problems without kernel assumptions.
problem Learning rates for Tikhonov-regularized learning problems.
method Minimax adaptive rates derived using Fourier isocapacitary condition and interpolation theory.
result Derivation of minimax adaptive rates without requiring kernel assumptions.
Second-order optimizers retain residual information after data deletion, affecting machine unlearning.
problem Residual information in second-order optimizers after data deletion.
method Comparison of first-order and second-order learners, eigendecomposition analysis.
result Second-order optimizers retain residual information, not detectable by first-order analysis.
Improved guarantees for misspecified kernelized bandit optimization.
problem Misspecification in kernelized bandit optimization.
method Localization and domain splitting techniques.
result Logarithmic or polylogarithmic growth of misspecification amplification.
Paper proves minibatch SGD for GP inference converges and improves generalization.
problem Theoretical understanding and practical use of SGD for correlated samples in Gaussian process inference.
method Proves minibatch SGD converges to a critical point with rate O(1/K) for K iterations, under certain kernel conditions.
result Minibatch SGD for GP inference improves generalization and reduces computational burden.