Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Complexity: Approximation-Estimation Trade-off

In course

MATH-412: Statistical machine learning

A course on statistical machine learning for supervised and unsupervised learning ...

Description

This lecture covers the explicit and implicit control of complexity in hypothesis spaces, including variables, polynomial functions, spline functions, wavelet approximations, and RKHS bandwidth. It also discusses risk decomposition, the approximation-estimation trade-off, overfitting, regularization, prediction error, bias-variance tradeoff, and the complexity of models.

Instructor

Yoav Zemel

Official source

Ontological neighbourhood

Statistics

Data analysis: Cross-validation

Mathematics

Analysis: Numerical analysis

Related concepts (32)

Overfitting

In mathematical modeling, overfitting is "the production of an analysis that corresponds too closely or exactly to a particular set of data, and may therefore fail to fit to additional data or predict future observations reliably". An overfitted model is a mathematical model that contains more parameters than can be justified by the data. In a mathematical sense, these parameters represent the degree of a polynomial. The essence of overfitting is to have unknowingly extracted some of the residual variation (i.

Bias–variance tradeoff

In statistics and machine learning, the bias–variance tradeoff is the property of a model that the variance of the parameter estimated across samples can be reduced by increasing the bias in the estimated parameters. The bias–variance dilemma or bias–variance problem is the conflict in trying to simultaneously minimize these two sources of error that prevent supervised learning algorithms from generalizing beyond their training set: The bias error is an error from erroneous assumptions in the learning algorithm.

Regularization (mathematics)

In mathematics, statistics, finance, computer science, particularly in machine learning and inverse problems, regularization is a process that changes the result answer to be "simpler". It is often used to obtain results for ill-posed problems or to prevent overfitting. Although regularization procedures can be divided in many ways, the following delineation is particularly helpful: Explicit regularization is regularization whenever one explicitly adds a term to the optimization problem.

Computational complexity

In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem. The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory.

Generalization error

For supervised learning applications in machine learning and statistical learning theory, generalization error (also known as the out-of-sample error or the risk) is a measure of how accurately an algorithm is able to predict outcome values for previously unseen data. Because learning algorithms are evaluated on finite samples, the evaluation of a learning algorithm may be sensitive to sampling error. As a result, measurements of prediction error on the current data may not provide much information about predictive ability on new data.

Related lectures (38)

Model Selection Criteria: AIC, BIC, Cp

Explores model selection criteria like AIC, BIC, and Cp in statistics for data science.

Generalization in Deep Learning

Explores generalization in deep learning, covering model complexity, implicit bias, and the double descent phenomenon.

Generalization Theory

Explores generalization theory in machine learning, addressing challenges in higher-dimensional spaces and the bias-variance tradeoff.

Double Descent Curves: Overparametrization

Explores double descent curves and overparametrization in machine learning models, highlighting the risks and benefits.