論文の概要: Tackling Combinatorial Distribution Shift: A Matrix Completion
Perspective
- arxiv url: http://arxiv.org/abs/2307.06457v1
- Date: Wed, 12 Jul 2023 21:17:47 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-14 16:27:51.312671
- Title: Tackling Combinatorial Distribution Shift: A Matrix Completion
Perspective
- Title（参考訳）: 組合せ分布シフトに取り組む:行列完全性の観点から
- Authors: Max Simchowitz and Kaiqing Zhang and Abhishek Gupta
- Abstract要約: a) テストランダムデータおよびトレーニングランダムデータの下で、ラベル$z$は、(x,y)$, (b) トレーニングディストリビューションは、別々に$x$と$y$の限界分布をカバーしているが、(c) テストディストリビューションは、トレーニングディストリビューションがカバーしていない製品ディストリビューションの例を含む。
- 参考スコア（独自算出の注目度）: 42.85196869759167
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Obtaining rigorous statistical guarantees for generalization under
distribution shift remains an open and active research area. We study a setting
we call combinatorial distribution shift, where (a) under the test- and
training-distributions, the labels $z$ are determined by pairs of features
$(x,y)$, (b) the training distribution has coverage of certain marginal
distributions over $x$ and $y$ separately, but (c) the test distribution
involves examples from a product distribution over $(x,y)$ that is {not}
covered by the training distribution. Focusing on the special case where the
labels are given by bilinear embeddings into a Hilbert space $H$: $\mathbb{E}[z
\mid x,y ]=\langle f_{\star}(x),g_{\star}(y)\rangle_{{H}}$, we aim to
extrapolate to a test distribution domain that is $not$ covered in training,
i.e., achieving bilinear combinatorial extrapolation.
Our setting generalizes a special case of matrix completion from
missing-not-at-random data, for which all existing results require the
ground-truth matrices to be either exactly low-rank, or to exhibit very sharp
spectral cutoffs. In this work, we develop a series of theoretical results that
enable bilinear combinatorial extrapolation under gradual spectral decay as
observed in typical high-dimensional data, including novel algorithms,
generalization guarantees, and linear-algebraic results. A key tool is a novel
perturbation bound for the rank-$k$ singular value decomposition approximations
between two matrices that depends on the relative spectral gap rather than the
absolute spectral gap, a result that may be of broader independent interest.
- Abstract（参考訳）: 分布シフト下での一般化のための厳密な統計的保証を得ることは、オープンかつアクティブな研究領域である。
私たちはコンビネート的分布シフトという設定を研究し
(a) テストおよびトレーニング配信の下では、ラベル$z$ は機能対 $(x,y)$ によって決定される。
b) トレーニング分布は、x$ と y$ を別にして、一定の限界分布をカバーするが、
(c) テスト分布は、トレーニング分布でカバーされている {not} である $(x,y)$ 以上の製品分布からの例を含む。
ラベルが双線型埋め込みによってヒルベルト空間 $H$: $\mathbb{E}[z \mid x,y]=\langle f_{\star} に与えられる特別な場合に着目して
x,g_{\star (複数形 x,g_{\stars)
(y)\rangle_{{H}}$、トレーニングでカバーされる$not$のテスト分布領域、すなわち双線形組合せ外挿を達成することを目指している。
本設定では,非ランダムデータから行列完備化の特別な事例を一般化し,既存の結果のすべてにおいて,地上構造行列を正確に低ランクにするか,あるいは非常にシャープなスペクトルカットオフを示す必要がある。
本研究では, 新アルゴリズム, 一般化保証, 線形代数的結果など, 典型的な高次元データに見られるような, 漸進的スペクトル崩壊下での双線形組合せ外挿を可能にする一連の理論的結果を開発する。
鍵となるツールは、絶対スペクトルギャップよりも相対スペクトルギャップに依存する2つの行列の間のランク-$k$ 特異値分解近似に対して束縛された新しい摂動である。
関連論文リスト
- Gradual Domain Adaptation via Manifold-Constrained Distributionally Robust Optimization [0.4732176352681218]
本稿では、多様体制約データ分布のクラスにおける段階的領域適応の課題に対処する。
本稿では,適応的なワッサースタイン半径を持つ分布ロバスト最適化(DRO)を基礎とした手法を提案する。
我々のバウンダリは、新たに導入されたそれとの互換性尺度に依存しており、シーケンスに沿ったエラー伝搬のダイナミクスを完全に特徴付けています。
論文 参考訳（メタデータ） (2024-10-17T22:07:25Z) - Out-Of-Domain Unlabeled Data Improves Generalization [0.7589678255312519]
本稿では,ラベルなしデータを半教師付き分類問題に組み込む新しい枠組みを提案する。
ラベルのないサンプルは一般化ギャップを狭めるために利用できることを示す。
我々は、さまざまな合成および実世界のデータセットで実施された実験を通じて、我々の主張を検証する。
論文 参考訳（メタデータ） (2023-09-29T02:00:03Z) - An Equivalence Principle for the Spectrum of Random Inner-Product Kernel
Matrices with Polynomial Scalings [21.727073594338297]
この研究は、機械学習と統計学の応用によって動機付けられている。
スケーリングシステムにおいて,これらのランダム行列の経験的分布の弱い限界を確立する。
我々の結果は、マルテンコ・パストゥル法と半円法の間の自由加法的畳み込みとして特徴づけられる。
論文 参考訳（メタデータ） (2022-05-12T18:50:21Z) - Testing distributional assumptions of learning algorithms [5.204779946147061]
テストレーナー対 $(mathcalA,mathcalT)$ の設計について検討する。
データ中の例の分布がテスタを$mathcalT$に渡せば、データ上の非依存な$mathcalA$の出力を安全に信頼できることを示す。
論文 参考訳（メタデータ） (2022-04-14T19:10:53Z) - Non-Gaussian Component Analysis via Lattice Basis Reduction [56.98280399449707]
非ガウス成分分析(NGCA)は分布学習問題である。
我々は,NGCA に対して,$A$ が離散的あるいはほぼ離散的であるような効率的なアルゴリズムを提供する。
論文 参考訳（メタデータ） (2021-12-16T18:38:02Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳（メタデータ） (2021-09-24T14:48:20Z) - Robust Learning of Optimal Auctions [84.13356290199603]
本研究では、入札者の評価値のサンプルを逆向きに破損させたり、逆向きに歪んだ分布から引き出すことができる場合に、サンプルから収益-最適マルチバイダオークションを学習する問題について検討する。
我々は,コルモゴロフ-スミルノフ距離における元の分布に対して$alpha$-closeの「全ての真の分布」に対して,収入がほぼ同時に最適であるメカニズムを学習できる新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-07-13T17:37:21Z) - Agnostic Learning of Halfspaces with Gradient Descent via Soft Margins [92.7662890047311]
勾配降下は、分類誤差$tilde O(mathsfOPT1/2) + varepsilon$ in $mathrmpoly(d,1/varepsilon)$ time and sample complexity.
論文 参考訳（メタデータ） (2020-10-01T16:48:33Z) - Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。
我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-30T19:10:32Z) - A Precise High-Dimensional Asymptotic Theory for Boosting and
Minimum-$\ell_1$-Norm Interpolated Classifiers [3.167685495996986]
本稿では,分離可能なデータの強化に関する高精度な高次元理論を確立する。
統計モデルのクラスでは、ブースティングの普遍性誤差を正確に解析する。
また, 推力試験誤差と最適ベイズ誤差の関係を明示的に説明する。
論文 参考訳（メタデータ） (2020-02-05T00:24:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。