論文の概要: Parametric RDT approach to computational gap of symmetric binary perceptron
- arxiv url: http://arxiv.org/abs/2601.10628v1
- Date: Thu, 15 Jan 2026 17:48:58 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-01-16 19:43:19.249991
- Title: Parametric RDT approach to computational gap of symmetric binary perceptron
- Title（参考訳）: 対称二元パーセプトロンの計算ギャップに対するパラメトリックRDT法
- Authors: Mihailo Stojnic,
- Abstract要約: 対称二元性パーセプトロン (SBP) における統計計算的ギャップ (SCG) の存在の可能性について, 浮揚ランダム双対性理論のパラメトリック利用による検討を行った。
第2昇降レベルでは、減少から任意に注文された$c$-sequenceへの構造変化が観察され、エンファシビリティに関連づけられた。
- 参考スコア（独自算出の注目度）: 2.538209532048867
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study potential presence of statistical-computational gaps (SCG) in symmetric binary perceptrons (SBP) via a parametric utilization of \emph{fully lifted random duality theory} (fl-RDT) [96]. A structural change from decreasingly to arbitrarily ordered $c$-sequence (a key fl-RDT parametric component) is observed on the second lifting level and associated with \emph{satisfiability} ($α_c$) -- \emph{algorithmic} ($α_a$) constraints density threshold change thereby suggesting a potential existence of a nonzero computational gap $SCG=α_c-α_a$. The second level estimate is shown to match the theoretical $α_c$ whereas the $r\rightarrow \infty$ level one is proposed to correspond to $α_a$. For example, for the canonical SBP ($κ=1$ margin) we obtain $α_c\approx 1.8159$ on the second and $α_a\approx 1.6021$ (with converging tendency towards $\sim 1.59$ range) on the seventh level. Our propositions remarkably well concur with recent literature: (i) in [20] local entropy replica approach predicts $α_{LE}\approx 1.58$ as the onset of clustering defragmentation (presumed driving force behind locally improving algorithms failures); (ii) in $α\rightarrow 0$ regime we obtain on the third lifting level $κ\approx 1.2385\sqrt{\frac{α_a}{-\log\left ( α_a \right ) }}$ which qualitatively matches overlap gap property (OGP) based predictions of [43] and identically matches local entropy based predictions of [24]; (iii) $c$-sequence ordering change phenomenology mirrors the one observed in asymmetric binary perceptron (ABP) in [98] and the negative Hopfield model in [100]; and (iv) as in [98,100], we here design a CLuP based algorithm whose practical performance closely matches proposed theoretical predictions.
- Abstract（参考訳）: 対称二元性パーセプトロン (SBP) における統計計算的ギャップ (SCG) の存在の可能性について, \emph{fully lifted random duality theory} (fl-RDT) [96] のパラメトリック利用による検討を行った。
第2昇降レベルでは、減少から任意に順序付けられた$c$-sequence(キーfl−RDTパラメトリック成分)への構造変化が観察され、非ゼロ計算ギャップ$SCG=α_c-α_a$の可能性を示唆する。
2階の推定値は理論上の$α_c$と一致するが、$r\rightarrow \infty$は$α_a$に対応するように提案される。
例えば、標準 SBP (κ=1$ margin) に対して、第2位は$α_c\approx 1.8159$、第7位は$α_a\approx 1.6021$となる(収束傾向は$\sim 1.59$ range)。
我々の命題は最近の文献と著しく一致している。
i) 局所エントロピーレプリカのアプローチでは、クラスタリングのデフラグメンテーションの開始として$α_{LE}\approx 1.58$を予測している。
i) $α\rightarrow 0$ regime において、[43] のオーバーラップギャップ特性(OGP) に基づく予測と、[24] の局所エントロピーに基づく予測とを質的に一致させる第3のリフトレベル $κ\approx 1.2385\sqrt {\frac{α_a}{-\log\left (α_a \right ) }}$ を得る。
(iii)$c$-sequence ordering change showmenologyは[98]の非対称二項パーセプトロン(ABP)および[100]の負ホップフィールドモデルで観測されたものを反映する。
ここでは,[98,100]と同様に,提案した理論予測と実用性能を密接に一致させるCLuPベースのアルゴリズムを設計する。
関連論文リスト
- Binary perceptron computational gap -- a parametric fl RDT view [2.538209532048867]
非対称二元パーセプトロン(ABP)は2つの相転移性制約密度閾値を示す。
本稿では, 高速昇降ランダム双対性理論 (fl RDT) [85] のパラメトリック利用について検討し, その可能性について検討する。
論文 参考訳（メタデータ） (2025-11-02T18:23:49Z) - Beyond likelihood ratio bias: Nested multi-time-scale stochastic approximation for likelihood-free parameter estimation [49.78792404811239]
確率分析形式が不明なシミュレーションベースモデルにおける推論について検討する。
我々は、スコアを同時に追跡し、パラメータ更新を駆動する比率のないネスト型マルチタイムスケール近似(SA)手法を用いる。
我々のアルゴリズムは、オリジナルのバイアス$Obig(sqrtfrac1Nbig)$を排除し、収束率を$Obig(beta_k+sqrtfracalpha_kNbig)$から加速できることを示す。
論文 参考訳（メタデータ） (2024-11-20T02:46:15Z) - Relative-Translation Invariant Wasserstein Distance [82.6068808353647]
距離の新しい族、相対翻訳不変ワッサーシュタイン距離(RW_p$)を導入する。
我々は、$RW_p 距離もまた、分布変換に不変な商集合 $mathcalP_p(mathbbRn)/sim$ 上で定義される実距離測度であることを示す。
論文 参考訳（メタデータ） (2024-09-04T03:41:44Z) - Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳（メタデータ） (2024-04-29T15:04:07Z) - Replicable Clustering [57.19013971737493]
我々は,統計学的な$k$-medians,統計学的な$k$-means,統計学的な$k$-centers問題のアルゴリズムをブラックボックス方式で近似ルーチンを用いて提案する。
理論的結果を検証するブラックボックスとしてsklearnの$k$-means++実装を用いた2次元合成分布の実験も行っている。
論文 参考訳（メタデータ） (2023-02-20T23:29:43Z) - Stochastic Zeroth order Descent with Structured Directions [10.604744518360464]
我々は, 有限差分法であるStructured Zeroth Order Descent (SSZD)を導入・解析し, 集合 $lleq d 方向の勾配を近似し, $d は周囲空間の次元である。
凸凸に対して、すべての$c1/2$に対して$O( (d/l) k-c1/2$)$ 上の関数の収束はほぼ確実に証明する。
論文 参考訳（メタデータ） (2022-06-10T14:00:06Z) - Single Trajectory Nonparametric Learning of Nonlinear Dynamics [8.438421942654292]
力学系の1つの軌道が与えられた場合、非パラメトリック最小二乗推定器(LSE)の性能を解析する。
我々は最近開発された情報理論手法を活用し、非仮説クラスに対するLSEの最適性を確立する。
我々は、リプシッツ力学、一般化線形モデル、再生ケルネルヒルベルト空間(RKHS)のある種のクラスで記述される関数によって記述される力学など、実用上の関心のあるいくつかのシナリオを専門とする。
論文 参考訳（メタデータ） (2022-02-16T19:38:54Z) - Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。
我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。
また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
論文 参考訳（メタデータ） (2021-07-02T16:21:52Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z) - A Precise High-Dimensional Asymptotic Theory for Boosting and
Minimum-$\ell_1$-Norm Interpolated Classifiers [3.167685495996986]
本稿では,分離可能なデータの強化に関する高精度な高次元理論を確立する。
統計モデルのクラスでは、ブースティングの普遍性誤差を正確に解析する。
また, 推力試験誤差と最適ベイズ誤差の関係を明示的に説明する。
論文 参考訳（メタデータ） (2020-02-05T00:24:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。