論文の概要: Data-Driven Projection for Reducing Dimensionality of Linear Programs:
Generalization Bound and Learning Methods
- arxiv url: http://arxiv.org/abs/2309.00203v2
- Date: Tue, 30 Jan 2024 02:55:08 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-31 19:04:07.109477
- Title: Data-Driven Projection for Reducing Dimensionality of Linear Programs:
Generalization Bound and Learning Methods
- Title（参考訳）: 線形プログラムの次元性低減のためのデータ駆動投影:一般化境界と学習法
- Authors: Shinsaku Sakaue, Taihei Oki
- Abstract要約: 高次元線形プログラム(LP)を効率的に解く方法は根本的な問題である。
近年,テキストラノム投影を用いたLPサイズ削減への関心が高まっている。
本稿では,ランダムなプロジェクションではなく,データから学習したプロジェクション行列を用いた,データ駆動型プロジェクションの新しい方向について検討する。
- 参考スコア（独自算出の注目度）: 27.394532878041694
- 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 \textit{random projections}, which can accelerate solving LPs
independently of improving LP solvers.
In this paper, we explore a new direction of \emph{data-driven projections},
which use projection matrices learned from data instead of random projection
matrices. Given data of past $n$-dimensional LPs, we learn an $n\times k$
projection matrix such that $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 \textit{data-driven algorithm design}, which connects the
amount of data sufficient for establishing generalization bounds to the
\textit{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 natural methods for learning projection
matrices: PCA- and gradient-based methods. While the former is simple and
efficient, the latter can sometimes lead to better solution quality. Our
experiments confirm the practical benefit of learning projection matrices from
data, achieving significantly higher solution quality than the existing random
projection while greatly reducing the time for solving LPs.
- Abstract（参考訳）: 高次元線形プログラム(LP)を効率的に解く方法は根本的な問題である。
近年, LP解法の改良とは無関係に, LPの解法を高速化できる \textit{random projections} を用いたLPサイズ削減への関心が高まっている。
本稿では,ランダムな投影行列ではなく,データから学習した投影行列を用いて,新たな方向を探究する。
過去の$n$-次元LPのデータから、$n > k$となるような$n\times k$プロジェクション行列を学ぶ。
将来のlpインスタンスに対処するとき、その次元を学習された投影行列を介してn$からk$に減らし、得られたlpを解いてk$-次元の解を得、学習された行列をそれに適用してn$-次元の解を回収する。
理論的には、自然の疑問は: 回復したソリューションの品質を保証するのに十分なデータがどれくらいあるか?
この問題は、一般化境界を確立するのに十分なデータ量と、パフォーマンス指標の \textit{pseudo-dimension} を結合する、 \textit{data-driven algorithm design} の枠組みに基づいて解決する。
擬次元上の上界を$\tilde{\mathrm{O}}(nk^2)$とすると、$\tilde{\mathrm{O}}$は対数因子を圧縮する。
また、$\Omega(nk)$ lower bound も提供しており、その結果は $\tilde{\mathrm{O}}(k)$ factor まで厳密であることを意味する。
実用面では,PCA法と勾配法という,投影行列を学習するための2つの自然な手法を探索する。
前者はシンプルで効率的だが、後者は時により良いソリューション品質をもたらすことがある。
実験では,データから投影行列を学習することの実用的利点を確認し,既存のランダム射影よりも高い解質を実現し,lpsの解決に要する時間を大幅に削減した。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。