We consider the problem of streaming kernel regression, when the observations arrive sequentially and the goal is to recover the underlying mean function, assumed to belong to an RKHS. The variance of the noise is not assumed to be known. In this context, we tackle the problem of tuning the regularization parameter adaptively at each time step, while maintaining tight confidence bounds estimates on the value of the mean function at each point. To this end, we first generalize existing results for finite-dimensional linear regression with fixed regularization and known variance to the kernel setup with a regularization parameter allowed to be a measurable function of past observations. Then, using appropriate self-normalized inequalities we build upper and lower bound estimates for the variance, leading to Bersntein-like concentration bounds. The later is used in order to define the adaptive regularization. The bounds resulting from our technique are valid uniformly over all observation points and all time steps, and are compared against the literature with numerical experiments. Finally, the potential of these tools is illustrated by an application to kernelized bandits, where we revisit the Kernel UCB and Kernel Thompson Sampling procedures, and show the benefits of the novel adaptive kernel tuning strategy.
Theorem extends the self-normalized bounds of @cite_7 from the setting of linear function spaces to that of an RKHS with sub-Gaussian noise. Based on a nontrivial adaptation of the Laplace method, it yields self-normalized inequalities in a setting of possibly infinite dimension. It generalizes the following result of @cite_6 to kernel regression with @math , which was already a generalization of a previous result by @cite_1 for bounded noise. It is also more general than the concentration result from @cite_3 , for kernel regression with @math , which holds .
@cite_3 @cite_1 @cite_6 @cite_7
2097476744 1967138577 2114147096 1615542443
This paper proves best known guarantees for exact reconstruction of a sparse signal f from few non-adaptive universal linear measurements. We consider Fourier measurements (random sample of frequencies of f) and random Gaussian measurements. The method for reconstruction that has recently gained momentum in the sparse approximation theory is to relax this highly non-convex problem to a convex problem, and then solve it as a linear program. What are best guarantees for the reconstruction problem to be equivalent to its convex relaxation is an open question. Recent work shows that the number of measurements k(r,n) needed to exactly reconstruct any r-sparse signal f of length n from its linear measurements with convex relaxation is usually O(r poly log (n)). However, known guarantees involve huge constants, in spite of very good performance of the algorithms in practice. In attempt to reconcile theory with practice, we prove the first guarantees for universal measurements (i.e. which work for all sparse functions) with reasonable constants. For Gaussian measurements, k(r,n) lsim 11.7 r [1.5 + log(n r)], which is optimal up to constants. For Fourier measurements, we prove the best known bound k(r, n) = O(r log(n) middot log2(r) log(r log n)), which is optimal within the log log n and log3 r factors. Our arguments are based on the technique of geometric functional analysis and probability in Banach spaces. In view of the minimization of a nonsmooth nonconvex function f, we prove an abstract convergence result for descent methods satisfying a sufficient-decrease assumption, and allowing a relative error tolerance. Our result guarantees the convergence of bounded sequences, under the assumption that the function f satisfies the Kurdyka–Łojasiewicz inequality. This assumption allows to cover a wide range of problems, including nonsmooth semi-algebraic (or more generally tame) minimization. The specialization of our result to different kinds of structured problems provides several new convergence results for inexact versions of the gradient method, the proximal method, the forward–backward splitting algorithm, the gradient projection and some proximal regularization of the Gauss–Seidel method in a nonconvex setting. Our results are illustrated through feasibility problems, or iterative thresholding procedures for compressive sensing. We consider inexact linear equations y ≈ Φx where y is a given vector in R n , Φ is a given n x m matrix, and we wish to find x 0,∈ as sparse as possible while obeying ∥y - Φx 0,∈ ∥ 2 ≤ ∈. In general, this requires combinatorial optimization and so is considered intractable. On the other hand, the l 1 -minimization problem min ∥x∥ 1 subject to ∥y - Φx∥ 2 ≤ e is convex and is considered tractable. We show that for most Φ, if the optimally sparse approximation x 0,∈ is sufficiently sparse, then the solution x 1,∈ of the l 1 -minimization problem is a good approximation to x 0,∈ . We suppose that the columns of Φ are normalized to the unit l 2 -norm, and we place uniform measure on such Φ. We study the underdetermined case where m ∼ τn and τ > 1, and prove the existence of p = p(r) > 0 and C = C(p, τ) so that for large n and for all Φ's except a negligible fraction, the following approximate sparse solution property of Φ holds: for every y having an approximation ∥y - Φx 0 ∥ 2 ≤ ∈ by a coefficient vector x 0 e R m with fewer than ρ · n nonzeros, ∥x 1,∈ - x 0 ∥ 2 ≤ C ≤ ∈. This has two implications. First, for most Φ, whenever the combinatorial optimization result x 0,∈ would be very sparse, x 1,∈ is a good approximation to x 0,∈ . Second, suppose we are given noisy data obeying y = Φx 0 + z where the unknown x 0 is known to be sparse and the noise ∥z∥ 2 ≤ ∈. For most Φ, noise-tolerant l 1 -minimization will stably recover x 0 from y in the presence of noise z. We also study the barely determined case m = n and reach parallel conclusions by slightly different arguments. Proof techniques include the use of almost-spherical sections in Banach space theory and concentration of measure for eigenvalues of random matrices. We prove an extension of McDiarmid's inequality for metric spaces with unbounded diameter. To this end, we introduce the notion of the subgaussian diameter, which is a distribution-dependent refinement of the metric diameter. Our technique provides an alternative approach to that of Kutin and Niyogi's method of weakly difference-bounded functions, and yields nontrivial, dimension-free results in some interesting cases where the former does not. As an application, we give apparently the first generalization bound in the algorithmic stability setting that holds for unbounded loss functions. This yields a novel risk bound for some regularized metric regression algorithms. We give two extensions of the basic concentration result. The first enables one to replace the independence assumption by appropriate strong mixing. The second generalizes the subgaussian technique to other Orlicz norms.