論文の概要: Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound

• arxiv url: http://arxiv.org/abs/2501.14349v6
• Date: Thu, 22 May 2025 02:11:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-23 14:49:21.32972
• Title: Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound
• Title（参考訳）: オンライン逆線形最適化:効率的な対数-回帰アルゴリズム、準最適ロバスト性、下界
• Authors: Shinsaku Sakaue, Taira Tsuchiya, Han Bao, Taihei Oki,
• Abstract要約: ラウンド単位の複雑さが$T$に依存しない最初の対数-回帰法を提案する。 我々の方法は極めて単純であり、オンラインニュートンステップ(ONS)を適切なexp-concave損失関数に適用する。 また、$Omega(n)$ の下限を示し、$O(nln T)$ 境界が $O(ln T)$ 係数まで固であることを示す。
• 参考スコア（独自算出の注目度）: 25.50155563108198
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In online inverse linear optimization, a learner observes time-varying sets of feasible actions and an agent's optimal actions, selected by solving linear optimization over the feasible actions. The learner sequentially makes predictions of the agent's true linear objective function, and their quality is measured by the regret, the cumulative gap between optimal objective values and those achieved by following the learner's predictions. A seminal work by B\"armann et al. (2017) obtained a regret bound of $O(\sqrt{T})$, where $T$ is the time horizon. Subsequently, the regret bound has been improved to $O(n^4 \ln T)$ by Besbes et al. (2021, 2025) and to $O(n \ln T)$ by Gollapudi et al. (2021), where $n$ is the dimension of the ambient space of objective vectors. However, these logarithmic-regret methods are highly inefficient when $T$ is large, as they need to maintain regions specified by $O(T)$ constraints, which represent possible locations of the true objective vector. In this paper, we present the first logarithmic-regret method whose per-round complexity is independent of $T$; indeed, it achieves the best-known bound of $O(n \ln T)$. Our method is strikingly simple: it applies the online Newton step (ONS) to appropriate exp-concave loss functions. Moreover, for the case where the agent's actions are possibly suboptimal, we establish a regret bound of $O(n\ln T + \sqrt{\Delta_T n\ln T})$, where $\Delta_T$ is the cumulative suboptimality of the agent's actions. This bound is achieved by using MetaGrad, which runs ONS with $\Theta(\ln T)$ different learning rates in parallel. We also present a lower bound of $\Omega(n)$, showing that the $O(n\ln T)$ bound is tight up to an $O(\ln T)$ factor.
• Abstract（参考訳）: オンライン逆線形最適化では、学習者は、実行可能な動作に対する線形最適化を解くことで選択された、実行可能な動作の時間変化とエージェントの最適動作を観察する。 学習者は、エージェントの真の線形目的関数の予測を逐次行い、その品質は、後悔、最適な目的値と学習者の予測に従うことによって達成されるものとの累積的ギャップによって測定される。 B\"armann et al (2017) によるセミナルな研究は、$O(\sqrt{T})$の後悔境界を得た。 その後、Besbes et al (2021, 2025) によって$O(n^4 \ln T)$ に、Gollapudi et al (2021) によって$O(n \ln T)$ に改善された。 しかし、これらの対数-回帰法は、$T$が大きければ非常に非効率であり、真の客観的ベクトルの可能な位置を表す$O(T)$制約によって指定された領域を維持する必要がある。 本稿では、単位単位の複雑さが$T$とは独立な最初の対数-回帰法を示し、実際、$O(n \ln T)$の最もよく知られている境界を達成している。 我々の方法は極めて単純であり、オンラインニュートンステップ(ONS)を適切なexp-concave損失関数に適用する。 さらに、エージェントの作用が亜最適である可能性がある場合には、$O(n\ln T + \sqrt{\Delta_T n\ln T})$の後悔境界を確立し、$\Delta_T$はエージェントの作用の累積的準最適値である。 このバウンダリはMetaGradを使用して実現され、OnSを$\Theta(\ln T)$の異なる学習レートで並列に実行する。 また、$Omega(n)$ の下限を示し、$O(n\ln T)$ 境界が $O(\ln T)$ 因子に固であることを示す。

関連論文リスト

• Sparsity-Based Interpolation of External, Internal and Swap Regret [4.753557469026313]
  本稿では,$phi$-regret最小化によるパフォーマンス指標のコンパレータについて検討する。 本稿では,インスタンス適応型$phi$-regretバウンダリを実現する単一アルゴリズムを提案する。 従来の$phi$-regretの最小化から外部後悔の最小化への削減を前提に、我々は後者をさらにオンライン線形回帰に変換することを目的としている。
  論文  参考訳（メタデータ） (2025-02-06T22:47:52Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)
• 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)
• 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)
• 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)
• Logistic Regression Regret: What's the Catch? [3.7311680121118345]
  パラメータに対する$L_infty$制約の下で、対数的後悔を伴う下界を導出する。 L$の制約については、十分に大きな$d$の場合、後悔は$d$で線形であるが、$T$で対数化されなくなることが示されている。
  論文  参考訳（メタデータ） (2020-02-07T18:36:39Z)

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

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