論文の概要: Corruption-Robust Lipschitz Contextual Search
- arxiv url: http://arxiv.org/abs/2307.13903v1
- Date: Wed, 26 Jul 2023 02:02:19 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-27 13:57:45.006277
- Title: Corruption-Robust Lipschitz Contextual Search
- Title（参考訳）: 破壊破壊リプシッツの文脈探索
- Authors: Shiliang Zuo
- Abstract要約: リプシッツ関数を劣化したバイナリ信号で学習する問題について研究する。
汚損防止アルゴリズムを設計するのに有用な,自然かつ強力なテクニックの正当性チェックを提示する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: I study the problem of learning a Lipschitz function with corrupted binary
signals. The learner tries to learn a Lipschitz function $f$ that the adversary
chooses. In each round, the adversary selects a context vector $x_t$ in the
input space, and the learner makes a guess to the true function value $f(x_t)$
and receives a binary signal indicating whether the guess was high or low. In a
total of $C$ rounds, the signal may be corrupted, though the value of $C$ is
unknown to the learner. The learner's goal is to incur a small cumulative loss.
I present a natural yet powerful technique sanity check, which proves useful in
designing corruption-robust algorithms. I design algorithms which (treating the
Lipschitz parameter $L$ as constant): for the symmetric loss, the learner
achieves regret $O(C\log T)$ with $d = 1$ and $O_d(C\log T + T^{(d-1)/d})$ with
$d > 1$; for the pricing loss the learner achieves regret $\widetilde{O}
(T^{d/(d+1)} + C\cdot T^{1/(d+1)})$.
- Abstract（参考訳）: リプシッツ関数を劣化したバイナリ信号で学習する問題について研究する。
学習者は、敵が選択するリプシッツ関数をf$で学習しようとする。
各ラウンドにおいて、敵は入力空間でコンテキストベクトル $x_t$ を選択し、学習者は真の関数値 $f(x_t)$ を推測し、その推測が高いか低いかを示すバイナリ信号を受信する。
合計$C$ラウンドでは、信号は破損する可能性があるが、学習者には$C$の値が不明である。
学習者の目標は、小さな累積損失を負うことである。
汚損防止アルゴリズムを設計するのに有用な,自然かつ強力なテクニックの正当性チェックを提示する。
i は、(リプシッツパラメータ $l$ を定数として扱う)アルゴリズムを設計する: 対称損失に対して、学習者は、$d = 1$ で、$o_d(c\log t + t^{(d-1)/d})$ で、$d > 1$ で、 学習者は$\widetilde{o} (t^{d/(d+1)} + c\cdot t^{1/(d+1)})$ で後悔する。
関連論文リスト
- Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise [9.378684220920562]
マスアートノイズの存在下でハーフスペースを学習するための、最も厳密な統計クエリ(SQ)の下界。
任意の $eta in [0,1/2]$ に対して、$eta$ よりも誤り分類誤差の少ない全ての SQ アルゴリズムは、スーパーポリノミカルな精度のクエリを必要とすることを示す。
論文 参考訳（メタデータ） (2022-01-24T17:33:19Z) - Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。
また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文 参考訳（メタデータ） (2021-11-09T16:50:18Z) - 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) - Memory-Sample Lower Bounds for Learning Parity with Noise [2.724141845301679]
ノイズ下でのパリティ学習においてよく研究されている問題に対して、任意の学習アルゴリズムは、$Omega(n2/varepsilon)$または指数的なサンプル数を必要とすることを示す。
我々の証明は[Raz'17,GRT'18]の引数をノイズケースに適応させることに基づいている。
論文 参考訳（メタデータ） (2021-07-05T23:34:39Z) - 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) - $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) - Learning and Testing Variable Partitions [13.575794982844222]
我々は $mathcalO(k n2)(delta + epsilon)$ が、任意の $epsilon > 0$ に対して $tildemathcalO(n2 mathrmpoly (1/epsilon)$ で学習可能であることを示す。
また、両面のテスタでさえ$k = 2$の場合に$Omega(n)$クエリが必要であることも示しています。
論文 参考訳（メタデータ） (2020-03-29T10:12:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。