I am wondering how to draw a sample complexity plot similar to the following figure which shows the estimated number of samples to incur no more than 10 percent generalisation error on average for the least squares algorithm for classification.

Sample Complexity Least Squeres

The problem assumes that we have $m$ patterns $\mathbf{x}_1,...,\mathbf{x}_m$ sampled uniformly at random from $\{−1,1\}^n$, where each label is defined as $y_i:=x_{i,1}$ (s.t. the label of pattern $\mathbf{x}$ is just its first coordinate). And the goal is to estimate the sample complexity as a function of the dimension ($n$) of the dataset.

The m (examples) versus n (dimension of dataset) plot also includes error bars indicating the standard deviation for the estimates of m. I'm not interested in that, just the function estimation.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.