Almost-Optimal Local-Search Methods for Sparse Tensor PCA

Max Lovig ⋆ , Conor Sheehan ⋆ , Konstantinos Tsirkas ⋆ and Ilias Zadik ⋆ · 2025

Read Almost-Optimal Local-Search Methods for Sparse Tensor PCA by Max Lovig ⋆ , Conor Sheehan ⋆ , Konstantinos Tsirkas ⋆ and Ilias Zadik ⋆ (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-09959.txt.

Introduction

Max Lovig, Conor Sheehan, Konstantinos Tsirkas, and Ilias Zadik wrote a 2025 statistics paper on local search methods for sparse tensor PCA. Local search is used everywhere in practice, yet its theory lags behind rival estimator families. Recent work had exposed a gap: broad classes of local Markov chain methods underperform other polynomial time algorithms on this problem.

The authors propose a family of local search methods that provably closes that gap. The set includes standard and randomized greedy algorithms run on a regularized posterior. It also includes new random threshold variants, which accept a move only when the gain clears a random bar. Their guarantees cover the known hard regimes and go beyond them. The work gives a widely used heuristic a firmer foundation.

Catalog record

CREATORMax Lovig ⋆ , Conor Sheehan ⋆ , Konstantinos Tsirkas ⋆ and Ilias Zadik ⋆
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE278 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-09959

Browse the full library · About the Tower of Babel