MerQuR+Statistics Glossary

Statistics Glossary → Random starts and local optima

Random starts and local optimaconcept

Running an iterative algorithm many times from different starting points, so that it does not get stuck in a merely local optimum and has a better chance of reaching the true best solution.

Methods such as k-means, the EM algorithm in latent class and profile analysis, neural-network training or t-SNE improve an objective function (within-cluster sum of squares, log-likelihood, loss) step by step. These functions can have many peaks or valleys; the algorithm converges to the one nearest its starting point, which may not be the global optimum. The algorithm is therefore run many times from different random starts and the solution with the best objective value is reported. Smart initialization methods such as k-means++ choose starting centres far apart from one another and so reduce the chance of ending in a poor solution.

Finding the best log-likelihood again from many starts gives confidence that the global optimum has been reached; if it was found only once, the number of starts should be increased. The random seed should be reported so that results can be reproduced. More starts lengthen computation time but never lower the quality of the solution. Disagreement between solutions can also signal that the model (e.g. one with many classes) is not well supported by the data.

An everyday example

A hiker trying to find the highest summit in foggy mountains, who simply follows whichever direction goes uphill at each step, will reach the top of the nearest small hill and may mistake it for the highest point. Starting the same walk from 20 different places in the region and picking the highest summit reached greatly improves the chance of finding the real highest peak.

In MerQur

It is set with 'Initialization (k-means++ / Random)' and 'Number of starts (nstart)' in K-Means Clustering, 'Number of random starts and Random seed' in Latent Class and Latent Profile Analysis, 'Seed repeats (initializations)' in the Neural Network, 'Initialization (PCA / Random)' in t-SNE and 'Number of starts' in Multidimensional Scaling. In the Unobserved Components Model, because the likelihood can be multimodal, multi-start ML selects the best log-likelihood.

Analyses where this concept appears

Neural Network (MLP)K-Means ClusteringLatent Class Analysis (LCA)Latent Profile Analysis (LPA)t-SNE (t-Distributed Stochastic Neighbor Embedding)Multidimensional Scaling (MDS)Unobserved Components Model (Structural Time Series)

Related concepts

Convergence and maximum iterationsRandom seed