Cover Image

The Algorithmic Phase Transition in Correlated Spiked Models

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Li, Zhangsong
Format:	Preprint
Published:	2025
Subjects:	Statistics Theory Machine Learning Probability 68Q87, 68Q17
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguity
by: Li, Zhangsong
Published: (2025)

Improved Computational Lower Bound of Estimation for Multi-Frequency Group Synchronization
by: Li, Zhangsong
Published: (2026)

Algorithmic Contiguity from Low-Degree Heuristic II: Predicting Detection-Recovery Gaps
by: Li, Zhangsong
Published: (2026)

A computational transition for detecting correlated stochastic block models by low-degree polynomials
by: Chen, Guanyi, et al.
Published: (2024)

A Smooth Computational Transition in Tensor PCA
by: Li, Zhangsong
Published: (2025)

Robust random graph matching in Gaussian models via vector approximate message passing
by: Li, Zhangsong
Published: (2024)

A polynomial-time iterative algorithm for random graph matching with non-vanishing correlation
by: Ding, Jian, et al.
Published: (2023)

Low-Degree Hardness of Detection for Correlated Erdős-Rényi Graphs
by: Ding, Jian, et al.
Published: (2023)

The Umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regime
by: Gong, Shuyang, et al.
Published: (2024)

Polynomial Identity Testing via Evaluation of Rational Functions
by: Hu, Ivan, et al.
Published: (2022)

Approximation and generalization properties of the random projection classification method
by: Boutin, Mireille, et al.
Published: (2021)

Information-Theoretic Thresholds for Bipartite Latent-Space Graphs under Noisy Observations
by: Göbel, Andreas, et al.
Published: (2026)

Fundamental Limits of Community Detection in Contextual Multi-Layer Stochastic Block Models
by: Gong, Shuyang, et al.
Published: (2026)

Private Evolution Converges
by: González, Tomás, et al.
Published: (2025)

Analysis of multivariate symbol statistics in primitive rational models
by: Goldwurm, Massimiliano, et al.
Published: (2026)

Stochastic gradient descent in high dimensions for multi-spiked tensor PCA
by: Arous, Gérard Ben, et al.
Published: (2024)

Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization
by: Lin, Tianrong
Published: (2023)

Computational barriers for permutation-based problems, and cumulants of weakly dependent random variables
by: Even, Bertrand, et al.
Published: (2025)

A Proof of The Changepoint Detection Threshold Conjecture in Preferential Attachment Models
by: Du, Hang, et al.
Published: (2025)

Teaching and Learning under Deductive Errors
by: Telle, Jan Arne, et al.
Published: (2026)

Computational lower bounds in latent models: clustering, sparse-clustering, biclustering
by: Even, Bertrand, et al.
Published: (2025)

Sharp threshold for network recovery from voter model dynamics
by: Du, Hang, et al.
Published: (2025)

Langevin dynamics for high-dimensional optimization: the case of multi-spiked tensor PCA
by: Arous, Gérard Ben, et al.
Published: (2024)

Asymptotic Optimism of Random-Design Linear and Kernel Regression Models
by: Luo, Hengrui, et al.
Published: (2025)

Adaptive learning of density ratios in RKHS
by: Zellinger, Werner, et al.
Published: (2023)

A semiconcavity approach to stability of entropic plans and exponential convergence of Sinkhorn's algorithm
by: Chiarini, Alberto, et al.
Published: (2024)

Finding a dense submatrix of a random matrix. Sharp bounds for online algorithms
by: Bhamidi, Shankar, et al.
Published: (2025)

The Kikuchi Hierarchy and Tensor PCA
by: Wein, Alexander S., et al.
Published: (2019)

Heart Disease Detection using Quantum Computing and Partitioned Random Forest Methods
by: Heidari, Hanif, et al.
Published: (2022)

Permutation recovery of spikes in noisy high-dimensional tensor estimation
by: Arous, Gérard Ben, et al.
Published: (2024)

Online minimum search for a Brownian bridge
by: Wu, Erik, et al.
Published: (2024)

Adaptivity Under Realizability Constraints: Comparing In-Context and Agentic Learning
by: Kratsios, Anastasis, et al.
Published: (2026)

Domain Generalization by Functional Regression
by: Holzleitner, Markus, et al.
Published: (2023)

Low-temperature Sampling on Sparse Random Graphs
by: Galanis, Andreas, et al.
Published: (2025)

Planting and MCMC Sampling from the Potts model
by: Galanis, Andreas, et al.
Published: (2024)

The Breakdown of Gaussian Universality in Classification of High-dimensional Linear Factor Mixtures
by: Mai, Xiaoyi, et al.
Published: (2024)

A packing lemma for VCN${}_k$-dimension and learning high-dimensional data
by: Coregliano, Leonardo N., et al.
Published: (2025)

Higher-Order Feature Attribution: Bridging Statistics, Explainable AI, and Topological Signal Processing
by: Butler, Kurt, et al.
Published: (2025)

Towards regularized learning from functional data with covariate shift
by: Holzleitner, Markus, et al.
Published: (2026)

Non-Robustness of the Zero-Temperature-Limit Gibbs Measures to Perturbations of the Potential
by: Gayral, Léo, et al.
Published: (2025)