論文の概要: Lifting uniform learners via distributional decomposition
- arxiv url: http://arxiv.org/abs/2303.16208v2
- Date: Thu, 30 Mar 2023 00:50:26 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-31 16:00:09.131445
- Title: Lifting uniform learners via distributional decomposition
- Title(参考訳): 分布分解による一様学習者のリフティング
- Authors: Guy Blanc, Jane Lange, Ali Malik, Li-Yang Tan
- Abstract要約: 均一分布の下で動作する任意のPAC学習アルゴリズムが、ブラックボックス方式で、任意の未知分布の$mathcalD$の下で動作させるアルゴリズムに変換可能であることを示す。
重要な技術的要素は、前述の$mathcalD$にアクセスすると、$mathcalD$の最適な決定木分解を生成するアルゴリズムである。
- 参考スコア(独自算出の注目度): 17.775217381568478
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: We show how any PAC learning algorithm that works under the uniform
distribution can be transformed, in a blackbox fashion, into one that works
under an arbitrary and unknown distribution $\mathcal{D}$. The efficiency of
our transformation scales with the inherent complexity of $\mathcal{D}$,
running in $\mathrm{poly}(n, (md)^d)$ time for distributions over $\{\pm 1\}^n$
whose pmfs are computed by depth-$d$ decision trees, where $m$ is the sample
complexity of the original algorithm. For monotone distributions our
transformation uses only samples from $\mathcal{D}$, and for general ones it
uses subcube conditioning samples.
A key technical ingredient is an algorithm which, given the aforementioned
access to $\mathcal{D}$, produces an optimal decision tree decomposition of
$\mathcal{D}$: an approximation of $\mathcal{D}$ as a mixture of uniform
distributions over disjoint subcubes. With this decomposition in hand, we run
the uniform-distribution learner on each subcube and combine the hypotheses
using the decision tree. This algorithmic decomposition lemma also yields new
algorithms for learning decision tree distributions with runtimes that
exponentially improve on the prior state of the art -- results of independent
interest in distribution learning.
- Abstract(参考訳): 均一分布の下で動作する任意のPAC学習アルゴリズムが、ブラックボックス方式で任意の未知分布である$\mathcal{D}$の下で機能するアルゴリズムに変換可能であることを示す。
変換の効率性は、$\mathcal{d}$の固有の複雑さとともにスケールし、$\mathrm{poly}(n, (md)^d)$の分布に対して$\{\pm 1\}^n$のpmfが深さ$d$決定木によって計算される。
単調分布の場合、変換は$\mathcal{d}$のサンプルのみを使用し、一般にはsubcube条件付きサンプルを使用する。
重要な技術的要素は、前述の$\mathcal{D}$へのアクセスが与えられたとき、解離部分キューブ上の均一分布の混合として$\mathcal{D}$:$\mathcal{D}$の近似を最適に決定木分解するアルゴリズムである。
この分解を手元に,各サブキューブ上で一様分布学習器を実行し,決定木を用いて仮説を結合する。
このアルゴリズム分解補題は、新しいアルゴリズムによって決定木分布を学習し、その実行時によって、以前の技術 -- 分散学習に対する独立した関心の結果 -- を指数関数的に改善する。
関連論文リスト
- 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) - Replicable Clustering [57.19013971737493]
我々は,統計学的な$k$-medians,統計学的な$k$-means,統計学的な$k$-centers問題のアルゴリズムをブラックボックス方式で近似ルーチンを用いて提案する。
理論的結果を検証するブラックボックスとしてsklearnの$k$-means++実装を用いた2次元合成分布の実験も行っている。
論文 参考訳(メタデータ) (2023-02-20T23:29:43Z) - Stochastic Approximation Approaches to Group Distributionally Robust
Optimization [96.26317627118912]
群分散ロバスト最適化(GDRO)
オンライン学習技術は、各ラウンドに必要なサンプル数をm$から1$に減らし、同じサンプルを保持する。
分布依存収束率を導出できる重み付きGDROの新規な定式化。
論文 参考訳(メタデータ) (2023-02-18T09:24:15Z) - Perfect Sampling from Pairwise Comparisons [26.396901523831534]
分散分布$mathcalD$の与えられたアクセスから最適なサンプルを効率よく取得する方法を,サポート対象の要素のペア比較に限定して検討する。
固定分布が$mathcalD$と一致するマルコフ連鎖を設計し、過去からの結合技術を用いて正確なサンプルを得るアルゴリズムを提供する。
論文 参考訳(メタデータ) (2022-11-23T11:20:30Z) - Robust Sparse Mean Estimation via Sum of Squares [48.07596965953344]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳(メタデータ) (2022-06-07T16:49:54Z) - Optimal Gradient Sliding and its Application to Distributed Optimization
Under Similarity [121.83085611327654]
積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。
エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。
提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
論文 参考訳(メタデータ) (2022-05-30T14:28:02Z) - An Improved Analysis of Gradient Tracking for Decentralized Machine
Learning [34.144764431505486]
トレーニングデータが$n$エージェントに分散されるネットワーク上での分散機械学習を検討する。
エージェントの共通の目標は、すべての局所損失関数の平均を最小化するモデルを見つけることである。
ノイズのない場合、$p$を$mathcalO(p-1)$から$mathcalO(p-1)$に改善します。
論文 参考訳(メタデータ) (2022-02-08T12:58:14Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳(メタデータ) (2020-05-13T16:44:12Z) - Learning and Testing Junta Distributions with Subcube Conditioning [11.464622619555222]
本研究では,一様分布に関して,1,1n$のユンタ分布の学習と試験の問題点について検討する。
主な寄与は、サブキューブ条件付き$k$-junta分布における関連する座標を見つけるアルゴリズムである。
論文 参考訳(メタデータ) (2020-04-26T22:52:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。