論文の概要: Unconstrained Dynamic Regret via Sparse Coding
- arxiv url: http://arxiv.org/abs/2301.13349v4
- Date: Fri, 11 Aug 2023 04:20:33 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-14 17:35:14.210592
- Title: Unconstrained Dynamic Regret via Sparse Coding
- Title（参考訳）: スパース符号化による無拘束動的後悔
- Authors: Zhiyu Zhang, Ashok Cutkosky, Ioannis Ch. Paschalidis
- Abstract要約: オンライン凸最適化(OCO)を2つの問題構造の結合の下で検討した。
本稿では, スパースコーディングフレームワークを用いて, 適応的再帰境界を新たに実現した。
- 参考スコア（独自算出の注目度）: 47.415099037249085
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Motivated by the challenge of nonstationarity in sequential decision making,
we study Online Convex Optimization (OCO) under the coupling of two problem
structures: the domain is unbounded, and the comparator sequence
$u_1,\ldots,u_T$ is arbitrarily time-varying. As no algorithm can guarantee low
regret simultaneously against all comparator sequences, handling this setting
requires moving from minimax optimality to comparator adaptivity. That is,
sensible regret bounds should depend on certain complexity measures of the
comparator relative to one's prior knowledge.
This paper achieves a new type of these adaptive regret bounds via a sparse
coding framework. The complexity of the comparator is measured by its energy
and its sparsity on a user-specified dictionary, which offers considerable
versatility. Equipped with a wavelet dictionary for example, our framework
improves the state-of-the-art bound (Jacobsen & Cutkosky, 2022) by adapting to
both ($i$) the magnitude of the comparator average $||\bar
u||=||\sum_{t=1}^Tu_t/T||$, rather than the maximum $\max_t||u_t||$; and ($ii$)
the comparator variability $\sum_{t=1}^T||u_t-\bar u||$, rather than the
uncentered sum $\sum_{t=1}^T||u_t||$. Furthermore, our analysis is simpler due
to decoupling function approximation from regret minimization.
- Abstract（参考訳）: 逐次的意思決定における非定常性の問題に動機づけられたオンライン凸最適化(oco)を,2つの問題構造の結合の下で検討した。
すべてのコンパレータシーケンスに対して同時に低い後悔を保証できないため、この設定を扱うにはミニマックス最適化からコンパレータ適応性に移行する必要がある。
すなわち、合理的な後悔の限界は、前者の知識に対するコンパレータのある種の複雑さの尺度に依存するべきである。
本稿では, スパースコーディングフレームワークを用いて, 適応的再帰境界を新たに実現した。
コンパレータの複雑さは、そのエネルギーとユーザが指定した辞書のスパーシティによって測定され、かなりの汎用性を提供する。
例えばウェーブレット辞書を具備した我々のフレームワークは、コンパレータの最大値である$||\bar u||=||\sum_{t=1}^Tu_t/T||$と$$\sum_{t=1}^T|u_t-\bar u|$に代えて、コンパレータの最大値である$||\bar u|||=1}^T|u_t|||$の両方に適応することで、最先端境界(Jacobsen & Cutkosky, 2022)を改善する。
さらに, 再帰最小化によるデカップリング関数近似により解析が簡単になる。
関連論文リスト
- Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - An Equivalence Between Static and Dynamic Regret Minimization [10.812831455376218]
線形損失に対して、動的後悔最小化は、拡張決定空間における静的後悔最小化と等価であることを示す。
R_T(u_1,dots,u_T)le tildeという形式の動的後悔を保証するアルゴリズムを提供する。
論文 参考訳（メタデータ） (2024-06-03T17:54:58Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Stochastic Distributed Optimization under Average Second-order
Similarity: Algorithms and Analysis [36.646876613637325]
マスタノードと$n-1$ローカルノードを含む有限サム分散最適化問題について検討する。
本稿では,SVRSとAccSVRSの2つの新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-04-15T08:18:47Z) - Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。
予測と高い確率で、新しい過剰なリスク境界を提供する。
我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
論文 参考訳（メタデータ） (2022-11-03T12:40:24Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - Submodular Maximization subject to a Knapsack Constraint: Combinatorial
Algorithms with Near-optimal Adaptive Complexity [13.416309759182635]
我々は、ほぼ最適の$O(log n)$適応複雑性を持つ非単調部分モジュラーアルゴリズムに対する最初の定数近似を得る。
我々のアルゴリズムは$tildeO(n2)$の値クエリを要求するが、代わりに$tildeO(n)$で実行するように修正できる。
これはまた、この問題に対して線形適応的な複雑性を持つ最初のアプローチであり、濃度制約や単調な目的の特別な場合であっても、最先端の手法に匹敵する。
論文 参考訳（メタデータ） (2021-02-16T18:15:51Z) - Escaping Saddle-Points Faster under Interpolation-like Conditions [19.9471360853892]
過度なパラメータ化の下では、いくつかの標準的な最適化アルゴリズムがサドルポイントを回避し、局所最小化器に収束する。
本稿では、PSGDアルゴリズムの1次オラクル複雑性について論じ、$epsilon$ localminimizerに到達した。
次に、Cubic-Regularized Newton (SCRN)アルゴリズムのアンダーライクな条件を分析し、局所最小化剤アンダーライクな条件に到達するためのオラクルの複雑さが$tildemathcalO (1/epsilon2.5)であることを示す。
論文 参考訳（メタデータ） (2020-09-28T02:15:18Z) - Practical and Parallelizable Algorithms for Non-Monotone Submodular
Maximization with Size Constraint [20.104148319012854]
サイズ制約に関して、必ずしも単調ではない部分モジュラ函数に対して存在および並列化可能である。
最適な適応性とほぼ最適な複雑性クエリを持つアルゴリズムによって達成される最適な近似係数を、0.193 - varepsilon$に改善する。
論文 参考訳（メタデータ） (2020-09-03T22:43:55Z) - Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
非定常環境におけるオンライン凸最適化について検討する。
パフォーマンス指標として動的後悔を選択します。
本研究では, 滑らかさを活かして, 動的後悔をさらに高めることが可能であることを示す。
論文 参考訳（メタデータ） (2020-07-07T14:10:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。