Curse of dimensionality

As explained in Bayesian Optimization in Action

The curse of dimensionality is the phenomenon in which computational or statistical costs grow exponentially as the number of dimensions increases.

The curse of dimensionality describes how many machine-learning procedures become exponentially more expensive as the dimensionality of the object of interest increases. In Bayesian optimization, estimating the distribution of an objective function’s optimizer requires exponentially more samples as the input vector grows. section 6.2.1 section 6.4

Optimizer location versus optimal value

Entropy search tries to model the optimizer x*, the input location where the objective reaches its maximum. Its distribution is complicated and increasingly costly to approximate in higher dimensions. A practical alternative targets the optimal value f* = f(x*), which is always one-dimensional; Max-value Entropy Search uses this reformulation to reduce the burden. section 6.2.1 section 6.4

Figure 6.11 The GP belief (top left), the distribution of the function optimizer x* (bottom), and the distribution of the optimal value f* (right). The distribution of the optimal value is always one-dimensional and, therefore, easier to work with than that of the optimizer.

Compare the complicated distribution of the optimizer x* with the one-dimensional distribution of the optimal value f*. section 6.2.1

How Bayesian Optimization in Action covers it

How deep it goes

Defines exponential cost and explains its effect on Gaussian-process sampling, stopping short of general complexity analysis.

Examples

Uses optimizer-location sampling and contrasts it with the one-dimensional optimal-value distribution.

What it assumes

Assumes familiarity with objective functions and Bayesian optimization while introducing the dimensionality-cost relationship directly.

What you can do after

Diagnose dimensionality bottlenecks and understand why targeting the optimal value enables a more tractable BayesOpt policy.

How it connects

Connects entropy search, Bayesian optimization, Gaussian processes, optimal values, and Max-value Entropy Search.

liveBookmanning.com

Read Bayesian Optimization in Action on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Natural Language Processing in Action, Second EditionThe curse of dimensionality is the difficulty of analyzing data as the number of dimensions grows, including sparse representations and increased computational cost.
• 

  liveBookmanning.com
  Advanced Algorithms and Data StructuresThe curse of dimensionality is the set of effects that make data analysis and algorithmic search increasingly difficult as the number of dimensions grows.
• 

  liveBookmanning.com
  Outlier Detection in PythonThe curse of dimensionality is a set of difficulties caused by increasing dimensionality, including data sparsity, less informative distances, and rapidly increasing computational demands.
• 

  liveBookmanning.com
  Data Without LabelsThe curse of dimensionality is the set of difficulties that arise when analyzing data in spaces with many dimensions, including degraded distance behavior, sparsity, increased computation, and overfitting.
• 

  liveBookmanning.com
  Build a Robo-Advisor with Python (From Scratch)The curse of dimensionality is the rapid growth in computational and data requirements as the number of states, variables, or dimensions in a problem increases.
• 

  liveBookmanning.com
  How Large Language Models WorkThe curse of dimensionality is the phenomenon in which increasing the number of dimensions causes the space, data requirements, and computational costs to grow substantially.

Compare how 7 books explain curse of dimensionality →

Related concepts

• dimensionality reductionaddressed by · Dimensionality reduction is the transformation of data into a representation with fewer dimensions while retaining selected information, structure, or relationships.
• feature selectionaddressed by · Feature selection is the process of choosing a subset of input features for use in a modeling, analysis, or prediction task.
• distance-based algorithmcontrasts with · A distance-based algorithm analyzes or identifies observations using distances between data points.
• univariate statistical testaddressed by · A univariate statistical test is a statistical procedure that analyzes one variable at a time to evaluate a statistical property, association, or unusualness.
• kernel density estimatecontrasts with · A kernel density estimate is a nonparametric probability-density estimate formed by combining localized kernel functions centered on observed data points.

This explainer was generated by Manning's knowledge graph from the text of Bayesian Optimization in Action. The section links point to the parts of the book it draws on.