SCIENCE@home

Instability, Computational Efficiency and Statistical Accuracy

Nhat Ho,K. Khamaru,Raaz Dwivedi,M. Wainwright,Michael I. Jordan,Bin Yu

Published 2020 in arXiv.org

ABSTRACT

Many statistical estimators are defined as the fixed point of a data-dependent operator, with estimators based on minimizing a cost function being an important special case. The limiting performance of such estimators depends on the properties of the population-level operator in the idealized limit of infinitely many samples. We develop a general framework that yields bounds on statistical accuracy based on the interplay between the deterministic convergence rate of the algorithm at the population level, and its degree of (in)stability when applied to an empirical object based on $n$ samples. Using this framework, we analyze both stable forms of gradient descent and some higher-order and unstable algorithms, including Newton's method and its cubic-regularized variant, as well as the EM algorithm. We provide applications of our general results to several concrete classes of models, including Gaussian mixture estimation, single-index models, and informative non-response models. We exhibit cases in which an unstable algorithm can achieve the same statistical accuracy as a stable algorithm in exponentially fewer steps---namely, with the number of iterations being reduced from polynomial to logarithmic in sample size $n$.

PUBLICATION RECORD

  • Publication year

    2020

  • Venue

    arXiv.org

  • Publication date

    2020-05-22

  • Fields of study

    Mathematics, Computer Science

  • Identifiers
    arXiv 2005.11411
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-50 of 50 references · Page 1 of 1

CITED BY

Showing 1-20 of 20 citing papers · Page 1 of 1