論文の概要: A fast algorithm to minimize prediction loss of the optimal solution in inverse optimization problem of MILP
- arxiv url: http://arxiv.org/abs/2405.14273v2
- Date: Thu, 22 May 2025 05:34:49 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-23 17:12:47.604351
- Title: A fast algorithm to minimize prediction loss of the optimal solution in inverse optimization problem of MILP
- Title（参考訳）: MILPの逆最適化問題における最適解の予測損失を最小化する高速アルゴリズム
- Authors: Akira Kitaoka,
- Abstract要約: 最適度損失に基づくステップサイズが$k-1/2$の手法が重みを効率よく学習することを示す。
実験により,提案手法はMILPの逆最適化問題を1/7ドル以下で解決することを示した。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the inverse optimization problem of estimating the weights of the objective function such that the given solution is an optimal solution for a mixed integer linear program (MILP). In this inverse optimization problem, the known methods exhibit inefficient convergence. Specifically, if $d$ denotes the dimension of the weights and $k$ the number of iterations, then the error of the weights is bounded by $O(k^{-1/(d-1)})$, leading to slow convergence as $d$ increases.We propose a projected subgradient method with a step size of $k^{-1/2}$ based on suboptimality loss. We theoretically show and demonstrate that the proposed method efficiently learns the weights. In particular, we show that there exists a constant $\gamma > 0$ such that the distance between the learned and true weights is bounded by $ O\left(k^{-1/(1+\gamma)} \exp\left(-\frac{\gamma k^{1/2}}{2+\gamma}\right)\right), $ or the optimal solution is exactly recovered. Furthermore, experiments demonstrate that the proposed method solves the inverse optimization problems of MILP using fewer than $1/7$ the number of MILP calls required by known methods, and converges within a finite number of iterations.
- Abstract（参考訳）: 混合整数線形プログラム(MILP)において、与えられた解が最適解であるような目的関数の重みを推定する逆最適化問題を考察する。
この逆最適化問題において、既知の手法は非効率収束を示す。
具体的には、$d$が重みの次元を表し、$k$が反復数数であるなら、重みの誤差は$O(k^{-1/(d-1)})$で制限され、d$が増加するにつれて収束が遅くなる。
本稿では,提案手法が効率よく重みを学習できることを理論的に示す。
特に、学習されたウェイトと真のウェイトの間の距離が$ O\left(k^{-1/(1+\gamma)} \exp\left(-\frac{\gamma k^{1/2}}{2+\gamma}\right)\right)、$または最適解が正確に回復されるような定数$\gamma > 0$が存在することを示す。
さらに,提案手法はMILPの逆最適化問題を1/7ドル以下で解き,有限個の繰り返しに収束することを示した。
関連論文リスト
- Optimal Rates for Robust Stochastic Convex Optimization [12.620782629498812]
我々は、$epsilon$-contaminationモデルの下で、最小最適過剰リスク(対数因子まで)を達成する新しいアルゴリズムを開発した。
我々のアルゴリズムは、個々のサンプル関数のリプシッツ連続性や滑らかさを含む厳密な仮定を必要としない。
我々は、ロバストSCOのための厳密な情報理論の下限でアルゴリズム開発を補完する。
論文 参考訳（メタデータ） (2024-12-15T00:52:08Z) - Alternating Minimization Schemes for Computing Rate-Distortion-Perception Functions with $f$-Divergence Perception Constraints [10.564071872770146]
離散メモリレスソースに対するRDPF(Ralse-Distortion-Perception Function)の計算について検討した。
最適パラメトリック解を特徴付ける。
歪みと知覚制約について十分な条件を提供する。
論文 参考訳（メタデータ） (2024-08-27T12:50:12Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。