論文の概要: Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDT

• arxiv url: http://arxiv.org/abs/2506.19276v1
• Date: Tue, 24 Jun 2025 03:12:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-25 19:48:23.466056
• Title: Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDT
• Title（参考訳）: 非対称二元パーセプトロンにおける希薄溶液クラスター-完全昇降RTTによる局所エントロピー
• Authors: Mihailo Stojnic,
• Abstract要約: 本研究では, 古典的非対称二元性パーセプトロン (ABP) とその関連エントロピー (LE) をアルゴリズム的硬さの潜在的源として検討した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study classical asymmetric binary perceptron (ABP) and associated \emph{local entropy} (LE) as potential source of its algorithmic hardness. Isolation of \emph{typical} ABP solutions in SAT phase seemingly suggests a universal algorithmic hardness. Paradoxically, efficient algorithms do exist even for constraint densities $\alpha$ fairly close but at a finite distance (\emph{computational gap}) from the capacity. In recent years, existence of rare large dense clusters and magical ability of fast algorithms to find them have been posited as the conceptual resolution of this paradox. Monotonicity or breakdown of the LEs associated with such \emph{atypical} clusters are predicated to play a key role in their thinning-out or even complete defragmentation. Invention of fully lifted random duality theory (fl RDT) [90,93,94] allows studying random structures \emph{typical} features. A large deviation upgrade, sfl LD RDT [96,97], moves things further and enables \emph{atypical} features characterizations as well. Utilizing the machinery of [96,97] we here develop a generic framework to study LE as an ABP's atypical feature. Already on the second level of lifting we discover that the LE results are closely matching those obtained through replica methods. For classical zero threshold ABP, we obtain that LE breaks down for $\alpha$ in $(0.77,0.78)$ interval which basically matches $\alpha\sim 0.75-0.77$ range that currently best ABP solvers can handle and effectively indicates that LE's behavior might indeed be among key reflections of the ABP's computational gaps presumable existence.
• Abstract（参考訳）: 古典的非対称二元性パーセプトロン (ABP) とそれに関連する \emph{local entropy} (LE) をアルゴリズム的硬さの潜在的源として研究する。 SAT相における \emph{typeal} ABP 解の分離は、普遍的なアルゴリズム的硬さを示唆している。 逆に、効率的なアルゴリズムは制約密度$\alpha$かなり近いとしても存在し、キャパシティから有限距離 (\emph{computational gap}) で存在する。 近年では、このパラドックスの概念的解決法として、希少な高密度クラスターの存在と高速アルゴリズムによる発見の魔法的な能力が提案されている。 このような \emph{atypical} クラスタに関連する LE の単調性や分解は、その薄型化や完全なデフラグメンテーションにおいて重要な役割を果たすと予測される。 完全持ち上げランダム双対性理論(fl RDT) [90,93,94] の発明は、ランダム構造 \emph{typeal} の特徴の研究を可能にする。 大規模な偏差アップグレードである sfl LD RDT [96,97] は、物事をさらに前進させ、 \emph{atypical} の特徴付けも可能にする。 ここでは [96,97] の機械を利用して, ABP の非典型的特徴として LE を研究するための汎用的な枠組みを開発する。 すでに第2レベルのリフトでは、LEの結果がレプリカ法で得られたものと密に一致していることが判明している。 古典的ゼロしきい値 ABP に対して、LE は $\alpha$ in $(0.77,0.78)$ interval で分解され、これは基本的に $\alpha\sim 0.75-0.77$ の範囲と一致する。

関連論文リスト

• SuperARC: An Agnostic Test for Narrow, General, and Super Intelligence Based On the Principles of Recursive Compression and Algorithmic Probability [0.14061979259370275]
  アルゴリズムの確率を基礎としたオープンエンドテストを導入する。 これはフロンティアモデルの定量的評価においてベンチマーク汚染を避けることができる。 圧縮はシステムの予測力と等価であり、直接的に比例することを示す。
  論文  参考訳（メタデータ） (2025-03-20T23:11:30Z)
• Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
  我々は$f$-divergence-regularized offline policy learningを分析する。 逆Kullback-Leibler (KL) の発散に対して、単極集中性の下での最初の$tildeO(epsilon-1)$サンプル複雑性を与える。 これらの結果は,$f$-divergence-regularized policy learningの包括的理解に向けて大きな一歩を踏み出したものと考えられる。
  論文  参考訳（メタデータ） (2025-02-09T22:14:45Z)
• Fast UCB-type algorithms for stochastic bandits with heavy and super heavy symmetric noise [45.60098988395789]
  マルチアームバンディットのためのUCB型アルゴリズムを構築するための新しいアルゴリズムを提案する。 報酬の対称雑音の場合、$O(log TsqrtKTlog T)$ regret bound を $Oleft の代わりに達成できることを示す。
  論文  参考訳（メタデータ） (2024-02-10T22:38:21Z)
• Approximating a RUM from Distributions on k-Slates [88.32814292632675]
  与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。 我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
  論文  参考訳（メタデータ） (2023-05-22T17:43:34Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• When are Local Queries Useful for Robust Learning? [25.832511407411637]
  本研究では,学習者が局所的なクエリを用いてより多くのパワーを与えられる学習モデルについて検討する。 我々は、ロバストな経験的リスク最小化を行う最初の分布自由アルゴリズムを与える。 我々は、0,1n$でハーフスペースに対してロバストな学習アルゴリズムを与え、その後、精度に縛られた敵に対して$mathbbRn$でハーフスペースに対してロバスト性を保証する。
  論文  参考訳（メタデータ） (2022-10-12T11:04:22Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。 真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-06-11T14:25:02Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。 ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
  論文  参考訳（メタデータ） (2020-04-25T05:45:59Z)

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

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