論文の概要: Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixtures

• arxiv url: http://arxiv.org/abs/2204.02550v1
• Date: Wed, 6 Apr 2022 03:03:39 GMT
• ステータス: 処理完了
• システム内更新日: 2022-04-08 00:20:38.620483
• Title: Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixtures
• Title（参考訳）: 連続LWEはLWEと同じくらい硬く、ガウス混合学習への応用
• Authors: Aparna Gupte, Neekon Vafa, Vinod Vaikuntanathan
• Abstract要約: 本稿では,誤り問題を伴う古典的学習と,その連続的なアナログであるCLWEとの間に直接的かつ概念的に簡易な還元効果を示す。 これにより、CLWEのアプリケーションにLWEベースの暗号の強力な能力を持たせることができます。
• 参考スコア（独自算出の注目度）: 11.348971335676444
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We show direct and conceptually simple reductions between the classical learning with errors (LWE) problem and its continuous analog, CLWE (Bruna, Regev, Song and Tang, STOC 2021). This allows us to bring to bear the powerful machinery of LWE-based cryptography to the applications of CLWE. For example, we obtain the hardness of CLWE under the classical worst-case hardness of the gap shortest vector problem. Previously, this was known only under quantum worst-case hardness of lattice problems. More broadly, with our reductions between the two problems, any future developments to LWE will also apply to CLWE and its downstream applications. As a concrete application, we show an improved hardness result for density estimation for mixtures of Gaussians. In this computational problem, given sample access to a mixture of Gaussians, the goal is to output a function that estimates the density function of the mixture. Under the (plausible and widely believed) exponential hardness of the classical LWE problem, we show that Gaussian mixture density estimation in $\mathbb{R}^n$ with roughly $\log n$ Gaussian components given $\mathsf{poly}(n)$ samples requires time quasi-polynomial in $n$. Under the (conservative) polynomial hardness of LWE, we show hardness of density estimation for $n^{\epsilon}$ Gaussians for any constant $\epsilon > 0$, which improves on Bruna, Regev, Song and Tang (STOC 2021), who show hardness for at least $\sqrt{n}$ Gaussians under polynomial (quantum) hardness assumptions. Our key technical tool is a reduction from classical LWE to LWE with $k$-sparse secrets where the multiplicative increase in the noise is only $O(\sqrt{k})$, independent of the ambient dimension $n$.
• Abstract（参考訳）: 本稿では,LWE問題とCLWE(Bruna,Regev,Song,Tang,STOC2021)との直接的,概念的に単純な相違点を示す。 これにより、LWEベースの暗号の強力な機械をCLWEの応用に適用することができる。 例えば、ギャップ最短ベクトル問題の古典的な最悪ケース硬さの下で、CLWEの硬さを得る。 以前は、これは格子問題の量子的最悪ケースハードネスの下でしか知られていなかった。 より広範に、この2つの問題の間の縮小により、LWEへの今後の開発はCLWEとその下流アプリケーションにも適用されるだろう。 具体的応用として,ガウス混合系の密度推定のための硬さ改善結果を示す。 この計算問題では、ガウスの混合物へのサンプルアクセスが与えられた場合、その混合物の密度関数を推定する関数を出力することが目的である。 古典的LWE問題の(楽観的で広く信じられている)指数的硬さの下で、約$\log n$ Gaussian 成分が $\mathsf{poly}(n)$ に与えられるガウス混合密度の推定は$n$で時間準多項式を必要とすることを示す。 LWE の(保存的な)多項式硬度の下では、任意の定数 $\epsilon > 0$ に対して $n^{\epsilon}$ Gaussian の密度推定の硬さを示し、これは、多項式(量子)硬さの仮定の下で少なくとも $\sqrt{n}$ Gaussians の硬さを示す Bruna, Regev, Song and Tang (STOC 2021) で改善する。 我々の重要な技術ツールは、音の乗法的な増加がわずか$o(\sqrt{k})$で、環境次元$n$とは無関係に、古典的なlweから$k$-sparseシークレットによるlweへの削減です。

関連論文リスト

• Convergence Rate Analysis of LION [54.28350823319057]
  LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。 従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
  論文  参考訳（メタデータ） (2024-11-12T11:30:53Z)
• Learning general Gaussian mixtures with efficient score matching [16.06356123715737]
  我々は、$d$次元で$k$ガウシアンの混合を学習する問題を研究する。 我々は、下層の混合成分について分離を前提としない。 我々は、ターゲット混合物から$dmathrmpoly(k/varepsilon)$サンプルを抽出し、サンプル-ポリノミカル時間で実行し、サンプリング器を構築するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-04-29T17:30:36Z)
• Tempered Calculus for ML: Application to Hyperbolic Model Embedding [70.61101116794549]
  MLで使用されるほとんどの数学的歪みは、本質的に自然界において積分的である。 本稿では,これらの歪みを改善するための基礎的理論とツールを公表し,機械学習の要件に対処する。 我々は、最近MLで注目を集めた問題、すなわち、ハイパーボリック埋め込みを「チープ」で正確なエンコーディングで適用する方法を示す。
  論文  参考訳（メタデータ） (2024-02-06T17:21:06Z)
• LWE with Quantum Amplitudes: Algorithm, Hardness, and Oblivious Sampling [6.219791262322396]
  実ガウス項を持つ $sfS|LWErangle$ および $sfC|LWErangle$ に対する新しいアルゴリズム、硬度結果、およびその他の関連する振幅を示す。
  論文  参考訳（メタデータ） (2023-10-01T11:53:24Z)
• Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samples [9.649879910148854]
  差分プライバシー(DP)制約下におけるガウシアン混合量の推定問題について検討する。 主な結果は、$textpoly(k,d,1/alpha,1/varepsilon,log (1/delta))$サンプルが$k$ Gaussians in $mathbbRd$から$alpha$までを推定するのに十分であることです。 これは GMM の構造的仮定を一切含まない問題に対する最初の有限標本複雑性上界である。
  論文  参考訳（メタデータ） (2023-09-07T17:02:32Z)
• Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals [43.0867217287089]
  ガウス分布の下で半空間を不可知的に学習する作業について検討する。 この課題に対して,ほぼ最適計算硬度を証明した。
  論文  参考訳（メタデータ） (2023-02-13T16:46:23Z)
• Robustly Learning Mixtures of $k$ Arbitrary Gaussians [47.40835932474677]
  任意の固定された$k$に対して$k$任意のガウスの混合を$mathbbRd$で頑健に推定する問題に対して、一定数の任意の汚職が存在する場合の時間アルゴリズムを与える。 本研究の主なツールは,2乗法に依拠する効率的な分節クラスタリングアルゴリズムと,Frobeniusノルムおよび低ランク項の誤りを許容する新しいテンソル分解アルゴリズムである。
  論文  参考訳（メタデータ） (2020-12-03T17:54:03Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• Continuous LWE [32.345218864470446]
  CLWEと呼ばれるLearning with Errors(LWE)問題の連続的な類似点を紹介する。 最短ケース格子問題の量子化をCLWEに与え、CLWEがLWEと同じような硬さの保証を享受していることを示す。
  論文  参考訳（メタデータ） (2020-05-19T17:16:12Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。 理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。 我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
  論文  参考訳（メタデータ） (2020-05-13T16:44:12Z)
• Randomized Exploration in Generalized Linear Bandits [56.05007606177762]
  一般化線形帯域に対する2つのランダム化アルゴリズムについて検討する。 最初のGLM-TSLは、ラプラス近似から後方分布への一般化線形モデル(GLM)をサンプリングする。 第2のGLM-FPLは、過去の報酬のランダムな摂動履歴にGLMを適合させる。
  論文  参考訳（メタデータ） (2019-06-21T04:57:54Z)

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

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