論文の概要: Unconstrained Online Optimization: Dynamic Regret Analysis of Strongly Convex and Smooth Problems

• arxiv url: http://arxiv.org/abs/2006.03912v2
• Date: Fri, 14 Aug 2020 17:28:53 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-24 21:33:40.910786
• Title: Unconstrained Online Optimization: Dynamic Regret Analysis of Strongly Convex and Smooth Problems
• Title（参考訳）: 制約のないオンライン最適化:強凸・平滑問題の動的回帰解析
• Authors: Ting-Jui Chang, Shahin Shahrampour
• Abstract要約: 本稿では,関数列の第1次および第2次情報が予測可能である場合に,楽観的なニュートン法を提案する。 OGD に対して多重勾配を用いることで、後悔の時に$O(minC*_2,T,V_T) の上限を達成できる。
• 参考スコア（独自算出の注目度）: 14.924672048447334
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The regret bound of dynamic online learning algorithms is often expressed in terms of the variation in the function sequence ($V_T$) and/or the path-length of the minimizer sequence after $T$ rounds. For strongly convex and smooth functions, , Zhang et al. establish the squared path-length of the minimizer sequence ($C^*_{2,T}$) as a lower bound on regret. They also show that online gradient descent (OGD) achieves this lower bound using multiple gradient queries per round. In this paper, we focus on unconstrained online optimization. We first show that a preconditioned variant of OGD achieves $O(C^*_{2,T})$ with one gradient query per round. We then propose online optimistic Newton (OON) method for the case when the first and second order information of the function sequence is predictable. The regret bound of OON is captured via the quartic path-length of the minimizer sequence ($C^*_{4,T}$), which can be much smaller than $C^*_{2,T}$. We finally show that by using multiple gradients for OGD, we can achieve an upper bound of $O(\min\{C^*_{2,T},V_T\})$ on regret.
• Abstract（参考訳）: 動的オンライン学習アルゴリズムの後悔境界は、関数列(V_T$)および/または$T$ラウンド後の最小値列のパス長の変化によって表されることが多い。 強い凸と滑らかな函数に対して、Zhangらは最小化列(C^*_{2,T}$)の平方経路長を後悔の低い境界として定めている。 彼らはまた、オンライン勾配降下(ogd)がラウンド毎に複数の勾配クエリを使用してこの下限を達成することも示している。 本稿では,制約のないオンライン最適化に注目する。 まず,プリコンディショニングしたogdが1ラウンドあたり1つの勾配クエリで$o(c^*_{2,t})$を達成することを示す。 次に,関数列の第1次および第2次情報が予測可能である場合に,オンライン楽観的ニュートン法を提案する。 OONの後悔境界は、最小化シーケンス(C^*_{4,T}$)のクォートパス長(C^*_{2,T}$)を介して取得され、これは$C^*_{2,T}$よりもはるかに小さい。 最終的に、OGD に対して多重勾配を用いることで、後悔して$O(\min\{C^*_{2,T},V_T\}) の上限が得られることを示す。

関連論文リスト

• Non-stationary Online Convex Optimization with Arbitrary Delays [50.46856739179311]
  本稿では,非定常環境における遅延オンライン凸最適化(OCO)について検討する。 まず, 遅延勾配の勾配降下ステップを, 到着順に応じて行う単純なアルゴリズム, DOGDを提案する。 DOGDが達成した動的後悔境界を$O(sqrtbardT(P_T+1))$に削減する改良アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-05-20T07:54:07Z)
• Non-stationary Projection-free Online Learning with Dynamic and Adaptive Regret Guarantees [36.746745619968024]
  本研究では,非定常プロジェクションフリーオンライン学習について検討し,動的後悔と適応的後悔を選択して評価を行った。 我々の結果は、プロジェクションフリーオンライン学習における最初の一般的な動的後悔境界であり、既存の$mathcalO(T3/4)$static regretを復元することができる。 本稿では,$tildemathcalO(tau3/4)$ アダプティブリフレッシュバウンドを長さ$tauの任意の間隔で達成するためのプロジェクションフリーな手法を提案する。
  論文  参考訳（メタデータ） (2023-05-19T15:02:10Z)
• Improved Dynamic Regret for Online Frank-Wolfe [54.690867216880356]
  オンライン凸最適化のための効率的なプロジェクションフリーアルゴリズムであるFrank-Wolfe (OFW) の動的後悔について検討する。 本稿では,FWの高速収束率をオフライン最適化からオンライン最適化に拡張することにより,OFWの動的後悔境界の改善を導出する。
  論文  参考訳（メタデータ） (2023-02-11T07:19:51Z)
• A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
  凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。 主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
  論文  参考訳（メタデータ） (2021-10-28T14:19:30Z)
• Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximation [29.549633678730054]
  線形関数近似を用いたエピソディック最短経路問題に対する2つのアルゴリズムを提案する。 1つは計算コストが高いが、$tildeo (sqrtb_star3 d3 k/cmin )$ regret が得られる。 2つ目は実際は計算的に効率的であり、同じ後悔境界が得られると推測する。
  論文  参考訳（メタデータ） (2021-05-04T16:05:08Z)
• 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)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。