論文の概要: Efficient Projection Algorithms onto the Weighted l1 Ball

• arxiv url: http://arxiv.org/abs/2009.02980v1
• Date: Mon, 7 Sep 2020 09:48:21 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-21 02:03:50.978279
• Title: Efficient Projection Algorithms onto the Weighted l1 Ball
• Title（参考訳）: 重み付きl1ボールへの効率的な投影アルゴリズム
• Authors: Guillaume Perez, Sebastian Ament, Carla Gomes, Michel Barlaud
• Abstract要約: 予測勾配降下は、多くの最適化や機械学習問題において効率的であることが証明されている。 重み付き $ell_1$ 球に有限長ベクトルを射影する3つの新しいアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 6.90115934143092
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Projected gradient descent has been proved efficient in many optimization and machine learning problems. The weighted $\ell_1$ ball has been shown effective in sparse system identification and features selection. In this paper we propose three new efficient algorithms for projecting any vector of finite length onto the weighted $\ell_1$ ball. The first two algorithms have a linear worst case complexity. The third one has a highly competitive performances in practice but the worst case has a quadratic complexity. These new algorithms are efficient tools for machine learning methods based on projected gradient descent such as compress sensing, feature selection. We illustrate this effectiveness by adapting an efficient compress sensing algorithm to weighted projections. We demonstrate the efficiency of our new algorithms on benchmarks using very large vectors. For instance, it requires only 8 ms, on an Intel I7 3rd generation, for projecting vectors of size $10^7$.
• Abstract（参考訳）: 予測勾配降下は、多くの最適化や機械学習問題において効率的であることが証明されている。 重み付き$\ell_1$ボールはスパースシステムの識別と特徴選択に有効であることが示されている。 本稿では,有限長ベクトルを重み付き$\ell_1$球に射影する3つの新しいアルゴリズムを提案する。 最初の2つのアルゴリズムは、線形最悪のケースの複雑さを持つ。 第3のケースは、実際には競争の激しいパフォーマンスですが、最悪のケースは二次的な複雑さがあります。 これらのアルゴリズムは,圧縮センシングや特徴選択といった予測勾配勾配に基づく機械学習手法の効率的なツールである。 重み付き投影に効率的な圧縮センシングアルゴリズムを適用することで,この効果を示す。 超大規模ベクトルを用いたベンチマークによる新しいアルゴリズムの有効性を実証する。 例えば、Intel I7 3世代では10^7$のベクトルを投影するのに8ミリ秒しか必要としない。

関連論文リスト

• Fundamental Machine Learning Routines as Quantum Algorithms on a Superconducting Quantum Computer [0.0]
  Harrow-Hassidim-Lloydアルゴリズムは、量子デバイス上の線形方程式のシステムを解くことを目的としている。 本稿では,これらの特徴が完全に一致しない場合のアルゴリズムの性能に関する数値的研究を行う。
  論文  参考訳（メタデータ） (2021-09-17T15:22:06Z)
• Choosing the Right Algorithm With Hints From Complexity Theory [16.33500498939925]
  我々は,メトロポリスのアルゴリズムが,合理的な問題サイズを考慮に入れた全てのアルゴリズムの中で,明らかに最良のものであることを示す。 このタイプの人工アルゴリズムは、$O(n log n)$ランタイムを持つので、重要度に基づくコンパクト遺伝的アルゴリズム(sig-cGA)は、高い確率で、DLB問題を解くことができる。
  論文  参考訳（メタデータ） (2021-09-14T11:12:32Z)
• RAMA: A Rapid Multicut Algorithm on GPU [23.281726932718232]
  本稿では,マルチカット問題(マグニチュード相関クラスタリング)に対する高並列原始双対アルゴリズムを提案する。 我々のアルゴリズムは、最適距離を推定する原始解と双対下界を生成する。 最大$mathcalO(108)$変数を数秒で、小さな原始双対ギャップで、非常に大規模なベンチマーク問題を解くことができる。
  論文  参考訳（メタデータ） (2021-09-04T10:33:59Z)
• BiAdam: Fast Adaptive Bilevel Optimization Methods [104.96004056928474]
  バイレベル最適化は多くの応用のために機械学習への関心が高まっている。 制約付き最適化と制約なし最適化の両方に有用な分析フレームワークを提供する。
  論文  参考訳（メタデータ） (2021-06-21T20:16:40Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。 我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
  論文  参考訳（メタデータ） (2021-03-04T19:01:20Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Kernel methods through the roof: handling billions of points efficiently [94.31450736250918]
  カーネル法は、非パラメトリック学習に対するエレガントで原則化されたアプローチを提供するが、今のところ大規模な問題ではほとんど利用できない。 最近の進歩は、最適化、数値線形代数、ランダム射影など、多くのアルゴリズム的アイデアの利点を示している。 ここでは、これらの取り組みをさらに進めて、GPUハードウェアを最大限に活用する解決器を開発し、テストする。
  論文  参考訳（メタデータ） (2020-06-18T08:16:25Z)

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

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