論文の概要: Unconstrained Robust Online Convex Optimization
- arxiv url: http://arxiv.org/abs/2506.12781v1
- Date: Sun, 15 Jun 2025 09:21:15 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-17 17:28:46.816672
- Title: Unconstrained Robust Online Convex Optimization
- Title（参考訳）: 制約のないロバストオンライン凸最適化
- Authors: Jiujia Zhang, Ashok Cutkosky,
- Abstract要約: 私たちは、アルゴリズムが低い後悔を保たなければならないという困難な「制約のない」設定に焦点を合わせます。
我々のアルゴリズムは、$G ge max_t |g_t|$ が知られているときに |u|G (sqrtT + k) $ を許す。
- 参考スコア（独自算出の注目度）: 38.9652176513385
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper addresses online learning with ``corrupted'' feedback. Our learner is provided with potentially corrupted gradients $\tilde g_t$ instead of the ``true'' gradients $g_t$. We make no assumptions about how the corruptions arise: they could be the result of outliers, mislabeled data, or even malicious interference. We focus on the difficult ``unconstrained'' setting in which our algorithm must maintain low regret with respect to any comparison point $u \in \mathbb{R}^d$. The unconstrained setting is significantly more challenging as existing algorithms suffer extremely high regret even with very tiny amounts of corruption (which is not true in the case of a bounded domain). Our algorithms guarantee regret $ \|u\|G (\sqrt{T} + k) $ when $G \ge \max_t \|g_t\|$ is known, where $k$ is a measure of the total amount of corruption. When $G$ is unknown we incur an extra additive penalty of $(\|u\|^2+G^2) k$.
- Abstract（参考訳）: 本稿では,「腐敗した」フィードバックによるオンライン学習について述べる。
我々の学習者は ``true'' の勾配に代えて $\tilde g_t$ という潜在的に破損した勾配が提供される。
汚職の発生について仮定することはありません。それらは、外れ値や不正なラベル付きデータ、さらには悪意のある干渉の結果であるかも知れません。
アルゴリズムは、任意の比較点 $u \in \mathbb{R}^d$ に対して、低い後悔を保たなければならない。
制約のない設定は、非常に少量の汚職(有界領域ではそうではない)であっても、既存のアルゴリズムが非常に後悔しているため、はるかに困難である。
我々のアルゴリズムは、後悔の$ \|u\|G (\sqrt{T} + k) $ if $G \ge \max_t \|g_t\|$ が知られているとき、$k$ は、腐敗の総量の測度である。
G$が未知であれば、$(\|u\|^2+G^2) k$の付加的なペナルティが生じる。
関連論文リスト
- Unconstrained Online Learning with Unbounded Losses [45.801991005821804]
我々は、無制限のドメインと非Lipschitz損失を伴うオンライン学習のための新しい設定を開発する。
R_T(u)le tilde O(G|u|sqrtT+L|u|2sqrtT)$ regret on any problem, the subgradients satisfy $|g_t|le G+L|w_t|$。
論文 参考訳（メタデータ） (2023-06-08T03:55:33Z) - Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial
Corruptions [98.75618795470524]
本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。
我々は不確実性に直面した楽観主義の原理に基づく新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-05-13T17:58:58Z) - Corralling a Larger Band of Bandits: A Case Study on Switching Regret
for Linear Bandits [99.86860277006318]
本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。
Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。
この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
論文 参考訳（メタデータ） (2022-02-12T21:55:44Z) - 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) - Corruption Robust Active Learning [43.279169081740726]
我々は、未知の逆ラベル汚職下でのバイナリ分類のためのストリーミングに基づくアクティブラーニングに関する理論的研究を行う。
本稿では, 従来のロバストCALフレームワークは, 破損しない場合と同様のラベル複雑性を保証できることを示す。
本稿では, 汚職の有無を仮定することなく, 確実に正しい新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-06-21T16:06:38Z) - 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) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。