Nearest neighbor has always been one of the most appealing non-parametric
approaches in machine learning, pattern recognition, computer vision, etc.
Previous empirical studies partly shows that nearest neighbor is resistant to
noise, yet there is a lack of deep analysis. This work presents the
finite-sample and distribution-dependent bounds on the consistency of nearest
neighbor in the random noise setting. The theoretical results show that, for
asymmetric noises, k-nearest neighbor is robust enough to classify most data
correctly, except for a handful of examples, whose labels are totally misled by
random noises. For symmetric noises, however, k-nearest neighbor achieves the
same consistent rate as that of noise-free setting, which verifies the
resistance of k-nearest neighbor to random noisy labels. Motivated by the
theoretical analysis, we propose the Robust k-Nearest Neighbor (RkNN) approach
to deal with noisy labels. The basic idea is to make unilateral corrections to
examples, whose labels are totally misled by random noises, and classify the
others directly by utilizing the robustness of k-nearest neighbor. We verify
the effectiveness of the proposed algorithm both theoretically and empirically.

通过研究在随机噪声情况下的 k - 最近邻（k-NN）一致性，提出了一种鲁棒的 k-NN 方法 (RkNN)，在处理噪声标签时具有一定的纠错和分类能力。

最近邻抵抗随机噪声标签

On the Resistance of Nearest Neighbor to Random Noisy Labels

Differential privacy is a cryptographically-motivated definition of privacy
which has gained significant attention over the past few years. Differentially
private solutions enforce privacy by adding random noise to a function computed
over the data, and the challenge in designing such algorithms is to control the
added noise in order to optimize the privacy-accuracy-sample size tradeoff.
This work studies differentially-private statistical estimation, and shows
upper and lower bounds on the convergence rates of differentially private
approximations to statistical estimators. Our results reveal a formal
connection between differential privacy and the notion of Gross Error
Sensitivity (GES) in robust statistics, by showing that the convergence rate of
any differentially private approximation to an estimator that is accurate over
a large class of distributions has to grow with the GES of the estimator. We
then provide an upper bound on the convergence rate of a differentially private
approximation to an estimator with bounded range and bounded GES. We show that
the bounded range condition is necessary if we wish to ensure a strict form of
differential privacy.

本研究探讨了差分隐私的统计估计问题，并且提出了差分隐私比较准确的估计方法，其中加入了随机噪声以提高数据的隐私保护性，同时也介绍了 Gross Error Sensitivity，将其与差分隐私紧密联系。

差分隐私统计估计的收敛速率

Convergence Rates for Differentially Private Statistical Estimation

Computing the first few singular vectors of a large matrix is a problem that
frequently comes up in statistics and numerical analysis. Given the presence of
noise, exact calculation is hard to achieve, and the following problem is of
importance:
\vskip2mm \centerline {\it How much a small perturbation to the matrix
changes the singular vectors ?} \vskip2mm Answering this question, classical
theorems, such as those of Davis-Kahan and Wedin, give tight estimates for the
worst-case scenario. In this paper, we show that if the perturbation (noise) is
random and our matrix has low rank, then better estimates can be obtained. Our
method relies on high dimensional geometry and is different from those used an
earlier papers.

本文提出了一种新方法，利用高维几何和随机噪声来更好地估计低秩矩阵的奇异向量，以应对矩阵扰动问题。