Ultrametric OGP - parametric RDT \emph{symmetric} binary perceptron connection

Mihailo Stojnic

cs.LGApr 21, 2026

Ultrametric OGP - parametric RDT \emph{symmetric} binary perceptron connection

Authors: Mihailo Stojnic

Abstract

In [97,99,100], an fl-RDT framework is introduced to characterize \emph{statistical computational gaps} (SCGs). Studying \emph{symmetric binary perceptrons} (SBPs), [100] obtained an \emph{algorithmic} threshold estimate $α_a\approx α_c^{(7)}\approx 1.6093$ at the 7th lifting level (for $κ=1$ margin), closely approaching $1.58$ local entropy (LE) prediction [18]. In this paper, we further connect parametric RDT to overlap gap properties (OGPs), another key geometric feature of the solution space. Specifically, for any positive integer $s$ , we consider $s$ -level ultrametric OGPs ( $ult_s$ -OGPs) and rigorously upper-bound the associated constraint densities $α_{ult_s}$ . To achieve this, we develop an analytical union-bounding program consisting of combinatorial and probabilistic components. By casting the combinatorial part as a convex problem and the probabilistic part as a nested integration, we conduct numerical evaluations and obtain that the tightest bounds at the first two levels, $\barα_{ult_1} \approx 1.6578$ and $\barα_{ult_2} \approx 1.6219$ , closely approach the 3rd and 4th lifting level parametric RDT estimates, $α_c^{(3)} \approx 1.6576$ and $α_c^{(4)} \approx 1.6218$ . We also observe excellent agreement across other key parameters, including overlap values and the relative sizes of ultrametric clusters. Based on these observations, we propose several conjectures linking $ult$ -OGP and parametric RDT. Specifically, we conjecture that algorithmic threshold $α_a=\lim_{s\rightarrow\infty} α_{ult_s} = \lim_{s\rightarrow\infty} \barα{ult_s} = \lim_{r\rightarrow\infty} α_{c}^{(r)}$ , and $α_{ult_s} \leq α_{c}^{(s+2)}$ (with possible equality for some (maybe even all) $s$ ). Finally, we discuss the potential existence of a full isomorphism connecting all key parameters of $ult$ -OGP and parametric RDT.

Explore similar work

Jun 18, 2026math.OC

Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Model

The John ellipsoid of a symmetric polytope

P=\{\mathbf{x}\in\mathbb{R}^d:\|\mathbf{A}\mathbf{x}\|_\infty\le1\}

\mathbf{A}\in\mathbb{R}^{n\times d}

, is computed by a long line of leverage-score algorithms, from Cohen, Cousins, Lee and Yang (COLT 2019) to its successors [WY24, CLS+25], all reaching a

(1+\varepsilon)

-approximation in

Θ(\varepsilon^{-1}\log(n/d))

iterations. We separate this complexity into three costs the modern line conflates (certification, identification, and accuracy) and locate the historical

\varepsilon^{-1}

in the first alone. In the equivalent D-optimal-design form

\min_{\mathbf{p}\inΔ_n}-\log\det(\sum_i p_i\mathbf{a}_i\mathbf{a}_i^\top)

, the leverage-score oracle is exactly the first-order oracle and the

(1+\varepsilon)

-John guarantee the Frank-Wolfe gap

g(\mathbf{p})\le\varepsilon d

; through this dictionary the costs come apart. The

\varepsilon^{-1}

is a certification artifact: the uniform average of the iterates, the certificate used throughout the line, has gap exactly

Θ(1/T)

, however cheap each iteration is made. Pointed instead at the last iterate the same oracle is fast: a warm-started accelerated method reaches the guarantee in

C(\mathbf{A})+O(\sqrtκ\log(1/\varepsilon))

queries after an

\varepsilon

-independent setup

C(\mathbf{A})

, and once the optimal face is identified the facial problem is an unconstrained self-concordant minimization whose Hessian the oracle recovers exactly, so damped Newton needs only

O(\log\log(1/\varepsilon))

steps, for a total of

C(\mathbf{A})+O(d^2\log\log(1/\varepsilon))

queries. The accuracy dependence is thus doubly logarithmic after an

\varepsilon

-independent, condition-dependent setup; the open problem is the remaining identification cost (a condition-free bound on reaching the optimal face) and lower bounds. Accuracy is not the obstruction.

Xiaoyu Li, Junwei Yu, Jiaojiao Jiang +2

Optimal Sample Complexity Polytopes Federated Averaging

Ask PDF

May 18, 2026cs.LG

The Symmetries of Three-Layer ReLU Networks

We develop a framework for analyzing parameter symmetries in deep ReLU networks and obtain a complete characterization of the generic parameter fibers for three-layer bottleneck architectures. Our approach provides explicit semi-algebraic descriptions of these fibers and yields a polynomial time algorithm for deciding functional equivalence of two parameters. The symmetries include discrete and continuous transformations arising from layer composition, and depend on whether deeper layers hide or preserve geometric structure from preceding layers. Finally, we show that some of these symmetries induce local conservation laws along gradient flow, while others do not.

Johanna Marie Gegenfurtner, Moritz Grillo, Guido Montúfar

Rectified Linear Unit Networks Symmetry Reparameterization Concept Bottleneck Models

Ask PDF

Jun 25, 2026cs.LG

Asymptotically Optimal Learning for Parametric Prophet Inequalities

We study learning in prophet inequalities with i.i.d. rewards drawn from an exponential-type parametric family with an unknown parameter

θ

, a class that includes exponential, Pareto, and bounded-support power-family distributions. We first characterize the optimal full-information asymptotic competitive ratio for this family. In the unbounded-support case, the limit is

{\left(θ/({θ-c_+})\right)^{c_+/θ}}/ {Γ(1-c_+/θ)},

while in the bounded-support case, the limit is

1

. We then propose a confidence-based dynamic-programming policy for online learning. By exploiting the explicit parametric structure, the policy achieves the same optimal asymptotic competitive ratio using only online observations, without external offline samples. We further derive distribution-specific convergence rates for canonical examples. Finally, numerical experiments on synthetic instances illustrate the performance of our algorithm.

Jung-hun Kim, Anna Grebennikova, Vianney Perchet

Concentration Inequalities Exponential Family

Ask PDF