論文の概要: Provably data-driven projection method for quadratic programming

• arxiv url: http://arxiv.org/abs/2509.04524v1
• Date: Wed, 03 Sep 2025 14:44:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-08 14:27:25.357392
• Title: Provably data-driven projection method for quadratic programming
• Title（参考訳）: 2次プログラミングのための確率的データ駆動プロジェクション法
• Authors: Anh Tuan Nguyen, Viet Anh Nguyen,
• Abstract要約: 凸二次プログラム(QP)におけるデータ駆動予測行列学習の一般化保証を解析する。 凸QPの解が特殊活性集合に対応する実現可能な領域に局在できることを実証する。 次に、最適解と入力対応設定を一致させる学習を含む、分析を他の設定に拡張します。
• 参考スコア（独自算出の注目度）: 18.20955065779317
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Projection methods aim to reduce the dimensionality of the optimization instance, thereby improving the scalability of high-dimensional problems. Recently, Sakaue and Oki proposed a data-driven approach for linear programs (LPs), where the projection matrix is learned from observed problem instances drawn from an application-specific distribution of problems. We analyze the generalization guarantee for the data-driven projection matrix learning for convex quadratic programs (QPs). Unlike in LPs, the optimal solutions of convex QPs are not confined to the vertices of the feasible polyhedron, and this complicates the analysis of the optimal value function. To overcome this challenge, we demonstrate that the solutions of convex QPs can be localized within a feasible region corresponding to a special active set, utilizing Caratheodory's theorem. Building on such observation, we propose the unrolled active set method, which models the computation of the optimal value as a Goldberg-Jerrum (GJ) algorithm with bounded complexities, thereby establishing learning guarantees. We then further extend our analysis to other settings, including learning to match the optimal solution and input-aware setting, where we learn a mapping from QP problem instances to projection matrices.
• Abstract（参考訳）: 射影法は,最適化インスタンスの次元性を低減し,高次元問題のスケーラビリティを向上させることを目的としている。 近年,Sakaue と Oki は線形プログラム (LP) に対するデータ駆動型手法を提案し,アプリケーション固有の問題分布から引き出された観測問題事例からプロジェクション行列を学習した。 凸二次プログラム(QP)におけるデータ駆動型プロジェクション行列学習の一般化保証を解析する。 LP とは異なり、凸 QP の最適解は実現可能なポリヘドロンの頂点に限らず、最適値関数の解析を複雑にする。 この課題を克服するために、凸QPの解が、カラテオドレイの定理を利用して、特別な活性集合に対応する実現可能な領域に局所化できることを実証する。 このような観測に基づいて、最適値の計算をGJ(Goldberg-Jerrum)アルゴリズムとしてモデル化し、学習保証を確立するアンロールアクティブセット手法を提案する。 そこでは,QP問題インスタンスから射影行列へのマッピングを学習し,最適解と入力認識設定を一致させるための学習を含む,分析をさらに他の設定に拡張する。

関連論文リスト

• Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
  本稿では,1次と2次の両方の定常点を見つけるための信頼逐次準計画法を提案する。 本手法は, 1次定常点に収束するため, 対象対象の近似を最小化して定義された各イテレーションの勾配ステップを計算する。 2階定常点に収束するため,本手法は負曲率を減少するヘッセン行列を探索する固有ステップも計算する。
  論文  参考訳（メタデータ） (2024-09-24T04:39:47Z)
• From Inverse Optimization to Feasibility to ERM [11.731853838892487]
  パラメータの予測に付加的なコンテキスト情報を利用するコンテキスト逆設定について検討する。 合成および実世界の問題に対する我々のアプローチを実験的に検証し,既存手法と比較して性能が向上したことを示す。
  論文  参考訳（メタデータ） (2024-02-27T21:06:42Z)
• Convex Q Learning in a Stochastic Environment: Extended Version [1.680268810119084]
  本稿では,関数近似を用いたマルコフ決定過程に対する凸Q-ラーニングの最初の定式化について紹介する。 提案アルゴリズムは収束し, 平均二乗感覚における収束率を求める新しい手法が導入された。 この理論は古典的な在庫管理問題への応用として説明されている。
  論文  参考訳（メタデータ） (2023-09-10T18:24:43Z)
• An inexact LPA for DC composite optimization and application to matrix completions with outliers [5.746154410100363]
  本稿では,複合最適化問題のクラスについて述べる。 合成構造を利用することで、ポテンシャル関数が反復列において1/2$のKL特性を持つ条件を与える。
  論文  参考訳（メタデータ） (2023-03-29T16:15:34Z)
• Fully Stochastic Trust-Region Sequential Quadratic Programming for Equality-Constrained Optimization Problems [62.83783246648714]
  目的と決定論的等式制約による非線形最適化問題を解くために,逐次2次プログラミングアルゴリズム(TR-StoSQP)を提案する。 アルゴリズムは信頼領域半径を適応的に選択し、既存の直線探索StoSQP方式と比較して不確定なヘッセン行列を利用することができる。
  論文  参考訳（メタデータ） (2022-11-29T05:52:17Z)
• Adaptive Stochastic Optimisation of Nonconvex Composite Objectives [2.1700203922407493]
  一般化された複合ミラー降下アルゴリズムの一群を提案し,解析する。 適応的なステップサイズでは、提案アルゴリズムは問題の事前知識を必要とせずに収束する。 決定集合の低次元構造を高次元問題に活用する。
  論文  参考訳（メタデータ） (2022-11-21T18:31:43Z)
• Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
  無限水平マルコフ決定過程(MDP)における最適政策学習の問題を考える。 リプシッツ連続関数を用いた凸プログラミング問題に対してミラー・ディクセントの変種が提案されている。 このアルゴリズムを一般の場合において解析し,提案手法の動作中に誤差を蓄積しない収束率の推定値を得る。
  論文  参考訳（メタデータ） (2021-02-27T19:28:39Z)
• Convex Geometry and Duality of Over-parameterized Neural Networks [70.15611146583068]
  有限幅2層ReLUネットワークの解析のための凸解析手法を開発した。 正規化学習問題に対する最適解が凸集合の極点として特徴づけられることを示す。 高次元では、トレーニング問題は無限に多くの制約を持つ有限次元凸問題としてキャストできることが示される。
  論文  参考訳（メタデータ） (2020-02-25T23:05:33Z)

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

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