論文の概要: Data-Driven Projection for Reducing Dimensionality of Linear Programs: Generalization Bound and Learning Methods

• arxiv url: http://arxiv.org/abs/2309.00203v1
• Date: Fri, 1 Sep 2023 01:44:57 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-04 14:51:57.140229
• Title: Data-Driven Projection for Reducing Dimensionality of Linear Programs: Generalization Bound and Learning Methods
• Title（参考訳）: 線形プログラムの次元性低減のためのデータ駆動投影:一般化境界と学習法
• Authors: Shinsaku Sakaue, Taihei Oki
• Abstract要約: 本稿では,高次元線形プログラム(LP)に対する単純なデータ駆動型アプローチについて検討する。 我々は$ntimes k$ textitprojection matrixを学び、これは次元を$n$から$k$に減らす。 次に、$k$-dimensional LPを解き、プロジェクション行列を乗算して$n$-dimensional の解を復元することにより、将来のLPインスタンスに対処する。
• 参考スコア（独自算出の注目度）: 27.394532878041694
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper studies a simple data-driven approach to high-dimensional linear programs (LPs). Given data of past $n$-dimensional LPs, we learn an $n\times k$ \textit{projection matrix} ($n > k$), which reduces the dimensionality from $n$ to $k$. Then, we address future LP instances by solving $k$-dimensional LPs and recovering $n$-dimensional solutions by multiplying the projection matrix. This idea is compatible with any user-preferred LP solvers, hence a versatile approach to faster LP solving. One natural question is: how much data is sufficient to ensure the recovered solutions' quality? We address this question based on the idea of \textit{data-driven algorithm design}, which relates the amount of data sufficient for generalization guarantees to the \textit{pseudo-dimension} of performance metrics. We present an $\tilde{\mathrm{O}}(nk^2)$ upper bound on the pseudo-dimension ($\tilde{\mathrm{O}}$ compresses logarithmic factors) and complement it by an $\Omega(nk)$ lower bound, hence tight up to an $\tilde{\mathrm{O}}(k)$ factor. On the practical side, we study two natural methods for learning projection matrices: PCA- and gradient-based methods. While the former is simple and efficient, the latter sometimes leads to better solution quality. Experiments confirm that learned projection matrices are beneficial for reducing the time for solving LPs while maintaining high solution quality.
• Abstract（参考訳）: 本稿では,高次元線形プログラム(LP)に対する単純なデータ駆動型アプローチについて検討する。 過去の$n$-次元LPのデータから、$n\times k$ \textit{projection matrix} (n > k$)を学ぶと、次元は$n$から$k$に減少する。 次に、$k$-dimensional LPを解き、プロジェクション行列を乗算して$n$-dimensional の解を復元することにより、将来のLPインスタンスに対処する。 このアイデアは、ユーザ優先のLPソルバと互換性があり、高速LPソルバに対する汎用的なアプローチである。 1つの自然な疑問は、回復したソリューションの品質を保証するのに十分なデータ量である。 この問題は、一般化保証に十分なデータの量と性能指標の \textit{pseudo-dimension} を関連づける、 \textit{data-driven algorithm design} という考え方に基づいている。 擬似次元上の$\tilde{\mathrm{o}}(nk^2)$アッパーバウンド(\tilde{\mathrm{o}}$ 対数因子を圧縮する)を示し、$\omega(nk)$ の下限で補完する。 実用面では,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)

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

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