Coefficient-based Regularized Distribution Regression

• URL: http://arxiv.org/abs/2208.12427v1
• Date: Fri, 26 Aug 2022 03:46:14 GMT
• Title: Coefficient-based Regularized Distribution Regression
• Authors: Yuan Mao, Lei Shi and Zheng-Chu Guo
• Abstract summary: We consider the coefficient-based regularized distribution regression which aims to regress from probability measures to real-valued responses over a kernel reproducing Hilbert space (RKHS) Asymptotic behaviors of the algorithm in different regularity ranges of the regression function are comprehensively studied. We get the optimal rates under some mild conditions, which matches the one-stage sampled minimax optimal rate.
• Score: 4.21768682940933
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we consider the coefficient-based regularized distribution regression which aims to regress from probability measures to real-valued responses over a reproducing kernel Hilbert space (RKHS), where the regularization is put on the coefficients and kernels are assumed to be indefinite. The algorithm involves two stages of sampling, the first stage sample consists of distributions and the second stage sample is obtained from these distributions. Asymptotic behaviors of the algorithm in different regularity ranges of the regression function are comprehensively studied and learning rates are derived via integral operator techniques. We get the optimal rates under some mild conditions, which matches the one-stage sampled minimax optimal rate. Compared with the kernel methods for distribution regression in the literature, the algorithm under consideration does not require the kernel to be symmetric and positive semi-definite and hence provides a simple paradigm for designing indefinite kernel methods, which enriches the theme of the distribution regression. To the best of our knowledge, this is the first result for distribution regression with indefinite kernels, and our algorithm can improve the saturation effect.

Related papers

• Optimal Rates for Vector-Valued Spectral Regularization Learning Algorithms [28.046728466038022]
  We study theoretical properties of a broad class of regularized algorithms with vector-valued output. We rigorously confirm the so-called saturation effect for ridge regression with vector-valued output. We present the upper bound for the finite sample risk general vector-valued spectral algorithms.
  arXiv  Detail & Related papers  (2024-05-23T16:45:52Z)
• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  In this paper, we propose a distributed sampling scheme based on the alternating direction method of multipliers. We provide both theoretical guarantees of our algorithm's convergence and experimental evidence of its superiority to the state-of-the-art. In simulation, we deploy our algorithm on linear and logistic regression tasks and illustrate its fast convergence compared to existing gradient-based methods.
  arXiv  Detail & Related papers  (2024-01-29T02:08:40Z)
• Adaptive Annealed Importance Sampling with Constant Rate Progress [68.8204255655161]
  Annealed Importance Sampling (AIS) synthesizes weighted samples from an intractable distribution. We propose the Constant Rate AIS algorithm and its efficient implementation for $alpha$-divergences.
  arXiv  Detail & Related papers  (2023-06-27T08:15:28Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• Beyond Exact Gradients: Convergence of Stochastic Soft-Max Policy Gradient Methods with Entropy Regularization [20.651913793555163]
  We revisit the classical entropy regularized policy gradient methods with the soft-max policy parametrization. We establish a global optimality convergence result and a sample complexity of $widetildemathcalO(frac1epsilon2)$ for the proposed algorithm.
  arXiv  Detail & Related papers  (2021-10-19T17:21:09Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  We present an analysis of the ExtraGradient (SEG) method with constant step size, and present variations of the method that yield favorable convergence. We prove that when augmented with averaging, SEG provably converges to the Nash equilibrium, and such a rate is provably accelerated by incorporating a scheduled restarting procedure.
  arXiv  Detail & Related papers  (2021-06-30T17:51:36Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  It is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth convex optimization have complexity bounds with dependence on confidence level. We propose novel stepsize rules for two methods with gradient clipping.
  arXiv  Detail & Related papers  (2021-06-10T17:54:21Z)
• Fast Statistical Leverage Score Approximation in Kernel Ridge Regression [12.258887270632869]
  Nystr"om approximation is a fast randomized method that rapidly solves kernel ridge regression (KRR) problems. We propose a linear time (modulo poly-log terms) algorithm to accurately approximate the statistical leverage scores in the stationary- Kernel-based KRR.
  arXiv  Detail & Related papers  (2021-03-09T05:57:08Z)
• Sparse Representations of Positive Functions via First and Second-Order Pseudo-Mirror Descent [15.340540198612823]
  We consider expected risk problems when the range of the estimator is required to be nonnegative. We develop first and second-order variants of approximation mirror descent employing emphpseudo-gradients. Experiments demonstrate favorable performance on ingeneous Process intensity estimation in practice.
  arXiv  Detail & Related papers  (2020-11-13T21:54:28Z)
• Early stopping and polynomial smoothing in regression with reproducing kernels [2.132096006921048]
  We study the problem of early stopping for iterative learning algorithms in a reproducing kernel Hilbert space (RKHS) We present a data-driven rule to perform early stopping without a validation set that is based on the so-called minimum discrepancy principle. The proposed rule is proved to be minimax-optimal over different types of kernel spaces.
  arXiv  Detail & Related papers  (2020-07-14T05:27:18Z)
• A Distributional Analysis of Sampling-Based Reinforcement Learning Algorithms [67.67377846416106]
  We present a distributional approach to theoretical analyses of reinforcement learning algorithms for constant step-sizes. We show that value-based methods such as TD($lambda$) and $Q$-Learning have update rules which are contractive in the space of distributions of functions.
  arXiv  Detail & Related papers  (2020-03-27T05:13:29Z)

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.