Fugu-MT 論文翻訳(概要): Learning low-degree functions from a logarithmic number of random queries

論文の概要: Learning low-degree functions from a logarithmic number of random queries

arxiv url: http://arxiv.org/abs/2109.10162v1
Date: Tue, 21 Sep 2021 13:19:04 GMT
ステータス: 処理完了
システム内更新日: 2021-09-22 18:21:39.336233
Title: Learning low-degree functions from a logarithmic number of random queries
Title（参考訳）: ランダムクエリの対数から低次関数を学習する
Authors: Alexandros Eskenazis and Paata Ivanisvili
Abstract要約: 任意の整数 $ninmathbbN$, $din1,ldots,n$ および任意の $varepsilon,deltain(0,1)$ に対して、有界関数 $f:-1,1nto[-1,1]$ に対して、少なくとも$d$ の次数を学ぶことができる。
参考スコア（独自算出の注目度）: 77.34726150561087
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We prove that for any integer $n\in\mathbb{N}$, $d\in\{1,\ldots,n\}$ and any $\varepsilon,\delta\in(0,1)$, a bounded function $f:\{-1,1\}^n\to[-1,1]$ of degree at most $d$ can be learned with probability at least $1-\delta$ and $L_2$-error $\varepsilon$ using $\log(\tfrac{n}{\delta})\,\varepsilon^{-d-1} C^{d^{3/2}\sqrt{\log d}}$ random queries for a universal finite constant $C>1$.
Abstract（参考訳）: 任意の整数 $n\in\mathbb{N}$, $d\in\{1,\ldots,n\}$ および任意の $\varepsilon,\delta\in(0,1)$, a bounded function $f:\{-1,1\}^n\to[-1,1]$ に対して、少なくとも 1-\delta$ と $L_2$-error $\varepsilon$ を $\log(\tfrac{n}{\delta})\,\varepsilon^{-d-1} C^{d^{3/2}\sqrt{\log d}} を用いて学習できることを証明する。

関連論文リスト

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)
Sharp Noisy Binary Search with Monotonic Probabilities [5.563988395126509]
我々はKarpとKleinbergのノイズの多いバイナリ検索モデルを再検討する。我々は[ frac1C_tau, varepsilon cdot left(lg n + O(log2/3 n log 1/3 frac1delta + log frac1delta)右から1-delta$の確率で成功するアルゴリズムを作成する。
論文参考訳（メタデータ） (2023-11-01T20:45:13Z)
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)
Coresets for Data Discretization and Sine Wave Fitting [39.18104905459739]
N]:=1,cdots,N$の整数列は、センサから受信される。目標は、これまでに受け取った$n$ポイントを1つの周波数で近似することである。経験的集合 $P$ of $n$ が加重部分集合 $Ssubseteq P$ を持つことを証明している。
論文参考訳（メタデータ） (2022-03-06T17:07:56Z)
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)
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)
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)
On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文参考訳（メタデータ） (2020-02-09T03:39:46Z)

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