Local Intrinsic Dimensionality and the Convergence Order of Fixed-Point Iteration

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 theoretical equivalence between the convergence order of fixed-point iteration and the local intrinsic dimensionality (LID) of the update function as measured from its fixed-point limit. We then show how an existing MLE estimator of LID can be adapted for the context of FPI to produce novel estimators of convergence order, even for those cases where the update function and the limit point of the iteration are unknown. Although most estimators of LID assume that the data samples are drawn from some distribution of distances to a reference point, we show how this assumption can be relaxed using the LID representation theorem. Experiments are provided for a variety of functions that show competitive performance against traditional estimators of convergence order.