論文の概要: Worst-case Error Bounds for Online Learning of Smooth Functions

• arxiv url: http://arxiv.org/abs/2502.16388v1
• Date: Sun, 23 Feb 2025 00:43:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-25 15:56:37.072527
• Title: Worst-case Error Bounds for Online Learning of Smooth Functions
• Title（参考訳）: スムース関数のオンライン学習のための最悪のエラー境界
• Authors: Weian Xie,
• Abstract要約: 本研究では,あるスムーズな制約のある実関数のオンライン学習における最悪の誤りについて検討する。 すべての$p, q ge 2$ および $eta ge 1$ に対して $operatornameopttextnf_p, eta (mathcalF_q)$ は有限であることを示す。 また、スムーズな関数のオンライン学習のためのノイズモデルを定義し、学習者は最大1回まで誤ったフィードバックを受けることができる。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: Online learning is a model of machine learning where the learner is trained on sequential feedback. We investigate worst-case error for the online learning of real functions that have certain smoothness constraints. Suppose that $\mathcal{F}_q$ is the class of all absolutely continuous functions $f: [0, 1] \rightarrow \mathbb{R}$ such that $\|f'\|_q \le 1$, and $\operatorname{opt}_p(\mathcal{F}_q)$ is the best possible upper bound on the sum of the $p^{\text{th}}$ powers of absolute prediction errors for any number of trials guaranteed by any learner. We show that for any $\delta, \epsilon \in (0, 1)$, $\operatorname{opt}_{1+\delta} (\mathcal{F}_{1+\epsilon}) = O(\min(\delta, \epsilon)^{-1})$. Combined with the previous results of Kimber and Long (1995) and Geneson and Zhou (2023), we achieve a complete characterization of the values of $p, q \ge 1$ that result in $\operatorname{opt}_p(\mathcal{F}_q)$ being finite, a problem open for nearly 30 years. We study the learning scenarios of smooth functions that also belong to certain special families of functions, such as polynomials. We prove a conjecture by Geneson and Zhou (2023) that it is not any easier to learn a polynomial in $\mathcal{F}_q$ than it is to learn any general function in $\mathcal{F}_q$. We also define a noisy model for the online learning of smooth functions, where the learner may receive incorrect feedback up to $\eta \ge 1$ times, denoting the worst-case error bound as $\operatorname{opt}^{\text{nf}}_{p, \eta} (\mathcal{F}_q)$. We prove that $\operatorname{opt}^{\text{nf}}_{p, \eta} (\mathcal{F}_q)$ is finite if and only if $\operatorname{opt}_p(\mathcal{F}_q)$ is. Moreover, we prove for all $p, q \ge 2$ and $\eta \ge 1$ that $\operatorname{opt}^{\text{nf}}_{p, \eta} (\mathcal{F}_q) = \Theta (\eta)$.
• Abstract（参考訳）: オンライン学習は機械学習のモデルであり、学習者はシーケンシャルなフィードバックに基づいて訓練される。 本研究では,あるスムーズな制約のある実関数のオンライン学習における最悪の誤りについて検討する。 f: [0, 1] \rightarrow \mathbb{R}$ を $\|f'\|_q \le 1$, and $\operatorname{opt}_p(\mathcal{F}_q)$ が任意の学習者が保証する任意の試行数に対する絶対予測誤差のパワーの和の最大上限であるとする。 任意の $\delta, \epsilon \in (0, 1)$, $\operatorname{opt}_{1+\delta} (\mathcal{F}_{1+\epsilon}) = O(\min(\delta, \epsilon)^{-1})$ であることを示す。 Kimber and Long (1995) と Geneson and Zhou (2023) の以前の結果と組み合わせて、$p, q \ge 1$ の値の完全な特徴づけを達成し、その結果 $\operatorname{opt}_p(\mathcal{F}_q)$ は有限となる。 多項式のような関数の特定の特別な族に属する滑らかな関数の学習シナリオについて検討する。 我々は、Geneson と Zhou (2023) による予想を証明し、$\mathcal{F}_q$ で多項式を学ぶことは、$\mathcal{F}_q$ で一般函数を学ぶことよりも容易ではない。 また、スムーズな関数のオンライン学習のためのノイズモデルを定義し、学習者は間違ったフィードバックを$\eta \ge 1$ timesまで受け取り、最悪のケースエラーを$\operatorname{opt}^{\text{nf}}_{p, \eta} (\mathcal{F}_q)$と記述する。 我々は、$\operatorname{opt}^{\text{nf}}_{p, \eta} (\mathcal{F}_q)$が有限であることと、$\operatorname{opt}_p(\mathcal{F}_q)$が有限であることを証明する。 さらに、すべての$p, q \ge 2$ および $\eta \ge 1$ に対して $\operatorname{opt}^{\text{nf}}_{p, \eta} (\mathcal{F}_q) = \Theta (\eta)$ を証明する。

関連論文リスト

• PREM: Privately Answering Statistical Queries with Relative Error [91.98332694700046]
  合成データを生成する新しいフレームワークである$mathsfPREM$(Private Relative Error Multiplicative weight update)を紹介します。 我々はアルゴリズムをほぼ一致する下界で補完する。
  論文  参考訳（メタデータ） (2025-02-20T18:32:02Z)
• Quantum Sabotage Complexity [0.7812210699650152]
  ここでは$mathsfQ(f_mathsfsab)$を示し、$f_mathsfsab$の量子クエリ複雑性を示す。 f$がインデックス関数であるとき、$mathsfQ(f_mathsfsab)=Theta(sqrtmathsfsab)$は、$mathsfQ(f_mathsfsab)=Theta(sqrtmathsf)の可能性を除外する。
  論文  参考訳（メタデータ） (2024-08-22T17:57:58Z)
• Quantum and classical query complexities of functions of matrices [0.0]
  任意の連続関数 $f(x):[-1,1]rightarrow [-1,1]$ に対して、計算の量子クエリ複雑性 $brai f(A) ketjpm varepsilon/4$ は$Omega(widetildedeg_varepsilon(f))$ で制限される。
  論文  参考訳（メタデータ） (2023-11-13T00:45:41Z)
• Online Learning of Smooth Functions [0.35534933448684125]
  隠れ関数が一定の滑らか性を持つことが知られている実数値関数のオンライン学習について検討する。 定数係数までシャープな$textopt_p(mathcal F_q)$の新たなバウンダリを見つける。 マルチ変数のセットアップでは、$textopt_p(mathcal F_q,d)$ to $textopt_p(mathcal F_q,d)$に関連する不等式を確立し、$textopt_p(mathcal F)$を示す。
  論文  参考訳（メタデータ） (2023-01-04T04:05:58Z)
• Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
  マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。 我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
  論文  参考訳（メタデータ） (2022-07-28T17:50:53Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• Learning low-degree functions from a logarithmic number of random queries [77.34726150561087]
  任意の整数 $ninmathbbN$, $din1,ldots,n$ および任意の $varepsilon,deltain(0,1)$ に対して、有界関数 $f:-1,1nto[-1,1]$ に対して、少なくとも$d$ の次数を学ぶことができる。
  論文  参考訳（メタデータ） (2021-09-21T13:19:04Z)
• 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)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)

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

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