論文の概要: Parameter-free Regret in High Probability with Heavy Tails
- arxiv url: http://arxiv.org/abs/2210.14355v1
- Date: Tue, 25 Oct 2022 21:43:44 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-27 13:18:57.801516
- Title: Parameter-free Regret in High Probability with Heavy Tails
- Title（参考訳）: 重い尾を持つ確率の高いパラメータフリー後悔
- Authors: Jiujia Zhang, Ashok Cutkosky
- Abstract要約: 非有界領域に対するオンライン凸最適化のための新しいアルゴリズムを提案する。
高確率のパラメータフリーな後悔は、潜在的に重み付き下次推定にのみアクセス可能である。
- 参考スコア（独自算出の注目度）: 45.11667443216861
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present new algorithms for online convex optimization over unbounded
domains that obtain parameter-free regret in high-probability given access only
to potentially heavy-tailed subgradient estimates. Previous work in unbounded
domains considers only in-expectation results for sub-exponential subgradients.
Unlike in the bounded domain case, we cannot rely on straight-forward
martingale concentration due to exponentially large iterates produced by the
algorithm. We develop new regularization techniques to overcome these problems.
Overall, with probability at most $\delta$, for all comparators $\mathbf{u}$
our algorithm achieves regret $\tilde{O}(\| \mathbf{u} \| T^{1/\mathfrak{p}}
\log (1/\delta))$ for subgradients with bounded $\mathfrak{p}^{th}$ moments for
some $\mathfrak{p} \in (1, 2]$.
- Abstract（参考訳）: 我々は,高確率でパラメータフリーな後悔を得られる非有界領域に対するオンライン凸最適化のための新しいアルゴリズムを提案する。
非有界領域での以前の研究は、部分指数準次数に対する予測内結果のみを考慮に入れている。
有界領域の場合とは異なり、アルゴリズムが生成する指数関数的に大きいイテレートのため、直進マーチンゲール濃度には依存できない。
これらの問題を克服する新たな正規化手法を開発した。
全体として、最大$\delta$ の確率で、すべての比較子に対して$\mathbf{u}$ のアルゴリズムは、いくつかの$\mathfrak{p} \in (1, 2]$ に対して有界な$\mathfrak{p}^{th}$ moments を持つ部分次数に対して$\tilde{o}(\| \mathbf{u} \| t^{1/\mathfrak{p}} \log (1/\delta))$ を満たす。
関連論文リスト
- High Probability Guarantees for Random Reshuffling [5.663909018247509]
非行列最適化問題に対処するために、ランダムリシャッフル(mathsfRR$)の勾配法を検討する。
本研究ではまず,$mathsfRR$sサンプリング手順におけるニューラルネットワークの複雑さについて検討する。
そこで我々は,乱数化摂動手順の定常点を含むランダムリシャッフル法(mathsfp$mathsfRR$)を設計する。
論文 参考訳（メタデータ） (2023-11-20T15:17:20Z) - Private Isotonic Regression [54.32252900997422]
部分順序集合 (poset) $mathcalX$ と任意のリプシッツ損失関数に対する等調回帰の問題を考察する。
約$mathrmwidth(mathcalX) cdot log|mathcalX| / n$, ここで$mathrmwidth(mathcalX)$はポーズの幅である。
上記の境界は本質的に最良であることを示す。
論文 参考訳（メタデータ） (2022-10-27T05:08:07Z) - Frank Wolfe Meets Metric Entropy [0.0]
フランク=ウルフの領域固有かつ容易に推定できる下界を確立する手法を提案する。
次元自由線型上界は、最悪の場合だけでなく、Emph平均の場合も失敗しなければならないことを示す。
また、核標準球にもこの現象が成立する。
論文 参考訳（メタデータ） (2022-05-17T21:23:36Z) - Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual Bandits [45.43968161616453]
バッチ線形文脈帯域に対する最適バッチ-regretトレードオフについて検討する。
時間的地平線が成長するにつれて2相表現を特徴とする後悔の保証を証明します。
また, 動的上界に依存した新しい行列不等式濃度を証明した。
論文 参考訳（メタデータ） (2021-10-15T12:32:33Z) - Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。
O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。
さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
論文 参考訳（メタデータ） (2021-10-15T00:54:04Z) - Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。
本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。
次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-10T13:07: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) - On the Last Iterate Convergence of Momentum Methods [32.60494006038902]
我々は、任意の一定の運動量係数に対して、最後の反復が誤差に苦しむリプシッツおよび凸函数が存在することを初めて証明する。
凸関数と滑らかな関数の設定では、新しいSGDMアルゴリズムが自動的に$O(fraclog TT)$のレートで収束することを示しています。
論文 参考訳（メタデータ） (2021-02-13T21:16:16Z) - On Convergence of Gradient Expected Sarsa($\lambda$) [25.983112169543375]
オフライン推定(マルチステップブートストラップ)を$mathttexpectedsarsa(lambda)$に適用することはオフポリシ学習において不安定であることを示す。
収束する$mathttgradientexpectedsarsa(lambda)$ ($mathttges(lambda)$)アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-12-14T01:27:24Z) - Thresholded Lasso Bandit [70.17389393497125]
Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。
一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
論文 参考訳（メタデータ） (2020-10-22T19:14:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。