論文の概要: 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への削減です。
関連論文リスト
- Tempered Calculus for ML: Application to Hyperbolic Model Embedding [74.82054459297169]
MLで使用されるほとんどの数学的歪みは、本質的に自然界において積分的である。
本稿では,これらの歪みを改善するための基礎的理論とツールを公表し,機械学習の要件に対処する。
我々は、最近MLで注目を集めた問題、すなわち、ハイパーボリック埋め込みを「チープ」で正確なエンコーディングで適用する方法を示す。
論文 参考訳(メタデータ) (2024-02-06T17:21:06Z) - On the Hardness of $\sf{S|LWE\rangle}$ with Gaussian and Other
Amplitudes [6.672877891213174]
ガウスおよびその他の振幅を持つ$sfS|LWErangle$に対する新しい硬さとアルゴリズムを示す。
我々の結果を解釈する1つの方法は、標準LWEのサブ指数時間量子アルゴリズムを示すために、$sfS|LWErangle$振幅の位相を扱うことだけが必要である。
論文 参考訳(メタデータ) (2023-10-01T11:53:24Z) - Mixtures of Gaussians are Privately Learnable with a Polynomial Number
of Samples [10.845497957542701]
差分プライバシー(DP)制約下におけるガウシアン混合量の推定問題について検討する。
我々の主な結果は、$tildeO(k2 d4 log1) / alpha2 varepsilon)$サンプルは、$(varepsilon, delta)$-DPを満足しながら、全変動距離$alpha$までの$k$ Gaussiansの混合を推定するのに十分であるということです。
論文 参考訳(メタデータ) (2023-09-07T17:02:32Z) - A Simple Proof of the Mixing of Metropolis-Adjusted Langevin Algorithm
under Smoothness and Isoperimetry [4.657614491309671]
MALAは$Oleft(frac(LUpsilon)frac12psi_mu2 logleft(frac1epsilonright)right logleft(frac1epsilonright)rightで混合する。
MALAは$Oleft(frac(LUpsilon)frac12psi_mu2 logleft(frac1epsilonright)rightで混在している。
論文 参考訳(メタデータ) (2023-04-08T20:17:29Z) - Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces
and ReLU Regression under Gaussian Marginals [43.0867217287089]
ガウス分布の下で半空間を不可知的に学習する作業について検討する。
この課題に対して,ほぼ最適計算硬度を証明した。
論文 参考訳(メタデータ) (2023-02-13T16:46:23Z) - Learning Gaussian Mixtures with Generalised Linear Models: Precise
Asymptotics in High-dimensions [79.35722941720734]
多クラス分類問題に対する一般化線形モデルは、現代の機械学習タスクの基本的な構成要素の1つである。
実験的リスク最小化による高次元推定器の精度を実証する。
合成データの範囲を超えて我々の理論をどのように適用できるかを論じる。
論文 参考訳(メタデータ) (2021-06-07T16:53:56Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。