論文の概要: Unconstrained Online Learning with Unbounded Losses
- arxiv url: http://arxiv.org/abs/2306.04923v2
- Date: Fri, 14 Jul 2023 20:44:43 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-18 22:01:22.323654
- Title: Unconstrained Online Learning with Unbounded Losses
- Title（参考訳）: 制約のないオンライン学習
- Authors: Andrew Jacobsen, Ashok Cutkosky
- Abstract要約: 我々は、無制限のドメインと非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|$。
- 参考スコア（独自算出の注目度）: 45.801991005821804
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Algorithms for online learning typically require one or more boundedness
assumptions: that the domain is bounded, that the losses are Lipschitz, or
both. In this paper, we develop a new setting for online learning with
unbounded domains and non-Lipschitz losses. For this setting we provide an
algorithm which guarantees $R_{T}(u)\le \tilde
O(G\|u\|\sqrt{T}+L\|u\|^{2}\sqrt{T})$ regret on any problem where the
subgradients satisfy $\|g_{t}\|\le G+L\|w_{t}\|$, and show that this bound is
unimprovable without further assumptions. We leverage this algorithm to develop
new saddle-point optimization algorithms that converge in duality gap in
unbounded domains, even in the absence of meaningful curvature. Finally, we
provide the first algorithm achieving non-trivial dynamic regret in an
unbounded domain for non-Lipschitz losses, as well as a matching lower bound.
The regret of our dynamic regret algorithm automatically improves to a novel
$L^{*}$ bound when the losses are smooth.
- Abstract（参考訳）: オンライン学習のアルゴリズムは一般に、ドメインが境界付けられたり、損失がリプシッツかその両方かという1つ以上の境界性仮定を必要とする。
本稿では,非有界領域と非Lipschitz損失を伴うオンライン学習のための新しい環境を開発する。
この設定のために、$R_{T}(u)\le \tilde O(G\|u\|\sqrt{T}+L\|u\|^{2}\sqrt{T})を保証できるアルゴリズムを提供する。
このアルゴリズムを利用して、有意な曲率がない場合でも、非有界領域の双対性ギャップに収束する新たな鞍点最適化アルゴリズムを開発する。
最後に,非Lipschitz損失に対する非有界領域における非自明な動的後悔を達成するアルゴリズムと,一致した下界を与える。
動的後悔アルゴリズムの後悔は、損失が滑らかな場合に自動的に新しい$l^{*}$バウンドに改善されます。
関連論文リスト
- An Equivalence Between Static and Dynamic Regret Minimization [10.812831455376218]
線形損失に対して、動的後悔最小化は、拡張決定空間における静的後悔最小化と等価であることを示す。
R_T(u_1,dots,u_T)le tildeという形式の動的後悔を保証するアルゴリズムを提供する。
論文 参考訳（メタデータ） (2024-06-03T17:54:58Z) - Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed
Rewards [40.99322897009357]
トランケーションと平均中央値に基づく2つの新しいアルゴリズムを提案する。
我々のトラニケーションベースのアルゴリズムは、既存のトラニケーションベースのアプローチと区別して、オンライン学習をサポートする。
我々のアルゴリズムは,$epsilon=1$の既存アルゴリズムと比較して,対数係数による後悔境界を改善する。
論文 参考訳（メタデータ） (2023-10-28T13:01:10Z) - Near-Optimal Algorithms for Private Online Optimization in the
Realizable Regime [74.52487417350221]
オンライン学習の問題は,ゼロロスソリューションが存在する,実現可能な環境において考慮する。
そこで我々は,ほぼ最適の後悔境界を求める新たなDPアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-27T21:19:24Z) - Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。
本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T14:37:21Z) - Parameter-free Regret in High Probability with Heavy Tails [45.11667443216861]
非有界領域に対するオンライン凸最適化のための新しいアルゴリズムを提案する。
高確率のパラメータフリーな後悔は、潜在的に重み付き下次推定にのみアクセス可能である。
論文 参考訳（メタデータ） (2022-10-25T21:43:44Z) - Online Learning with Bounded Recall [11.046741824529107]
本研究では,繰り返しゲーム研究に人気がある「バウンド・リコール」環境において,オンライン学習の完全情報化の課題について検討する。
オンライン学習アルゴリズム $mathcalA$ が$M$-$textitbounded-recall$ であるとき、$t$ の出力が$M$以前の報酬の関数として記述できる。
論文 参考訳（メタデータ） (2022-05-28T20:52:52Z) - 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) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - 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) - Adaptive Online Learning with Varying Norms [45.11667443216861]
オンライン凸最適化アルゴリズムは、あるドメインで$w_t$を出力する。
この結果を用いて新しい「完全行列」型後悔境界を得る。
論文 参考訳（メタデータ） (2020-02-10T17:22:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。