Fugu-MT 論文翻訳(概要): A fast algorithm to minimize prediction loss of the optimal solution in inverse optimization problem of MILP

論文の概要: 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)
Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文参考訳（メタデータ） (2024-10-03T15:04:01Z)
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)
A quantum central path algorithm for linear optimization [5.450016817940232]
中心経路の量子力学的シミュレーションにより線形最適化問題を解くための新しい量子アルゴリズムを提案する。このアプローチは、$m$制約と$n$変数を含む線形最適化問題を$varepsilon$-optimalityに解くアルゴリズムをもたらす。標準ゲートモデル(すなわち、量子RAMにアクセスせずに)では、我々のアルゴリズムは少なくとも$$mathcalO left( sqrtm + n textsfnnz (A) fracR_1 を用いてLO問題の高精度な解を得ることができる。
論文参考訳（メタデータ） (2023-11-07T13:26:20Z)
Fast Minimization of Expected Logarithmic Loss via Stochastic Dual Averaging [8.990961435218544]
本稿では,対数障壁を用いたB$-sample双対平均化法を提案する。 Poisson逆問題に対して、我々のアルゴリズムは$smashtildeO(d3/varepsilon2)$ timeで$varepsilon$解を得る。量子状態トモグラフィーの最大線量推定を計算するとき、我々のアルゴリズムは $smashtildeO(d3/varepsilon2)$ time で $varepsilon$-optimal Solution を得る。
論文参考訳（メタデータ） (2023-11-05T03:33:44Z)
An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization [37.300102993926046]
リプシッツの目的の滑らかな点も凸点も生成しない点の複雑さについて検討する。私たちの分析は単純だが強力だ。 Goldstein-subdifferential set, これは最近の進歩を可能にする。非滑らかな非最適化
論文参考訳（メタデータ） (2023-07-10T11:56:04Z)
An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文参考訳（メタデータ） (2023-06-30T08:34:29Z)
Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文参考訳（メタデータ） (2022-10-23T21:24:37Z)
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)
Instance Specific Approximations for Submodular Maximization [45.91235224228292]
実世界のインスタンス上で最適な解に対して,アルゴリズムの性能をベンチマークする手法を模索する。大きな疑問は、実際に遭遇したインスタンスの最適なソリューションと比較して、アルゴリズムのパフォーマンスを測定する方法です。我々の主な貢献は、サブモジュラー最小化のための新しいアルゴリズムではなく、サブモジュラーインスタンスのアルゴリズムがいかに最適かを測定する分析手法である。
論文参考訳（メタデータ） (2021-02-23T19:39:32Z)
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)
Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文参考訳（メタデータ） (2020-06-16T17:55:46Z)
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)
Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文参考訳（メタデータ） (2020-04-16T19:16:38Z)

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

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