論文の概要: Corruption-Robust Lipschitz Contextual Search

• arxiv url: http://arxiv.org/abs/2307.13903v4
• Date: Thu, 1 Feb 2024 08:11:55 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-02 19:24:09.333692
• Title: Corruption-Robust Lipschitz Contextual Search
• Title（参考訳）: 破壊破壊リプシッツの文脈探索
• Authors: Shiliang Zuo
• Abstract要約: リプシッツ関数を劣化したバイナリ信号で学習する問題について研究する。 本研究は,新しいアルゴリズム手法であるエマフォノスティックチェックと,新しい解析手法を紹介する。
• 参考スコア（独自算出の注目度）: 2.296475290901356
• 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 $L$-Lipschitz function $f: [0,1]^d \rightarrow [0, L]$ that the adversary chooses. There is a total of $T$ rounds. In each round $t$, 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 is high or low. In a total of $C$ rounds, the signal may be corrupted, though the value of $C$ is \emph{unknown} to the learner. The learner's goal is to incur a small cumulative loss. This work introduces the new algorithmic technique \emph{agnostic checking} as well as new analysis techniques. I design algorithms which: for the symmetric loss, the learner achieves regret $L\cdot O(C\log T)$ with $d = 1$ and $L\cdot O_d(C\log T + T^{(d-1)/d})$ with $d > 1$; for the pricing loss, the learner achieves regret $L\cdot \widetilde{O} (T^{d/(d+1)} + C\cdot T^{1/(d+1)})$.
• Abstract（参考訳）: リプシッツ関数を劣化したバイナリ信号で学習する問題について研究する。 学習者は、相手が選択した$L$-Lipschitz関数 $f: [0,1]^d \rightarrow [0,L]$を学習しようとする。 合計で$T$のラウンドがある。 各ラウンド$t$において、相手は入力空間内のコンテキストベクトル$x_t$を選択し、学習者は真関数値$f(x_t)$に推測を行い、推測値が高いか低いかを示すバイナリ信号を受け取る。 合計$C$ラウンドでは、信号は破損する可能性があるが、学習者には$C$の値は \emph{unknown} である。 学習者の目標は、小さな累積損失を負うことである。 本研究は,新しいアルゴリズム手法であるemph{agnostic check}と新しい解析手法を紹介する。 対称損失に対して、学習者は、$d = 1$ で、$l\cdot o_d(c\log t + t^{(d-1)/d})$ で、$d > 1$ で、 学習者は、$l\cdot \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)

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

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