論文の概要: On the Cryptographic Hardness of Learning Single Periodic Neurons

• arxiv url: http://arxiv.org/abs/2106.10744v1
• Date: Sun, 20 Jun 2021 20:03:52 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-22 15:38:57.449855
• Title: On the Cryptographic Hardness of Learning Single Periodic Neurons
• Title（参考訳）: 単周期ニューロン学習の暗号的困難性について
• Authors: Min Jae Song, Ilias Zadik, Joan Bruna
• Abstract要約: ノイズの存在下での等方性ガウス分布より単一ニューロンを学習する際の暗号的難易度を簡易に低減することを示す。 提案アルゴリズムは勾配ベースや逆SQ-timeアルゴリズムではなく,LLL(Lenstra-LenstraLov'asz)格子に基づく。
• 参考スコア（独自算出の注目度）: 42.86685497609574
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We show a simple reduction which demonstrates the cryptographic hardness of learning a single periodic neuron over isotropic Gaussian distributions in the presence of noise. More precisely, our reduction shows that any polynomial-time algorithm (not necessarily gradient-based) for learning such functions under small noise implies a polynomial-time quantum algorithm for solving worst-case lattice problems, whose hardness form the foundation of lattice-based cryptography. Our core hard family of functions, which are well-approximated by one-layer neural networks, take the general form of a univariate periodic function applied to an affine projection of the data. These functions have appeared in previous seminal works which demonstrate their hardness against gradient-based (Shamir'18), and Statistical Query (SQ) algorithms (Song et al.'17). We show that if (polynomially) small noise is added to the labels, the intractability of learning these functions applies to all polynomial-time algorithms under the aforementioned cryptographic assumptions. Moreover, we demonstrate the necessity of noise in the hardness result by designing a polynomial-time algorithm for learning certain families of such functions under exponentially small adversarial noise. Our proposed algorithm is not a gradient-based or an SQ algorithm, but is rather based on the celebrated Lenstra-Lenstra-Lov\'asz (LLL) lattice basis reduction algorithm. Furthermore, in the absence of noise, this algorithm can be directly applied to solve CLWE detection (Bruna et al.'21) and phase retrieval with an optimal sample complexity of $d+1$ samples. In the former case, this improves upon the quadratic-in-$d$ sample complexity required in (Bruna et al.'21). In the latter case, this improves upon the state-of-the-art AMP-based algorithm, which requires approximately $1.128d$ samples (Barbier et al.'19).
• Abstract（参考訳）: ノイズの存在下での等方性ガウス分布より単一周期ニューロンを学習する際の暗号的難易度を簡易に低減することを示す。 より正確には、そのような関数を小さな雑音下で学習するための多項式時間アルゴリズム(必ずしも勾配ベースではない)は、最悪の場合の格子問題を解く多項式時間量子アルゴリズムを意味する。 1層ニューラルネットワークによって近似された我々のコアハード関数群は、データのアフィン射影に適用される不定周期関数の一般的な形を取る。 これらの関数は、勾配に基づくアルゴリズム(Shamir'18)や統計クエリ(SQ)アルゴリズム(Song et al.'17)に対する硬さを示す以前の基礎研究に現れている。 ラベルに(ポリノミカルに)小さなノイズを加えると、これらの関数を学習する難易度は上記の暗号仮定の下で全ての多項式時間アルゴリズムに適用できることを示す。 さらに,このような関数の特定の族を指数的に小さな対向雑音下で学習する多項式時間アルゴリズムを設計することにより,難易度結果におけるノイズの必要性を示す。 提案アルゴリズムは勾配ベースやSQアルゴリズムではなく,Lenstra-Lenstra-Lov\asz (LLL) 格子ベース削減アルゴリズムに基づいている。 さらに、ノイズがない場合には、このアルゴリズムを直接適用してCLWE検出を解くことができる(Bruna et al)。 '21) と最適試料量$d+1$サンプルの位相検索を行った。 前者の場合、これは (Bruna et al.'21) で必要とされる2次対価のサンプル複雑性により改善される。 後者の場合、これは最先端のAMPベースのアルゴリズムを改善し、約1.128d$サンプル(Barbier et al)を必要とする。 '19).

関連論文リスト

• Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginals [10.850101961203752]
  正方形損失目標を持つガウスの辺縁部における任意のバイアスのReLU活性化(あるいはニューロン)を学習する問題を考察する。 我々の主な成果は時間統計クエリ(SQ)アルゴリズムであり、任意のバイアスに対して最初の定数係数近似を与える。 我々のアルゴリズムは、勾配降下に基づく既存のアルゴリズムから興味深い逸脱を示す。
  論文  参考訳（メタデータ） (2024-11-21T17:43:51Z)
• Information limits and Thouless-Anderson-Palmer equations for spiked matrix models with structured noise [19.496063739638924]
  構造スパイクモデルに対するベイズ推定の飽和問題を考える。 適応的なThouless-Anderson-Palmer方程式の理論にインスパイアされた効率的なアルゴリズムを用いて、統計的限界を予測する方法を示す。
  論文  参考訳（メタデータ） (2024-05-31T16:38:35Z)
• Geometry-Aware Approaches for Balancing Performance and Theoretical Guarantees in Linear Bandits [6.907555940790131]
  トンプソンサンプリングとグリーディは有望な経験的性能を示したが、これは悲観的な理論的後悔の境界とは対照的である。 本研究では不確実楕円体の幾何学的特性を追跡する新しいデータ駆動手法を提案する。 ベースアルゴリズムが不十分な問題インスタンスを特定し,コース修正する。
  論文  参考訳（メタデータ） (2023-06-26T17:38:45Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
  本研究では,Tsybakovノイズの存在下でのPAC学習の相同性半空間の問題について検討する。 我々のアルゴリズムは、任意の精度$epsilon$で真のハーフスペースを学習する。
  論文  参考訳（メタデータ） (2020-10-04T22:19:06Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Computational Barriers to Estimation from Low-Degree Polynomials [81.67886161671379]
  本研究では,隠れ構造物の存在を検知する作業において,低次構造物のパワーについて検討する。 大規模な「信号+雑音」問題に対して、任意の程度に達成可能な最良の平均二乗誤差に対して、ユーザフレンドリな下界を与える。 応用として,植込みサブマトリクスに対する低次平均2乗誤差の厳密な評価と高密度サブグラフ問題について述べる。
  論文  参考訳（メタデータ） (2020-08-05T17:52:10Z)
• Active Model Estimation in Markov Decision Processes [108.46146218973189]
  マルコフ決定過程(MDP)をモデル化した環境の正確なモデル学習のための効率的な探索の課題について検討する。 マルコフに基づくアルゴリズムは,本アルゴリズムと極大エントロピーアルゴリズムの両方を小サンプル方式で上回っていることを示す。
  論文  参考訳（メタデータ） (2020-03-06T16:17:24Z)

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

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