Search

Recently the adaption problem of Information-Based Complexity (IBC) for linear problems in the randomized setting was solved in Heinrich (2024) [8]. Several papers treating further aspects of this problem followed. However, all examples obtained so far were vector-valued. In this paper we settle the scalar-valued case. We study the complexity of mean computation in finite dimensional sequence spaces with mixed L p N norms. We determine the n -th minimal errors in the randomized adaptive and non-adaptive settings. It turns out that among the problems considered there are examples where adaptive and non-adaptive n -th minimal errors deviate by a power of n. The gap can be (up to log factors) of the order n 1 / 4. We also show how to turn such results into infinite dimensional examples with suitable deviation for all n simultaneously. [ABSTRACT FROM AUTHOR]

In recent years, functional linear models have attracted growing attention in statistics and machine learning for recovering the slope function or its functional predictor. This paper considers online regularized learning algorithm for functional linear models in a reproducing kernel Hilbert space. It provides convergence analysis of excess prediction error and estimation error with polynomially decaying step-size and constant step-size, respectively. Fast convergence rates can be derived via a capacity dependent analysis. Introducing an explicit regularization term extends the saturation boundary of unregularized online learning algorithms with polynomially decaying step-size and achieves fast convergence rates of estimation error without capacity assumption. In contrast, the latter remains an open problem for the unregularized online learning algorithm with decaying step-size. This paper also demonstrates competitive convergence rates of both prediction error and estimation error with constant step-size compared to existing literature. [ABSTRACT FROM AUTHOR]

This paper focuses on the approximation of continuous functions on the unit sphere by spherical polynomials of degree n via hyperinterpolation. Hyperinterpolation of degree n is a discrete approximation of the L 2 -orthogonal projection of the same degree with its Fourier coefficients evaluated by a positive-weight quadrature rule that exactly integrates all spherical polynomials of degree at most 2 n. This paper aims to bypass this quadrature exactness assumption by replacing it with the Marcinkiewicz–Zygmund property proposed in a previous paper. Consequently, hyperinterpolation can be constructed by a positive-weight quadrature rule (not necessarily with quadrature exactness). This scheme is referred to as unfettered hyperinterpolation. This paper provides a reasonable error estimate for unfettered hyperinterpolation. The error estimate generally consists of two terms: a term representing the error estimate of the original hyperinterpolation of full quadrature exactness and another introduced as compensation for the loss of exactness degrees. A guide to controlling the newly introduced term in practice is provided. In particular, if the quadrature points form a quasi-Monte Carlo (QMC) design, then there is a refined error estimate. Numerical experiments verify the error estimates and the practical guide. [ABSTRACT FROM AUTHOR]

We give an overview of certain aspects of tractability analysis of multivariate problems. This paper is not intended to give a complete account of the subject, but provides an insight into how the theory works for particular types of problems. We mainly focus on linear problems on Hilbert spaces, and mostly allow arbitrary linear information. In such cases, tractability analysis is closely linked to an analysis of the singular values of the operator under consideration. We also highlight the more recent developments regarding exponential and generalized tractability. The theoretical results are illustrated by several examples throughout the article. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of finding how close two sums of m th roots can be to each other. For integers m ≥ 2 , k ≥ 1 and 0 ≤ s ≤ k , let e m (s , k) > 0 and E m (s , k) > 0 be the largest exponents such that for infinitely many integers N there exist k positive integers a 1 , ... , a k ≤ N for which two sums of their m th roots ∑ j = 1 s a j m and ∑ j = s + 1 k a j m are distinct but not further than N − e m (s , k) from each other, or they are distinct modulo 1 but not further than N − E m (s , k) from each other modulo 1. Some upper bounds on e m (s , k) and E m (s , k) can be derived by a Liouville-type argument, while lower bounds are usually difficult to obtain. We prove that e m (s , k) ≥ min ⁡ (2 s , k − 1 , 2 k − 2 s) − 1 / m for 1 ≤ s < k and that E m (s , k) ≥ min ⁡ (2 s , k − 2 , 2 k − 2 s) + 2 − 1 / m for 0 ≤ s ≤ k. Very recently, Steinerberger managed to show that E 2 (k , k) ≥ c k 3 , where c > 0 is a small absolute constant. This seems to be the first result when the bound for s = k is increasing in k. By an entirely different argument, for any integers m ≥ 2 , k ≥ 1 and s in the range 0 ≤ s ≤ k , we show that E m (s , k) ≥ (k − 2) / m + 1. In particular, for m = 2 and any non-negative integer s ≤ k , this yields the bound E 2 (s , k) ≥ k / 2 , which is much better than c k 3. We also prove that e 2 (2 , 4) = 7 / 2 , which settles a problem raised by O'Rourke in 1981. These problems can be also considered for non-integer m. In particular, we show that 1 ≤ E 3 / 2 (1 , 1) ≤ 4 / 3 , and that E 3 / 2 (1 , 1) = 1 under assumption of the abc -conjecture. [ABSTRACT FROM AUTHOR]

Functional data analysis offers a set of statistical methods concerned with extracting insights from intrinsically infinite-dimensional data and has attracted considerable amount of attentions in the past few decades. In this paper, we study robust functional linear regression model with a scalar response and a functional predictor in the framework of reproducing kernel Hilbert spaces. A gradient descent algorithm with early stopping is introduced to solve the corresponding empirical risk minimization problem associated with robust loss functions. By appropriately selecting the early stopping rule and the scaling parameter of the robust losses, the convergence of the proposed algorithm is established when the response variable is bounded or satisfies a moment condition. Explicit learning rates with respect to both estimation and prediction error are provided in terms of regularity of the regression function and eigenvalue decay rate of the integral operator induced by the reproducing kernel and covariance function. [ABSTRACT FROM AUTHOR]

Ezquerro and Hernandez (2009) studied a modified Chebyshev's method to solve a nonlinear equation approximately in the Banach space setting where the convergence analysis utilizes Taylor series expansion and hence requires the existence of at least fourth-order Fréchet derivative of the involved operator. No error estimate on the error distance was given in their work. In this paper, we obtained the convergence order and error estimate of the error distance without Taylor series expansion. We have made assumptions only on the involved operator and its first and second Fréchet derivative. So, we extend the applicability of the modified Chebyshev's method. Further, we compare the modified Chebyshev method's efficiency index and dynamics with other similar methods. Numerical examples validate the theoretical results. [ABSTRACT FROM AUTHOR]

We study the numerical integration of functions from isotropic Sobolev spaces W p s ([ 0 , 1 ] d) using finitely many function evaluations within randomized algorithms, aiming for the smallest possible probabilistic error guarantee ε > 0 at confidence level 1 − δ ∈ (0 , 1). For spaces consisting of continuous functions, non-linear Monte Carlo methods with optimal confidence properties have already been known, in few cases even linear methods that succeed in that respect. In this paper we promote a method called stratified control variates (SCV) and by it show that already linear methods achieve optimal probabilistic error rates in the high smoothness regime without the need to adjust algorithmic parameters to the uncertainty δ. We also analyse a version of SCV in the low smoothness regime where W p s ([ 0 , 1 ] d) may contain functions with singularities. Here, we observe a polynomial dependence of the error on δ − 1 in contrast to the logarithmic dependence in the high smoothness regime. [ABSTRACT FROM AUTHOR]

In this paper we consider integration and L 2 -approximation for functions over R s from weighted Hermite spaces. The first part of the paper is devoted to a comparison of several weighted Hermite spaces that appear in literature, which is interesting on its own. Then we study tractability of the integration and L 2 -approximation problem for the introduced Hermite spaces, which describes the growth rate of the information complexity when the error threshold ε tends to 0 and the problem dimension s grows to infinity. Our main results are characterizations of tractability in terms of the involved weights, which model the importance of the successive coordinate directions for functions from the weighted Hermite spaces. [ABSTRACT FROM AUTHOR]

The usual univariate interpolation problem of finding a monic polynomial f of degree n that interpolates n given values is well understood. This paper studies a variant where f is required to be composite, say, a composition of two polynomials of degrees d and e , respectively, with d e = n , and with d + e − 1 given values. Some special cases are easy to solve, and for the general case, we construct a homotopy between it and a special case. We compute a geometric solution of the algebraic curve presenting this homotopy, and this also provides an answer to the interpolation task. The computing time is polynomial in the geometric data, like the degree, of this curve. A consequence is that for almost all inputs, a decomposable interpolation polynomial exists. [ABSTRACT FROM AUTHOR]

In this paper, we consider the adaptive Huber trace regression model with matrix covariates. A non-convex penalty function is employed to account for the low-rank structure of the unknown parameter. Under some mild conditions, we establish an upper bound for the statistical rate of convergence of the regularized matrix estimator. Theoretically, we can deal with heavy-tailed distributions with bounded (1 + δ) -th moment for any δ > 0. Furthermore, we derive the effect of the adaptive parameter on the final estimator. Some simulations, as well as a real data example, are designed to show the finite sample performance of the proposed method. [ABSTRACT FROM AUTHOR]

In this paper, a unified study is presented for the design and analysis of a broad class of linear regression methods. The proposed general framework includes the conventional linear regression methods (such as the least squares regression and the Ridge regression) and some new regression methods (e.g. the Landweber regression and Showalter regression), which have recently been introduced in the fields of optimization and inverse problems. The strong consistency, the reduced mean squared error, the asymptotic Gaussian property, and the best worst case error of this class of linear regression methods are investigated. Various numerical experiments are performed to demonstrate the consistency and efficiency of the proposed class of methods for linear regression. [ABSTRACT FROM AUTHOR]

In this paper, we consider stochastic differential equations whose drift coefficient is superlinearly growing and piecewise continuous, and whose diffusion coefficient is superlinearly growing and locally Hölder continuous. We first prove the existence and uniqueness of solution to such stochastic differential equations and then propose a tamed-adaptive Euler-Maruyama approximation scheme. We study the rate of convergence in L 1 -norm of the scheme in both finite and infinite time intervals. [ABSTRACT FROM AUTHOR]