論文の概要: Accelerated Nonnegative Tensor Completion via Integer Programming
- arxiv url: http://arxiv.org/abs/2211.15770v1
- Date: Mon, 28 Nov 2022 21:00:25 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-30 15:35:54.655146
- Title: Accelerated Nonnegative Tensor Completion via Integer Programming
- Title（参考訳）: 整数プログラミングによる加速非負テンソル補完
- Authors: Wenhao Pan, Anil Aswani and Chen Chen
- Abstract要約: 整数計画法に基づく非負のテンソル完備化へのアプローチを提案する。
我々はアルゴリズムと同じ理論的な保証を維持できるいくつかの変種を探索するが、潜在的に高速な計算を提供する。
- 参考スコア（独自算出の注目度）: 7.3149416054553065
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The problem of tensor completion has applications in healthcare, computer
vision, and other domains. However, past approaches to tensor completion have
faced a tension in that they either have polynomial-time computation but
require exponentially more samples than the information-theoretic rate, or they
use fewer samples but require solving NP-hard problems for which there are no
known practical algorithms. A recent approach, based on integer programming,
resolves this tension for nonnegative tensor completion. It achieves the
information-theoretic sample complexity rate and deploys the Blended
Conditional Gradients algorithm, which requires a linear (in numerical
tolerance) number of oracle steps to converge to the global optimum. The
tradeoff in this approach is that, in the worst case, the oracle step requires
solving an integer linear program. Despite this theoretical limitation,
numerical experiments show that this algorithm can, on certain instances, scale
up to 100 million entries while running on a personal computer. The goal of
this paper is to further enhance this algorithm, with the intention to expand
both the breadth and scale of instances that can be solved. We explore several
variants that can maintain the same theoretical guarantees as the algorithm,
but offer potentially faster computation. We consider different data
structures, acceleration of gradient descent steps, and the use of the Blended
Pairwise Conditional Gradients algorithm. We describe the original approach and
these variants, and conduct numerical experiments in order to explore various
tradeoffs in these algorithmic design choices.
- Abstract（参考訳）: テンソル完備化の問題には、医療、コンピュータビジョン、その他の領域への応用がある。
しかし、従来のテンソル完備化へのアプローチは、多項式時間計算を持つが、情報理論速度よりも指数関数的に多くのサンプルを必要とするか、より少ないサンプルを使用するが、既知の実用的なアルゴリズムが存在しないNPハード問題を解く必要があるという緊張に直面している。
整数計画に基づく最近のアプローチは、非負のテンソル完全化に対するこの緊張を解消する。
情報理論的なサンプル複雑性率を達成し、大域的最適に収束するためには、線形(数値的寛容)数のオラクルステップを必要とするBlended Conditional Gradientsアルゴリズムをデプロイする。
このアプローチのトレードオフは、最悪の場合、oracleのステップは整数線形プログラムの解決を必要とすることである。
この理論的な制限にもかかわらず、数値実験により、このアルゴリズムは、ある場合において、パーソナルコンピュータ上で実行中に最大1億のエントリをスケール可能であることが示された。
本稿の目標は,解決可能なインスタンスの広さと規模を拡大することを目的として,このアルゴリズムをさらに強化することである。
我々はアルゴリズムと同じ理論的保証を維持することができるが、より高速な計算を提供するいくつかの変種を探索する。
我々は、異なるデータ構造、勾配降下ステップの加速、Blended Pairwise Conditional Gradientsアルゴリズムの利用について検討する。
提案手法は, アルゴリズム設計の選択において, 様々なトレードオフを探索するために, 数値実験を行うものである。
関連論文リスト
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Tensor Completion via Integer Optimization [7.813563137863005]
テンソル完備化問題の主な課題は、計算力と情報理論サンプルの複雑さ率の基本的な緊張である。
過去のアプローチでは、情報理論の速度を達成するか、対応する解を計算するための実用的なアルゴリズムが欠如していた。
本稿では, 線形数のオラクルステップと情報理論速度で証明可能な収束(数値耐性)を両立させることにより, この緊張を解消する新しいテンソル完備化アルゴリズムを開発する。
論文 参考訳（メタデータ） (2024-02-06T21:44:07Z) - When can you trust feature selection? -- I: A condition-based analysis
of LASSO and generalised hardness of approximation [49.1574468325115]
近似入力を読み取る際に、LASSOのミニミサの正しいサポートセットを(確率$>1/2$で)決定できないことを示す。
不適切な入力の場合、アルゴリズムは永遠に動作するので、間違った答えを出すことはない。
無限条件数を持つ点を含む開集合上で定義される任意のアルゴリズムに対して、アルゴリズムが永久に実行されるか、間違った解を生成するような入力が存在する。
論文 参考訳（メタデータ） (2023-12-18T18:29:01Z) - Quantum Sparse Coding [5.130440339897477]
我々はスパース符号化のための量子インスピレーション付きアルゴリズムを開発した。
量子コンピュータとイジングマシンの出現は、より正確な推定につながる可能性がある。
我々はLightrの量子インスパイアされたデジタルプラットフォーム上でシミュレーションデータを用いて数値実験を行う。
論文 参考訳（メタデータ） (2022-09-08T13:00:30Z) - On efficient algorithms for computing near-best polynomial
approximations to high-dimensional, Hilbert-valued functions from limited
samples [1.0650780147044159]
スパース近似は、限られたサンプルから滑らかで高次元の関数を近似するのに欠かせないものとなっている。
本稿では,指数的あるいは代数的収束率を主張するアルゴリズムと理論的保証と,サンプリング,アルゴリズム的,物理的離散化誤差に対する頑健性を紹介する。
論文 参考訳（メタデータ） (2022-03-25T20:56:07Z) - Nonnegative Tensor Completion via Integer Optimization [5.932152752097064]
我々は,本アルゴリズムが情報理論速度を達成しつつ,線形(数値耐性)なオラクルステップ数に収束することを証明した。
ノルムは0-1ポリトープで定義されるので、これは整数線形計画法を用いてポリトープ上の線形分離問題を解くことができることを意味する。
論文 参考訳（メタデータ） (2021-11-08T15:43:19Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - Refined bounds for algorithm configuration: The knife-edge of dual class
approximability [94.83809668933021]
トレーニングセットが、トレーニングセット上でのパラメータの平均メトリックのパフォーマンスが、予想される将来的なパフォーマンスに最も近いことを保証するために、どの程度の規模が必要かを調査する。
この近似が L-無限ノルムの下で成り立つなら、強いサンプル複雑性境界を与えることができる。
我々は、コンピュータ科学において最も強力なツールの一つである整数プログラミングの文脈において、我々の限界を実証的に評価する。
論文 参考訳（メタデータ） (2020-06-21T15:32:21Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳（メタデータ） (2020-05-09T02:48:23Z) - Stochastic Optimization for Regularized Wasserstein Estimators [10.194798773447879]
ワッサーシュタイン推定器勾配の正規化版を、自然次元のサブ線形なステップ毎の時間で解くアルゴリズムを導入する。
このアルゴリズムは他のタスクにも拡張可能であることを示し、その中にはWasserstein Barycentersの推定も含まれる。
論文 参考訳（メタデータ） (2020-02-20T12:04:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。