論文の概要: Faster Maximum Feasible Subsystem Solutions for Dense Constraint Matrices

• arxiv url: http://arxiv.org/abs/2102.05744v1
• Date: Wed, 10 Feb 2021 21:26:27 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-12 14:05:00.601196
• Title: Faster Maximum Feasible Subsystem Solutions for Dense Constraint Matrices
• Title（参考訳）: 密制約行列に対する高速最大実現可能サブシステム解
• Authors: Fereshteh Fakhar Firouzeh, John W. Chinneck, Sreeraman Rajan
• Abstract要約: Max Feasible Subsystem 問題は、機械学習や圧縮センシングといった幅広い応用において重要である。 厳密な制約行列の場合,既存のFSを拡張して,解の品質を維持したり改善したりしながら,その速度を大幅に向上させる。 圧縮センシングにおける二項分類とスパースリカバリ(sparse recovery)という,密度制約行列を持つ2つのアプリケーション上で,拡張アルゴリズムを検証した。
• 参考スコア（独自算出の注目度）: 0.2578242050187029
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Finding the largest cardinality feasible subset of an infeasible set of linear constraints is the Maximum Feasible Subsystem problem (MAX FS). Solving this problem is crucial in a wide range of applications such as machine learning and compressive sensing. Although MAX FS is NP-hard, useful heuristic algorithms exist, but these can be slow for large problems. We extend the existing heuristics for the case of dense constraint matrices to greatly increase their speed while preserving or improving solution quality. We test the extended algorithms on two applications that have dense constraint matrices: binary classification, and sparse recovery in compressive sensing. In both cases, speed is greatly increased with no loss of accuracy.
• Abstract（参考訳）: 線形制約の不可能集合の最大のカーディナリティ実現可能なサブセットを見つけることは、最大実現可能なサブシステム問題(MAX FS)である。 この問題を解決することは、機械学習や圧縮センシングなど、幅広いアプリケーションにおいて不可欠である。 MAX FSはNPハードであるが、有用なヒューリスティックアルゴリズムが存在するが、大きな問題では遅い。 我々は,厳密な制約行列の場合の既存のヒューリスティックスを拡張し,解の品質を維持したり改善したりしながら,その速度を大幅に向上させる。 重み付き制約行列を持つ2つのアプリケーションで拡張アルゴリズムをテストする:バイナリ分類と圧縮センシングにおけるスパース回復。 どちらの場合も、精度を損なわずに速度が大幅に向上します。

関連論文リスト

• Accelerated First-Order Optimization under Nonlinear Constraints [97.16266088683061]
  制約付きFrankWolf-e-eに対して,高速化された1次アルゴリズムの新たなクラスを設計する。 これらのアルゴリズムの重要な性質は制約の数である。 我々は,非制約を効率的に扱えるとともに,最先端のパフォーマンスを$ellp1$で回復できることを示す。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• An Inexact Feasible Quantum Interior Point Method for Linearly Constrained Quadratic Optimization [0.0]
  量子線形システムアルゴリズム(QLSA)は、線形システムの解法に依存するアルゴリズムを高速化する可能性がある。 本研究では, 線形制約付き2次最適化問題の解法において, 実効性のないQIPM(Inexact-Feasible QIPM)を提案する。
  論文  参考訳（メタデータ） (2023-01-13T01:36:13Z)
• Multi-block Min-max Bilevel Optimization with Applications in Multi-task Deep AUC Maximization [36.743632418094]
  マルチブロックのmin-max双レベル最適化問題に対処するシングルループアルゴリズムを提案する。 我々のアルゴリズムは数百のタスクで問題に取り組むのに利用できることを示す。
  論文  参考訳（メタデータ） (2022-06-01T06:42:36Z)
• Block-coordinate Frank-Wolfe algorithm and convergence analysis for semi-relaxed optimal transport problem [20.661025590877774]
  凸半緩和最適輸送(OT)問題に対する高速ブロックコーディネートFrank-Wolfe (BCFW) アルゴリズムを提案する。 数値実験により,提案アルゴリズムはカラー転送に有効であり,最先端のアルゴリズムを超越することを示した。
  論文  参考訳（メタデータ） (2022-05-27T05:54:45Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。 量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。 提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
  論文  参考訳（メタデータ） (2022-05-24T03:49:10Z)
• A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm for Bilevel Optimization [112.59170319105971]
  問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。 MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
  論文  参考訳（メタデータ） (2021-02-15T07:10:33Z)
• The limits of min-max optimization algorithms: convergence to spurious non-critical sets [82.74514886461257]
  min-max最適化アルゴリズムは周期サイクルや同様の現象が存在するため、はるかに大きな問題に遭遇する。 問題のどの点も引き付けないアルゴリズムが存在することを示す。 ほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほとんどである。
  論文  参考訳（メタデータ） (2020-06-16T10:49:27Z)
• Multi-Objective Matrix Normalization for Fine-grained Visual Recognition [153.49014114484424]
  双線形プールは細粒度視覚認識(FGVC)において大きな成功を収める 近年,行列パワー正規化は双線形特徴量において2次情報を安定化させることができることが示されている。 両線形表現を同時に正規化できる効率的な多目的行列正規化法(MOMN)を提案する。
  論文  参考訳（メタデータ） (2020-03-30T08:40:35Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)

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

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