What does big O mean in KNN optimal weights?

Question

Wiki gives this definition of KNN

In pattern recognition, the k-nearest neighbors algorithm (k-NN) is a non-parametric method used for classification and regression. In both cases, the input consists of the k closest training examples in the feature space. The output depends on whether k-NN is used for classification or regression:

• In k-NN classification, the output is a class membership. An object is classified by a plurality vote of its neighbors, with the object
  being assigned to the class most common among its k nearest neighbors (k is a positive integer, typically small). If k = 1, then the object is simply assigned to the class of that single nearest neighbor.
• In k-NN regression, the output is the property value for the object. This value is the average of the values of k nearest neighbors.

k-NN is a type of instance-based learning, or lazy learning, where the function is only approximated locally and all computation is deferred until classification.

Both for classification and regression, a useful technique can be to assign weights to the contributions of the neighbors, so that the nearer neighbors contribute more to the average than the more distant ones. For example, a common weighting scheme consists in giving each neighbor a weight of 1/d, where d is the distance to the neighbor.

and this explanation about "The weighted nearest neighbour classifier"

The k-nearest neighbour classifier can be viewed as assigning the k nearest neighbours a weight 1/k and all others 0 weight. This can be generalised to weighted nearest neighbour classifiers. That is, where the ith nearest neighbour is assigned a weight ${\displaystyle > w_{ni}}$, with ${\displaystyle \sum _{i=1}^{n}w_{ni}=1}$. An analogous result on the strong consistency of weighted nearest neighbour classifiers also holds.

Let $C_{n}^{wnn}$ denote the weighted nearest classifier with weights $\{w_{{ni}}\}_{{i=1}}^{n}$.

Subject to regularity conditions on the class distributions the excess risk has the following asymptotic expansion ${\mathcal {R}}_{{\mathcal {R}}}(C_{{n}}^{{wnn}})-{\mathcal {R}}_{{{\mathcal {R}}}}(C^{{Bayes}})=\left(B_{1}s_{n}^{2}+B_{2}t_{n}^{2}\right)\{1+o(1)\},$

and this formula

With optimal weights the dominant term in the asymptotic expansion of the excess risk is ${\mathcal {O}}(n^{{-{\frac 4{d+4}}}})$

Does $\mathcal {O}$ here mean the Big O notation or something else?

Answer 1

In this context, "O" is being used as shorthand for the big O notation, which is a mathematical notation used to describe the asymptotic behavior of a function. In the formula you provided, O(n−4d+4) is an upper bound on the dominant term in the asymptotic expansion of the excess risk for a weighted nearest neighbor classifier with optimal weights.

The big O notation is often used to describe the computational complexity of algorithms, and in this case it is being used to describe the asymptotic behavior of the excess risk as the size of the dataset (n) and the number of dimensions (d) increase. The specific form of the big O notation in this formula (O(n−4d+4)) indicates that the dominant term in the expansion of the excess risk decreases with increasing n and d, but the rate of decrease is polynomial rather than exponential. This is considered to be relatively efficient compared to other algorithms, which may have higher big O complexity (e.g. O(n^2) or O(n^3)).

Answer 2

To further clarify the answer of @Mohith7548 , the O() notation in your KNN description refers to the rate of convergence of the statistical estimator. This is not about computational efficiency of algorithms, but rather, how far are the estimates output by the KNN algorithm expected to be from perfect estimates (i.e. the best possible predictions) for a dataset with sample size n and dimensionality d. As n grows to infinity, the KNN estimator should converge to the optimal predictor (under some basic regularity conditions), and the O() formula describes how fast this convergence happens as n increases. The convergence is slower with high-dimensional data, because statistical estimation of more numbers is harder (see "curse of dimensionality").

See "convergence in probability" to learn more about this topic of statistical convergence rates (which are different that computational complexity).