Source author record

Vladimir Koltchinskii

Vladimir Koltchinskii appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.ST Statistics Theory math.PR Machine Learning math.DG

Catalog footprint

What is connected

22works

5topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

Estimation of smooth functionals in high-dimensional models: bootstrap chains and Gaussian approximation

Let $X^{(n)}$ be an observation sampled from a distribution $P_θ^{(n)}$ with an unknown parameter $θ,$ $θ$ being a vector in a Banach space $E$ (most often, a high-dimensional space of dimension $d$). We study the problem of estimation of $f(θ)$ for a functional $f:E\mapsto {\mathbb R}$ of some smoothness $s>0$ based on an observation $X^{(n)}\sim P_θ^{(n)}.$ Assuming that there exists an estimator $\hat θ_n=\hat θ_n(X^{(n)})$ of parameter $θ$ such that $\sqrt{n}(\hat θ_n-θ)$ is sufficiently close in distribution to a mean zero Gaussian random vector in $E,$ we construct a functional $g:E\mapsto {\mathbb R}$ such that $g(\hat θ_n)$ is an asymptotically normal estimator of $f(θ)$ with $\sqrt{n}$ rate provided that $s>\frac{1}{1-α}$ and $d\leq n^α$ for some $α\in (0,1).$ We also derive general upper bounds on Orlicz norm error rates for estimator $g(\hat θ)$ depending on smoothness $s,$ dimension $d,$ sample size $n$ and the accuracy of normal approximation of $\sqrt{n}(\hat θ_n-θ).$ In particular, this approach yields asymptotically efficient estimators in some high-dimensional exponential models.

preprint2016arXiv

Estimation of low rank density matrices: bounds in Schatten norms and other distances

Let ${\mathcal S}_m$ be the set of all $m\times m$ density matrices (Hermitian positively semi-definite matrices of unit trace). Consider a problem of estimation of an unknown density matrix $ρ\in {\mathcal S}_m$ based on outcomes of $n$ measurements of observables $X_1,\dots, X_n\in {\mathbb H}_m$ (${\mathbb H}_m$ being the space of $m\times m$ Hermitian matrices) for a quantum system identically prepared $n$ times in state $ρ.$ Outcomes $Y_1,\dots, Y_n$ of such measurements could be described by a trace regression model in which ${\mathbb E}_ρ(Y_j|X_j)={\rm tr}(ρX_j), j=1,\dots, n.$ The design variables $X_1,\dots, X_n$ are often sampled at random from the uniform distribution in an orthonormal basis $\{E_1,\dots, E_{m^2}\}$ of ${\mathbb H}_m$ (such as Pauli basis). The goal is to estimate the unknown density matrix $ρ$ based on the data $(X_1,Y_1), \dots, (X_n,Y_n).$ Let $$ \hat Z:=\frac{m^2}{n}\sum_{j=1}^n Y_j X_j $$ and let $\check ρ$ be the projection of $\hat Z$ onto the convex set ${\mathcal S}_m$ of density matrices. It is shown that for estimator $\check ρ$ the minimax lower bounds in classes of low rank density matrices (established earlier) are attained up logarithmic factors for all Schatten $p$-norm distances, $p\in [1,\infty]$ and for Bures version of quantum Hellinger distance. Moreover, for a slightly modified version of estimator $\check ρ$ the same property holds also for quantum relative entropy (Kullback-Leibler) distance between density matrices.

preprint2016arXiv

New asymptotic results in principal component analysis

Let $X$ be a mean zero Gaussian random vector in a separable Hilbert space ${\mathbb H}$ with covariance operator $Σ:={\mathbb E}(X\otimes X).$ Let $Σ=\sum_{r\geq 1}μ_r P_r$ be the spectral decomposition of $Σ$ with distinct eigenvalues $μ_1>μ_2> \dots$ and the corresponding spectral projectors $P_1, P_2, \dots.$ Given a sample $X_1,\dots, X_n$ of size $n$ of i.i.d. copies of $X,$ the sample covariance operator is defined as $\hat Σ_n := n^{-1}\sum_{j=1}^n X_j\otimes X_j.$ The main goal of principal component analysis is to estimate spectral projectors $P_1, P_2, \dots$ by their empirical counterparts $\hat P_1, \hat P_2, \dots$ properly defined in terms of spectral decomposition of the sample covariance operator $\hat Σ_n.$ The aim of this paper is to study asymptotic distributions of important statistics related to this problem, in particular, of statistic $\|\hat P_r-P_r\|_2^2,$ where $\|\cdot\|_2^2$ is the squared Hilbert--Schmidt norm. This is done in a "high-complexity" asymptotic framework in which the so called effective rank ${\bf r}(Σ):=\frac{{\rm tr}(Σ)}{\|Σ\|_{\infty}}$ (${\rm tr}(\cdot)$ being the trace and $\|\cdot\|_{\infty}$ being the operator norm) of the true covariance $Σ$ is becoming large simultaneously with the sample size $n,$ but ${\bf r}(Σ)=o(n)$ as $n\to\infty.$ In this setting, we prove that, in the case of one-dimensional spectral projector $P_r,$ the properly centered and normalized statistic $\|\hat P_r-P_r\|_2^2$ with {\it data-dependent} centering and normalization converges in distribution to a Cauchy type limit. The proofs of this and other related results rely on perturbation analysis and Gaussian concentration.

preprint2016arXiv

Nuclear norm penalization and optimal rates for noisy low rank matrix completion

This paper deals with the trace regression model where $n$ entries or linear combinations of entries of an unknown $m_1\times m_2$ matrix $A_0$ corrupted by noise are observed. We propose a new nuclear norm penalized estimator of $A_0$ and establish a general sharp oracle inequality for this estimator for arbitrary values of $n,m_1,m_2$ under the condition of isometry in expectation. Then this method is applied to the matrix completion problem. In this case, the estimator admits a simple explicit form and we prove that it satisfies oracle inequalities with faster rates of convergence than in the previous works. They are valid, in particular, in the high-dimensional setting $m_1m_2\gg n$. We show that the obtained rates are optimal up to logarithmic factors in a minimax sense and also derive, for any fixed matrix $A_0$, a non-minimax lower bound on the rate of convergence of our estimator, which coincides with the upper bound up to a constant factor. Finally, we show that our procedure provides an exact recovery of the rank of $A_0$ with probability close to 1. We also discuss the statistical learning setting where there is no underlying model determined by $A_0$ and the aim is to find the best trace regression model approximating the data.

preprint2016arXiv

Optimal Estimation of Low Rank Density Matrices

The density matrices are positively semi-definite Hermitian matrices of unit trace that describe the state of a quantum system. The goal of the paper is to develop minimax lower bounds on error rates of estimation of low rank density matrices in trace regression models used in quantum state tomography (in particular, in the case of Pauli measurements) with explicit dependence of the bounds on the rank and other complexity parameters. Such bounds are established for several statistically relevant distances, including quantum versions of Kullback-Leibler divergence (relative entropy distance) and of Hellinger distance (so called Bures distance), and Schatten $p$-norm distances. Sharp upper bounds and oracle inequalities for least squares estimator with von Neumann entropy penalization are obtained showing that minimax lower bounds are attained (up to logarithmic factors) for these distances.

preprint2015arXiv

Asymptotics and Concentration Bounds for Bilinear Forms of Spectral Projectors of Sample Covariance

Let $X,X_1,\dots, X_n$ be i.i.d. Gaussian random variables with zero mean and covariance operator $Σ={\mathbb E}(X\otimes X)$ taking values in a separable Hilbert space ${\mathbb H}.$ Let $$ {\bf r}(Σ):=\frac{{\rm tr}(Σ)}{\|Σ\|_{\infty}} $$ be the effective rank of $Σ,$ ${\rm tr}(Σ)$ being the trace of $Σ$ and $\|Σ\|_{\infty}$ being its operator norm. Let $$\hat Σ_n:=n^{-1}\sum_{j=1}^n (X_j\otimes X_j)$$ be the sample (empirical) covariance operator based on $(X_1,\dots, X_n).$ The paper deals with a problem of estimation of spectral projectors of the covariance operator $Σ$ by their empirical counterparts, the spectral projectors of $\hat Σ_n$ (empirical spectral projectors). The focus is on the problems where both the sample size $n$ and the effective rank ${\bf r}(Σ)$ are large. This framework includes and generalizes well known high-dimensional spiked covariance models. Given a spectral projector $P_r$ corresponding to an eigenvalue $μ_r$ of covariance operator $Σ$ and its empirical counterpart $\hat P_r,$ we derive sharp concentration bounds for bilinear forms of empirical spectral projector $\hat P_r$ in terms of sample size $n$ and effective dimension ${\bf r}(Σ).$ Building upon these concentration bounds, we prove the asymptotic normality of bilinear forms of random operators $\hat P_r -{\mathbb E}\hat P_r$ under the assumptions that $n\to \infty$ and ${\bf r}(Σ)=o(n).$ In a special case of eigenvalues of multiplicity one, these results are rephrased as concentration bounds and asymptotic normality for linear forms of empirical eigenvectors. Other results include bounds on the bias ${\mathbb E}\hat P_r-P_r$ and a method of bias reduction as well as a discussion of possible applications to statistical inference in high-dimensional principal component analysis.

preprint2015arXiv

Estimation of Low-Rank Covariance Function

We consider the problem of estimating a low rank covariance function $K(t,u)$ of a Gaussian process $S(t), t\in [0,1]$ based on $n$ i.i.d. copies of $S$ observed in a white noise. We suggest a new estimation procedure adapting simultaneously to the low rank structure and the smoothness of the covariance function. The new procedure is based on nuclear norm penalization and exhibits superior performances as compared to the sample covariance function by a polynomial factor in the sample size $n$. Other results include a minimax lower bound for estimation of low-rank covariance functions showing that our procedure is optimal as well as a scheme to estimate the unknown noise variance of the Gaussian process.

preprint2015arXiv

Normal approximation and concentration of spectral projectors of sample covariance

Let $X,X_1,\dots, X_n$ be i.i.d. Gaussian random variables in a separable Hilbert space ${\mathbb H}$ with zero mean and covariance operator $Σ={\mathbb E}(X\otimes X),$ and let $\hat Σ:=n^{-1}\sum_{j=1}^n (X_j\otimes X_j)$ be the sample (empirical) covariance operator based on $(X_1,\dots, X_n).$ Denote by $P_r$ the spectral projector of $Σ$ corresponding to its $r$-th eigenvalue $μ_r$ and by $\hat P_r$ the empirical counterpart of $P_r.$ The main goal of the paper is to obtain tight bounds on $$ \sup_{x\in {\mathbb R}} \left|{\mathbb P}\left\{\frac{\|\hat P_r-P_r\|_2^2-{\mathbb E}\|\hat P_r-P_r\|_2^2}{{\rm Var}^{1/2}(\|\hat P_r-P_r\|_2^2)}\leq x\right\}-Φ(x)\right|, $$ where $\|\cdot\|_2$ denotes the Hilbert--Schmidt norm and $Φ$ is the standard normal distribution function. Such accuracy of normal approximation of the distribution of squared Hilbert--Schmidt error is characterized in terms of so called effective rank of $Σ$ defined as ${\bf r}(Σ)=\frac{{\rm tr}(Σ)}{\|Σ\|_{\infty}},$ where ${\rm tr}(Σ)$ is the trace of $Σ$ and $\|Σ\|_{\infty}$ is its operator norm, as well as another parameter characterizing the size of ${\rm Var}(\|\hat P_r-P_r\|_2^2).$ Other results include non-asymptotic bounds and asymptotic representations for the mean squared Hilbert--Schmidt norm error ${\mathbb E}\|\hat P_r-P_r\|_2^2$ and the variance ${\rm Var}(\|\hat P_r-P_r\|_2^2),$ and concentration inequalities for $\|\hat P_r-P_r\|_2^2$ around its expectation.

preprint2015arXiv

Perturbation of linear forms of singular vectors under Gaussian noise

Let $A\in\mathbb{R}^{m\times n}$ be a matrix of rank $r$ with singular value decomposition (SVD) $A=\sum_{k=1}^rσ_k (u_k\otimes v_k),$ where $\{σ_k, k=1,\ldots,r\}$ are singular values of $A$ (arranged in a non-increasing order) and $u_k\in {\mathbb R}^m, v_k\in {\mathbb R}^n, k=1,\ldots, r$ are the corresponding left and right orthonormal singular vectors. Let $\tilde{A}=A+X$ be a noisy observation of $A,$ where $X\in\mathbb{R}^{m\times n}$ is a random matrix with i.i.d. Gaussian entries, $X_{ij}\sim\mathcal{N}(0,τ^2),$ and consider its SVD $\tilde{A}=\sum_{k=1}^{m\wedge n}\tildeσ_k(\tilde{u}_k\otimes\tilde{v}_k)$ with singular values $\tildeσ_1\geq\ldots\geq\tildeσ_{m\wedge n}$ and singular vectors $\tilde{u}_k,\tilde{v}_k,k=1,\ldots, m\wedge n.$ The goal of this paper is to develop sharp concentration bounds for linear forms $\langle \tilde u_k,x\rangle, x\in {\mathbb R}^m$ and $\langle \tilde v_k,y\rangle, y\in {\mathbb R}^n$ of the perturbed (empirical) singular vectors in the case when the singular values of $A$ are distinct and, more generally, concentration bounds for bilinear forms of projection operators associated with SVD. In particular, the results imply upper bounds of the order $O\biggl(\sqrt{\frac{\log(m+n)}{m\vee n}}\biggr)$ (holding with a high probability) on $$\max_{1\leq i\leq m}\big|\big<\tilde{u}_k-\sqrt{1+b_k}u_k,e_i^m\big>\big|\ \ {\rm and} \ \ \max_{1\leq j\leq n}\big|\big<\tilde{v}_k-\sqrt{1+b_k}v_k,e_j^n\big>\big|,$$ where $b_k$ are properly chosen constants characterizing the bias of empirical singular vectors $\tilde u_k, \tilde v_k$ and $\{e_i^m,i=1,\ldots,m\}, \{e_j^n,j=1,\ldots,n\}$ are the canonical bases of $\mathbb{R}^m, {\mathbb R}^n,$ respectively.

preprint2014arXiv

$L_1$-Penalization in Functional Linear Regression with Subgaussian Design

We study functional regression with random subgaussian design and real-valued response. The focus is on the problems in which the regression function can be well approximated by a functional linear model with the slope function being "sparse" in the sense that it can be represented as a sum of a small number of well separated "spikes". This can be viewed as an extension of now classical sparse estimation problems to the case of infinite dictionaries. We study an estimator of the regression function based on penalized empirical risk minimization with quadratic loss and the complexity penalty defined in terms of $L_1$-norm (a continuous version of LASSO). The main goal is to introduce several important parameters characterizing sparsity in this class of problems and to prove sharp oracle inequalities showing how the $L_2$-error of the continuous LASSO estimator depends on the underlying sparsity of the problem.

preprint2014arXiv

Concentration Inequalities and Moment Bounds for Sample Covariance Operators

Let $X,X_1,\dots, X_n,\dots$ be i.i.d. centered Gaussian random variables in a separable Banach space $E$ with covariance operator $Σ:$ $$ Σ:E^{\ast}\mapsto E,\ \ Σu = {\mathbb E}\langle X,u\rangle, u\in E^{\ast}. $$ The sample covariance operator $\hat Σ:E^{\ast}\mapsto E$ is defined as $$ \hat Σu := n^{-1}\sum_{j=1}^n \langle X_j,u\rangle X_j, u\in E^{\ast}. $$ The goal of the paper is to obtain concentration inequalities and expectation bounds for the operator norm $\|\hat Σ-Σ\|$ of the deviation of the sample covariance operator from the true covariance operator. In particular, it is shown that $$ {\mathbb E}\|\hat Σ-Σ\|\asymp \|Σ\|\biggl(\sqrt{\frac{{\bf r}(Σ)}{n}}\bigvee \frac{{\bf r}(Σ)}{n}\biggr), $$ where $$ {\bf r}(Σ):=\frac{\Bigl({\mathbb E}\|X\|\Bigr)^2}{\|Σ\|}. $$ Moreover, under the assumption that ${\bf r}(Σ)\lesssim n,$ it is proved that, for all $t\geq 1,$ with probability at least $1-e^{-t}$ \begin{align*} \Bigl|\|\hatΣ- Σ\|-{\mathbb E}\|\hatΣ- Σ\|\Bigr| \lesssim \|Σ\|\biggl(\sqrt{\frac{t}{n}}\bigvee \frac{t}{n}\biggr). \end{align*}

preprint2013arXiv

Bounding the smallest singular value of a random matrix without concentration

Given $X$ a random vector in ${\mathbb{R}}^n$, set $X_1,...,X_N$ to be independent copies of $X$ and let $Γ=\frac{1}{\sqrt{N}}\sum_{i=1}^N <X_i,\cdot>e_i$ be the matrix whose rows are $\frac{X_1}{\sqrt{N}},\dots, \frac{X_N}{\sqrt{N}}$. We obtain sharp probabilistic lower bounds on the smallest singular value $λ_{\min}(Γ)$ in a rather general situation, and in particular, under the assumption that $X$ is an isotropic random vector for which $\sup_{t\in S^{n-1}}{\mathbb{E}}|<t,X>|^{2+η} \leq L$ for some $L,η>0$. Our results imply that a Bai-Yin type lower bound holds for $η>2$, and, up to a log-factor, for $η=2$ as well. The bounds hold without any additional assumptions on the Euclidean norm $\|X\|_{\ell_2^n}$. Moreover, we establish a nontrivial lower bound even without any higher moment assumptions (corresponding to the case $η=0$), if the linear forms satisfy a weak `small ball' property.

preprint2013arXiv

Low rank estimation of smooth kernels on graphs

Let (V,A) be a weighted graph with a finite vertex set V, with a symmetric matrix of nonnegative weights A and with Laplacian $Δ$. Let $S_*:V\times V\mapsto{\mathbb{R}}$ be a symmetric kernel defined on the vertex set V. Consider n i.i.d. observations $(X_j,X_j',Y_j),j=1,\ldots,n$, where $X_j,X_j'$ are independent random vertices sampled from the uniform distribution in V and $Y_j\in{\mathbb{R}}$ is a real valued response variable such that ${\mathbb{E}}(Y_j|X_j,X_j')=S_*(X_j,X_j'),j=1,\ldots,n$. The goal is to estimate the kernel $S_*$ based on the data $(X_1,X_1',Y_1),\ldots,(X_n,X_n',Y_n)$ and under the assumption that $S_*$ is low rank and, at the same time, smooth on the graph (the smoothness being characterized by discrete Sobolev norms defined in terms of the graph Laplacian). We obtain several results for such problems including minimax lower bounds on the $L_2$-error and upper bounds for penalized least squares estimators both with nonconvex and with convex penalties.

preprint2012arXiv

Low Rank Estimation of Similarities on Graphs

Let (V, E) be a graph with vertex set V and edge set E. Let (X, X', Y) \in V \times V \times {-1, 1} be a random triple, where X, X' are independent uniformly distributed vertices and Y is a label indicating whether X, X' are "similar" (Y = +1), or not (Y = -1). Our goal is to estimate the regression function S\ast (u, v) = E(Y |X = u, X = v), u, v \in V based on training data consisting of n i.i.d. copies of (X, X',Y). We are interested in this problem in the case when S\ast is a symmetric low rank kernel and, in addition to this, it is assumed that S\ast is "smooth" on the graph. We study estimators based on a modified least squares method with complexity penalization involving both the nuclear norm and Sobolev type norms of symmetric kernels on the graph and prove upper bounds on L2 -type errors of such estimators with explicit dependence both on the rank of S\ast and on the degree of its smoothness.

preprint2012arXiv

Sharp Oracle Inequalities in Low Rank Estimation

The paper deals with the problem of penalized empirical risk minimization over a convex set of linear functionals on the space of Hermitian matrices with convex loss and nuclear norm penalty. Such penalization is often used in low rank matrix recovery in the cases when the target function can be well approximated by a linear functional generated by a Hermitian matrix of relatively small rank (comparing with the size of the matrix). Our goal is to prove sharp low rank oracle inequalities that involve the excess risk (the approximation error) with constant equal to one and the random error term with correct dependence on the rank of the oracle.

preprint2012arXiv

Sparsity in multiple kernel learning

The problem of multiple kernel learning based on penalized empirical risk minimization is discussed. The complexity penalty is determined jointly by the empirical $L_2$ norms and the reproducing kernel Hilbert space (RKHS) norms induced by the kernels with a data-driven choice of regularization parameters. The main focus is on the case when the total number of kernels is large, but only a relatively small number of them is needed to represent the target function, so that the problem is sparse. The goal is to establish oracle inequalities for the excess risk of the resulting prediction rule showing that the method is adaptive both to the unknown design distribution and to the sparsity of the problem.

preprint2010arXiv

Von Neumann Entropy Penalization and Low Rank Matrix Estimation

A problem of statistical estimation of a Hermitian nonnegatively definite matrix of unit trace (for instance, a density matrix in quantum state tomography) is studied. The approach is based on penalized least squares method with a complexity penalty defined in terms of von Neumann entropy. A number of oracle inequalities have been proved showing how the error of the estimator depends on the rank and other characteristics of the oracles. The methods of proofs are based on empirical processes theory and probabilistic inequalities for random matrices, in particular, noncommutative versions of Bernstein inequality.

preprint2007arXiv

2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization

Let $\mathcal{F}$ be a class of measurable functions $f:S\mapsto [0,1]$ defined on a probability space $(S,\mathcal{A},P)$. Given a sample (X_1,...,X_n) of i.i.d. random variables taking values in S with common distribution P, let P_n denote the empirical measure based on (X_1,...,X_n). We study an empirical risk minimization problem $P_nf\to \min$, $f\in \mathcal{F}$. Given a solution $\hat{f}_n$ of this problem, the goal is to obtain very general upper bounds on its excess risk \[\mathcal{E}_P(\hat{f}_n):=P\hat{f}_n-\inf_{f\in \mathcal{F}}Pf,\] expressed in terms of relevant geometric parameters of the class $\mathcal{F}$. Using concentration inequalities and other empirical processes tools, we obtain both distribution-dependent and data-dependent upper bounds on the excess risk that are of asymptotically correct order in many examples. The bounds involve localized sup-norms of empirical and Rademacher processes indexed by functions from the class. We use these bounds to develop model selection techniques in abstract risk minimization problems that can be applied to more specialized frameworks of regression and classification.

preprint2006arXiv

Concentration inequalities and asymptotic results for ratio type empirical processes

Let $\mathcal{F}$ be a class of measurable functions on a measurable space $(S,\mathcal{S})$ with values in $[0,1]$ and let \[P_n=n^{-1}\sum_{i=1}^nδ_{X_i}\] be the empirical measure based on an i.i.d. sample $(X_1,...,X_n)$ from a probability distribution $P$ on $(S,\mathcal{S})$. We study the behavior of suprema of the following type: \[\sup_{r_n<σ_Pf\leq δ_n}\frac{|P_nf-Pf|}{ϕ(σ_Pf)},\] where $σ_Pf\ge\operatorname {Var}^{1/2}_Pf$ and $ϕ$ is a continuous, strictly increasing function with $ϕ(0)=0$. Using Talagrand's concentration inequality for empirical processes, we establish concentration inequalities for such suprema and use them to derive several results about their asymptotic behavior, expressing the conditions in terms of expectations of localized suprema of empirical processes. We also prove new bounds for expected values of sup-norms of empirical processes in terms of the largest $σ_Pf$ and the $L_2(P)$ norm of the envelope of the function class, which are especially suited for estimating localized suprema. With this technique, we extend to function classes most of the known results on ratio type suprema of empirical processes, including some of Alexander's results for VC classes of sets. We also consider applications of these results to several important problems in nonparametric statistics and in learning theory (including general excess risk bounds in empirical risk minimization and their versions for $L_2$-regression and classification and ratio type bounds for margin distributions in classification).

preprint2006arXiv

Empirical graph Laplacian approximation of Laplace--Beltrami operators: Large sample results

Let ${M}$ be a compact Riemannian submanifold of ${{\bf R}^m}$ of dimension $\scriptstyle{d}$ and let ${X_1,...,X_n}$ be a sample of i.i.d. points in ${M}$ with uniform distribution. We study the random operators $$ Δ_{h_n,n}f(p):=\frac{1}{nh_n^{d+2}}\sum_{i=1}^n K(\frac{p-X_i}{h_n})(f(X_i)-f(p)), p\in M $$ where ${K(u):={\frac{1}{(4π)^{d/2}}}e^{-\|u\|^2/4}}$ is the Gaussian kernel and ${h_n\to 0}$ as ${n\to\infty.}$ Such operators can be viewed as graph laplacians (for a weighted graph with vertices at data points) and they have been used in the machine learning literature to approximate the Laplace-Beltrami operator of ${M,}$ ${Δ_Mf}$ (divided by the Riemannian volume of the manifold). We prove several results on a.s. and distributional convergence of the deviations ${Δ_{h_n,n}f(p)-{\frac{1}{|μ|}}Δ_Mf(p)}$ for smooth functions ${f}$ both pointwise and uniformly in ${f}$ and ${p}$ (here ${|μ|=μ(M)}$ and $μ$ is the Riemannian volume measure). In particular, we show that for any class ${\cal F}$ of three times differentiable functions on ${M}$ with uniformly bounded derivatives $$ \sup_{p\in M}\sup_{f\in F}\Big|Δ_{h_n,p}f(p)-\frac{1}{|μ|}Δ_Mf(p)\Big|= O\Big(\sqrt{\frac{\log(1/h_n)}{nh_n^{d+2}}}\Big) a.s. $$ as soon as $$ nh_n^{d+2}/\log h_n^{-1}\to \infty and nh^{d+4}_n/\log h_n^{-1}\to 0, $$ and also prove asymptotic normality of ${Δ_{h_n,p}f(p)-{\frac{1}{|μ|}}Δ_Mf(p)}$ (functional CLT) for a fixed ${p\in M}$ and uniformly in ${f}.$

preprint2006arXiv

High Dimensional Probability

About forty years ago it was realized by several researchers that the essential features of certain objects of Probability theory, notably Gaussian processes and limit theorems, may be better understood if they are considered in settings that do not impose structures extraneous to the problems at hand. For instance, in the case of sample continuity and boundedness of Gaussian processes, the essential feature is the metric or pseudometric structure induced on the index set by the covariance structure of the process, regardless of what the index set may be. This point of view ultimately led to the Fernique-Talagrand majorizing measure characterization of sample boundedness and continuity of Gaussian processes, thus solving an important problem posed by Kolmogorov. Similarly, separable Banach spaces provided a minimal setting for the law of large numbers, the central limit theorem and the law of the iterated logarithm, and this led to the elucidation of the minimal (necessary and/or sufficient) geometric properties of the space under which different forms of these theorems hold. However, in light of renewed interest in Empirical processes, a subject that has considerably influenced modern Statistics, one had to deal with a non-separable Banach space, namely $\mathcal{L}_{\infty}$. With separability discarded, the techniques developed for Gaussian processes and for limit theorems and inequalities in separable Banach spaces, together with combinatorial techniques, led to powerful inequalities and limit theorems for sums of independent bounded processes over general index sets, or, in other words, for general empirical processes.

preprint2004arXiv

Weighted uniform consistency of kernel density estimators

Let f_n denote a kernel density estimator of a continuous density f in d dimensions, bounded and positive. Let Ψ(t) be a positive continuous function such that \|Ψf^β\|_{\infty}<\infty for some 0<β<1/2. Under natural smoothness conditions, necessary and sufficient conditions for the sequence \sqrt\frac{nh_n^d}{2|\log h_n^d|}\|Ψ(t)(f_n(t)-Ef_n(t))\|_{\infty} to be stochastically bounded and to converge a.s. to a constant are obtained. Also, the case of larger values of βis studied where a similar sequence with a different norming converges a.s. either to 0 or to +\infty, depending on convergence or divergence of a certain integral involving the tail probabilities of Ψ(X). The results apply as well to some discontinuous not strictly positive densities.

Vladimir Koltchinskii

What is connected

Connect this record

See the researcher in context

Building this map preview

22 published item(s)

Estimation of smooth functionals in high-dimensional models: bootstrap chains and Gaussian approximation

Estimation of low rank density matrices: bounds in Schatten norms and other distances

New asymptotic results in principal component analysis

Nuclear norm penalization and optimal rates for noisy low rank matrix completion

Optimal Estimation of Low Rank Density Matrices

Asymptotics and Concentration Bounds for Bilinear Forms of Spectral Projectors of Sample Covariance

Estimation of Low-Rank Covariance Function

Normal approximation and concentration of spectral projectors of sample covariance

Perturbation of linear forms of singular vectors under Gaussian noise

$L_1$-Penalization in Functional Linear Regression with Subgaussian Design

Concentration Inequalities and Moment Bounds for Sample Covariance Operators

Bounding the smallest singular value of a random matrix without concentration

Low rank estimation of smooth kernels on graphs

Low Rank Estimation of Similarities on Graphs

Sharp Oracle Inequalities in Low Rank Estimation

Sparsity in multiple kernel learning

Von Neumann Entropy Penalization and Low Rank Matrix Estimation

2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization

Concentration inequalities and asymptotic results for ratio type empirical processes

Empirical graph Laplacian approximation of Laplace--Beltrami operators: Large sample results

High Dimensional Probability

Weighted uniform consistency of kernel density estimators