論文の概要: Sparsity-Based Interpolation of External, Internal and Swap Regret

• arxiv url: http://arxiv.org/abs/2502.04543v1
• Date: Thu, 06 Feb 2025 22:47:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-10 14:58:21.005936
• Title: Sparsity-Based Interpolation of External, Internal and Swap Regret
• Title（参考訳）: 外部・内部・スワップレグレットの空間的補間
• Authors: Zhou Lu, Y. Jennifer Sun, Zhiyu Zhang,
• Abstract要約: 本稿では,$phi$-regret最小化によるパフォーマンス指標のコンパレータについて検討する。 本稿では,インスタンス適応型$phi$-regretバウンダリを実現する単一アルゴリズムを提案する。 従来の$phi$-regretの最小化から外部後悔の最小化への削減を前提に、我々は後者をさらにオンライン線形回帰に変換することを目的としている。
• 参考スコア（独自算出の注目度）: 4.753557469026313
• License:
• Abstract: Focusing on the expert problem in online learning, this paper studies the interpolation of several performance metrics via $\phi$-regret minimization, which measures the performance of an algorithm by its regret with respect to an arbitrary action modification rule $\phi$. With $d$ experts and $T\gg d$ rounds in total, we present a single algorithm achieving the instance-adaptive $\phi$-regret bound \begin{equation*} \tilde O\left(\min\left\{\sqrt{d-d^{\mathrm{unif}}_\phi+1},\sqrt{d-d^{\mathrm{self}}_\phi}\right\}\cdot\sqrt{T}\right), \end{equation*} where $d^{\mathrm{unif}}_\phi$ is the maximum amount of experts modified identically by $\phi$, and $d^{\mathrm{self}}_\phi$ is the amount of experts that $\phi$ trivially modifies to themselves. By recovering the optimal $O(\sqrt{T\log d})$ external regret bound when $d^{\mathrm{unif}}_\phi=d$, the standard $\tilde O(\sqrt{T})$ internal regret bound when $d^{\mathrm{self}}_\phi=d-1$ and the optimal $\tilde O(\sqrt{dT})$ swap regret bound in the worst case, we improve existing results in the intermediate regimes. In addition, the same algorithm achieves the optimal quantile regret bound, which corresponds to even easier settings of $\phi$ than the external regret. Building on the classical reduction from $\phi$-regret minimization to external regret minimization on stochastic matrices, our main idea is to further convert the latter to online linear regression using Haar-wavelet-inspired matrix features. Then, we apply a particular $L_1$-version of comparator-adaptive online learning algorithms to exploit the sparsity in this regression subroutine.
• Abstract（参考訳）: 本稿では,オンライン学習における専門的問題に着目し,任意の行動修正規則である$\phi$-regret最小化($\phi$-regret minimization)によるいくつかのパフォーマンス指標の補間について検討する。 合計$d$のエキスパートと$T\gg d$のラウンドで、インスタンス適応型$\phi$-regret bound \begin{equation*} \tilde O\left(\min\left\{\sqrt{d-d^{\mathrm{unif}}_\phi+1},\sqrt{d-d^{\mathrm{self}}_\phi}\right\cdot\sqrt{T}\right), \end{equation*} ここで$d^{\mathrm{unif}}_\phi$は、$\phi$と$d^{\mathrm{self}}_\phi$によって修正された専門家の最大値である。 最適な$O(\sqrt{T\log d})$external regret bound if $d^{\mathrm{unif}}_\phi=d$, the standard $\tilde O(\sqrt{T})$ internal regret bound when $d^{\mathrm{self}}_\phi=d-1$, and the optimal $\tilde O(\sqrt{dT})$ swap regret bound in the worst case, we improve existing results in the intermediate regimes。 さらに、同じアルゴリズムは、外部の後悔よりもより簡単な$\phi$の設定に対応する最適な量子的後悔境界を達成する。 古典的な$\phi$-regretの最小化から、確率行列上の外部後悔の最小化への最小化を基礎として、Haar-wavelet に着想を得た行列特徴を用いて、後者をオンライン線形回帰に変換することを目的としている。 次に、この回帰サブルーチンの空間性を利用するために、コンパレータ適応型オンライン学習アルゴリズムの特定の$L_1$-versionを適用する。

関連論文リスト

• Nearly Optimal Algorithms with Sublinear Computational Complexity for Online Kernel Regression [13.510889339096117]
  後悔と計算コストのトレードオフは、オンラインカーネル回帰の根本的な問題である。 AOGD-ALDとNONS-ALDの2つの新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-14T07:39:09Z)
• Logarithmic Regret from Sublinear Hints [76.87432703516942]
  自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。 また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
  論文  参考訳（メタデータ） (2021-11-09T16:50:18Z)
• Improved Regret Bounds for Online Submodular Maximization [10.089520556398575]
  我々は、各ステップ$tin[T]$において、固定凸からアクション$x_t$を選択し、コンパクトなドメインセット$mathcalK$を選択するオンライン最適化問題を考える。 ユーティリティ関数 $f_t(cdot)$ が明らかになり、アルゴリズムはペイオフ $f_t(x_t)$ を受け取る。
  論文  参考訳（メタデータ） (2021-06-15T02:05:35Z)
• Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933]
  本稿では、ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられた、コンテキスト線形帯域の次の変種について考察する。 我々は、真の点$w*$と分離オラクルが返す超平面の間の全距離を、低い「回帰」を持つ新しい切断平面アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-06-09T05:39:05Z)
• 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)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。 最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
  論文  参考訳（メタデータ） (2020-03-04T07:36:38Z)
• Adaptive Online Learning with Varying Norms [45.11667443216861]
  オンライン凸最適化アルゴリズムは、あるドメインで$w_t$を出力する。 この結果を用いて新しい「完全行列」型後悔境界を得る。
  論文  参考訳（メタデータ） (2020-02-10T17:22:08Z)

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

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