# Fully lifted random duality theory

arXiv: https://arxiv.org/abs/2312.00070 · HTML: https://mlsanity.com/paper/2312.00070/

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Nov 2023.

## Built on by (most cited first, 18 of 18)

- [Fl RDT based ultimate lowering of the negative spherical perceptron capacity](https://mlsanity.com/paper/2312.16531/) (2023)
- [Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDT](https://mlsanity.com/paper/2506.19276/) (2025)
- [A CLuP algorithm to practically achieve ~ 0.76 SK--model ground state free energy](https://mlsanity.com/paper/2507.09247/) (2025)
- [Fixed width treelike neural networks capacity analysis -- generic activations](https://mlsanity.com/paper/2402.05696/) (2024)
- [Injectivity capacity of ReLU gates](https://mlsanity.com/paper/2410.20646/) (2024)
- [High-Dimensional Statistics: Reflections on Progress and Open Problems](https://mlsanity.com/paper/2605.05076/) (2026)
- [Capacity of the treelike sign perceptrons neural networks with one hidden layer -- RDT based upper bounds](https://mlsanity.com/paper/2312.08244/) (2023)
- [Lifted RDT based capacity analysis of the 1-hidden layer treelike sign perceptrons neural networks](https://mlsanity.com/paper/2312.08257/) (2023)
- [Deep ReLU networks -- injectivity capacity upper bounds](https://mlsanity.com/paper/2412.19677/) (2024)
- [CLuP practically achieves ~ 1.77 positive and ~ 0.33 negative Hopfield model ground state free energy](https://mlsanity.com/paper/2507.22396/) (2025)
- [Binary perceptron computational gap -- a parametric fl RDT view](https://mlsanity.com/paper/2511.01037/) (2025)
- [Capacity of the Hebbian-Hopfield network associative memory](https://mlsanity.com/paper/2403.01907/) (2024)
- [Parametric RDT approach to computational gap of symmetric binary perceptron](https://mlsanity.com/paper/2601.10628/) (2026)
- [Theoretical limits of descending ℓ0 sparse-regression ML algorithms](https://mlsanity.com/paper/2410.07651/) (2024)
- [Phase transition of descending phase retrieval algorithms](https://mlsanity.com/paper/2506.18275/) (2025)
- [Optimal spectral initializers impact on phase retrieval phase transitions -- an RDT view](https://mlsanity.com/paper/2506.18279/) (2025)
- [Phase retrieval with rank d measurements -- descending algorithms phase transitions](https://mlsanity.com/paper/2506.18282/) (2025)
- [Ultrametric OGP - parametric RDT symmetric binary perceptron connection](https://mlsanity.com/paper/2604.19712/) (2026)

## Abstract (arXiv)

We study a generic class of random optimization problems (rops) and their typical behavior. The foundational aspects of the random duality theory (RDT), associated with rops, were discussed in citeStojnicRegRndDlt10, where it was shown that one can often infer rops' behavior even without actually solving them. Moreover, citeStojnicRegRndDlt10 uncovered that various quantities relevant to rops (including, for example, their typical objective values) can be determined (in a large dimensional context) even completely analytically. The key observation was that the strong deterministic duality implies the, so-called, strong random duality and therefore the full exactness of the analytical RDT characterizations. Here, we attack precisely those scenarios where the strong deterministic duality is not necessarily present and connect them to the recent progress made in studying bilinearly indexed (bli) random processes in citeStojnicnflgscompyx23,Stojnicsflgscompyx23. In particular, utilizing a fully lifted (fl) interpolating comparison mechanism introduced in citeStojnicnflgscompyx23, we establish corresponding fully lifted RDT (fl RDT). We then rely on a stationarized fl interpolation realization introduced in citeStojnicsflgscompyx23 to obtain complete statitionarized fl RDT (sfl RDT). A few well known problems are then discussed as illustrations of a wide range of practical applications implied by the generality of the considered rops.