Fugu-MT 論文翻訳(概要): Learning bounded subsets of $L

論文の概要: Learning bounded subsets of $L_p$

arxiv url: http://arxiv.org/abs/2002.01182v1
Date: Tue, 4 Feb 2020 09:25:34 GMT
ステータス: 処理完了
システム内更新日: 2023-01-04 02:52:18.394379
Title: Learning bounded subsets of $L_p$
Title（参考訳）: 有界部分集合の学習 $l_p$
Authors: Shahar Mendelson
Abstract要約: 基礎となるクラスが$L_p$の有界部分集合であり、対象の$Y$が$L_p$に属する学習問題を研究する。任意の$p > 4$ の急激なサンプル複雑性の推定値を示す。
参考スコア（独自算出の注目度）: 8.147652597876862
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study learning problems in which the underlying class is a bounded subset of $L_p$ and the target $Y$ belongs to $L_p$. Previously, minimax sample complexity estimates were known under such boundedness assumptions only when $p=\infty$. We present a sharp sample complexity estimate that holds for any $p > 4$. It is based on a learning procedure that is suited for heavy-tailed problems.
Abstract（参考訳）: 基礎となるクラスが$L_p$の有界部分集合であり、対象の$Y$が$L_p$に属する学習問題を研究する。以前は、ミニマックスサンプルの複雑性推定は、そのような有界性仮定の下で、$p=\infty$のときのみ知られていた。任意の$p > 4$ の急激なサンプル複雑性の推定値を示す。これは、重み付き問題に適した学習手順に基づいている。

関連論文リスト

One-Shot Learning for k-SAT [2.6293381978389787]
我々は、$k$-SATのワンショット学習が、満足度しきい値を大きく下回っていることを示す。学習アルゴリズムの解析を単純化し、$d$のより強いバウンダリを$beta$で取得する。
論文参考訳（メタデータ） (2025-02-10T23:56:08Z)
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)
The Sample Complexity of Multi-Distribution Learning for VC Classes [25.73730126599202]
マルチディストリビューション学習は、PAC学習を複数のデータ分布を持つ設定に一般化したものである。 PAC学習クラスでは, 既知の上層境界と下層境界との間に大きなギャップが残っている。本稿では,この問題の最近の進展と,統計学習におけるゲームダイナミクスの利用の基礎となるいくつかのハードルについて論じる。
論文参考訳（メタデータ） (2023-07-22T18:02:53Z)
Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文参考訳（メタデータ） (2023-07-13T18:59:28Z)
The Sample Complexity of Approximate Rejection Sampling with Applications to Smoothed Online Learning [29.44582058149344]
n$ の関数としての最適総変分距離が $tildeTheta(fracDf'(n))$ によって与えられることを示す。次に、スムーズなオンライン学習という非常に異なる分野のアプリケーションを検討します。
論文参考訳（メタデータ） (2023-02-09T14:20:14Z)
Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path [106.37656068276902]
本稿では,最短経路(SSP)問題において,$epsilon$-optimal Policyを学習する際のサンプル複雑性について検討する。学習者が生成モデルにアクセスできる場合、複雑性境界を導出する。我々は、$S$状態、$A$アクション、最小コスト$c_min$、およびすべての状態に対する最適ポリシーの最大期待コストを持つ最悪のSSPインスタンスが存在することを示す。
論文参考訳（メタデータ） (2022-10-10T18:34:32Z)
Overcoming the Long Horizon Barrier for Sample-Efficient Reinforcement Learning with Latent Low-Rank Structure [9.759209713196718]
我々は、対応する最適$Q*$関数が低ランクであるMDPのクラスを考える。より強い低階構造仮定の下では、生成モデル(LR-MCPI)と低階経験値イテレーション(LR-EVI)が、ランクに対して$tildeOleft((|S|+|A|)mathrmpoly(d,H)/epsilon2right)$の所望のサンプル複雑性を実現することが示されている。
論文参考訳（メタデータ） (2022-06-07T20:39:51Z)
Average-case Complexity of Teaching Convex Polytopes via Halfspace Queries [55.28642461328172]
平均的なケースの教えの複雑さは$Theta(d)$であり、最悪のケースの教えの複雑さは$Theta(n)$とは対照的である。我々の洞察は、$phi$-separable dichotomiesの平均ケースの複雑さに厳密な拘束力を確立することを可能にする。
論文参考訳（メタデータ） (2020-06-25T19:59:24Z)
$Q$-learning with Logarithmic Regret [60.24952657636464]
楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
論文参考訳（メタデータ） (2020-06-16T13:01:33Z)
Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文参考訳（メタデータ） (2020-06-06T13:34:41Z)
Differentially Private Release and Learning of Threshold Functions [27.612916837481485]
我々は、$(epsilon, delta)$微分プライベートアルゴリズムのサンプル複雑性に対して、新しい上界と下界を証明した。完全に順序付けられたドメイン上のしきい値関数$c_x$は$c_x(y) = 1$ if $y le x$と評価され、$0$と評価される。
論文参考訳（メタデータ） (2015-04-28T16:15:01Z)

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