論文の概要: Learning in Inverse Optimization: Incenter Cost, Augmented Suboptimality
Loss, and Algorithms
- arxiv url: http://arxiv.org/abs/2305.07730v2
- Date: Tue, 23 Jan 2024 21:44:40 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-25 17:51:39.877179
- Title: Learning in Inverse Optimization: Incenter Cost, Augmented Suboptimality
Loss, and Algorithms
- Title(参考訳): 逆最適化における学習:インセンタコスト、拡張されたサブ最適化損失、アルゴリズム
- Authors: Pedro Zattoni Scroccaro, Bilge Atasoy, Peyman Mohajerin Esfahani
- Abstract要約: 我々は、最近Besbesらによって提案された「内心」の概念を、周辺に類似した新しい概念として紹介する。
本稿では,不整合データ問題に対する内心的概念の緩和であるASL (Augmented Suboptimality Loss) という新たな損失関数を提案する。
このアルゴリズムは、近似的な下位段階の評価とミラー降下更新ステップを組み合わせることで、高濃度の離散可能な集合を持つIO問題に対して、確実に効率的である。
- 参考スコア(独自算出の注目度): 4.0295993947651025
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In Inverse Optimization (IO), an expert agent solves an optimization problem
parametric in an exogenous signal. From a learning perspective, the goal is to
learn the expert's cost function given a dataset of signals and corresponding
optimal actions. Motivated by the geometry of the IO set of consistent cost
vectors, we introduce the "incenter" concept, a new notion akin to circumcenter
recently proposed by Besbes et al. (2023). Discussing the geometric and
robustness interpretation of the incenter cost vector, we develop corresponding
tractable convex reformulations, which are in contrast with the circumcenter,
which we show is equivalent to an intractable optimization program. We further
propose a novel loss function called Augmented Suboptimality Loss (ASL), a
relaxation of the incenter concept for problems with inconsistent data.
Exploiting the structure of the ASL, we propose a novel first-order algorithm,
which we name Stochastic Approximate Mirror Descent. This algorithm combines
stochastic and approximate subgradient evaluations, together with mirror
descent update steps, which is provably efficient for the IO problems with
discrete feasible sets with high cardinality. We implement the IO approaches
developed in this paper as a Python package called InvOpt. Our numerical
experiments are reproducible, and the underlying source code is available as
examples in the InvOpt package.
- Abstract(参考訳): 逆最適化(IO)では、エキスパートエージェントが外因性信号でパラメトリックな最適化問題を解く。
学習の観点からは、信号のデータセットと対応する最適なアクションが与えられた専門家のコスト関数を学ぶことが目標である。
一貫性のあるコストベクトルのio集合の幾何学に動機づけられ、besbes et al. (2023) によって最近提案されたcircorcenterに似た「内心」概念を導入する。
中心コストベクトルの幾何的・ロバスト性解釈を議論し, 円周と対照的なトラクタブル凸修正法を開発し, トラクタブル最適化プログラムと等価であることを示した。
さらに,不整合データ問題に対する中心概念の緩和であるASL(Augmented Suboptimality Loss)という新たな損失関数を提案する。
ASL の構造を探索し,Stochastic Approximate Mirror Descent と呼ばれる新しい一階法を提案する。
このアルゴリズムは、確率的および近似的な劣次評価とミラー降下更新ステップを組み合わせることで、高濃度の離散可逆集合を持つio問題に対して有効である。
InvOptと呼ばれるPythonパッケージとして,本論文で開発されたIOアプローチを実装した。
我々の数値実験は再現可能であり、根底にあるソースコードはInvOptパッケージの例である。
関連論文リスト
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳(メタデータ) (2024-09-07T06:37:23Z) - Sparsity-Constraint Optimization via Splicing Iteration [1.3622424109977902]
我々は sPlicing itEration (SCOPE) を用いたスペーサリティ制約最適化アルゴリズムを開発した。
SCOPEはパラメータをチューニングせずに効率的に収束する。
SCOPEを用いて2次最適化を解き、スパース分類器を学習し、バイナリ変数のスパースマルコフネットワークを復元する。
C++実装に基づいたオープンソースのPythonパッケージskscopeがGitHubで公開されている。
論文 参考訳(メタデータ) (2024-06-17T18:34:51Z) - Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits [12.674929126684528]
我々は、プレイヤーがPアクションの中から d 個の基本アイテムを含む集合のパワーセットから選択する半帯域の問題に対処する。
提案手法は半帯域フィードバックを効果的に活用し,帯域フィードバックアプローチより優れていることを示す。
論文 参考訳(メタデータ) (2024-02-23T08:07:54Z) - Robust expected improvement for Bayesian optimization [1.8130068086063336]
本稿では,BO/GPフレームワークに敵対的手法を組み込む,堅牢な予測改善(REI)と呼ばれる代理モデルとアクティブラーニング手法を提案する。
ベンチマーク・シンセティック・エクササイズと、様々な複雑さの実際の問題について、いくつかの競合相手と比較し、比較する。
論文 参考訳(メタデータ) (2023-02-16T22:34:28Z) - Adaptive Zeroth-Order Optimisation of Nonconvex Composite Objectives [1.7640556247739623]
ゼロ階エントロピー合成目的のためのアルゴリズムを解析し,次元依存性に着目した。
これは、ミラー降下法と推定類似関数を用いて、決定セットの低次元構造を利用して達成される。
勾配を改善するため、Rademacherに基づく古典的なサンプリング法を置き換え、ミニバッチ法が非ユークリ幾何学に対処することを示す。
論文 参考訳(メタデータ) (2022-08-09T07:36:25Z) - Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
空間的制約が存在する場合の高次元統計量と非破壊的最適化の関連について検討する。
これらの問題に対する新規で簡単な最適化法を開発した。
結論として、効率よくステーションに収束する一階法は、これらのタスクに対して効率的なアルゴリズムを導出する。
論文 参考訳(メタデータ) (2021-09-23T17:38:24Z) - Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。
我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。
また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
論文 参考訳(メタデータ) (2021-07-02T16:21:52Z) - Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
無限水平マルコフ決定過程(MDP)における最適政策学習の問題を考える。
リプシッツ連続関数を用いた凸プログラミング問題に対してミラー・ディクセントの変種が提案されている。
このアルゴリズムを一般の場合において解析し,提案手法の動作中に誤差を蓄積しない収束率の推定値を得る。
論文 参考訳(メタデータ) (2021-02-27T19:28:39Z) - Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box
Optimization Framework [100.36569795440889]
この作業は、一階情報を必要としない零次最適化(ZO)の反復である。
座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
論文 参考訳(メタデータ) (2020-12-21T17:29:58Z) - Accelerated Algorithms for Convex and Non-Convex Optimization on
Manifolds [9.632674803757475]
距離における凸問題と非最適化問題の解法を提案する。
提案アルゴリズムは,目的関数における複雑性のレベルに適応する。
論文 参考訳(メタデータ) (2020-10-18T02:48:22Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳(メタデータ) (2020-07-10T05:20:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。