論文の概要: Dynamic social learning under graph constraints
- arxiv url: http://arxiv.org/abs/2007.03983v3
- Date: Sat, 24 Jul 2021 18:27:15 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-12 13:54:48.852307
- Title: Dynamic social learning under graph constraints
- Title(参考訳): グラフ制約下における動的社会学習
- Authors: Konstantin Avrachenkov, Vivek S. Borkar, Sharayu Moharir, Suhail M.
Shah
- Abstract要約: マルコフ雑音の近似として記述できる経験過程は、あるランダムウォークと同じ確率則を持つことを示す。
この同値性を用いて、$alpha > 0$ の場合、結果は $alphauparrowinfty$ を緩やかにすることで、ある制限的な意味で最適値の周りに集中することを示す。
- 参考スコア(独自算出の注目度): 6.920276126310229
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We introduce a model of graph-constrained dynamic choice with reinforcement
modeled by positively $\alpha$-homogeneous rewards. We show that its empirical
process, which can be written as a stochastic approximation recursion with
Markov noise, has the same probability law as a certain vertex reinforced
random walk. We use this equivalence to show that for $\alpha > 0$, the
asymptotic outcome concentrates around the optimum in a certain limiting sense
when `annealed' by letting $\alpha\uparrow\infty$ slowly.
- Abstract(参考訳): 我々は,正に$\alpha$均質な報酬をモデルとしたグラフ拘束動的選択モデルを提案する。
マルコフ雑音による確率近似再帰法として記述できる経験的過程は、ある頂点強化ランダムウォークと同じ確率則を持つことを示す。
この等価性を用いて、$\alpha > 0$ の場合、漸近的な結果が$\alpha\uparrow\infty$ を緩やかにすることで 'アンネール' した場合の最適値を中心に集中することを示す。
関連論文リスト
- Provably Robust Temporal Difference Learning for Heavy-Tailed Rewards [27.209606183563853]
動的勾配クリッピング機構による時間差(TD)学習は,重み付き報酬分布に対して確実に堅牢化できることを確認した。
TD学習に基づくNACの頑健な変種が$tildemathcalO(varepsilon-frac1p)$サンプル複雑性を達成することを示す。
論文 参考訳(メタデータ) (2023-06-20T11:12:21Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳(メタデータ) (2022-12-19T14:48:54Z) - Exponential Concentration of Stochastic Approximation with Non-vanishing
Gradient [0.0]
近似アルゴリズムの振る舞いを分析し,各ステップで目標に向かって進行する。
非消滅マルコフを持つ射影勾配 Descent に対して、我々の結果は$O(t)$および線形収束率を証明するのに使うことができる。
論文 参考訳(メタデータ) (2022-08-15T14:57:26Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳(メタデータ) (2022-06-17T06:10:20Z) - High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad
Stepsize [55.0090961425708]
本研究では,AdaGradのスムーズな非確率問題に対する簡易な高確率解析法を提案する。
我々はモジュラーな方法で解析を行い、決定論的設定において相補的な$mathcal O (1 / TT)$収束率を得る。
我々の知る限りでは、これは真に適応的なスキームを持つAdaGradにとって初めての高い確率である。
論文 参考訳(メタデータ) (2022-04-06T13:50:33Z) - Optimal and instance-dependent guarantees for Markovian linear
stochastic approximation [77.84027086542827]
標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。
マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
論文 参考訳(メタデータ) (2021-12-23T18:47:50Z) - Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov
Random Fields [51.07460861448716]
本稿では,データから学ぶための凸解析フレームワークを提案する。
三角凸分解はその上部に対応する変換によって保証されることを示す。
論文 参考訳(メタデータ) (2021-09-17T17:46:12Z) - ROOT-SGD: Sharp Nonasymptotics and Asymptotic Efficiency in a Single
Algorithm [77.71051081132912]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
emphRecursive One-Over-T Root (ROOTSGD) と呼ばれる小説を考案する。
有限サンプル勾配, 漸近感覚, 感覚を同時に達成することを証明する。
論文 参考訳(メタデータ) (2020-08-28T14:46:56Z) - Fairness constraints can help exact inference in structured prediction [37.76221231305701]
直交連結グラフ$G$と2進ラベルの真のベクトルを持つ生成モデルについて検討する。
フェアネスとモデル性能の間の既知のトレードオフとは対照的に、フェアネス制約の追加は正確なリカバリの確率を向上させる。
論文 参考訳(メタデータ) (2020-07-01T04:11:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。