論文の概要: Optimal and Efficient Online Inverse Optimization

• arxiv url: http://arxiv.org/abs/2610.08735v1
• Date: Tue, 06 Oct 2026 17:37:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-08 02:58:30.151921
• Title: Optimal and Efficient Online Inverse Optimization
• Title（参考訳）: 最適かつ効率的なオンライン逆最適化
• Abstract要約: 逆線形最適化では、学習者はアクションを推奨し、$mathbbRd$上で固定された未知の線形目的を最大化する専門家の選択を観察する。 我々の決定論的アルゴリズムはすべての地平線に対して$O(sqrt d)$を後悔し、時間内に$d$と$T$を実行していることを示す。
• 参考スコア（独自算出の注目度）: 72.20380065366825
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In online inverse linear optimization, a learner recommends an action and then observes the choice of an expert who maximizes a fixed, unknown linear objective on $\mathbb{R}^{d}$; the goal is to learn to optimize this objective without observing it. Sakaue recently obtained the optimal regret $O(\sqrt d)$ with a randomized algorithm making $(dT)^{O(d)}$ linear optimizations per round, and asked whether it can be attained in polynomial time. We answer positively: our deterministic algorithm has regret $O(\sqrt d)$ for every horizon $T$ and runs in time polynomial in $d$ and $T$. It is a variant of the variable-metric algorithms of Sakaue et al.\ and Cai et al., in which a metric update is revoked once the query point moves far enough from where the update was made.
• Abstract（参考訳）: オンライン逆線形最適化では、学習者はアクションを推奨し、$\mathbb{R}^{d}$上で固定された未知の線形目的を最大化する専門家の選択を観察する。 坂上は、最近、1ラウンドあたりの線形最適化を$(dT)^{O(d)} とするランダム化アルゴリズムで最適な後悔$O(\sqrt d)$を取得し、多項式時間で達成できるかどうかを問うた。 我々の決定論的アルゴリズムはすべての地平線に対して$O(\sqrt d)$を後悔し、時間多項式を$d$と$T$で実行する。 Sakaue et al \ と Cai et al の変数メトリックアルゴリズムの変種であり、クエリポイントが更新された場所から十分に移動したら、メトリック更新が取り消される。

関連論文リスト

• Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights [18.046669772867443]
  固定された未知の線形効用を用いた逆線形最適化について検討する。 各ラウンドにおいて、環境はコンパクトなアクションセットを示し、学習者はそれからアクションを推奨し、環境は同じセット上でユーティリティを最大化するアクションを返す。 効用ベクトルと作用が$d$次元ユークリッド単位球に置かれるとき、我々は無作為なアルゴリズムを与える-------------------------------------------------- (sqrt d)$------------------------------------------------------------------------------------------------- -------------------
  論文  参考訳（メタデータ） (2026-09-22T19:13:53Z)
• Efficient Online Inverse Optimization with $O(d)$ Regret [26.77597743186513]
  オンライン逆線形最適化のための決定論的アルゴリズムを,残差$O(d)$,地平線一様,ラウンド毎の$O(d2)$時間で提供する。 この順序の境界は最近Dewasurendraによって得られたが、全てのスケールでカバーを列挙する不適切な規則により、1ラウンド当たり$T(d)の費用がかかる。
  論文  参考訳（メタデータ） (2026-09-11T18:55:31Z)
• 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)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion [46.46038357597395]
  本稿では,新しい解析手法を用いて,未知の非平滑な目的を最適化するアルゴリズムを提案する。 決定論的二階スムーズな目的のために、先進的な楽観的なオンライン学習技術を適用することで、新しい$O(delta0.5)All$が最適または最もよく知られた結果の回復を可能にする。
  論文  参考訳（メタデータ） (2023-02-07T22:09:20Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。 提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。 我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
  論文  参考訳（メタデータ） (2021-06-15T02:23:07Z)
• Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
  現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。 本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。 次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-10T13:07: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)

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

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