論文の概要: Determinantal point processes based on orthogonal polynomials for
sampling minibatches in SGD
- arxiv url: http://arxiv.org/abs/2112.06007v1
- Date: Sat, 11 Dec 2021 15:09:19 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-17 11:27:58.298138
- Title: Determinantal point processes based on orthogonal polynomials for
sampling minibatches in SGD
- Title（参考訳）: SGDにおけるミニバッチサンプリングのための直交多項式に基づく決定点過程
- Authors: Remi Bardenet, Subhro Ghosh, Meixia Lin
- Abstract要約: 勾配降下(SGD)は機械学習の基盤である。
デフォルトのミニバッチ構成では、望ましいサイズのサブセットを一様にサンプリングする。
DPPと制御された近似の列が、一様サンプリングよりもバッチサイズで高速に崩壊するばらつきを持つ勾配推定器にどのように影響するかを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: Stochastic gradient descent (SGD) is a cornerstone of machine learning. When
the number N of data items is large, SGD relies on constructing an unbiased
estimator of the gradient of the empirical risk using a small subset of the
original dataset, called a minibatch. Default minibatch construction involves
uniformly sampling a subset of the desired size, but alternatives have been
explored for variance reduction. In particular, experimental evidence suggests
drawing minibatches from determinantal point processes (DPPs), distributions
over minibatches that favour diversity among selected items. However, like in
recent work on DPPs for coresets, providing a systematic and principled
understanding of how and why DPPs help has been difficult. In this work, we
contribute an orthogonal polynomial-based DPP paradigm for minibatch sampling
in SGD. Our approach leverages the specific data distribution at hand, which
endows it with greater sensitivity and power over existing data-agnostic
methods. We substantiate our method via a detailed theoretical analysis of its
convergence properties, interweaving between the discrete data set and the
underlying continuous domain. In particular, we show how specific DPPs and a
string of controlled approximations can lead to gradient estimators with a
variance that decays faster with the batchsize than under uniform sampling.
Coupled with existing finite-time guarantees for SGD on convex objectives, this
entails that, DPP minibatches lead to a smaller bound on the mean square
approximation error than uniform minibatches. Moreover, our estimators are
amenable to a recent algorithm that directly samples linear statistics of DPPs
(i.e., the gradient estimator) without sampling the underlying DPP (i.e., the
minibatch), thereby reducing computational overhead. We provide detailed
synthetic as well as real data experiments to substantiate our theoretical
claims.
- Abstract（参考訳）: 確率勾配降下(SGD)は機械学習の基盤となっている。
データ項目の数値Nが大きい場合、SGDは、ミニバッチと呼ばれる元のデータセットの小さなサブセットを使用して、経験的リスクの勾配のバイアスのない推定器を構築することに依存する。
デフォルトのミニバッチ構成では、所望のサイズのサブセットを均一にサンプリングするが、分散低減のために代替案が検討されている。
特に、実験的な証拠は、決定的点過程(dpps)からミニバッチを描き、選択された項目の多様性を好むミニバッチ上の分布を示唆している。
しかし、コアセットのDPPに関する最近の研究のように、DPPがどのように、なぜ助けられるのかを体系的で原則的に理解することは困難である。
本研究では,SGD におけるミニバッチサンプリングのための直交多項式に基づく DPP パラダイムを提案する。
提案手法は,既存のデータに依存しない手法よりも高感度で高感度なデータ分散を実現する。
本手法は,その収束特性を理論的に詳細に解析し,離散データ集合と基礎となる連続領域の間を行き来する手法である。
特に,特定のDPPと制御された近似の列が,一様サンプリングよりもバッチサイズで高速に崩壊するばらつきを持つ勾配推定器にどのように影響するかを示す。
凸目的に対するSGDの既存の有限時間保証と組み合わせると、DPPミニバッチは均一なミニバッチよりも平均二乗近似誤差の小さい境界に導かれる。
さらに,基礎となるdpp(ミニバッチ)をサンプリングすることなく,dppの線形統計量(勾配推定値)を直接サンプリングし,計算オーバーヘッドを低減した最近のアルゴリズムを改良した。
理論的な主張を裏付けるために、詳細な合成と実際のデータ実験を提供する。
関連論文リスト
- A Bayesian Approach to Data Point Selection [24.98069363998565]
データポイントの選択(DPS)は、ディープラーニングにおいて重要なトピックになりつつある。
既存のDPSへのアプローチは、主にバイレベル最適化(BLO)の定式化に基づいている。
DPSに対する新しいベイズ的アプローチを提案する。
論文 参考訳（メタデータ） (2024-11-06T09:04:13Z) - Not All Samples Should Be Utilized Equally: Towards Understanding and Improving Dataset Distillation [57.6797306341115]
我々は,サンプル難易度の観点から,マッチングに基づくDD手法の理解に向けて最初の一歩を踏み出した。
次に、データプルーニングのニューラルネットワークスケーリング法則をDDに拡張し、これらのマッチングベースの手法を理論的に説明する。
SDC(Sampple Difficulty Correction)アプローチを導入し、より簡単なサンプルを生成して、より高いデータセット品質を実現する。
論文 参考訳（メタデータ） (2024-08-22T15:20:32Z) - On Calibrating Diffusion Probabilistic Models [78.75538484265292]
拡散確率モデル(DPM)は様々な生成タスクにおいて有望な結果を得た。
そこで本研究では,任意の事前学習DPMを校正する簡単な方法を提案する。
キャリブレーション法は1回だけ行い, 得られたモデルをサンプリングに繰り返し使用することができる。
論文 参考訳（メタデータ） (2023-02-21T14:14:40Z) - Adaptive Sketches for Robust Regression with Importance Sampling [64.75899469557272]
我々は、勾配降下(SGD)による頑健な回帰を解くためのデータ構造を導入する。
我々のアルゴリズムは、サブ線形空間を使用し、データに1回パスするだけで、SGDの$T$ステップを重要サンプリングで効果的に実行します。
論文 参考訳（メタデータ） (2022-07-16T03:09:30Z) - A Langevin-like Sampler for Discrete Distributions [15.260564469562542]
離散ランゲヴィン計画 (DLP) は、複雑な高次元離散分布をサンプリングするための単純でスケーラブルな勾配に基づく提案である。
DLPは1ステップですべての座標を並列に更新することができ、変更の大きさはステップサイズによって制御される。
未調整, 調整, プリコンディショニングバージョンを含む, サンプリングアルゴリズムのいくつかの変種を開発する。
論文 参考訳（メタデータ） (2022-06-20T17:36:03Z) - Gaussian Process Inference Using Mini-batch Stochastic Gradient Descent:
Convergence Guarantees and Empirical Benefits [21.353189917487512]
勾配降下(SGD)とその変種は、機械学習問題のアルゴリズムとして確立されている。
我々は、最小バッチSGDが全ログ類似損失関数の臨界点に収束することを証明して一歩前進する。
我々の理論的な保証は、核関数が指数的あるいは固有デカイを示すことを前提としている。
論文 参考訳（メタデータ） (2021-11-19T22:28:47Z) - Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and
Beyond [63.59034509960994]
シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。
ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。
我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
論文 参考訳（メタデータ） (2021-10-20T02:25:25Z) - Nonparametric estimation of continuous DPPs with kernel methods [0.0]
パラメトリックおよび非パラメトリック推論法は、有限の場合、すなわち、点パターンが有限の基底集合に存在する場合において提案されている。
我々は、この最大可能性(MLE)問題の制限バージョンが、RKHSにおける非負関数に対する最近の表現定理の範囲内にあることを示す。
この有限次元問題を解くための固定点アルゴリズムを提案し,解析し,実証する。
論文 参考訳（メタデータ） (2021-06-27T11:57:14Z) - Attentional-Biased Stochastic Gradient Descent [74.49926199036481]
深層学習におけるデータ不均衡やラベルノイズ問題に対処するための証明可能な手法(ABSGD)を提案する。
本手法は運動量SGDの簡易な修正であり,各試料に個別の重み付けを行う。
ABSGDは追加コストなしで他の堅牢な損失と組み合わせられるほど柔軟である。
論文 参考訳（メタデータ） (2020-12-13T03:41:52Z) - Sparse Feature Selection Makes Batch Reinforcement Learning More Sample
Efficient [62.24615324523435]
本稿では,スパース線形関数近似を用いた高次元バッチ強化学習(RL)の統計的解析を行う。
候補となる機能が多数存在する場合,提案手法がバッチRLをより効率的にサンプリングできるという事実に光を当てる。
論文 参考訳（メタデータ） (2020-11-08T16:48:02Z) - Learning from DPPs via Sampling: Beyond HKPV and symmetry [2.0305676256390934]
行列点過程(DPP)の線形統計量の分布関数を近似する方法を示す。
我々のアプローチはスケーラブルであり、従来の対称カーネルを超えて非常に一般的なDPPに適用できる。
論文 参考訳（メタデータ） (2020-07-08T17:33:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。