Fugu-MT 論文翻訳(概要): On the Multidimensional Random Subset Sum Problem

論文の概要: On the Multidimensional Random Subset Sum Problem

arxiv url: http://arxiv.org/abs/2207.13944v1
Date: Thu, 28 Jul 2022 08:10:43 GMT
ステータス: 処理完了
システム内更新日: 2022-07-29 12:10:59.905768
Title: On the Multidimensional Random Subset Sum Problem
Title（参考訳）: 多次元ランダム部分集合和問題について
Authors: Luca Becchetti (DIAG), Arthur Carvalho Walraven da Cuhna (COATI), Andrea Clementi, Francesco d'Amore (COATI), Hicham Lesfari (COATI), Emanuele Natale (COATI), Luca Trevisan
Abstract要約: 確率変数 $X_1, ..., X_n$ が与えられたランダム部分集合 Sum 問題では、任意の点 $z in [-1,1]$ を部分集合 $X_i_1(z), ..., X_i_s(z)$ の和として近似したい。我々は、$d$次元において、$n = O(d3log frac 1varepsilon cdot
参考スコア（独自算出の注目度）: 0.9007371440329465
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In the Random Subset Sum Problem, given $n$ i.i.d. random variables $X_1, ..., X_n$, we wish to approximate any point $z \in [-1,1]$ as the sum of a suitable subset $X_{i_1(z)}, ..., X_{i_s(z)}$ of them, up to error $\varepsilon$. Despite its simple statement, this problem is of fundamental interest to both theoretical computer science and statistical mechanics. More recently, it gained renewed attention for its implications in the theory of Artificial Neural Networks. An obvious multidimensional generalisation of the problem is to consider $n$ i.i.d.\ $d$-dimensional random vectors, with the objective of approximating every point $\mathbf{z} \in [-1,1]^d$. Rather surprisingly, after Lueker's 1998 proof that, in the one-dimensional setting, $n=O(\log \frac 1\varepsilon)$ samples guarantee the approximation property with high probability, little progress has been made on achieving the above generalisation. In this work, we prove that, in $d$ dimensions, $n = O(d^3\log \frac 1\varepsilon \cdot (\log \frac 1\varepsilon + \log d))$ samples suffice for the approximation property to hold with high probability. As an application highlighting the potential interest of this result, we prove that a recently proposed neural network model exhibits \emph{universality}: with high probability, the model can approximate any neural network within a polynomial overhead in the number of parameters.
Abstract（参考訳）: n$ i.i.d. 確率変数 $x_1, ..., x_n$ が与えられたランダム部分集合和問題では、任意の点 $z \in [-1,1]$ を適切な部分集合 $x_{i_1(z)}, ..., x_{i_s(z)}$ の和として近似し、エラー $\varepsilon$ にしたい。単純な主張にもかかわらず、この問題は理論計算機科学と統計力学の両方に根本的な関心がある。最近では、ニューラルネットワークの理論におけるその意味について、新たな注目を集めている。この問題の明らかな多次元一般化は、すべての点 $\mathbf{z} \in [-1,1]^d$ を近似することを目的として、$n$ i.d.\ $d$-dimensionalランダムベクトルを考えることである。より驚くべきことに、Luekerの1998年の証明の後、一次元の設定において、$n=O(\log \frac 1\varepsilon)$サンプルは高い確率で近似性を保証するが、上記の一般化を達成するにはほとんど進歩していない。この研究において、$d$次元において、$n = O(d^3\log \frac 1\varepsilon \cdot (\log \frac 1\varepsilon + \log d))$サンプルが高い確率で保持できる近似特性に十分であることを示す。この結果の潜在的関心を強調するアプリケーションとして、最近提案されたニューラルネットワークモデルが 'emph{Universality} を示すことを証明している。

関連論文リスト

Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians [7.04316974339151]
本研究では,サンプルが未知の集合に落下した場合にのみ,分布パラメータの推定を行う。我々は,PAC学習から,正・負のサンプルによるPAC学習まで,独立したツールを開発する。
論文参考訳（メタデータ） (2024-10-02T15:21:07Z)
Iterative thresholding for non-linear learning in the strong $\varepsilon$-contamination model [3.309767076331365]
閾値降下を用いた単一ニューロンモデル学習のための近似境界を導出する。線形回帰問題も研究し、$sigma(mathbfx) = mathbfx$ となる。
論文参考訳（メタデータ） (2024-09-05T16:59:56Z)
Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。目標は、低ランク因子の積として$mathbfA$を近似することである。我々の手法はBMF問題の他の一般的な変種に一般化する。
論文参考訳（メタデータ） (2023-06-02T18:55:27Z)
Learning (Very) Simple Generative Models Is Hard [45.13248517769758]
我々は,$mathbbRdtobbRd'$の出力座標が$mathrmpoly(d)$ニューロンを持つ一層ReLUネットワークである場合でも,リアルタイムアルゴリズムが問題を解決可能であることを示す。我々の証明の鍵となる要素は、コンパクトに支持されたピースワイズ線形関数$f$をニューラルネットワークで束ねたスロープで構築することであり、$mathcalN(0,1)$のプッシュフォワードは$mathcalのすべての低度モーメントと一致する。
論文参考訳（メタデータ） (2022-05-31T17:59:09Z)
Unique Games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell's inequality [6.621324975749854]
関数 $f:mathbbRn の -1, 1$ への雑音安定性は $f(boldsymbolx) cdot f(boldsymboly)$ の期待値であることを示す。我々は $langle f(boldsymbolx), f(boldsymboly)rangle$ の期待値は、関数 $f(x) = x_leq k / Vert x_leq k / によって最小化されると予想する。
論文参考訳（メタデータ） (2021-11-01T20:45:42Z)
Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文参考訳（メタデータ） (2021-08-19T16:16:48Z)
From Smooth Wasserstein Distance to Dual Sobolev Norm: Empirical Approximation and Statistical Applications [18.618590805279187]
我々は$mathsfW_p(sigma)$が$pth次スムーズな双対ソボレフ$mathsfd_p(sigma)$で制御されていることを示す。我々は、すべての次元において$sqrtnmathsfd_p(sigma)(hatmu_n,mu)$の極限分布を導出する。
論文参考訳（メタデータ） (2021-01-11T17:23:24Z)
Sparse sketches with small inversion bias [79.77110958547695]
逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
論文参考訳（メタデータ） (2020-11-21T01:33:15Z)
Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文参考訳（メタデータ） (2020-06-06T13:34:41Z)
A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
論文参考訳（メタデータ） (2020-06-02T16:38:36Z)
Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

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