論文の概要: From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model

• arxiv url: http://arxiv.org/abs/2602.09457v1
• Date: Tue, 10 Feb 2026 06:46:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-11 20:17:43.413393
• Title: From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model
• Title（参考訳）: ランダム次数モデルによる平均感度から小損失レグレト境界へ
• Authors: Shinsaku Sakaue, Yuichi Yoshida,
• Abstract要約: ランダム順序モデルにおいて、損失関数の多元集合が逆向きに選択されるが、一様ランダムな順序で表されるオンライン学習について検討する。 提案手法は,無作為順序モデルにおける小さめの後悔境界の確立において,スパーシフィケーションと関連する手法のパワーに光を当てるものである。
• 参考スコア（独自算出の注目度）: 26.860985092865203
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study online learning in the random-order model, where the multiset of loss functions is chosen adversarially but revealed in a uniformly random order. Building on the batch-to-online conversion by Dong and Yoshida (2023), we show that if an offline algorithm admits a $(1+\varepsilon)$-approximation guarantee and the effect of $\varepsilon$ on its average sensitivity is characterized by a function $\varphi(\varepsilon)$, then an adaptive choice of $\varepsilon$ yields a small-loss regret bound of $\tilde O(\varphi^{\star}(\mathrm{OPT}_T))$, where $\varphi^{\star}$ is the concave conjugate of $\varphi$, $\mathrm{OPT}_T$ is the offline optimum over $T$ rounds, and $\tilde O$ hides polylogarithmic factors in $T$. Our method requires no regularity assumptions on loss functions, such as smoothness, and can be viewed as a generalization of the AdaGrad-style tuning applied to the approximation parameter $\varepsilon$. Our result recovers and strengthens the $(1+\varepsilon)$-approximate regret bounds of Dong and Yoshida (2023) and yields small-loss regret bounds for online $k$-means clustering, low-rank approximation, and regression. We further apply our framework to online submodular function minimization using $(1\pm\varepsilon)$-cut sparsifiers of submodular hypergraphs, obtaining a small-loss regret bound of $\tilde O(n^{3/4}(1 + \mathrm{OPT}_T^{3/4}))$, where $n$ is the ground-set size. Our approach sheds light on the power of sparsification and related techniques in establishing small-loss regret bounds in the random-order model.
• Abstract（参考訳）: ランダム順序モデルにおいて、損失関数の多元集合が逆向きに選択されるが、一様ランダムな順序で表されるオンライン学習について検討する。 Dong and Yoshida (2023) によるバッチ・ツー・オンライン変換に基づいて、オフラインアルゴリズムが$(1+\varepsilon)$-approximationの保証と、その平均感度に対する$\varepsilon$の効果を特徴付ける関数 $\varphi(\varepsilon)$ とすると、$\varepsilon$ の適応選択は $\tilde O(\mathrm{OPT}_T)$ の小さな余剰なリフレッシュバウンドを$\tilde O(\mathrm{OPT}_T)$ とすることで、$\varphi^{\star}$ は $\varphi$, $\mathrm{OPT}_T)$ の共役である。 この方法では、滑らかさなどの損失関数に対する正規性仮定は必要とせず、近似パラメータ $\varepsilon$ に適用された AdaGrad スタイルのチューニングの一般化と見なすことができる。 この結果から,Dong と Yoshida (2023) の$(1+\varepsilon)$-approximate regret bounds を回復・強化し,オンラインの$k$-means クラスタリング,低ランク近似,レグレッションに対して少額の後悔bounds が得られる。 1\pm\varepsilon)$-cut sparsifiers of submodular hypergraphs, obtained a small-loss regret bound of $\tilde O(n^{3/4}(1 + \mathrm{OPT}_T^{3/4})$, where $n$ is the ground-set size。 提案手法は, 乱数次モデルにおける小さめの後悔境界の確立において, スパーシフィケーションと関連する手法のパワーに光を当てるものである。

関連論文リスト

• 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)
• Robust learning of halfspaces under log-concave marginals [6.852292115526837]
  線形しきい値関数を学習し、境界体積$O(r+varepsilon)$の分類子を半径摂動$r$で返すアルゴリズムを与える。 dtildeO(1/varepsilon2)$の時間とサンプルの複雑さはブール回帰の複雑さと一致する。
  論文  参考訳（メタデータ） (2025-05-19T20:12:16Z)
• Misspecified $Q$-Learning with Sparse Linear Function Approximation: Tight Bounds on Approximation Error [25.777423855881878]
  我々は、$Oleft(Hepsilonright)$-optimal Policyを得ることができることを示す新しい除去アルゴリズムを示す。 我々は上界を$widetildeOmegaleft(Hepsilonright)$-optimality lower boundで補い、この問題の完全な図面を与える。
  論文  参考訳（メタデータ） (2024-07-18T15:58:04Z)
• Optimal Sketching Bounds for Sparse Linear Regression [116.30196615349226]
  我々は、$ell_p$ノルムや広範なヒンジ様損失関数のクラスから、様々な損失関数の下で、$k$スパース線形回帰の難読スケッチを研究する。 スパース$ell$varepsレグレッションの場合、$Theta(klog(d/k)/varepsilon2)$ rowsでスケッチの上に曖昧な分布が存在し、これは定数要素に固執することを示している。 また、$O(mu2 klog(mun d/varepsilon)/varのスケッチも示します。
  論文  参考訳（メタデータ） (2023-04-05T07:24:19Z)
• Sparse Signal Detection in Heteroscedastic Gaussian Sequence Models: Sharp Minimax Rates [1.0309387309011746]
  スパースな代替品に対する信号検出問題を、既知のスパシティ$s$に対して検討する。 ミニマックス分離半径$epsilon*$の上の上限と下限を見つけ、それらが常に一致することを証明する。 以上の結果から,epsilon*$の挙動に関する新たな位相遷移が,Sigma$の疎度レベル,$Lt$メトリック,およびヘテロスセダサシティプロファイル(herescedasticity profile)に現れる。
  論文  参考訳（メタデータ） (2022-11-15T23:53:39Z)
• Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithm [46.36534144138337]
  本稿では,オフライン強化学習におけるポリシー評価のサンプル複雑さについて検討する。 低分布シフトの仮定の下では、最大$oleft(maxleft fracleftvert thetapirightvert _24varepsilon4logfracddelta,frac1varepsilon2left(d+logfrac1deltaright)right right)$サンプルを必要とするアルゴリズムがあることを示す。
  論文  参考訳（メタデータ） (2021-03-17T18:18:57Z)
• 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)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
  期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
  論文  参考訳（メタデータ） (2020-05-29T07:20:35Z)

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

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