論文の概要: Generalization Bound and Learning Methods for Data-Driven Projections in Linear Programming

• arxiv url: http://arxiv.org/abs/2309.00203v3
• Date: Tue, 21 May 2024 01:05:58 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-22 19:20:36.657107
• Title: Generalization Bound and Learning Methods for Data-Driven Projections in Linear Programming
• Title（参考訳）: 線形プログラミングにおけるデータ駆動射影の一般化境界と学習法
• Authors: Shinsaku Sakaue, Taihei Oki,
• Abstract要約: 高次元線形プログラムを効率的に解く方法は根本的な問題である。 近年,乱射影を用いたLPサイズ削減への関心が高まっている。 本稿では、ランダムな投影ではなく、データから学習した投影行列を用いた、データ駆動投影の新しい方向について検討する。
• 参考スコア（独自算出の注目度）: 23.188831772813103
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: How to solve high-dimensional linear programs (LPs) efficiently is a fundamental question. Recently, there has been a surge of interest in reducing LP sizes using random projections, which can accelerate solving LPs independently of improving LP solvers. This paper explores a new direction of data-driven projections, which use projection matrices learned from data instead of random projection matrices. Given training data of $n$-dimensional LPs, we learn an $n\times k$ projection matrix with $n > k$. When addressing a future LP instance, we reduce its dimensionality from $n$ to $k$ via the learned projection matrix, solve the resulting LP to obtain a $k$-dimensional solution, and apply the learned matrix to it to recover an $n$-dimensional solution. On the theoretical side, a natural question is: how much data is sufficient to ensure the quality of recovered solutions? We address this question based on the framework of data-driven algorithm design, which connects the amount of data sufficient for establishing generalization bounds to the pseudo-dimension of performance metrics. We obtain an $\tilde{\mathrm{O}}(nk^2)$ upper bound on the pseudo-dimension, where $\tilde{\mathrm{O}}$ compresses logarithmic factors. We also provide an $\Omega(nk)$ lower bound, implying our result is tight up to an $\tilde{\mathrm{O}}(k)$ factor. On the practical side, we explore two simple methods for learning projection matrices: PCA- and gradient-based methods. While the former is relatively efficient, the latter can sometimes achieve better solution quality. Experiments demonstrate that learning projection matrices from data is indeed beneficial: it leads to significantly higher solution quality than the existing random projection while greatly reducing the time for solving LPs.
• Abstract（参考訳）: 高次元線形プログラム(LP)を効率的に解く方法は根本的な問題である。 近年、乱射影を用いたLPサイズ削減への関心が高まっており、LP解法の改善とは無関係に、LPの解法を高速化することができる。 本稿では、ランダムな投影行列ではなく、データから学習した投影行列を用いた、データ駆動投影の新しい方向について検討する。 n 次元 LP のトレーニングデータを考えると、$n > k$ の射影行列が$n\times k$ となる。 将来のLPインスタンスに対処するとき、学習されたプロジェクション行列を介してその次元を$n$から$k$に減らし、その結果のLPを解いて$k$次元の解を取得し、学習した行列をそれに適用して$n$次元の解を復元する。 理論上、自然な疑問は、回復したソリューションの品質を保証するのに十分なデータがどのくらいあるか、ということです。 この問題は、一般化境界を確立するのに十分なデータ量と性能指標の擬似次元を結合する、データ駆動型アルゴリズム設計の枠組みに基づいて解決される。 擬次元上の上界を$\tilde{\mathrm{O}}(nk^2)$とすると、$\tilde{\mathrm{O}}$は対数因子を圧縮する。 また、$\Omega(nk)$ lower bound も提供しており、その結果は $\tilde{\mathrm{O}}(k)$ factor まで厳密であることを意味する。 実用面では,PCA法と勾配法という,投影行列を学習するための2つの簡単な方法を検討する。 前者は比較的効率的であるが、後者は時により良いソリューション品質を達成することができる。 実験により、データから予測行列を学習することは本当に有益であることが示され、既存のランダムな予測よりも解の質が大幅に向上し、LPの解法にかかる時間が大幅に短縮される。

関連論文リスト

• Sparse Gaussian Graphical Models with Discrete Optimization: Computational and Statistical Perspectives [8.403841349300103]
  本研究では,無向ガウス図形モデルに基づくスパースグラフの学習問題を考察する。 擬似微分関数の $ell_0$-penalized バージョンに基づく新しい推定器 GraphL0BnB を提案する。 実/合成データセットに関する数値実験により,本手法がほぼ最適に,p = 104$の問題を解けることが示唆された。
  論文  参考訳（メタデータ） (2023-07-18T15:49:02Z)
• Sparse Linear Centroid-Encoder: A Convex Method for Feature Selection [1.057079240576682]
  本稿では,Sparse Centroid-Encoder (SLCE) を提案する。 このアルゴリズムは線形ネットワークを使用して、ニューラルネットワークを同時に再構築する。
  論文  参考訳（メタデータ） (2023-06-07T23:07:55Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  非PSDおよび2乗根行列の次元削減法を提案する。 複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
  論文  参考訳（メタデータ） (2021-06-16T04:07:48Z)
• Hutch++: Optimal Stochastic Trace Estimation [75.45968495410048]
  我々は、任意の正半定値(PSD)$A$に対して、$(1 pm epsilon)$を$tr(A)$に近似する新しいランダム化アルゴリズムであるHutch++を導入する。 実験ではハッチンソン法を著しく上回る結果を得た。
  論文  参考訳（メタデータ） (2020-10-19T16:45:37Z)
• Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
  ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。 我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-09-30T19:10:32Z)
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping [99.59319332864129]
  本稿では,割引決定(MDP)のための強化学習について検討する。 本稿では,特徴写像を利用した新しいアルゴリズムを提案し,$tilde O(dsqrtT/ (1-gamma)2)$ regretを求める。 以上の結果から,提案した強化学習アルゴリズムは,最大1-γ-0.5$の係数でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-23T17:08:54Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)
• Sketching Transformed Matrices with Applications to Natural Language Processing [76.6222695417524]
  本稿では, 変換行列を用いて, 与えられた小さな行列の積を計算するための空間効率のよいスケッチアルゴリズムを提案する。 提案手法は誤差が小さく,空間と時間の両方で効率がよいことを示す。
  論文  参考訳（メタデータ） (2020-02-23T03:07:31Z)
• Optimal Exact Matrix Completion Under new Parametrization [0.0]
  適応サンプリング法を用いて、$m倍 n$ の階数 $r$ の行列の正確な完備化の問題を研究した。 対象行列を正確に復元する行列補完アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-02-06T18:31:47Z)

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

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