# Regularly random duality

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Mar 2013.

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

- [Binary perceptrons capacity via fully lifted random duality theory](https://mlsanity.com/paper/2312.00073/) (2023)
- [Fl RDT based ultimate lowering of the negative spherical perceptron capacity](https://mlsanity.com/paper/2312.16531/) (2023)
- [Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective](https://mlsanity.com/paper/2109.09859/) (2021)
- [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)
- [Parametric RDT approach to computational gap of symmetric binary perceptron](https://mlsanity.com/paper/2601.10628/) (2026)
- [Phase Transitions in Recovery of Structured Signals from Corrupted Measurements](https://mlsanity.com/paper/2101.00599/) (2021)
- [Causal Inference (C-inf) -- closed form worst case typical phase transitions](https://mlsanity.com/paper/2301.00793/) (2023)
- [Causal Inference (C-inf) -- asymmetric scenario of typical phase transitions](https://mlsanity.com/paper/2301.00801/) (2023)
- [Exact objectives of random linear programs and mean widths of random polyhedrons](https://mlsanity.com/paper/2403.03637/) (2024)
- [Ridge interpolators in correlated factor regression models -- exact risk analysis](https://mlsanity.com/paper/2406.09183/) (2024)
- [Precise analysis of ridge interpolators under heavy correlations -- a Random Duality Theory view](https://mlsanity.com/paper/2406.09199/) (2024)
- [Theoretical limits of descending ℓ0 sparse-regression ML algorithms](https://mlsanity.com/paper/2410.07651/) (2024)
- [Sparsifying Suprema of Gaussian Processes](https://mlsanity.com/paper/2411.14664/) (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)
- [Precise sample covariance spectral norm error -- an RDT view](https://mlsanity.com/paper/2607.14460/) (2026)

## Abstract (arXiv)

In this paper we look at a class of random optimization problems. We discuss ways that can help determine typical behavior of their solutions. When the dimensions of the optimization problems are large such an information often can be obtained without actually solving the original problems. Moreover, we also discover that fairly often one can actually determine many quantities of interest (such as, for example, the typical optimal values of the objective functions) completely analytically. We present a few general ideas and emphasize that the range of applications is enormous.