Developing efficient and guaranteed nonconvex algorithms has been an important challenge in modern machine learning. Algorithms with good empirical performance such as stochastic gradient descent often lack theoretical guarantees. In this paper, we analyze the class of homotopy or continuation methods for global optimization of nonconvex functions. These methods start from an objective function that is efficient to optimize (e.g. convex), and progressively modify it to obtain the required objective, and the solutions are passed along the homotopy path. For the challenging problem of tensor PCA, we prove global convergence of the homotopy method in the "high noise" regime. The signal-to-noise requirement for our algorithm is tight in the sense that it matches the recovery guarantee for the best degree-4 sum-of-squares algorithm. In addition, we prove a phase transition along the homotopy path for tensor PCA. This allows to simplify the homotopy method to a local search algorithm, viz., tensor power iterations, with a specific initialization and a noise injection procedure, while retaining the theoretical guarantees.

In Supplementary Table 1 of this Article, 23 samples (B10K-DU-029-32, B10K-DU-029-33, B10K-DU-029-36 to B10K-DU-029-44, B10K-DU- 029-46, B10K-DU-029-47, B10K-DU-029-49 to B10K-DU-029-53, B10K-DU- 029-75 to B10K-DU-029-77, B10K-DU-029-80, and B10K-DU-030-03; styled in boldface in the revised table) were assigned to the incorrect institution. Supplementary Table 1 has been amended to reflect the correct source institution for these samples, and associated data (tissue, museum ID/source specimen ID, site, state/province, latitude, longitude, date collected and sex) have been updated accordingly. The original table is provided as Supplementary Information to this Amendment, and the original Article has been corrected online.

Whole-genome sequencing projects are increasingly populating the tree of life and characterizing biodiversity^1-4. Sparse taxon sampling has previously been proposed to confound phylogenetic inference⁵, and captures only a fraction of the genomic diversity. Here we report a substantial step towards the dense representation of avian phylogenetic and molecular diversity, by analysing 363 genomes from 92.4% of bird families-including 267 newly sequenced genomes produced for phase II of the Bird 10,000 Genomes (B10K) Project. We use this comparative genome dataset in combination with a pipeline that leverages a reference-free whole-genome alignment to identify orthologous regions in greater numbers than has previously been possible and to recognize genomic novelties in particular bird lineages. The densely sampled alignment provides a single-base-pair map of selection, has more than doubled the fraction of bases that are confidently predicted to be under conservation and reveals extensive patterns of weak selection in predominantly non-coding DNA. Our results demonstrate that increasing the diversity of genomes used in comparative studies can reveal more shared and lineage-specific variation, and improve the investigation of genomic characteristics. We anticipate that this genomic resource will offer new perspectives on evolutionary processes in cross-species comparative analyses and assist in efforts to conserve species.