Local intrinsic dimensionality and the estimation of convergence order

Fixed-point iteration (FPI) is a crucially important technique at the foundation of many scientific and engineering fields, such as numerical analysis, dynamical systems, optimization, and machine learning. In these domains, algorithmic efficiency and stability is often assessed using the notion of convergence order, a quantity whose estimation has typically involved line fitting in log–log space, or finding the limit of an associated function on differences of sequence values. In this paper, we establish a precise equivalence between the convergence order of a fixed-point update function and the local intrinsic dimensionality (LID) of that function once its fixed point is translated to the origin. Building on this insight, we propose a unified framework for re-purposing existing distributional estimators of LID to estimate the convergence order. Of the LID estimators considered, we show that two, the MLE (Hill) estimator and a Bayesian estimator, have practical and convenient closed-form expressions. We further investigate how these estimators of convergence order can be enhanced using Aitken’s Δ² method for accelerating convergence in slow scenarios, as well as a Bayesian smoothing layer for reducing variance when the number of samples is small. Empirically, we benchmark our LID-based estimators against classical sequenced-based and curve-fitting methods in three experimental settings: root-finding, general iteration, and machine learning regression. Results indicate that our approaches frequently match or surpass the classical estimators in accuracy, while offering robust performance over a broader range of convergence scenarios.