論文の概要: A fast algorithm to minimize prediction loss of the optimal solution in inverse optimization problem of MILP

• arxiv url: http://arxiv.org/abs/2405.14273v1
• Date: Thu, 23 May 2024 07:51:05 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-24 18:14:32.507536
• Title: A fast algorithm to minimize prediction loss of the optimal solution in inverse optimization problem of MILP
• Title（参考訳）: MILPの逆最適化問題における最適解の予測損失を最小化する高速アルゴリズム
• Authors: Akira Kitaoka,
• Abstract要約: 本稿では,MILPの最適解(PLS)の予測損失を与えられたデータで最小化する問題に取り組む。 我々はMILPのPSSを最小化するための高速アルゴリズムを提案する。 提案アルゴリズムは,既存のアルゴリズムと比較して,PSSを2桁以上改善した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper tackles the problem of minimizing the prediction loss of the optimal solution (PLS) of the MILP with given data, which is one of the inverse optimization problems. While existing methods can approximately solve this problem, their implementation in the high-dimensional case to minimize the PLS is computationally expensive because they are inefficient in reducing the prediction loss of weights (PLW). We propose a fast algorithm for minimizing the PLS of MILP. To demonstrate this property, we attribute the problem of minimizing the PLS to that of minimizing the suboptimality loss (SL), which is convex. If the PLS does not vanish, we can adapt the SL to have the estimated loss (SPO loss) with a positive lower bound, which enables us to evaluate the PLW. Consequently, we prove that the proposed algorithm can effectively reduce the PLW and achieve the minimum value of PLS. Our numerical experiments demonstrated that our algorithm successfully achieved the minimum PLS. Compared to existing methods, our algorithm exhibited a smaller dimensionality effect and minimized the PLS in less than 1/7 the number of iterations. Especially in high dimensions, our algorithm significantly improved the PLS by more than two orders of magnitude compared to existing algorithms.
• Abstract（参考訳）: 本稿では,MILPの最適解(PLS)の予測損失を,逆最適化問題の1つである所定のデータで最小化する問題に取り組む。 既存の手法では、この問題をほぼ解決できるが、PLSを最小化するための高次元の場合の実装は、重量の予測損失(PLW)を減らすのに非効率であるため、計算的に高価である。 我々はMILPのPSSを最小化するための高速アルゴリズムを提案する。 この特性を示すために、PSSの最小化は、凸であるSL(suboptimality loss)の最小化の問題に起因する。 PLSが消滅しない場合、SLを正の下限で推定損失(SPO損失)に適応させることで、PLWを評価することができる。 その結果,提案アルゴリズムはPLWを効果的に低減し,PLSの最小値が得られることを示した。 我々の数値実験は、我々のアルゴリズムが最小のPSSを達成できたことを実証した。 既存の手法と比較して,本アルゴリズムは次元効果が小さく,PSSを1/7未満のイテレーション数で最小化する。 特に高次元では,既存のアルゴリズムに比べてPSSを2桁以上改善した。

関連論文リスト

• Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm [101.44676036551537]
  One-way partial AUC (OPAUC) と Two-way partial AUC (TPAUC) はバイナリ分類器の平均性能を測定する。 既存の手法のほとんどはPAUCをほぼ最適化するしかなく、制御不能なバイアスにつながる。 本稿では,分散ロバスト最適化AUCによるPAUC問題の簡易化について述べる。
  論文  参考訳（メタデータ） (2022-10-08T08:26:22Z)
• Large-scale Optimization of Partial AUC in a Range of False Positive Rates [51.12047280149546]
  ROC曲線 (AUC) の下の領域は、機械学習において最も広く使われている分類モデルのパフォーマンス指標の1つである。 近年の封筒平滑化技術に基づく効率的な近似勾配降下法を開発した。 提案アルゴリズムは,効率のよい解法を欠くランク付けされた範囲損失の和を最小化するためにも利用できる。
  論文  参考訳（メタデータ） (2022-03-03T03:46:18Z)
• An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learning [24.634592613300274]
  我々は,ミニバッチ勾配推定を用いて,滑らかで凸な目標,あるいは凸な目標を最適化するアルゴリズムを提案し,解析する。 このアルゴリズムは、ミニバッチサイズと最小損失の両方に同時に依存する点において最適である。
  論文  参考訳（メタデータ） (2021-06-04T21:06:00Z)
• Delayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applications [24.763531954075656]
  線形制約問題(LCP)に対する新しいプロジェクションベースアルゴリズムのクラスについて検討する。 そこで本研究では,射影を一時的に呼び出す遅延射影手法を提案し,射影周波数を下げ,射影効率を向上させる。 強凸, 一般凸のどちらの場合においても, 投射効率を向上させることが可能であることを示す。
  論文  参考訳（メタデータ） (2021-01-05T13:42:41Z)
• Train simultaneously, generalize better: Stability of gradient-based minimax learners [12.691047660244331]
  コンベックス・コンベブと非コンベックス・ミニマックス・セッティングの両方において,訓練されたミニマックスモデルの性能において重要な役割を担っている。 学習したミニマックスモデルの一般化における最適化アルゴリズムの役割を示す数値的な結果について議論する。
  論文  参考訳（メタデータ） (2020-10-23T17:44:43Z)
• Optimal quantisation of probability measures using maximum mean discrepancy [10.29438865750845]
  何人かの研究者は、確率測度を定量化する方法として、最大平均誤差 (MMD) の最小化を提案している。 離散的候補集合よりもMDDを優しく最小化する逐次アルゴリズムを考える。 本手法を各反復時の候補集合のミニバッチに適用する変種について検討する。
  論文  参考訳（メタデータ） (2020-10-14T13:09:48Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  スケッチに基づくL2正規化最小二乗問題の解法を提案する。 我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
  論文  参考訳（メタデータ） (2020-06-10T15:00:09Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。 本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
  論文  参考訳（メタデータ） (2020-05-10T19:52:03Z)

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

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