論文の概要: Binary perceptron computational gap -- a parametric fl RDT view
- arxiv url: http://arxiv.org/abs/2511.01037v1
- Date: Sun, 02 Nov 2025 18:23:49 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-11-05 16:37:27.039349
- Title: Binary perceptron computational gap -- a parametric fl RDT view
- Title（参考訳）: 双対パーセプトロン計算ギャップ-パラメトリックfl RDT
- Authors: Mihailo Stojnic,
- Abstract要約: 非対称二元パーセプトロン(ABP)は2つの相転移性制約密度閾値を示す。
本稿では, 高速昇降ランダム双対性理論 (fl RDT) [85] のパラメトリック利用について検討し, その可能性について検討する。
- 参考スコア（独自算出の注目度）: 2.538209532048867
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Recent studies suggest that asymmetric binary perceptron (ABP) likely exhibits the so-called statistical-computational gap characterized with the appearance of two phase transitioning constraint density thresholds: \textbf{\emph{(i)}} the \emph{satisfiability threshold} $\alpha_c$, below/above which ABP succeeds/fails to operate as a storage memory; and \textbf{\emph{(ii)}} \emph{algorithmic threshold} $\alpha_a$, below/above which one can/cannot efficiently determine ABP's weight so that it operates as a storage memory. We consider a particular parametric utilization of \emph{fully lifted random duality theory} (fl RDT) [85] and study its potential ABP's algorithmic implications. A remarkable structural parametric change is uncovered as one progresses through fl RDT lifting levels. On the first two levels, the so-called $\c$ sequence -- a key parametric fl RDT component -- is of the (natural) decreasing type. A change of such phenomenology on higher levels is then connected to the $\alpha_c$ -- $\alpha_a$ threshold change. Namely, on the second level concrete numerical values give for the critical constraint density $\alpha=\alpha_c\approx 0.8331$. While progressing through higher levels decreases this estimate, already on the fifth level we observe a satisfactory level of convergence and obtain $\alpha\approx 0.7764$. This allows to draw two striking parallels: \textbf{\emph{(i)}} the obtained constraint density estimate is in a remarkable agrement with range $\alpha\in (0.77,0.78)$ of clustering defragmentation (believed to be responsible for failure of locally improving algorithms) [17,88]; and \textbf{\emph{(ii)}} the observed change of $\c$ sequence phenomenology closely matches the one of the negative Hopfield model for which the existence of efficient algorithms that closely approach similar type of threshold has been demonstrated recently [87].
- Abstract（参考訳）: 最近の研究では、非対称二成分パーセプトロン(ABP)は2つの位相遷移制約密度しきい値の出現を特徴とするいわゆる統計計算ギャップを示す可能性が示唆されている: \textbf{\emph{
(i)}} \emph{satisfiability threshold} $\alpha_c$,low/above, ABP がストレージメモリとして動作するために/fails を成功/失敗する; \textbf{\emph{
(ii)}} \emph{algorithmic threshold} $\alpha_a$, below/above ここでは、ABPの重量を効率的に決定することができず、記憶メモリとして動作する。
本稿では,fl RDT (fl RDT) [85] の特殊パラメトリック利用について検討し,その可能性について検討する。
fl RDT昇降レベルが進むにつれて、顕著な構造パラメトリックな変化が明らかになる。
最初の2つのレベルでは、いわゆる$\c$シーケンス(キーパラメトリック fl RDT コンポーネント)は(自然な)減少型です。
このような現象学の上位レベルにおける変化は、$\alpha_c$ -- $\alpha_a$閾値変化に関連付けられる。
すなわち、第2のレベルでは、具体的な数値は臨界制約密度$\alpha=\alpha_c\approx 0.8331$を与える。
より高いレベルの進行は、この見積もりを減少させるが、既に第5のレベルでは、良好な収束レベルを観察し、$\alpha\approx 0.7764$を得る。
これにより、2つの顕著な並列を描画できる。
(i) 得られた制約密度推定値は、クラスタリングのデフラグメンテーション(局所的な改善アルゴリズムの失敗の原因と考えられる) [17,88] と \textbf{\emph{ のレンジ$$$\alpha\in (0.77,0.78)$の顕著な増加である。
(ii)}} 観測された$\c$シーケンス現象学の変化は、類似のしきい値に近づく効率的なアルゴリズムの存在を示す負のホップフィールドモデルの1つと密接に一致している[87]。
関連論文リスト
- Theoretical Framework for Tempered Fractional Gradient Descent: Application to Breast Cancer Classification [0.0]
本稿では,分数計算と指数的テンパリングを併用し,勾配に基づく学習を向上する新しい最適化フレームワークTFGDを紹介する。
TFGD は、履歴勾配を分数係数 $|w_j| = binomalphaj$ で重み付けし、テンパリングパラメータ $lambda$ で指数関数的に減衰するテンパリングメモリ機構を組み込むことで制限に対処する。
乳がんデータセットにおける実証的検証は、TFGDの優位性を示し、98.25%のテスト精度(vs.92.11%のSGD)と2$times$高速収束を達成した。
論文 参考訳（メタデータ） (2025-04-26T08:26:34Z) - A Nearly Optimal Single Loop Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness [15.656614304616006]
本稿では、上層関数が非定常で、潜在的に非有界な滑らかさを持ち、下層関数が凸であるような二層最適化の問題を考察する。
既存のアルゴリズムはネストループに依存しており、これは重要なチューニング作業を必要とし、実用的ではない。
論文 参考訳（メタデータ） (2024-12-28T04:40:27Z) - 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) - Theoretical limits of descending $\ell_0$ sparse-regression ML algorithms [0.0]
本研究では,emphmaximum-likelihood (ML)デコーディングの性能解析プログラムを開発した。
ML性能パラメータの鍵となるのは、残留エンフェロ平均二乗誤差(textbfRMSE$)を発見し、いわゆるエンフェロ遷移(PT)現象を示す。
Fl RDTの具体的実装と実用的妥当性は、典型的には、基礎となる数値評価のサイズのセットを実行する能力に依存している。
論文 参考訳（メタデータ） (2024-10-10T06:33:41Z) - An Accelerated Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness [15.656614304616006]
本稿では,上層関数が非凸であり,下層関数が強凸である二層最適化問題のクラスについて検討する。
これらの問題は、非有界ネットワークを用いたテキスト分類など、データ学習に大きな応用がある。
本稿では,AccBO という新しい高速化バイレベル最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-09-28T02:30:44Z) - Adaptive Federated Learning Over the Air [108.62635460744109]
オーバー・ザ・エア・モデル・トレーニングの枠組みの中で,適応勾配法,特にAdaGradとAdamの連合バージョンを提案する。
解析の結果,AdaGrad に基づくトレーニングアルゴリズムは $mathcalO(ln(T) / T 1 - frac1alpha の速度で定常点に収束することがわかった。
論文 参考訳（メタデータ） (2024-03-11T09:10:37Z) - Stochastic Gradient Succeeds for Bandits [64.17904367852563]
エンフィスト確率勾配帯域幅アルゴリズムは,O (1/t)$レートで,エンフィグロブな最適ポリシに収束することを示す。
興味深いことに、勾配帯域アルゴリズムのグローバル収束は以前に確立されていない。
論文 参考訳（メタデータ） (2024-02-27T06:05:01Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - Rate-matching the regret lower-bound in the linear quadratic regulator
with unknown dynamics [6.287145010885044]
本稿では、O_p(sqrtT,textpolylog(T))$という新しい後悔の上限を確立する。
同時に$O_p(sqrtT,textpolylog(T))$の動的値に縛られる推定誤差を確立する。
論文 参考訳（メタデータ） (2022-02-11T17:50:14Z) - Differentially Quantized Gradient Methods [53.3186247068836]
微分量子化グラディエントDescence (DQ-GD) が$maxsigma_mathrmGD, rhon 2-R$の線形収縮係数を得ることを示す。
あるクラス内のアルゴリズムは$maxsigma_mathrmGD, 2-R$よりも早く収束できない。
論文 参考訳（メタデータ） (2020-02-06T20:40:53Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。