論文の概要: Minimax-Optimal Small-Loss Bounds for Online Linear Optimisation on $\ell_p$ Balls

• arxiv url: http://arxiv.org/abs/2610.36097v1
• Date: Mon, 26 Oct 2026 18:15:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-28 21:04:31.398606
• Title: Minimax-Optimal Small-Loss Bounds for Online Linear Optimisation on $\ell_p$ Balls
• Title（参考訳）: $\ell_p$ボール上でのオンライン線形最適化のための最小極小損失境界
• Abstract要約: Follow-the-regularized-leaderアルゴリズムは、損失シーケンス毎に、$T$や$_T$を知らずに、後悔する$O_pを達成する。 平均がゼロ座標を持たない i.d. 損失に対しては、期待される後悔の正確な$log T$係数を計算する。
• 参考スコア（独自算出の注目度）: 1.4975436239088316
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study full-information online linear optimisation on the unit $\ell_p$ ball in $\mathbb{R}^d$, for fixed $2\le p<\infty$ and losses of dual norm at most one. Let $Δ_T$ denote the cumulative loss of the best fixed action above each round's minimum. A follow-the-regularised-leader (FTRL) algorithm attains, on every loss sequence and without knowing $T$ or $Δ_T$, regret $O_p(1+\min\{Δ_T^{1-1/p},\, d^{1/2-1/p}\sqrt{Δ_T}\})$. Matching lower bounds show that this rate is minimax for each fixed $p$, and its constant $(2+o(1))p/\log p$ is optimal as $p\to\infty$ among guarantees uniform in $d$ and $T$. The algorithm uses a bounded radial regulariser and switches at most once to its quadratic augmentation. On some paths where follow-the-leader (FTL) has regret one, its regret grows with $T$. A switching extension keeps the sharp constant and also guarantees $\mathrm{Reg}_T\le 2\,\mathrm{Reg}_T^{\mathrm{FTL}}$. For i.i.d. losses whose mean has no zero coordinates, we compute the exact $\log T$ coefficient of the expected regret, which separates FTL's variance term from the bias of the regulariser.
• Abstract（参考訳）: 固定された2ドル p<\infty$ に対して$\ell_p$ ball in $\mathbb{R}^d$ の完全情報オンライン線形最適化と、最大 1 つの双対ノルムの損失について検討する。 Δ_T$ は各ラウンドの最小値を超える最良の固定作用の累積損失を表す。 追従規則化リーダ(FTRL)アルゴリズムは、損失シーケンス毎に、T$またはΔ_T$を知らずに、後悔$O_p(1+\min\{Δ_T^{1-1/p},\,d^{1/2-1/p}\sqrt{Δ_T}\})$を達成できる。 下限をマッチングすると、この値は固定された$p$に対してミニマックスであり、その定数$(2+o(1))p/\log p$は$d$と$T$の保証の中で$p\to\infty$として最適である。 このアルゴリズムは、有界ラジアル正規化器を使用し、最大1回はその2次拡大に切り替える。 フォロー・ザ・リーダー(FTL)が後悔しているいくつかの経路では、その後悔はT$で増大する。 スイッチング拡張はシャープ定数を保持し、$\mathrm{Reg}_T\le 2\,\mathrm{Reg}_T^{\mathrm{FTL}}$を保証します。 平均がゼロ座標を持たないd.d.損失に対して、期待される後悔の正確な$\log T$係数を計算し、FTLの分散項を正規化器のバイアスから分離する。

関連論文リスト

• Geometry-Dependent Bounds for Online Non-Monotone DR-Submodular Maximization [55.29259818039367]
  凸閉集合上の逆オンライン非負の非単調DR-部分モジュラ函数について検討する。 学習者は、目的を観察する前に各アクションを学習し、後から最高の固定アクションと競合する。 定数対物列は、最適に多くの1次クエリでオフラインの$(4/9-varepsilon)$近似を生成する。
  論文  参考訳（メタデータ） (2026-09-30T18:26:29Z)
• Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
  一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。 スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
  論文  参考訳（メタデータ） (2026-09-07T01:38:41Z)
• From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model [26.860985092865203]
  ランダム順序モデルにおいて、損失関数の多元集合が逆向きに選択されるが、一様ランダムな順序で表されるオンライン学習について検討する。 提案手法は,無作為順序モデルにおける小さめの後悔境界の確立において,スパーシフィケーションと関連する手法のパワーに光を当てるものである。
  論文  参考訳（メタデータ） (2026-02-10T06:46:01Z)
• Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and $(L_0, L_1)$-Smoothness [57.93371273485736]
  我々は、最近提案された$ell$-smoothness条件$|nabla2f(x)|| le ellleft(||nabla f(x)||right),$$$L$-smoothnessと$(L_0,L_1)$-smoothnessを一般化する関数を持つ凸最適化問題の一階法について検討する。
  論文  参考訳（メタデータ） (2025-08-09T08:28:06Z)
• High-Dimensional Calibration from Swap Regret [40.9736612423411]
  任意の凸集合 $mathcalP 部分集合 mathbbRd$ 上での多次元予測のオンライン校正について検討する。 我々は、$O(sqrtrho T)$$$T$ラウンド後の最悪の後悔を保証できるならば、$T = exp(logd/epsilon2) の後、$epsilon$-calibrated 予測を得ることができることを示した。
  論文  参考訳（メタデータ） (2025-05-27T17:31:47Z)
• Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound [25.50155563108198]
  ラウンド単位の複雑さが$T$に依存しない最初の対数-回帰法を提案する。 我々の方法は極めて単純であり、オンラインニュートンステップ(ONS)を適切なexp-concave損失関数に適用する。 また、$Omega(n)$ の下限を示し、$O(nln T)$ 境界が $O(ln T)$ 係数まで固であることを示す。
  論文  参考訳（メタデータ） (2025-01-24T09:19:15Z)
• 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)

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

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