論文の概要: Ultrametric OGP - parametric RDT \emph{symmetric} binary perceptron connection

• arxiv url: http://arxiv.org/abs/2604.19712v1
• Date: Tue, 21 Apr 2026 17:36:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-22 22:41:49.905103
• Title: Ultrametric OGP - parametric RDT \emph{symmetric} binary perceptron connection
• Title（参考訳）: 超音波OGP-パラメトリックRTT \emph{symmetric}バイナリパーセプトロン接続
• Authors: Mihailo Stojnic,
• Abstract要約: 97,99,100]では,数値計算ギャップ(SCG)を特徴づけるfl-RDTフレームワークが導入された。 さらにパラメトリックRTTを重なり合うギャップ特性(OGP)に接続する。 我々は$ult$-OGP とパラメータ RDT をリンクするいくつかの予想を提案する。
• 参考スコア（独自算出の注目度）: 2.538209532048867
• License: http://creativecommons.org/licenses/by/4.0/
• 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.
• Abstract（参考訳）: 97,99,100]では、fl-RDTフレームワークを導入して、 \emph{statistical compute gaps} (SCGs) を特徴付ける。 Emph{symmetric binary perceptrons} (SBPs) を調べたところ、[100] は7番目のリフトレベル(κ=1$マージン)で \emph{algorithmic} しきい値の推定値 $α_a\approx α_c^{(7)}\approx 1.6093$ を得た。 本稿ではさらにパラメトリックRTTを、解空間の別の重要な幾何学的特徴であるギャップ特性(OGP)と重なり合うように接続する。 具体的には、任意の正の整数 $s$ に対して、$s$ レベルのウルトラメトリック OGPs (ult_s$-OGPs) と、関連する制約密度 $α_{ult_s}$ を厳密に上界に考える。 そこで我々は,組合せ的および確率的成分からなる解析的ユニオンバウンディングプログラムを開発した。 結合部を凸問題として、確率部をネスト積分として、数値的な評価を行い、最初の2つのレベルにおいて最も厳しい境界である $\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$。 また、重なり値や超音速クラスタの相対サイズなど、他の重要なパラメータ間での優れた一致も観察する。 これらの観測に基づいて、$ult$-OGP とパラメータ RDT をリンクするいくつかの予想を提案する。 具体的には、アルゴリズムしきい値 $α_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)}$ を予想する。 最後に、$ult$-OGP とパラメトリック RDT のすべてのキーパラメータを連結する完全同型の存在の可能性について議論する。

関連論文リスト

• Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1)$-Smoothness [74.18546828528298]
  SignSGD with Majority Votingは,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappaka ppakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa -1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappappapa-1right,Kappaを用いて,複雑性の全範囲で堅牢に動作することを示す。
  論文  参考訳（メタデータ） (2025-02-11T19:54:11Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• On the $O(\frac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [54.28350823319057]
  本稿では、RMSPropとその運動量拡張を考察し、$frac1Tsum_k=1Tの収束速度を確立する。 我々の収束率は、次元$d$を除くすべての係数に関して下界と一致する。 収束率は$frac1Tsum_k=1Tと類似していると考えられる。
  論文  参考訳（メタデータ） (2024-02-01T07:21:32Z)
• How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initialization [46.55524654398093]
  過パラメータ化が降下の収束挙動をどのように変化させるかを示す。 目的は、ほぼ等方的線形測定から未知の低ランクの地上構造行列を復元することである。 本稿では,GDの一段階だけを修飾し,$alpha$に依存しない収束率を求める手法を提案する。
  論文  参考訳（メタデータ） (2023-10-03T03:34:22Z)
• Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces [2.687607197645453]
  次元$Theta(log n)$ が $(sqrt3/2-o(1))$hard である場合でさえ、FPTアルゴリズムを近似する。 また、次元 $Theta(log n)$ が $(sqrt3/2-o(1))$hard であるような特別な場合でさえ、FPTアルゴリズムを近似することを示す。
  論文  参考訳（メタデータ） (2023-05-12T08:43:28Z)
• On the Complexity of Decentralized Smooth Nonconvex Finite-Sum Optimization [21.334985032433778]
  分散最適化問題 $min_bf xinmathbb Rd f(bf x)triq frac1msum_i=1m f_i(bf x)triq frac1nsum_j=1n。
  論文  参考訳（メタデータ） (2022-10-25T11:37:11Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。