論文の概要: Online Self-Concordant and Relatively Smooth Minimization, With
Applications to Online Portfolio Selection and Learning Quantum States
- arxiv url: http://arxiv.org/abs/2210.00997v1
- Date: Mon, 3 Oct 2022 15:07:19 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-04 14:40:42.843895
- Title: Online Self-Concordant and Relatively Smooth Minimization, With
Applications to Online Portfolio Selection and Learning Quantum States
- Title（参考訳）: オンライン自己調和・相対スムース最小化とオンラインポートフォリオ選択と学習量子状態への応用
- Authors: Chung-En Tsai and Hao-Chung Cheng and Yen-Huan Li
- Abstract要約: 損失関数が自己調和障壁であり、凸関数 $h$ に対して滑らかで、おそらくは非Lipschitz であるようなオンライン凸最適化問題を考える。
我々は、オンラインミラー降下の後悔を$h$で分析し、以下のことを統一的に証明する。
- 参考スコア（独自算出の注目度）: 10.758021887982782
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Consider an online convex optimization problem where the loss functions are
self-concordant barriers, smooth relative to a convex function $h$, and
possibly non-Lipschitz. We analyze the regret of online mirror descent with
$h$. Then, based on the result, we prove the following in a unified manner.
Denote by $T$ the time horizon and $d$ the parameter dimension. 1. For online
portfolio selection, the regret of $\widetilde{\text{EG}}$, a variant of
exponentiated gradient due to Helmbold et al., is $\tilde{O} ( T^{2/3} d^{1/3}
)$ when $T > 4 d / \log d$. This improves on the original $\tilde{O} ( T^{3/4}
d^{1/2} )$ regret bound for $\widetilde{\text{EG}}$. 2. For online portfolio
selection, the regret of online mirror descent with the logarithmic barrier is
$\tilde{O}(\sqrt{T d})$. The regret bound is the same as that of Soft-Bayes due
to Orseau et al. up to logarithmic terms. 3. For online learning quantum states
with the logarithmic loss, the regret of online mirror descent with the
log-determinant function is also $\tilde{O} ( \sqrt{T d} )$. Its per-iteration
time is shorter than all existing algorithms we know.
- Abstract（参考訳）: 損失関数が自己一致障壁であり、凸関数 $h$ に対して滑らかであり、おそらく非リプシッツであるオンライン凸最適化問題を考える。
我々はオンラインミラー降下の後悔を$h$で分析する。
そして、その結果に基づいて、以下のことを統一的に証明する。
t$ the time horizon と $d$ the parameter dimension で表す。
1. オンラインポートフォリオ選択において、helmboldらによる拡張勾配の変種である$\widetilde{\text{eg}}$の後悔は、$t > 4 d / \log d$であるなら$\tilde{o} (t^{2/3} d^{1/3})である。
これは元の$\tilde{o} ( t^{3/4} d^{1/2} )$ regret bound for $\widetilde{\text{eg}}$ で改善される。
2. オンラインポートフォリオ選択の場合,対数障壁によるオンラインミラー降下の後悔は$\tilde{O}(\sqrt{T d})$である。
後悔のバウンドは、orseau et al. から対数項まで、soft-bayes と同じである。
3.対数損失のあるオンライン学習量子状態の場合、対数決定関数によるオンラインミラー降下の後悔もまた$\tilde{O} ( \sqrt{T d} )$である。
その文単位の時間は、我々が知っているすべての既存のアルゴリズムよりも短い。
関連論文リスト
- Nearly Optimal Regret for Decentralized Online Convex Optimization [53.433398074919]
分散オンライン凸最適化(D-OCO)は,局所計算と通信のみを用いて,グローバルな損失関数の列を最小化することを目的としている。
我々は凸関数と強い凸関数の残差をそれぞれ低減できる新しいD-OCOアルゴリズムを開発した。
我々のアルゴリズムは、$T$、$n$、$rho$の点でほぼ最適です。
論文 参考訳（メタデータ） (2024-02-14T13:44:16Z) - Oracle-Efficient Hybrid Online Learning with Unknown Distribution [16.73555330791045]
有限VCクラスに対して$tildeO(Tfrac34)$,$tildeO(Tfracp+1p+2)$に対して$alpha$fat-shattering dimensionを持つクラスに対して$tildeO(Tfracp+1p+2)$という,計算効率のよいオンライン予測器が存在することを示す。
すると、結果が$K$変更で分布をシフトするシナリオにまで拡張され、$tildeO(Tfrac45Kfrac15)が返り咲く。
論文 参考訳（メタデータ） (2024-01-27T22:45:02Z) - 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) - Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。
我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。
技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
論文 参考訳（メタデータ） (2022-10-15T09:22:22Z) - Optimal Dynamic Regret in LQR Control [23.91519151164528]
我々は、LQR制御という2次的損失の連続を伴う非確率的制御の問題を考察する。
我々は、$tildeO(textmaxn1/3 MathcalTV(M_1:n)2/3, 1)$の最適動的(政治的)後悔を実現するオンラインアルゴリズムを提供する。
論文 参考訳（メタデータ） (2022-06-18T18:00:21Z) - Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。
経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
論文 参考訳（メタデータ） (2021-03-25T18:52:17Z) - 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) - $Q$-learning with Logarithmic Regret [60.24952657636464]
楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
論文 参考訳（メタデータ） (2020-06-16T13:01:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。