論文の概要: Sharper bounds for online learning of smooth functions of a single
variable
- arxiv url: http://arxiv.org/abs/2105.14648v1
- Date: Sun, 30 May 2021 23:06:21 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-02 07:30:45.207279
- Title: Sharper bounds for online learning of smooth functions of a single
variable
- Title（参考訳）: 単一変数の滑らかな関数のオンライン学習のためのよりシャープな境界
- Authors: Jesse Geneson
- Abstract要約: ここでは$opt_1+epsilon(mathcalF_q) = Theta(epsilon-frac12)$を示します。
また、$opt_1+epsilon(mathcalF_q) = Theta(epsilon-frac12)$ も示します。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We investigate the generalization of the mistake-bound model to continuous
real-valued single variable functions. Let $\mathcal{F}_q$ be the class of
absolutely continuous functions $f: [0, 1] \rightarrow \mathbb{R}$ with
$||f'||_q \le 1$, and define $opt_p(\mathcal{F}_q)$ as the best possible bound
on the worst-case sum of the $p^{th}$ powers of the absolute prediction errors
over any number of trials. Kimber and Long (Theoretical Computer Science, 1995)
proved for $q \ge 2$ that $opt_p(\mathcal{F}_q) = 1$ when $p \ge 2$ and
$opt_p(\mathcal{F}_q) = \infty$ when $p = 1$. For $1 < p < 2$ with $p =
1+\epsilon$, the only known bound was $opt_p(\mathcal{F}_{q}) =
O(\epsilon^{-1})$ from the same paper. We show for all $\epsilon \in (0, 1)$
and $q \ge 2$ that $opt_{1+\epsilon}(\mathcal{F}_q) =
\Theta(\epsilon^{-\frac{1}{2}})$, where the constants in the bound do not
depend on $q$. We also show that $opt_{1+\epsilon}(\mathcal{F}_{\infty}) =
\Theta(\epsilon^{-\frac{1}{2}})$.
- Abstract（参考訳）: 連続実数値単変数関数に対する誤りバウンドモデルの一般化について検討する。
0, 1] \rightarrow \mathbb{R}$ with $|f'||_q \le 1$, and defined $opt_p(\mathcal{F}_q)$ as the best possible bound on the worst-case sum of the $p^{th}$ power of the absolute prediction error over any number of trial。
Kimber and Long (Theoretical Computer Science, 1995) は$q \ge 2$に対して$opt_p(\mathcal{F}_q) = 1$ = $p \ge 2$と$opt_p(\mathcal{F}_q) = \infty$は$p = 1$であることを示した。
1 < p < 2$ with $p = 1+\epsilon$ に対し、唯一知られている境界は同じ論文から$opt_p(\mathcal{f}_{q}) = o(\epsilon^{-1})$ である。
すべての$\epsilon \in (0, 1)$および$q \ge 2$ that $opt_{1+\epsilon}(\mathcal{F}_q) = \Theta(\epsilon^{-\frac{1}{2}})$に対して、境界の定数は$q$に依存しない。
また、$opt_{1+\epsilon}(\mathcal{F}_{\infty}) = \Theta(\epsilon^{-\frac{1}{2}})$ を示す。
関連論文リスト
- Coresets for Multiple $\ell_p$ Regression [47.790126028106734]
サイズ $tilde O(varepsilon-2d)$ for $p2$ と $tilde O(varepsilon-pdp/2)$ for $p>2$ のコアセットを構築します。
1p2$の場合、すべての行列は$tilde O(varepsilon-1k)$行のサブセットを持ち、$(varepsilon-1k)$-a optimal $k$-dimensional subspace for $ell_p$ subspace approximationである。
論文 参考訳（メタデータ） (2024-06-04T15:50:42Z) - $\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) - 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) - 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) - 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) - 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) - 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) - Mathematical comparison of classical and quantum mechanisms in
optimization under local differential privacy [0.0]
我々は、$mathrmEC_n(varepsilon)not=mathrmCQ_n(varepsilon)$ for every $nge3$を示し、$mathrmEC_n(varepsilon)$と$mathrmCQ_n(varepsilon)$の差をある方法で見積もる。
論文 参考訳（メタデータ） (2020-11-19T17:05:11Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。