論文の概要: Optimal Online Generalized Linear Regression with Stochastic Noise and
Its Application to Heteroscedastic Bandits
- arxiv url: http://arxiv.org/abs/2202.13603v2
- Date: Mon, 27 Mar 2023 17:52:52 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-29 03:51:55.477603
- Title: Optimal Online Generalized Linear Regression with Stochastic Noise and
Its Application to Heteroscedastic Bandits
- Title（参考訳）: 確率的雑音を伴う最適オンライン一般化線形回帰とそのヘテロシドスティックバンディットへの応用
- Authors: Heyang Zhao and Dongruo Zhou and Jiafan He and Quanquan Gu
- Abstract要約: 一般化線形モデルの設定におけるオンライン一般化線形回帰の問題について検討する。
ラベルノイズに対処するため、古典的追従正規化リーダ(FTRL)アルゴリズムを鋭く解析する。
本稿では,FTRLに基づくアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 88.6139446295537
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of online generalized linear regression in the
stochastic setting, where the label is generated from a generalized linear
model with possibly unbounded additive noise. We provide a sharp analysis of
the classical follow-the-regularized-leader (FTRL) algorithm to cope with the
label noise. More specifically, for $\sigma$-sub-Gaussian label noise, our
analysis provides a regret upper bound of $O(\sigma^2 d \log T) + o(\log T)$,
where $d$ is the dimension of the input vector, $T$ is the total number of
rounds. We also prove a $\Omega(\sigma^2d\log(T/d))$ lower bound for stochastic
online linear regression, which indicates that our upper bound is nearly
optimal. In addition, we extend our analysis to a more refined Bernstein noise
condition. As an application, we study generalized linear bandits with
heteroscedastic noise and propose an algorithm based on FTRL to achieve the
first variance-aware regret bound.
- Abstract（参考訳）: 確率的条件下でのオンライン一般化線形回帰の問題について検討し、そこでラベルは有界な加法雑音を持つ一般化線形モデルから生成される。
ラベルノイズに対処するため、古典的追従正規化リーダ(FTRL)アルゴリズムを鋭く解析する。
より具体的には、$\sigma$-sub-gaussian ラベルノイズに対して、我々の分析は、$o(\sigma^2 d \log t) + o(\log t)$ の後悔の上限を与え、ここで $d$ は入力ベクトルの次元であり、$t$ はラウンドの総数である。
また、確率的オンライン線形回帰に対して$\Omega(\sigma^2d\log(T/d))$ lower boundを証明し、上界がほぼ最適であることを示す。
さらに,より洗練されたベルンシュタイン雑音条件に解析を拡張した。
本研究では,ヘテロシデスティックノイズを持つ一般化線形バンディットを探索し,ftrlに基づくアルゴリズムを提案する。
関連論文リスト
- Improved Regret of Linear Ensemble Sampling [9.410437324336275]
アンサンブルサイズを$T$とすると、線形アンサンブルサンプリングは$tildemathcalO(d3/2sqrtT)$の頻繁な残差を達成できる。
我々の貢献は、アンサンブルサンプリングの理論的な基礎を前進させ、他のランダム化探索アルゴリズムの最もよく知られた境界と一致させた。
論文 参考訳（メタデータ） (2024-11-06T14:09:11Z) - High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noise [59.25598762373543]
重み付き雑音の存在下でのストリーミングデータにおける学習の精度保証について検討した。
解析的に、与えられた問題に対する設定の選択に$ta$を使うことができることを実証する。
論文 参考訳（メタデータ） (2023-10-28T18:53:41Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。
マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
論文 参考訳（メタデータ） (2021-12-23T18:47:50Z) - Towards Sample-Optimal Compressive Phase Retrieval with Sparse and
Generative Priors [59.33977545294148]
O(k log L)$サンプルは振幅に基づく経験損失関数を最小化する任意のベクトルに信号が近いことを保証するのに十分であることを示す。
この結果はスパース位相検索に適応し、基底信号が$s$-sparseおよび$n$-dimensionalである場合、$O(s log n)$サンプルは同様の保証に十分であることを示す。
論文 参考訳（メタデータ） (2021-06-29T12:49:54Z) - Max-Linear Regression by Convex Programming [5.366354612549172]
我々は、最大線形回帰問題の推定器として、アンカーレグレッション(AR)によって与えられるスケーラブルな凸プログラムを定式化し、解析する。
以上の結果から, 対数係数まで, 正確な回復スケールについて, 十分な数のノイズのない観測結果が得られた。
論文 参考訳（メタデータ） (2021-03-12T00:55:54Z) - Convergence Rates of Stochastic Gradient Descent under Infinite Noise
Variance [14.06947898164194]
ヘビーテールは様々なシナリオで勾配降下 (sgd) で現れる。
SGDの収束保証は、潜在的に無限のばらつきを持つ状態依存性および重尾ノイズ下で提供します。
その結果,SGDは無限に分散した重尾雑音下であっても,地球最適値に収束できることが示された。
論文 参考訳（メタデータ） (2021-02-20T13:45:11Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z) - Least Squares Regression with Markovian Data: Fundamental Limits and
Algorithms [69.45237691598774]
マルコフ連鎖からデータポイントが依存しサンプリングされる最小二乗線形回帰問題について検討する。
この問題を$tau_mathsfmix$という観点から、鋭い情報理論のミニマックス下限を確立する。
本稿では,経験的リプレイに基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-16T04:26:50Z) - Tight Nonparametric Convergence Rates for Stochastic Gradient Descent
under the Noiseless Linear Model [0.0]
このモデルに基づく最小二乗リスクに対する1パス, 固定段差勾配勾配の収束度を解析した。
特殊な場合として、ランダムなサンプリング点における値のノイズのない観測から単位区間上の実関数を推定するオンラインアルゴリズムを解析する。
論文 参考訳（メタデータ） (2020-06-15T08:25:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。