論文の概要: Online Learning of Smooth Functions
- arxiv url: http://arxiv.org/abs/2301.01434v1
- Date: Wed, 4 Jan 2023 04:05:58 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-05 15:22:32.778752
- Title: Online Learning of Smooth Functions
- Title(参考訳): スムース関数のオンライン学習
- Authors: Jesse Geneson and Ethan Zhou
- Abstract要約: 隠れ関数が一定の滑らか性を持つことが知られている実数値関数のオンライン学習について検討する。
定数係数までシャープな$textopt_p(mathcal F_q)$の新たなバウンダリを見つける。
マルチ変数のセットアップでは、$textopt_p(mathcal F_q,d)$ to $textopt_p(mathcal F_q,d)$に関連する不等式を確立し、$textopt_p(mathcal F)$を示す。
- 参考スコア(独自算出の注目度): 0.35534933448684125
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study the online learning of real-valued functions where
the hidden function is known to have certain smoothness properties.
Specifically, for $q \ge 1$, let $\mathcal F_q$ be the class of absolutely
continuous functions $f: [0,1] \to \mathbb R$ such that $\|f'\|_q \le 1$. For
$q \ge 1$ and $d \in \mathbb Z^+$, let $\mathcal F_{q,d}$ be the class of
functions $f: [0,1]^d \to \mathbb R$ such that any function $g: [0,1] \to
\mathbb R$ formed by fixing all but one parameter of $f$ is in $\mathcal F_q$.
For any class of real-valued functions $\mathcal F$ and $p>0$, let
$\text{opt}_p(\mathcal F)$ be the best upper bound on the sum of
$p^{\text{th}}$ powers of absolute prediction errors that a learner can
guarantee in the worst case. In the single-variable setup, we find new bounds
for $\text{opt}_p(\mathcal F_q)$ that are sharp up to a constant factor. We
show for all $\varepsilon \in (0, 1)$ that
$\text{opt}_{1+\varepsilon}(\mathcal{F}_{\infty}) =
\Theta(\varepsilon^{-\frac{1}{2}})$ and
$\text{opt}_{1+\varepsilon}(\mathcal{F}_q) =
\Theta(\varepsilon^{-\frac{1}{2}})$ for all $q \ge 2$. We also show for
$\varepsilon \in (0,1)$ that $\text{opt}_2(\mathcal
F_{1+\varepsilon})=\Theta(\varepsilon^{-1})$. In addition, we obtain new exact
results by proving that $\text{opt}_p(\mathcal F_q)=1$ for $q \in (1,2)$ and $p
\ge 2+\frac{1}{q-1}$. In the multi-variable setup, we establish inequalities
relating $\text{opt}_p(\mathcal F_{q,d})$ to $\text{opt}_p(\mathcal F_q)$ and
show that $\text{opt}_p(\mathcal F_{\infty,d})$ is infinite when $p<d$ and
finite when $p>d$. We also obtain sharp bounds on learning $\mathcal
F_{\infty,d}$ for $p < d$ when the number of trials is bounded.
- Abstract(参考訳): 本稿では,隠れ関数が一定の滑らか性を持つことが知られている実数値関数のオンライン学習について検討する。
具体的には、$q \ge 1$ に対して、$\mathcal f_q$ を絶対連続関数 $f: [0,1] \to \mathbb r$ のクラスとし、$\|f'\|_q \le 1$ とする。
q \ge 1$ と $d \in \mathbb z^+$ に対して、$\mathcal f_{q,d}$ を関数のクラスとする: [0,1]^d \to \mathbb r$ 任意の関数$g: [0,1] \to \mathbb r$ は、$f$ のパラメータの1つを除いて、$\mathcal f_q$ となる。
任意の実数値関数のクラス$\mathcal f$ と $p>0$ に対して、$\text{opt}_p(\mathcal f)$ を$p^{\text{th}}$ の合計の最高上限とし、最悪の場合学習者が保証できる絶対予測誤差のパワーを与える。
単変数のセットアップでは、$\text{opt}_p(\mathcal F_q)$ の新しい境界が定数係数までシャープになる。
すべての$\varepsilon \in (0, 1)$ that $\text{opt}_{1+\varepsilon}(\mathcal{F}_{\infty}) = \Theta(\varepsilon^{-\frac{1}{2}})$ and $\text{opt}_{1+\varepsilon}(\mathcal{F}_q) = \Theta(\varepsilon^{-\frac{1}{2}})$ for all $q \ge 2$を示す。
また、$\varepsilon \in (0,1)$ that $\text{opt}_2(\mathcal F_{1+\varepsilon})=\Theta(\varepsilon^{-1})$ を示す。
さらに、$\text{opt}_p(\mathcal F_q)=1$ for $q \in (1,2)$と$p \ge 2+\frac{1}{q-1}$を証明することによって、新しい正確な結果が得られる。
多変数設定では、$\text{opt}_p(\mathcal F_{q,d})$ to $\text{opt}_p(\mathcal F_q)$ に関する不等式を確立し、$\text{opt}_p(\mathcal F_{\infty,d})$ が$p<d$ で有限であれば $p>d$ が無限となることを示す。
また、試行回数が有界であれば、$\mathcal F_{\infty,d}$ for $p < d$ を学習する際の鋭い境界も得られる。
関連論文リスト
- PREM: Privately Answering Statistical Queries with Relative Error [91.98332694700046]
合成データを生成する新しいフレームワークである$mathsfPREM$(Private Relative Error Multiplicative weight update)を紹介します。
我々はアルゴリズムをほぼ一致する下界で補完する。
論文 参考訳(メタデータ) (2025-02-20T18:32:02Z) - Efficient Continual Finite-Sum Minimization [52.5238287567572]
連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。
我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。
また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
論文 参考訳(メタデータ) (2024-06-07T08:26:31Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳(メタデータ) (2023-06-02T18:55:27Z) - $L^p$ sampling numbers for the Fourier-analytic Barron space [0.0]
f(x) = int_mathbbRd F(xi), e2 pi i langle x, xi rungle, d xi quad text with quad int_mathbbRd |F(xi)| cdot (1 + |xi|)sigma, d xi infty。
$ (複数形 $s)
論文 参考訳(メタデータ) (2022-08-16T08:41:48Z) - On Outer Bi-Lipschitz Extensions of Linear Johnson-Lindenstrauss
Embeddings of Low-Dimensional Submanifolds of $\mathbb{R}^N$ [0.24366811507669117]
$mathcalM$ を $mathbbRN$ のコンパクト $d$-次元部分多様体とし、リーチ $tau$ とボリューム $V_mathcal M$ とする。
非線形関数 $f: mathbbRN rightarrow mathbbRmm が存在し、$m leq C left(d / epsilon2right) log left(fracsqrt[d]V_math が存在することを証明します。
論文 参考訳(メタデータ) (2022-06-07T15:10:46Z) - 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) - 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) - Linear Bandits on Uniformly Convex Sets [88.3673525964507]
線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。
2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
論文 参考訳(メタデータ) (2021-03-10T07:33:03Z) - Some convergent results for Backtracking Gradient Descent method on
Banach spaces [0.0]
bf Theorem.$X$をバナッハ空間とし、$f:Xrightarrow mathbbR$を$C2$関数とする。
$mathcalC$ を $f$ の臨界点の集合とする。
論文 参考訳(メタデータ) (2020-01-16T12:49:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。