論文の概要: Explicit Iteration Complexity of Exact Data-Driven Inverse Optimization for Integer Linear Programs

• arxiv url: http://arxiv.org/abs/2607.22263v1
• Date: Fri, 24 Jul 2026 12:56:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-27 20:58:57.127503
• Title: Explicit Iteration Complexity of Exact Data-Driven Inverse Optimization for Integer Linear Programs
• Title（参考訳）: 整数線形プログラムにおける厳密なデータ駆動逆最適化の明示的反復複雑性
• Abstract要約: データ駆動逆最適化問題(DDIOP)は、観測された最適解法データを説明する目的関数パラメータ(重み)を推定する問題である。 前方問題は整数線形プログラム (ILP) であるとき、射影次数降下に十分な反復数を与える。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A data-driven inverse optimization problem (DDIOP) is the problem of estimating the objective-function parameters (weights) that explain observed optimal-solution data, and it arises in many applications, including integer linear programming (ILP). It is known that, by applying gradient-based optimization methods to the suboptimality loss, the inverse optimization of ILPs can be solved exactly within finitely many oracle iterations, and that the required number of iterations is bounded as $T=O(1/γ(\ell_{\mathrm{sub}})^2)$ in terms of a problem-dependent geometric constant $γ(\ell_{\mathrm{sub}})$. However, no means of bounding $γ(\ell_{\mathrm{sub}})$ from below as a function of the problem size has been available, and hence the number of iterations could not be given as an explicit function of the problem size. We therefore give, when the forward problem is an integer linear program (ILP), the number of iterations sufficient for projected subgradient descent applied to the suboptimality loss to achieve exact consistency with the observed data, as a fully explicit function of the number of samples, the dimension of the features, the ranges of the features, and the structure of the constraint coefficient matrix, up to polynomial factors in the basic constants (the diameter of the weight set, the step-size parameter, and the Lipschitz constant of the suboptimality loss).
• Abstract（参考訳）: データ駆動逆最適化問題(DDIOP)は、観測された最適解法データを説明する目的関数パラメータ(重み)を推定する問題であり、整数線形プログラミング(ILP)を含む多くのアプリケーションで発生する。 勾配に基づく最適化法を最適性損失に適用することにより、ICPの逆最適化が有限個のオラクル反復で正確に解けることや、必要回数の反復は問題依存の幾何定数 $γ(\ell_{\mathrm{sub}})$ で$T=O(1/γ(\ell_{\mathrm{sub}})^2)$ と有界であることが知られている。 しかし、以下から問題サイズの関数として$γ(\ell_{\mathrm{sub}})$を束縛する手段は存在せず、したがって、繰り返しの数は問題サイズの明示的な関数として与えられない。 したがって、前方問題は整数線型計画 (ILP) であるとき、観測されたデータとの正確な整合性を達成するために、下降勾配の投影に十分なイテレーションの個数は、サンプルの数、特徴の次元、特徴の範囲、および制約係数行列の構造の完全な明示的な関数として、基本定数(重みセットの直径、ステップサイズパラメータ、および下降損失のリプシッツ定数)の多項式因子まで与える。

関連論文リスト

• An Efficient Spatial Branch-and-Bound Algorithm for Global Optimization of Gaussian Process Posterior Mean Functions [2.738648582869357]
  空間空間の分枝および分枝における部分解析的下界表現が平均値に有効であることを示す。 その結果,PALM-Meanはデータ点数の増加に伴い,汎用的グローバルトレーニングの改善を図っている。
  論文  参考訳（メタデータ） (2026-04-21T01:13:54Z)
• Bregman Linearized Augmented Lagrangian Method for Nonconvex Constrained Stochastic Zeroth-order Optimization [9.482573620753442]
  本稿では,0階推定器と分散手法を組み合わせたBregman線形化ラグランジアン法を提案する。 その結果,提案手法の複雑性は,必要条件(O(d))よりも低次元依存性を実現することができることがわかった。
  論文  参考訳（メタデータ） (2025-04-13T02:44:47Z)
• Gradient-free stochastic optimization for additive models [50.57026826740147]
  本稿では,Polyak-Lojasiewicz あるいは強凸条件を満たす目的関数に対する雑音観測によるゼロ次最適化の問題に対処する。 対象関数は加法的構造を持ち、H"古い関数族によって特徴づけられる高次滑らか性特性を満たすと仮定する。
  論文  参考訳（メタデータ） (2025-03-03T23:39:08Z)
• Optimization on a Finer Scale: Bounded Local Subgradient Variation Perspective [17.5796206457693]
  局所的な局所次変分の下での非滑らかな最適化問題について検討する。 得られた目的のクラスは、定義されたクラスに基づいて目的のクラスをカプセル化する。
  論文  参考訳（メタデータ） (2024-03-24T22:42:40Z)
• Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching [55.28394191394675]
  等式制約付き非線形非IBS最適化問題に対する適応的不正確なニュートン法を開発した。 ベンチマーク非線形問題,LVMのデータによる制約付きロジスティック回帰,PDE制約問題において,本手法の優れた性能を示す。
  論文  参考訳（メタデータ） (2023-05-28T06:33:37Z)
• Low-complexity subspace-descent over symmetric positive definite manifold [9.346050098365648]
  対称正定値多様体(SPD)上の関数の最小化のための低複素性アルゴリズムを開発する。 提案手法は、慎重に選択された部分空間を利用して、更新をイテレートのコレスキー因子とスパース行列の積として記述することができる。
  論文  参考訳（メタデータ） (2023-05-03T11:11:46Z)
• Sparse Polynomial Optimization: Theory and Practice [5.27013884159732]
  本書は、この課題に重要な科学的意味を持って取り組むためのいくつかの取り組みを提示している。 これは計算複雑性の観点からうまくスケールする代替の最適化スキームを提供する。 制約のない問題や制約のない問題に対して、緩和の疎開的階層を提示する。
  論文  参考訳（メタデータ） (2022-08-23T18:56:05Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• Square Root Bundle Adjustment for Large-Scale Reconstruction [56.44094187152862]
  QR分解によるランドマーク変数のnullspace marginalizationに依存するバンドル調整問題の新たな定式化を提案する。 平方根束調整と呼ばれる私たちのアプローチは、一般的に使用されるSchur補完トリックと代数的に等価です。 BALデータセットを用いた実世界での実験では、提案されたソルバが単一の精度でも平均的等しく正確なソリューションで達成できることを示す。
  論文  参考訳（メタデータ） (2021-03-02T16:26:20Z)
• Global Convergence of Model Function Based Bregman Proximal Minimization Algorithms [17.740376367999705]
  連続微分可能関数のリプシッツ写像は様々な最適化アルゴリズムにおいて重要な役割を果たす。 モデル$L$madプロパティと呼ばれるグローバル収束アルゴリズムを提案します。
  論文  参考訳（メタデータ） (2020-12-24T08:09:22Z)
• Revisiting SGD with Increasingly Weighted Averaging: Optimization and Generalization Perspectives [50.12802772165797]
  平均化手法は、全ての反復解を一つの解に結合する。 実験は、他の平均化方式と比較して、トレードオフと平均化の有効性を示した。
  論文  参考訳（メタデータ） (2020-03-09T18:14:00Z)
• Implicit differentiation of Lasso-type models for hyperparameter optimization [82.73138686390514]
  ラッソ型問題に適した行列逆転のない効率的な暗黙微分アルゴリズムを提案する。 提案手法は,解の空間性を利用して高次元データにスケールする。
  論文  参考訳（メタデータ） (2020-02-20T18:43:42Z)

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

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