論文の概要: Efficient Unbiased Sparsification

• arxiv url: http://arxiv.org/abs/2402.14925v2
• Date: Wed, 24 Jul 2024 16:54:33 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-25 19:10:54.923913
• Title: Efficient Unbiased Sparsification
• Title（参考訳）: 効率的なアンビシド・スパリフィケーション
• Authors: Leighton Barnes, Stephen Cameron, Timothy Chow, Emma Cohen, Keith Frankston, Benjamin Howard, Fred Kochman, Daniel Scheinerman, Jeffrey VanderKam,
• Abstract要約: ベクトル $pin mathbbRn$ の非バイアス付き $m$-スパーシフィケーション(unbiased $m$-sparsification of a vector $pin mathbbRn$)は、無作為なベクトル $Qin mathbbRn$ であり、平均 $p$ は少なくとも $mn$ でない座標を持つ。 本研究の主な成果は、置換不変あるいは加法的に分離可能な異種に対する効率的な非偏平スパーシフィケーションである。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: An unbiased $m$-sparsification of a vector $p\in \mathbb{R}^n$ is a random vector $Q\in \mathbb{R}^n$ with mean $p$ that has at most $m<n$ nonzero coordinates. Unbiased sparsification compresses the original vector without introducing bias; it arises in various contexts, such as in federated learning and sampling sparse probability distributions. Ideally, unbiased sparsification should also minimize the expected value of a divergence function $\mathsf{Div}(Q,p)$ that measures how far away $Q$ is from the original $p$. If $Q$ is optimal in this sense, then we call it efficient. Our main results describe efficient unbiased sparsifications for divergences that are either permutation-invariant or additively separable. Surprisingly, the characterization for permutation-invariant divergences is robust to the choice of divergence function, in the sense that our class of optimal $Q$ for squared Euclidean distance coincides with our class of optimal $Q$ for Kullback-Leibler divergence, or indeed any of a wide variety of divergences.
• Abstract（参考訳）: ベクトル $p\in \mathbb{R}^n$ の非バイアス付き$m$-スパーシフィケーション(unbiased $m$-sparsification of a vector $p\in \mathbb{R}^n$)は、無作為ベクトル $Q\in \mathbb{R}^n$ であり、最小の$m<n$非ゼロ座標を持つ平均$p$ である。 偏りのないスパーシフィケーションは、バイアスを導入することなく元のベクトルを圧縮し、連邦学習やスパース確率分布のサンプリングなど、様々な文脈で発生する。 理想的には、バイアスのないスパーシフィケーションは、元の$p$からQ$がどれくらい遠いかを測る発散関数 $\mathsf{Div}(Q,p)$ の期待値を最小化する。 この意味で$Q$が最適であれば、効率性と呼ぶ。 本研究の主な成果は、置換不変あるいは加法的に分離可能な異種に対する効率的な非偏平スパーシフィケーションである。 驚いたことに、置換不変な発散の特徴づけは、二乗ユークリッド距離に対する最適$Q$のクラスが、クルバック・リーブラー発散のための最適$Q$のクラス、あるいは実際は様々な発散のクラスと一致するという意味で、発散関数の選択に頑健である。

関連論文リスト

• Variational Inference for Uncertainty Quantification: an Analysis of Trade-offs [10.075911116030621]
  p$ が分解されない場合、任意の分解された近似 $qin Q$ は以下の3つの不確実性尺度のうちの1つを正確に推定できることを示す。 古典的なKulback-Leiblerの発散、より一般的なR'enyiの発散、および$nabla log p$ と $nabla log q$ を比較するスコアベースの発散を考える。
  論文  参考訳（メタデータ） (2024-03-20T16:56:08Z)
• Universality of max-margin classifiers [10.797131009370219]
  非ガウス的特徴に対する誤分類誤差の高次元普遍性と大域化写像の役割について検討する。 特に、オーバーパラメトリゼーションしきい値と一般化誤差はより単純なモデルで計算できる。
  論文  参考訳（メタデータ） (2023-09-29T22:45:56Z)
• Statistical Learning under Heterogeneous Distribution Shift [71.8393170225794]
  ground-truth predictor is additive $mathbbE[mathbfz mid mathbfx,mathbfy] = f_star(mathbfx) +g_star(mathbfy)$.
  論文  参考訳（メタデータ） (2023-02-27T16:34:21Z)
• Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
  既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。 我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
  論文  参考訳（メタデータ） (2022-03-18T18:50:52Z)
• Thinking Outside the Ball: Optimal Learning with Gradient Descent for Generalized Linear Stochastic Convex Optimization [37.177329562964765]
  我々は凸リプシッツ損失を伴う線形予測、あるいはより一般に一般化線型形式の凸最適化問題を考える。 この設定では、初期反復が明示的な正規化や投影を伴わずにグラディエント Descent (GD) を停止し、過大なエラーを最大$epsilon$で保証することを示した。 しかし、標準球における一様収束は、$Theta (1/epsilon4)$サンプルを用いた最適下界学習を保証できることを示しているが、分布依存球における一様収束に依存している。
  論文  参考訳（メタデータ） (2022-02-27T09:41:43Z)
• Random matrices in service of ML footprint: ternary random features with no performance loss [55.30329197651178]
  我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。 3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。 提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
  論文  参考訳（メタデータ） (2021-10-05T09:33:49Z)
• 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)
• Multivariate mean estimation with direction-dependent accuracy [8.147652597876862]
  独立な同一分布観測に基づくランダムベクトルの平均を推定する問題を考察する。 確率ベクトルの1次元辺の分散があまり小さくない全ての方向において、ほぼ最適誤差を持つ推定器を証明した。
  論文  参考訳（メタデータ） (2020-10-22T17:52:45Z)
• Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
  エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。 代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
  論文  参考訳（メタデータ） (2020-06-12T10:21:40Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)

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

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