論文の概要: Efficient Online Inverse Optimization with $O(d)$ Regret

• arxiv url: http://arxiv.org/abs/2609.13440v1
• Date: Fri, 11 Sep 2026 18:55:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-16 07:15:05.323581
• Title: Efficient Online Inverse Optimization with $O(d)$ Regret
• Title（参考訳）: O(d)$ Regret を用いた効率的なオンライン逆最適化
• Abstract要約: オンライン逆線形最適化のための決定論的アルゴリズムを,残差$O(d)$,地平線一様,ラウンド毎の$O(d2)$時間で提供する。 この順序の境界は最近Dewasurendraによって得られたが、全てのスケールでカバーを列挙する不適切な規則により、1ラウンド当たり$T(d)の費用がかかる。
• 参考スコア（独自算出の注目度）: 26.77597743186513
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We give a deterministic algorithm for online inverse linear optimization with regret $O(d)$, uniform in the horizon and $O(d^{2})$ time per round. A bound of this order was obtained recently by Dewasurendra, settling a question of Gollapudi et al.\ and of Oki and Sakaue, but by an improper rule that enumerates covers at every scale and costs $T^{Θ(d)}$ a round; ours is the first efficient such bound and the first proper one. We build on the variable-metric framework of Sakaue et al., adding a self-normalized rank-one update, and we replace the $\log\det$ potential by the trace power $\tr(H^{-1/2})$, which is bounded outright and removes the $\ln T$. The bound also holds against an expert that does not optimize, and we give corruption-robust and rank-adaptive variants, and an application to convex minimization.
• Abstract（参考訳）: 我々は,オンライン逆線形最適化のための決定論的アルゴリズムを,残差$O(d)$,地平線一様,$O(d^{2})$ラウンド毎の時間で提供する。 この順序の有界性は、最近Dewasurendraによって得られ、Gollapudi et al \ と Oki と Sakaue の疑問を定めているが、すべてのスケールでカバーを列挙し、1ラウンド当たり$T^{*(d)} の費用を計る不適切な規則によって得られる。 Sakaue ら al の変数計量フレームワーク上に自己正規化階数 1 の更新を加え、トレースパワー $\tr(H^{-1/2})$ で $\log\det$ potential を置き換える。 このバウンダリは、最適化されていない専門家に対しても有効であり、汚職とランク順応の亜種、および凸最小化への応用を与えます。

関連論文リスト

• Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence [54.59847568544922]
  有限水平時間同質なマルコフ決定過程に対して、$A$状態、$A$アクション、hoighty $H$、および1ドルで有界なトラジェクティブ当たりの合計報酬について、地平自由な後悔について検討する。 失敗確率$$K$はエピソード数で$tilde O(sqrtSAK+S3K)$ hides $mathsfpolyである。
  論文  参考訳（メタデータ） (2026-07-22T07:42:19Z)
• A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees [58.59385794080679]
  本稿では,後悔を遅延非依存の学習項と遅延誘発のドリフト項に分解する連続時間モデルを提案する。 バンディット凸最適化では,最先端の1次数に適合する遅延依存項を用いて,既存の残差境界を大幅に改善する。
  論文  参考訳（メタデータ） (2026-02-02T18:17:34Z)
• Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback [49.84060509296641]
  オンライン有限水平マルコフ決定過程を逆向きに変化した損失と総括的帯域幅フィードバック(フルバンド幅)を用いて研究する。 この種のフィードバックの下では、エージェントは、軌跡内の各中間段階における個々の損失よりも、軌跡全体に生じる総損失のみを観察する。 この設定のための最初のポリシー最適化アルゴリズムを紹介します。
  論文  参考訳（メタデータ） (2025-02-06T12:03:24Z)
• Online Convex Optimization with a Separation Oracle [10.225358400539719]
  本稿では,オンライン凸最適化(OCO)のための新しいプロジェクションフリーアルゴリズムを提案する。 我々のアルゴリズムは、$widetildeO(sqrtdT + kappa d)$の償却バウンダリを達成し、ラウンド毎に$widetildeO(1)の呼び出ししか必要としない。
  論文  参考訳（メタデータ） (2024-10-03T13:35:08Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Near-Optimal Algorithms for Private Online Optimization in the Realizable Regime [74.52487417350221]
  オンライン学習の問題は,ゼロロスソリューションが存在する,実現可能な環境において考慮する。 そこで我々は,ほぼ最適の後悔境界を求める新たなDPアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-27T21:19:24Z)
• Iterative Hard Thresholding with Adaptive Regularization: Sparser Solutions Without Sacrificing Runtime [17.60502131429094]
  本稿では,条件数関数としてスペーサー解を復元する反復型ハードしきい値決定アルゴリズムの簡単な修正を提案する。 提案するアルゴリズムである正規化IHTは、疎度$O(skappa)$の解を返す。 我々のアルゴリズムはARHTよりも大幅に改善され、またスパーシティ$O(skappa)$の解も見つかる。
  論文  参考訳（メタデータ） (2022-04-11T19:33: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)

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

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