論文の概要: Sparse Optimization on General Atomic Sets: Greedy and Forward-Backward Algorithms

• arxiv url: http://arxiv.org/abs/1912.11931v1
• Date: Thu, 26 Dec 2019 20:52:40 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-10 07:59:59.145973
• Title: Sparse Optimization on General Atomic Sets: Greedy and Forward-Backward Algorithms
• Title（参考訳）: 一般原子集合のスパース最適化:GreedyとForward-Backwardアルゴリズム
• Authors: Thomas Zhang
• Abstract要約: 我々は, 疎性を維持しつつ, 強近似保証を達成できることを, 欲求アルゴリズムが示す。 特に、多くの興味のある設定において、グレディアルゴリズムは、疎性を維持しながら強い近似を保証することができることを示す。 第二に、弱部分モジュラー性という別の概念を定義し、より親しみやすいバージョンと密接に関連していることが示される。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of sparse atomic optimization, where the notion of "sparsity" is generalized to meaning some linear combination of few atoms. The definition of atomic set is very broad; popular examples include the standard basis, low-rank matrices, overcomplete dictionaries, permutation matrices, orthogonal matrices, etc. The model of sparse atomic optimization therefore includes problems coming from many fields, including statistics, signal processing, machine learning, computer vision and so on. Specifically, we consider the problem of maximizing a restricted strongly convex (or concave), smooth function restricted to a sparse linear combination of atoms. We extend recent work that establish linear convergence rates of greedy algorithms on restricted strongly concave, smooth functions on sparse vectors to the realm of general atomic sets, where the convergence rate involves a novel quantity: the "sparse atomic condition number". This leads to the strongest known multiplicative approximation guarantees for various flavors of greedy algorithms for sparse atomic optimization; in particular, we show that in many settings of interest the greedy algorithm can attain strong approximation guarantees while maintaining sparsity. Furthermore, we introduce a scheme for forward-backward algorithms that achieves the same approximation guarantees. Secondly, we define an alternate notion of weak submodularity, which we show is tightly related to the more familiar version that has been used to prove earlier linear convergence rates. We prove analogous multiplicative approximation guarantees using this alternate weak submodularity, and establish its distinct identity and applications.
• Abstract（参考訳）: スパース原子最適化の問題を考えると、「スパーシティ」という概念は、少数の原子の線形結合を意味するために一般化される。 原子集合の定義は非常に広く、一般的な例としては、標準基底、低ランク行列、過剰完全辞書、置換行列、直交行列などがある。 したがって、スパース原子最適化のモデルは、統計学、信号処理、機械学習、コンピュータビジョンなど、多くの分野から生じる問題を含む。 具体的には、制限された強い凸(または凹凸)を最大化する問題を考える。 我々は、制限された強凹凸上のグリーディアルゴリズムの線形収束率、スパースベクトル上の滑らかな関数を一般原子集合の領域に確立する最近の研究を拡張し、収束率は新しい量を含む:「スパース原子状態数」である。 このことは、スパース原子最適化のための様々なグリーディアルゴリズムのフレーバーに対する最強の乗法近似を保証することにつながるが、特に、多くの興味のある設定において、このグリーディアルゴリズムは疎性を維持しながら強い近似を保証することができることを示す。 さらに,同じ近似保証を実現する前向きアルゴリズムのスキームを導入する。 第二に, 弱部分モジュラリティの代替概念を定め, 従来の線形収束率の証明に用いられてきたより親しみやすいバージョンと密接な関係があることを示した。 この代替的な弱部分モジュラリティを用いて類似の乗法近似の保証を証明し、その特異性と応用性を確立する。

関連論文リスト

• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• A fast Multiplicative Updates algorithm for Non-negative Matrix Factorization [2.646309221150203]
  本稿では,各サブプロブレムに対してヘッセン行列のより厳密な上界を構築することにより,乗法更新アルゴリズムの改善を提案する。 コンバージェンスはまだ保証されており、我々は実際に合成と実世界の両方のデータセットで、提案したfastMUアルゴリズムが通常の乗算更新アルゴリズムよりも数桁高速であることを示す。
  論文  参考訳（メタデータ） (2023-03-31T12:09:36Z)
• Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
  本稿では,初期監視情報を同時に拡張し,識別親和性行列を構築することのできる,新しい半教師付きサブスペースクラスタリング手法を提案する。 6つの一般的なベンチマークデータセットの総合的な実験結果から,本手法が最先端手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-05-21T01:47:17Z)
• Infinite-Dimensional Sparse Learning in Linear System Identification [0.2867517731896504]
  本稿では,原子ノルム正規化に基づく無限次元スパース学習アルゴリズムを提案する。 この問題の解決の難しさは、無限の原子モデルが存在するという事実にある。
  論文  参考訳（メタデータ） (2022-03-28T13:18:48Z)
• Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
  ヒルベルト空間全体の部分空間への発展を制限する混合作用素を構築するための枠組みを提案する。 我々は,「ワンホット」状態の部分空間を保存するために設計された「XY」ミキサーを,多くの計算基底状態によって与えられる部分空間の一般の場合に一般化する。 我々の分析は、現在知られているよりもCXゲートが少ない"XY"ミキサーのトロタライズも有効である。
  論文  参考訳（メタデータ） (2022-03-11T17:19:26Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。 そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-30T19:17:35Z)
• Nonlinear matrix recovery using optimization on the Grassmann manifold [18.655422834567577]
  本研究では,列が部分空間の結合などの非線形構造に従う部分観測された高階クラスタリング行列の復元問題について検討する。 交代極限はクルディカ・ロジャシ性質を用いて一意点に収束することを示す。
  論文  参考訳（メタデータ） (2021-09-13T16:13:13Z)
• Provably Convergent Working Set Algorithm for Non-Convex Regularized Regression [0.0]
  本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。 その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
  論文  参考訳（メタデータ） (2020-06-24T07:40:31Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  最小二乗問題に対する反復スケッチの性能について検討する。 本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。 これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
  論文  参考訳（メタデータ） (2020-02-03T16:17:50Z)

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

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