論文の概要: When Is Tracking Affordable? A Movement-Budget Feasibility Threshold for Dynamic Regret

• arxiv url: http://arxiv.org/abs/2611.02812v1
• Date: Mon, 02 Nov 2026 09:18:33 GMT
• ステータス: 情報取得中
• システム内更新日: 2026-11-03 19:21:49.8626
• Title: When Is Tracking Affordable? A Movement-Budget Feasibility Threshold for Dynamic Regret
• Title（参考訳）: 追跡はいつ継続可能か : 動的回帰のための運動予算性閾値
• Abstract要約: 動的後悔はオンライン学習者を移動コンパレータに対して測定し、標準分析は学習者が各ラウンドで自由に移動できると仮定する。 学習者は、その全運動に対して、厳しい予算でS$を与えられる。 予算対応のステップサイズで計画されたオンライン勾配降下は、予算実現可能であり、$o(GDT)$ once $S = (D + P_T)$に達する。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: Dynamic regret measures an online learner against a moving comparator, and standard analyses assume the learner may move freely at every round. We study what happens when it may not: the learner is given a hard budget $S$ on its total movement $\sum_t \|x_t - x_{t-1}\|$. Our main result is that a movement budget creates a feasibility barrier. On a domain of diameter $D$ with $G$-Lipschitz convex losses, for every comparator path length $P_T \in [D, DT]$ we exhibit a deterministic adversary that forces $R_d = Ω(GDT)$ on every budget-feasible algorithm whenever $S \le c P_T$ for a universal constant $c>0$. This barrier is caused by the budget rather than by a volatile environment: for fixed $D$, it applies when $P_T = o(T)$, where the unconstrained minimax rate $Θ(G\sqrt{D(D+P_T)T})$ is sublinear, so the same instances are learnable with an unbounded budget and unlearnable without one. Conversely, projected online gradient descent with a budget-aware step size is budget-feasible and attains $o(GDT)$ once $S = ω(D + P_T)$. Thus the critical movement scale is $D+P_T$: linear regret is unavoidable below a sufficiently small constant multiple of $P_T$, while sublinear regret is achievable when $S/(D+P_T)\to\infty$ in the learnable regime. The construction rests on a distinction we make explicit: what makes a comparator expensive to track under a movement budget is the distance it forces the learner to travel, not its path length. Above the threshold we give a budget-dependent upper bound and identify the tight minimax rate in this region as an open problem rather than claiming a product law. Experiments support the predicted transition location and the $1/S$ decay.
• Abstract（参考訳）: 動的後悔はオンライン学習者を移動コンパレータに対して測定し、標準分析は学習者が各ラウンドで自由に移動できると仮定する。 学習者は、その総移動量$\sum_t \|x_t - x_{t-1}\|$で、ハード予算$S$を与えられる。 我々の主な成果は、運動予算が実現可能性障壁を生み出すことである。 直径$D$と$G$-Lipschitz凸損失の領域では、すべてのコンパレータパス長$P_T \in [D, DT]$に対して、$R_d = Ω(GDT)$を強制する決定論的逆数を示す。 固定$D$の場合、$P_T = o(T)$で、制約なしのミニマックスレート$\(G\sqrt{D(D+P_T)T})$がサブラインである場合、同じインスタンスは非有界な予算で学習可能であり、それなしでは学習できない。 逆に、予算対応のステップサイズを持つオンライン勾配勾配は予算可能であり、$o(GDT)$ once $S = ω(D + P_T)$に達する。 したがって、臨界運動スケールは$D+P_T$である: 線形後悔は、学習可能な状態において、$S/(D+P_T)\to\infty$のとき、十分に小さな定数倍の$P_T$以下では避けられない。 コンパレータが運動予算の下で追跡するのに高価になるのは、学習者が移動するのに要する距離であって、パスの長さではないということです。 しきい値の上に予算依存の上限を与え、この領域の厳密なミニマックスレートを積法則を主張するよりもオープンな問題とみなす。 実験は予測される遷移位置と1/Sの崩壊をサポートする。

関連論文リスト

• Minimax-Optimal Small-Loss Bounds for Online Linear Optimisation on $\ell_p$ Balls [1.4975436239088316]
  Follow-the-regularized-leaderアルゴリズムは、損失シーケンス毎に、$T$や$_T$を知らずに、後悔する$O_pを達成する。 平均がゼロ座標を持たない i.d. 損失に対しては、期待される後悔の正確な$log T$係数を計算する。
  論文  参考訳（メタデータ） (2026-10-26T18:15:38Z)
• Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
  一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。 スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
  論文  参考訳（メタデータ） (2026-09-07T01:38:41Z)
• Complexity of Classical Acceleration for $\ell_1$-Regularized PageRank [14.919427330415608]
  FISTAは1/$ローカリティスケーリングを保ちながら$$への依存を改善することができることを示す。 我々はFISTAをわずかに過正規化された目的に基づいて解析し、チェック可能な閉じ込め条件下では、全ての刺激活性化が境界集合内に存在することを示す。 これにより、加速された$(sqrt)-1log(/varepsilon)$項と境界オーバーヘッド$sqrtvol(mathcalB)/(3/2)$からなるバウンダリが得られる。
  論文  参考訳（メタデータ） (2026-02-24T17:35:46Z)
• 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)
• 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)
• Minimal Expected Regret in Linear Quadratic Control [79.81807680370677]
  オンライン学習アルゴリズムを考案し、その期待された後悔を保証します。 当時のこの後悔は、$A$と$B$が未知の場合、$widetildeO((d_u+d_x)sqrtd_xT)$によって上界(i)となる。
  論文  参考訳（メタデータ） (2021-09-29T14:07:21Z)
• Online Convex Optimization with Continuous Switching Constraint [78.25064451417082]
  連続的なスイッチング制約を伴うオンライン凸最適化の問題を紹介する。 強い凸関数の場合、後悔境界は$O(log T)$ for $S=Omega(log T)$、$O(minT/exp(S)+S,T)$ for $S=O(log T)$に改善できることを示す。
  論文  参考訳（メタデータ） (2021-03-21T11:43:35Z)
• $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)
• Near-optimal Regret Bounds for Stochastic Shortest Path [63.029132134792555]
  最短経路 (SSP) は計画と制御においてよく知られた問題であり、エージェントは最小の総コストで目標状態に到達する必要がある。 任意の学習アルゴリズムは、最悪の場合、少なくとも$Omega(B_star sqrt|S| |A|K)$後悔しなければならない。
  論文  参考訳（メタデータ） (2020-02-23T09:10:14Z)

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

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