論文の概要: Downsampling for Testing and Learning in Product Distributions
- arxiv url: http://arxiv.org/abs/2007.07449v2
- Date: Mon, 15 Nov 2021 20:53:31 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-10 06:50:33.263274
- Title: Downsampling for Testing and Learning in Product Distributions
- Title（参考訳）: 製品配布におけるテストと学習のためのダウンサンプリング
- Authors: Nathaniel Harms, Yuichi Yoshida
- Abstract要約: 未知確率分布が $mathbbRd$ 上の積分布であるような分布自由なプロパティテストと学習問題について検討する。
ハーフスペースの交叉、しきい値関数、凸集合、および$k$交互関数などの多くの重要な関数のクラスでは、既知のアルゴリズムは、分布のサポートサイズに依存する複雑さを持つ。
本稿では,これらの問題を解消する一般手法として,ダウンログ(downlog)を提案する。
- 参考スコア（独自算出の注目度）: 24.48103093661132
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study distribution-free property testing and learning problems where the
unknown probability distribution is a product distribution over $\mathbb{R}^d$.
For many important classes of functions, such as intersections of halfspaces,
polynomial threshold functions, convex sets, and $k$-alternating functions, the
known algorithms either have complexity that depends on the support size of the
distribution, or are proven to work only for specific examples of product
distributions. We introduce a general method, which we call downsampling, that
resolves these issues. Downsampling uses a notion of "rectilinear isoperimetry"
for product distributions, which further strengthens the connection between
isoperimetry, testing, and learning. Using this technique, we attain new
efficient distribution-free algorithms under product distributions on
$\mathbb{R}^d$:
1. A simpler proof for non-adaptive, one-sided monotonicity testing of
functions $[n]^d \to \{0,1\}$, and improved sample complexity for testing
monotonicity over unknown product distributions, from $O(d^7)$ [Black,
Chakrabarty, & Seshadhri, SODA 2020] to $\widetilde O(d^3)$.
2. Polynomial-time agnostic learning algorithms for functions of a constant
number of halfspaces, and constant-degree polynomial threshold functions.
3. An $\exp(O(d \log(dk)))$-time agnostic learning algorithm, and an
$\exp(O(d \log(dk)))$-sample tolerant tester, for functions of $k$ convex sets;
and a $2^{\widetilde O(d)}$ sample-based one-sided tester for convex sets.
4. An $\exp(\widetilde O(k \sqrt d))$-time agnostic learning algorithm for
$k$-alternating functions, and a sample-based tolerant tester with the same
complexity.
- Abstract（参考訳）: 未知確率分布が$\mathbb{r}^d$ を超える積分布である分布自由特性試験と学習問題について検討する。
半空間の交叉、多項式しきい値関数、凸集合、および $k$-アルタネート関数のような多くの重要な関数クラスにおいて、既知のアルゴリズムは、分布の支持サイズに依存する複雑さを持つか、製品分布の特定の例でのみ機能することが証明される。
我々は,これらの問題を解消する一般的な手法であるdownsamplingを提案する。
ダウンサンプリングは、製品分布に対する「回帰イソペリメトリ(rectilinear isoperimetry)」の概念を使い、イソペリメトリ、テスト、学習の関連性をさらに強化する。
この手法を用いて、製品分布下での新しい効率的な分布のないアルゴリズムを$\mathbb{R}^d$: 1. 関数の非適応的で一方的な単調性テストの簡易な証明を$[n]^d \to \{0,1\}$で達成し、未知の製品分布上で単調性をテストするためのサンプルの複雑さを$O(d^7)$ [Black, Chakrabarty, & Seshadhri, SODA 2020] から$\widetilde O(d^3)$に改善する。
2. 半空間の定数数と多項式閾値関数の関数に対する多項式時間非依存学習アルゴリズム
3.$\exp(o(d \log(dk)))$-time agnostic learningアルゴリズムと$k$凸集合の関数に対して$\exp(o(d \log(dk))$-sample tolerance testerと$^{\widetilde o(d)}$ 凸集合のサンプルベース片面テスト器。
4.$\exp(\widetilde O(k \sqrt d))$-time agnostic learning algorithm for $k$-alternating function, and a sample-based tolerant tester with the complexity。
関連論文リスト
- Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds [9.036777309376697]
Klivans、Stavropoulos、Vasilyanは、分散シフトを伴うテスト可能な学習の研究を始めた。
それらのモデルは、$mathcalD'$に仮定されないという点で、以前のすべての作業から逸脱している。
論文 参考訳（メタデータ） (2024-04-02T23:34:39Z) - Agnostically Learning Multi-index Models with Queries [54.290489524576756]
本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。
クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
論文 参考訳（メタデータ） (2023-12-27T15:50:47Z) - Testable Learning with Distribution Shift [9.036777309376697]
分散シフトを伴うテスト可能学習と呼ばれる新しいモデルを定義する。
テスト分布上の分類器の性能を証明可能なアルゴリズムを得る。
ハーフスペースやハーフスペースの交点,決定木といった概念クラスを学ぶ上で,いくつかの肯定的な結果が得られる。
論文 参考訳（メタデータ） (2023-11-25T23:57:45Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Testing distributional assumptions of learning algorithms [5.204779946147061]
テストレーナー対 $(mathcalA,mathcalT)$ の設計について検討する。
データ中の例の分布がテスタを$mathcalT$に渡せば、データ上の非依存な$mathcalA$の出力を安全に信頼できることを示す。
論文 参考訳（メタデータ） (2022-04-14T19:10:53Z) - Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures [9.053430799456587]
有限混合系における非パラメトリック分布の学習問題について検討する。
このようなモデルにおける成分分布を学習するために、サンプルの複雑さに厳密な境界を定めている。
論文 参考訳（メタデータ） (2022-03-28T23:53:48Z) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。
本稿では,この数値をほぼ最適に推定する手法を提案する。
論文 参考訳（メタデータ） (2022-02-15T03:49:28Z) - Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
高確率状態に着目して離散分布を試験する問題について検討する。
一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
論文 参考訳（メタデータ） (2020-09-14T16:09:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。