Fugu-MT 論文翻訳(概要): Learning and Testing Variable Partitions

論文の概要: Learning and Testing Variable Partitions

arxiv url: http://arxiv.org/abs/2003.12990v1
Date: Sun, 29 Mar 2020 10:12:32 GMT
ステータス: 処理完了
システム内更新日: 2022-12-18 13:23:10.611482
Title: Learning and Testing Variable Partitions
Title（参考訳）: 変数分割の学習とテスト
Authors: Andrej Bogdanov and Baoxiang Wang
Abstract要約: 我々は $mathcalO(k n2)(delta + epsilon)$ が、任意の $epsilon > 0$ に対して $tildemathcalO(n2 mathrmpoly (1/epsilon)$ で学習可能であることを示す。また、両面のテスタでさえ$k = 2$の場合に$Omega(n)$クエリが必要であることも示しています。
参考スコア（独自算出の注目度）: 13.575794982844222
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: $ $Let $F$ be a multivariate function from a product set $\Sigma^n$ to an Abelian group $G$. A $k$-partition of $F$ with cost $\delta$ is a partition of the set of variables $\mathbf{V}$ into $k$ non-empty subsets $(\mathbf{X}_1, \dots, \mathbf{X}_k)$ such that $F(\mathbf{V})$ is $\delta$-close to $F_1(\mathbf{X}_1)+\dots+F_k(\mathbf{X}_k)$ for some $F_1, \dots, F_k$ with respect to a given error metric. We study algorithms for agnostically learning $k$ partitions and testing $k$-partitionability over various groups and error metrics given query access to $F$. In particular we show that $1.$ Given a function that has a $k$-partition of cost $\delta$, a partition of cost $\mathcal{O}(k n^2)(\delta + \epsilon)$ can be learned in time $\tilde{\mathcal{O}}(n^2 \mathrm{poly} (1/\epsilon))$ for any $\epsilon > 0$. In contrast, for $k = 2$ and $n = 3$ learning a partition of cost $\delta + \epsilon$ is NP-hard. $2.$ When $F$ is real-valued and the error metric is the 2-norm, a 2-partition of cost $\sqrt{\delta^2 + \epsilon}$ can be learned in time $\tilde{\mathcal{O}}(n^5/\epsilon^2)$. $3.$ When $F$ is $\mathbb{Z}_q$-valued and the error metric is Hamming weight, $k$-partitionability is testable with one-sided error and $\mathcal{O}(kn^3/\epsilon)$ non-adaptive queries. We also show that even two-sided testers require $\Omega(n)$ queries when $k = 2$. This work was motivated by reinforcement learning control tasks in which the set of control variables can be partitioned. The partitioning reduces the task into multiple lower-dimensional ones that are relatively easier to learn. Our second algorithm empirically increases the scores attained over previous heuristic partitioning methods applied in this context.
Abstract（参考訳）: $Let $F$ は積集合 $\Sigma^n$ からアベリア群 $G$ への多変数函数である。 $k$-partition of $F$ with cost $\delta$ は変数の集合 $\mathbf{V}$ から $k$ 非空部分集合 $(\mathbf{X}_1, \dots, \mathbf{X}_k)$ への分割であり、$F(\mathbf{V})$ は $F_1(\mathbf{X}_1)+\dots+F_k(\mathbf{X}_k)$ に対して、与えられた誤差計量に関して $F_1, \dots, F_k$ となる。我々は、様々なグループに対して$k$パーティションを学習し、$F$へのクエリアクセスを与えられたエラーメトリクスに対して$k$パーティショナビリティをテストするアルゴリズムを研究した。特に、$k$-partition of cost$\delta$を持つ関数に対して、$\mathcal{o}(k n^2)(\delta + \epsilon)$ の分割は、$\tilde{\mathcal{o}}(n^2 \mathrm{poly} (1/\epsilon))$ 任意の$\epsilon > 0$ に対して学習できる。対照的に、$k = 2$ と $n = 3$ では、コスト$\delta + \epsilon$ の分割はnp-hardである。 f$ が実数値で、エラーメトリックが 2-ノルムである場合、$\sqrt{\delta^2 + \epsilon}$ の2分割は $\tilde{\mathcal{o}}(n^5/\epsilon^2)$ で学習できる。 $f$ が $\mathbb{z}_q$-valued であり、エラーメトリクスが重くなり、$k$-partitionability は片側のエラーでテスト可能であり、$\mathcal{o}(kn^3/\epsilon)$ は非適応クエリである。また、両面のテスタでさえ$k = 2$の場合に$\Omega(n)$クエリが必要であることも示しています。この作業は、制御変数の集合を分割できる強化学習制御タスクによって動機づけられた。パーティショニングはタスクを比較的学習しやすい複数の低次元のタスクに還元する。第2のアルゴリズムは,この文脈で適用した従来のヒューリスティック分割法より得られたスコアを経験的に向上させる。

関連論文リスト

The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文参考訳（メタデータ） (2024-10-26T06:21:42Z)
LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
任意の$K$に対して、$n$とは独立に「普遍集合」$Uサブセット[n]$が存在し、任意の$Q$と任意の行$i$に対して、大きな注目スコアが$A_i,j$ in row $i$ of $A$は全て$jin U$を持つことを示す。我々は、視覚変換器のスキームの利点を実証的に示し、トレーニング中に我々の普遍的なセットを使用する新しいモデルのトレーニング方法を示した。
論文参考訳（メタデータ） (2024-10-07T19:47:13Z)
Outlier Robust Multivariate Polynomial Regression [27.03423421704806]
1,1]n 回 mathbbR$ は $(mathbfx_i,p(mathbfx_i)$ のうるさいバージョンである。目標は、$hatp$を$ell_in$-distanceの$O(sigma)$を$p$から出力することである。
論文参考訳（メタデータ） (2024-03-14T15:04:45Z)
$\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。 p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。 p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
論文参考訳（メタデータ） (2023-07-11T08:51:53Z)
Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。目標は、低ランク因子の積として$mathbfA$を近似することである。我々の手法はBMF問題の他の一般的な変種に一般化する。
論文参考訳（メタデータ） (2023-06-02T18:55:27Z)
Phase Transitions in the Detection of Correlated Databases [12.010807505655238]
本稿では,2つのガウスデータベースの相関関係を$mathsfXinmathbbRntimes d$と$mathsfYntimes d$で検出する問題について検討する。この問題は、ソーシャルメディア、計算生物学などの分析に関係している。
論文参考訳（メタデータ） (2023-02-07T10:39:44Z)
Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文参考訳（メタデータ） (2022-02-10T16:10:41Z)
Fair Representation Clustering with Several Protected Classes [13.53362222844008]
我々は、各クラスタが異なるグループから個人を公平に表現する必要があるフェア$k$-medianの問題を研究する。我々は、$O(log k)$-approximationアルゴリズムを示し、$nO(ell)$で実行します。
論文参考訳（メタデータ） (2022-02-03T03:45:45Z)
Mediated Uncoupled Learning: Learning Functions without Direct Input-output Correspondences [80.95776331769899]
ペア化されたデータがない場合、$X$から$Y$を予測するタスクを考えます。単純なアプローチは、$S_X$で$U$から$U$を予測し、$S_Y$で$U$から$Y$を予測することである。我々は$U$を予測しない新しい方法を提案するが、$f(X)$と$S_X$をトレーニングすることで$Y = f(X)$を直接学習し、$h(U)$を予測する。
論文参考訳（メタデータ） (2021-07-16T22:13:29Z)
Sharper bounds for online learning of smooth functions of a single variable [0.0]
ここでは$opt_1+epsilon(mathcalF_q) = Theta(epsilon-frac12)$を示します。また、$opt_1+epsilon(mathcalF_q) = Theta(epsilon-frac12)$ も示します。
論文参考訳（メタデータ） (2021-05-30T23:06:21Z)
The planted matching problem: Sharp threshold and infinite-order phase transition [25.41713098167692]
ランダムに重み付けされた$ntimes n$ bipartite graphに隠された完全マッチング$M*$を再構築する問題について検討する。任意の小さな定数 $epsilon>0$ に対して $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ が成り立つ場合、任意の推定値の再構築誤差は $0$ から有界であることが示される。
論文参考訳（メタデータ） (2021-03-17T00:59:33Z)

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

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