論文の概要: 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}$の近似を最適に決定木分解するアルゴリズムである。 この分解を手元に,各サブキューブ上で一様分布学習器を実行し,決定木を用いて仮説を結合する。 このアルゴリズム分解補題は、新しいアルゴリズムによって決定木分布を学習し、その実行時によって、以前の技術 -- 分散学習に対する独立した関心の結果 -- を指数関数的に改善する。

関連論文リスト

• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Learning general Gaussian mixtures with efficient score matching [16.06356123715737]
  我々は、$d$次元で$k$ガウシアンの混合を学習する問題を研究する。 我々は、下層の混合成分について分離を前提としない。 我々は、ターゲット混合物から$dmathrmpoly(k/varepsilon)$サンプルを抽出し、サンプル-ポリノミカル時間で実行し、サンプリング器を構築するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-04-29T17:30:36Z)
• 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)
• Perfect Sampling from Pairwise Comparisons [26.396901523831534]
  分散分布$mathcalD$の与えられたアクセスから最適なサンプルを効率よく取得する方法を,サポート対象の要素のペア比較に限定して検討する。 固定分布が$mathcalD$と一致するマルコフ連鎖を設計し、過去からの結合技術を用いて正確なサンプルを得るアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2022-11-23T11:20:30Z)
• 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)
• SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  SURFは分布を断片的に近似するアルゴリズムである。 実験では最先端のアルゴリズムよりも優れています。
  論文  参考訳（メタデータ） (2020-02-22T01:03:33Z)

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

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