論文の概要: On the necessity of adaptive regularisation:Optimal anytime online learning on $\boldsymbol{\ell_p}$-balls
- arxiv url: http://arxiv.org/abs/2506.19752v1
- Date: Tue, 24 Jun 2025 16:06:56 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-25 19:48:23.715175
- Title: On the necessity of adaptive regularisation:Optimal anytime online learning on $\boldsymbol{\ell_p}$-balls
- Title（参考訳）: 適応正則化の必要性について:$\boldsymbol{\ell_p}$-ballsにおける最適オンライン学習
- Authors: Emmeran Johnson, David Martínez-Rubio, Ciara Pike-Burke, Patrick Rebeschini,
- Abstract要約: オンライン凸最適化を$ell_p$-balls in $mathbbRd$ for $p > 2$で検討する。
常にサブ線形であるが、最適の後悔は、高次元の設定($d > T$)と低次元の設定($d leq T$)のシフトを示す。
- 参考スコア（独自算出の注目度）: 17.599348264171862
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study online convex optimization on $\ell_p$-balls in $\mathbb{R}^d$ for $p > 2$. While always sub-linear, the optimal regret exhibits a shift between the high-dimensional setting ($d > T$), when the dimension $d$ is greater than the time horizon $T$ and the low-dimensional setting ($d \leq T$). We show that Follow-the-Regularised-Leader (FTRL) with time-varying regularisation which is adaptive to the dimension regime is anytime optimal for all dimension regimes. Motivated by this, we ask whether it is possible to obtain anytime optimality of FTRL with fixed non-adaptive regularisation. Our main result establishes that for separable regularisers, adaptivity in the regulariser is necessary, and that any fixed regulariser will be sub-optimal in one of the two dimension regimes. Finally, we provide lower bounds which rule out sub-linear regret bounds for the linear bandit problem in sufficiently high-dimension for all $\ell_p$-balls with $p \geq 1$.
- Abstract（参考訳）: オンライン凸最適化を$\ell_p$-balls in $\mathbb{R}^d$ for $p > 2$で検討する。
常に部分線型であるが、最適の後悔は高次元の設定($d > T$)と、次元$d$が時間地平線($T$)と低次元の設定($d \leq T$)の間のシフトを示す。
次元レギュラーに適応する時間変化正則化を持つFTRL(Follow-the-Regularized-Leader)が,すべての次元レギュラーに対して常に最適であることを示す。
これにより、固定された非適応正規化を伴うFTRLの任意の最適性が得られるかどうかを問う。
我々の主な結果は、分離可能な正則器の場合、正則器の適応性は必要であり、固定正則器は2次元状態のうちの1つで準最適となることを証明している。
最後に、すべての$\ell_p$-balls with $p \geq 1$に対して、線形バンディット問題に対する部分線型後悔境界を十分に高次元で除外する下界を与える。
関連論文リスト
- Minimax Adaptive Online Nonparametric Regression over Besov Spaces [10.138723409205497]
我々は,連続的かつ極めて不規則な予測規則の豊富なクラスに対して,凸損失を伴うオンライン逆回帰について検討した。
本稿では,$(s,p,q)$の事前知識を必要とせずに逐次予測を行う適応ウェーブレットベースのアルゴリズムを提案する。
また、空間的不均一な滑らかさを動的に追跡できる局所適応拡張を設計する。
論文 参考訳（メタデータ） (2025-05-26T09:23:11Z) - No-Regret Linear Bandits under Gap-Adjusted Misspecification [38.592043705502725]
既存の線形包帯の作用は通常、最良の線形近似のsup-norm誤差を測定する一様不特定パラメータ$epsilon$に依存する。
そこで本研究では,各入力における近似誤差をx$で近似し,その差分をx$で比例する,より自然な不特定モデルを提案する。
我々は,従来のLinUCBアルゴリズムが,そのような$rho$-gap-adjusted misspecificationに対して自動的に堅牢であることを示す。
論文 参考訳（メタデータ） (2025-01-09T16:44:53Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Improved Dynamic Regret for Online Frank-Wolfe [54.690867216880356]
オンライン凸最適化のための効率的なプロジェクションフリーアルゴリズムであるFrank-Wolfe (OFW) の動的後悔について検討する。
本稿では,FWの高速収束率をオフライン最適化からオンライン最適化に拡張することにより,OFWの動的後悔境界の改善を導出する。
論文 参考訳（メタデータ） (2023-02-11T07:19:51Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Private Convex Optimization in General Norms [23.166642097170545]
任意のノルム$normxcdot$におけるリプシッツである凸関数の微分プライベート最適化のための新しいフレームワークを提案する。
本稿では,このメカニズムが差分プライバシーを満足し,DP-ERM(経験的リスク最小化)とDP-SCO(確率的凸最適化)の両方を解決することを示す。
我々のフレームワークは、一般ノルム空間におけるプライベート凸最適化に初めて適用され、ミラー降下によって達成された非プライベートSCOレートを直接回復する。
論文 参考訳（メタデータ） (2022-07-18T02:02:22Z) - A Unified Analysis Method for Online Optimization in Normed Vector Space [3.615256443481602]
正規化されたベクトル空間におけるオンライン最適化のための一般化されたコサイン則に依存する統一解析法を提案する。
オンラインゲームにおける損失をモノトーン演算子に置き換えることで,オンラインコンベックスをオンラインモノトーン最適化に拡張する。
論文 参考訳（メタデータ） (2021-12-22T18:48:19Z) - Non-Euclidean Differentially Private Stochastic Convex Optimization [15.302167005107135]
雑音勾配降下法(SGD)アルゴリズムは低次元状態において最適過大なリスクを達成できることを示す。
私たちの作品は、規則性、均一凸性、均一な平滑性の概念など、規範空間の幾何学から概念を導き出します。
論文 参考訳（メタデータ） (2021-03-01T19:48:44Z) - Naive Exploration is Optimal for Online LQR [49.681825576239355]
最適後悔尺度は$widetildeTheta(sqrtd_mathbfu2 d_mathbfx T)$で、$T$は時間ステップの数、$d_mathbfu$は入力空間の次元、$d_mathbfx$はシステム状態の次元である。
我々の下界は、かつての$mathrmpoly(logT)$-regretアルゴリズムの可能性を排除する。
論文 参考訳（メタデータ） (2020-01-27T03:44:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。