論文の概要: Binary perceptron: efficient algorithms can find solutions in a rare well-connected cluster

• arxiv url: http://arxiv.org/abs/2111.03084v1
• Date: Thu, 4 Nov 2021 18:00:31 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-08 16:14:20.228113
• Title: Binary perceptron: efficient algorithms can find solutions in a rare well-connected cluster
• Title（参考訳）: バイナリパーセプトロン: 効率的なアルゴリズムは希少な連結クラスタにおける解を見つけることができる
• Authors: Emmanuel Abbe, Shuangping Li, Allan Sly
• Abstract要約: 最近、対称二項パーセプトロンのほとんど全ての解が、低制約密度でも孤立していることが示されている。 いくつかのアルゴリズムは、低密度の解を見つけるために経験的に示されている。 この現象は、溶液の亜支配領域と密接な連結領域の存在によって、数値的に正当化されている。
• 参考スコア（独自算出の注目度）: 21.356438315715888
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: It was recently shown that almost all solutions in the symmetric binary perceptron are isolated, even at low constraint densities, suggesting that finding typical solutions is hard. In contrast, some algorithms have been shown empirically to succeed in finding solutions at low density. This phenomenon has been justified numerically by the existence of subdominant and dense connected regions of solutions, which are accessible by simple learning algorithms. In this paper, we establish formally such a phenomenon for both the symmetric and asymmetric binary perceptrons. We show that at low constraint density (equivalently for overparametrized perceptrons), there exists indeed a subdominant connected cluster of solutions with almost maximal diameter, and that an efficient multiscale majority algorithm can find solutions in such a cluster with high probability, settling in particular an open problem posed by Perkins-Xu '21. In addition, even close to the critical threshold, we show that there exist clusters of linear diameter for the symmetric perceptron, as well as for the asymmetric perceptron under additional assumptions.
• Abstract（参考訳）: 最近、対称二項パーセプトロンのほとんど全ての解が低制約密度でも孤立していることが示され、典型的な解を見つけることは難しいことが示唆された。 対照的に、いくつかのアルゴリズムは、低密度の解を見つけることに経験的に成功している。 この現象は、単純な学習アルゴリズムによってアクセス可能な解の非支配的かつ密結合領域の存在によって、数値的に正当化されている。 本稿では、対称および非対称二元パーセプトロンの両方に対して、正式にそのような現象を確立する。 低制約密度(高パラメータのパーセプトロンと同値)では、ほぼ最大径の解の非支配的な連結クラスターが存在し、効率的なマルチスケールの多数決アルゴリズムはそのようなクラスターの解を高い確率で見つけることができ、特にパーキンス-xu '21によって生じるオープン問題に落ち着くことができる。 さらに、臨界しきい値に近づくと、対称パーセプトロンや追加の仮定の下で非対称パーセプトロンに対して線形な直径のクラスターが存在することが示される。

関連論文リスト

• HeNCler: Node Clustering in Heterophilous Graphs through Learned Asymmetric Similarity [55.27586970082595]
  HeNClerは、Heterophilous Node Clusteringの新しいアプローチである。 HeNClerは異種グラフコンテキストにおけるノードクラスタリングタスクの性能を大幅に向上させることを示す。
  論文  参考訳（メタデータ） (2024-05-27T11:04:05Z)
• Discretize Relaxed Solution of Spectral Clustering via a Non-Heuristic Algorithm [77.53604156112144]
  我々は、元の問題と離散化アルゴリズムを橋渡しする1次項を開発する。 非ヒューリスティック法は元のグラフ切断問題を認識しているため、最終的な離散解の方が信頼性が高い。
  論文  参考訳（メタデータ） (2023-10-19T13:57:38Z)
• The star-shaped space of solutions of the spherical negative perceptron [4.511197686627054]
  低エネルギー構成が複雑な連結構造によく見られることを示す。 我々は、他のほとんどの解と連結された非定型ハイマージンの部分集合を同定する。
  論文  参考訳（メタデータ） (2023-05-18T00:21:04Z)
• Typical and atypical solutions in non-convex neural networks with discrete and continuous weights [2.7127628066830414]
  ランダムな規則や関連を学習する単純な非拘束型ネットワークモデルとして、二項および連続負マージンパーセプトロンについて検討する。 どちらのモデルも、非常に平坦で幅の広い劣支配的な最小化器を示す。 両モデルにおいて、学習装置としての一般化性能は、広い平坦な最小化器の存在により大幅に向上することを示した。
  論文  参考訳（メタデータ） (2023-04-26T23:34:40Z)
• Infinite-Dimensional Sparse Learning in Linear System Identification [0.2867517731896504]
  本稿では,原子ノルム正規化に基づく無限次元スパース学習アルゴリズムを提案する。 この問題の解決の難しさは、無限の原子モデルが存在するという事実にある。
  論文  参考訳（メタデータ） (2022-03-28T13:18:48Z)
• On the Complexity of a Practical Primal-Dual Coordinate Method [63.899427212054995]
  ランダム・座標降下法(PURE-CD)を用いた原始双対アルゴリズムの複雑性境界を証明した。 バイマックス性能問題を解くための優れた外挿が得られることが示されている。
  論文  参考訳（メタデータ） (2022-01-19T16:14:27Z)
• Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
  ヒルベルト空間の既知の低次元部分空間を探索することにより、確率観測の集合を用いて近似解を計算する手法を検討する。 本稿では,線形関数近似を用いた政策評価問題に対する時間差分学習手法の誤差を正確に評価する方法について述べる。
  論文  参考訳（メタデータ） (2020-12-09T20:19:32Z)
• Entanglement marginal problems [0.0]
  絡み合いの限界問題は、多くの還元密度行列が全体分離可能な量子状態と互換性があるかどうかを決定することである。 完全分離可能な拡張を許容する量子状態境界の集合の半定値プログラミング緩和の階層性を提案する。 我々の結果は、1次元の翻訳不変系や余剰対称性を持つ高次元など無限のシステムにまで拡張される。
  論文  参考訳（メタデータ） (2020-06-16T10:48:56Z)
• Eigendecomposition-Free Training of Deep Networks for Linear Least-Square Problems [107.3868459697569]
  我々は、ディープネットワークのトレーニングに固有分解のないアプローチを導入する。 この手法は固有分解の明示的な微分よりもはるかに堅牢であることを示す。 我々の手法は収束特性が良く、最先端の結果が得られます。
  論文  参考訳（メタデータ） (2020-04-15T04:29:34Z)
• Convex Geometry and Duality of Over-parameterized Neural Networks [70.15611146583068]
  有限幅2層ReLUネットワークの解析のための凸解析手法を開発した。 正規化学習問題に対する最適解が凸集合の極点として特徴づけられることを示す。 高次元では、トレーニング問題は無限に多くの制約を持つ有限次元凸問題としてキャストできることが示される。
  論文  参考訳（メタデータ） (2020-02-25T23:05:33Z)
• The quantum marginal problem for symmetric states: applications to variational optimization, nonlocality and self-testing [0.0]
  対称$d$レベルのシステムに対する量子境界問題の解法を提案する。 量子情報中心問題における本手法の適用性について,いくつかの事例研究で概説する。
  論文  参考訳（メタデータ） (2020-01-13T18:20:53Z)

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

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