Over the last decades, two distinct approaches have been instrumental to our understanding of the computational complexity of statistical estimation. The statistical physics literature predicts algorithmic hardness through local stability and monotonicity properties of the Franz–Parisi potential, while the rigorous average-case complexity literature characterizes hardness via the limitations of restricted algorithmic classes, most notably low-degree polynomial estimators. In this work, we show that for estimation problems the power of low-degree polynomials is governed by the monotonicity of the annealed Franz–Parisi potential for a broad family of Gaussian additive models. Subject to the low-degree conjecture for these Gaussian additive models, this identifies the polynomial-time estimation threshold with the monotonicity threshold of the annealed Franz–Parisi potential.

Mask-based pretraining has become a cornerstone of modern large-scale models across language, vision, and recently biology. Despite its empirical success, its role and limits in learning data representations have been unclear. In this work, we show that the behavior of mask-based pretraining can be directly characterized by test risk in high-dimensional minimum-norm ("ridge-less") linear regression, without relying on further model specifications. Further analysis of linear models uncovers several novel aspects of mask-based pretraining. The theoretical framework and its implications have been validated across diverse neural architectures (including MLPs, CNNs, and Transformers) applied to both vision and language tasks. Guided by our theory, we propose an embarrassingly simple yet overlooked pretraining scheme named *Randomly Random Mask AutoEncoding* (**R²MAE**), which enforces capturing multi-scale features from data and is able to outperform optimal fixed mask ratio settings in our linear model framework. We implement R²MAE in vision, language, DNA sequence, and single-cell models, where it consistently outperforms standard and more complicated masking schemes, leading to improvements for state-of-the-art models. Our code is available at [this URL](https://github.com/MingzeDong/r2mae).