Subexponential optimization and sampling conjecture for the low-temperature CREM

About 2 years old · traced to

Consider a continuous random energy model (CREM) with concave covariance function AA, inverse temperature β>βc\beta>\beta_c, \tilde\text{ and } ?\text{?}, and ?\text{?}. Let OPT=max∣v∣=NXv\text{OPT}=\text{max}_{|v|=N}X_v and let KL\text{KL} denote Kullback–Leibler divergence. Low-temperature algorithmic tradeoff conjecture. For ?\text{?} and ?\text{?}, there is a 2O~ε(Nα)2^{\widetilde{O}_{\varepsilon}(N^\alpha)}-time algorithm which, with high probability, both finds v^\widehat v satisfying Xv^≥OPT−εN1−2αX_{\widehat v}\geq\mathrm{OPT}-\varepsilon N^{1-2\alpha} and outputs a distribution μ^\widehat\mu satisfying KL⁡(μ^∥μβ,N)≤εN1−2α\operatorname{KL}(\widehat\mu\|\mu_{\beta,N})\leq\varepsilon N^{1-2\alpha}. The conjecture proposes a Pareto tradeoff between running time and optimization and sampling accuracy in the low-temperature regime, while the supplied text does not specify whether it has been proved or disproved.

References

Primary source

Holden Lee and Qiang Wu, “Sampling from the Continuous Random Energy Model in Total Variation Distance”, arXiv:2407.00868 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.