論文の概要: Best Principal Submatrix Selection for the Maximum Entropy Sampling
Problem: Scalable Algorithms and Performance Guarantees
- arxiv url: http://arxiv.org/abs/2001.08537v2
- Date: Fri, 1 Oct 2021 17:45:51 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-07 12:47:10.972546
- Title: Best Principal Submatrix Selection for the Maximum Entropy Sampling
Problem: Scalable Algorithms and Performance Guarantees
- Title（参考訳）: 最大エントロピーサンプリング問題に対する最適部分行列選択:スケーラブルアルゴリズムと性能保証
- Authors: Yongchun Li, Weijun Xie
- Abstract要約: MESPは医療、電力システム、製造業、データサイエンスなど、多くの分野に広く応用されている。
我々はMESPのための新しい凸整数プログラムを導出し、その連続緩和がほぼ最適解をもたらすことを示す。
数値実験により,これらの近似アルゴリズムは,中規模および大規模のインスタンスをほぼ最適に効率的に解けることを示した。
- 参考スコア（独自算出の注目度）: 1.7640556247739623
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper studies a classic maximum entropy sampling problem (MESP), which
aims to select the most informative principal submatrix of a prespecified size
from a covariance matrix. MESP has been widely applied to many areas, including
healthcare, power system, manufacturing and data science. By investigating its
Lagrangian dual and primal characterization, we derive a novel convex integer
program for MESP and show that its continuous relaxation yields a near-optimal
solution. The results motivate us to study an efficient sampling algorithm and
develop its approximation bound for MESP, which improves the best-known bound
in literature. We then provide an efficient deterministic implementation of the
sampling algorithm with the same approximation bound. By developing new
mathematical tools for the singular matrices and analyzing the Lagrangian dual
of the proposed convex integer program, we investigate the widely-used local
search algorithm and prove its first-known approximation bound for MESP. The
proof techniques further inspire us with an efficient implementation of the
local search algorithm. Our numerical experiments demonstrate that these
approximation algorithms can efficiently solve medium-sized and large-scale
instances to near-optimality. Our proposed algorithms are coded and released as
open-source software. Finally, we extend the analyses to the A-Optimal MESP
(A-MESP), where the objective is to minimize the trace of the inverse of the
selected principal submatrix.
- Abstract（参考訳）: 本稿では,共分散行列から所定のサイズの最も有益な主部分行列を選択することを目的とした,古典的最大エントロピーサンプリング問題(mesp)について述べる。
MESPは医療、電力システム、製造、データサイエンスなど多くの分野に広く応用されている。
ラグランジアン双対と原始的性質を調べることにより、MESPのための新しい凸整数プログラムを導出し、その連続緩和がほぼ最適解をもたらすことを示す。
その結果, 効率的なサンプリングアルゴリズムの研究とMESPの近似法の開発が動機となり, 文献の最もよく知られた境界を改良する。
そして、同じ近似境界を持つサンプリングアルゴリズムの効率的な決定論的実装を提供する。
特異行列の新しい数学的ツールを開発し,提案した凸整数プログラムのラグランジアン双対を解析することにより,広く使われている局所探索アルゴリズムを検証し,MESPに対する最初の近似を証明した。
証明手法は局所探索アルゴリズムの効率的な実装にさらに刺激を与えてくれる。
数値実験により,これらの近似アルゴリズムは,中規模および大規模インスタンスをほぼ最適に効率的に解けることを示した。
提案アルゴリズムは,オープンソースソフトウェアとして実装・リリースされている。
最後に、分析をA-Optimal MESP(A-MESP)に拡張し、選択された主部分行列の逆のトレースを最小限にすることを目的とする。
関連論文リスト
- Federated Conditional Stochastic Optimization [110.513884892319]
条件付き最適化は、不変学習タスク、AUPRC、AMLなど、幅広い機械学習タスクで見られる。
本稿では,分散フェデレーション学習のためのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-10-04T01:47:37Z) - Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and
Optimal Algorithms [64.10576998630981]
最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。
ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。
本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
論文 参考訳（メタデータ） (2023-06-21T17:03:22Z) - Representation Learning with Multi-Step Inverse Kinematics: An Efficient
and Optimal Approach to Rich-Observation RL [106.82295532402335]
既存の強化学習アルゴリズムは、計算的難易度、強い統計的仮定、最適なサンプルの複雑さに悩まされている。
所望の精度レベルに対して、レート最適サンプル複雑性を実現するための、最初の計算効率の良いアルゴリズムを提供する。
我々のアルゴリズムMusIKは、多段階の逆運動学に基づく表現学習と体系的な探索を組み合わせる。
論文 参考訳（メタデータ） (2023-04-12T14:51:47Z) - Optimizing Objective Functions from Trained ReLU Neural Networks via
Sampling [0.0]
本稿では、ReLUアクティベーションを用いたトレーニングニューラルネットワークを最適化する、スケーラブルでサンプリングベースのアルゴリズムを提案する。
本稿ではまず,ReLUニューラルネットワークのピースワイズ線形構造を利用した反復アルゴリズムを提案する。
次に、各反復で計算されたLPソリューションの近傍を探索することで、このアプローチを拡張します。
論文 参考訳（メタデータ） (2022-05-27T18:35:48Z) - Variational Quantum Algorithms for Semidefinite Programming [3.481985817302898]
半定値プログラム(SDP)は、操作研究、最適化、量子情報科学などにおける凸最適化問題である。
本稿では,SDPを近似的に解くための変分量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-12-16T13:10:48Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Multi-View Spectral Clustering with High-Order Optimal Neighborhood
Laplacian Matrix [57.11971786407279]
マルチビュースペクトルクラスタリングは、データ間の固有のクラスタ構造を効果的に明らかにすることができる。
本稿では,高次最適近傍ラプラシア行列を学習するマルチビュースペクトルクラスタリングアルゴリズムを提案する。
提案アルゴリズムは, 1次ベースと高次ベースの両方の線形結合の近傍を探索し, 最適ラプラシア行列を生成する。
論文 参考訳（メタデータ） (2020-08-31T12:28:40Z) - Exact and Approximation Algorithms for Sparse PCA [1.7640556247739623]
本稿では,MISDP(MISDP)とMISDP(MISDP)について述べる。
次に、それらの連続緩和値の理論的最適性ギャップを分析し、それらが最先端の値よりも強いことを証明する。
市販の解法は一般にMISDPを解くのが難しいため,MISDPと同等の大きさのMILP(mixed-integer linear program)を用いてSPCAを任意の精度で近似する。
論文 参考訳（メタデータ） (2020-08-28T02:07:08Z) - A Riemannian Primal-dual Algorithm Based on Proximal Operator and its
Application in Metric Learning [3.511851311025242]
一次変数と双対変数を反復的に最適化する原始双対アルゴリズムを提案する。
提案アルゴリズムの収束を証明し,その非漸近収束率を示す。
ファンドマネージメントにおける最適ファンド選択問題に関する予備実験の結果,有効性が確認された。
論文 参考訳（メタデータ） (2020-05-19T03:31:01Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。