論文の概要: Simple Alternating Minimization Provably Solves Complete Dictionary Learning

• arxiv url: http://arxiv.org/abs/2210.12816v1
• Date: Sun, 23 Oct 2022 18:30:45 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-25 22:11:47.888766
• Title: Simple Alternating Minimization Provably Solves Complete Dictionary Learning
• Title（参考訳）: 辞書学習の完全性を保証する簡易交互最小化
• Authors: Geyu Liang, Gavin Zhang, Salar Fattahi, Richard Y. Zhang
• Abstract要約: 本稿では、与えられた信号の集合を学習辞書からの原子の線形結合として再パラメータ化することを目的とする完全な辞書問題に焦点を当てる。 理論的および実践的な辞書学習には、実用的なアルゴリズムに対する理論的保証の欠如と、大規模データセットを扱う際のスケーラビリティの低下という2つの大きな課題がある。
• 参考スコア（独自算出の注目度）: 13.056764072568749
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper focuses on complete dictionary learning problem, where the goal is to reparametrize a set of given signals as linear combinations of atoms from a learned dictionary. There are two main challenges faced by theoretical and practical studies of dictionary learning: the lack of theoretical guarantees for practically-used heuristic algorithms, and their poor scalability when dealing with huge-scale datasets. Towards addressing these issues, we show that when the dictionary to be learned is orthogonal, that an alternating minimization method directly applied to the nonconvex and discrete formulation of the problem exactly recovers the ground truth. For the huge-scale, potentially online setting, we propose a minibatch version of our algorithm, which can provably learn a complete dictionary from a huge-scale dataset with minimal sample complexity, linear sparsity level, and linear convergence rate, thereby negating the need for any convex relaxation for the problem. Our numerical experiments showcase the superiority of our method compared with the existing techniques when applied to tasks on real data.
• Abstract（参考訳）: 本稿では、与えられた信号の集合を学習辞書から線形結合として再パラメータ化することを目的とする完全な辞書学習問題に焦点を当てる。 辞書学習の理論的および実践的な研究には、実用的なヒューリスティックアルゴリズムの理論的保証の欠如と、大規模なデータセットを扱う際のスケーラビリティの低下という2つの大きな課題がある。 これらの問題に対処するために,学習すべき辞書が直交している場合,問題の非凸および離散的定式化に直接適用される交互最小化法が基底真理を正確に回復することを示す。 大規模かつ潜在的にオンラインな設定のために,本アルゴリズムのミニバッチ版を提案する。サンプル複雑性,線形スパーシティレベル,線形収束率を最小とした大規模データセットから完全な辞書を学習できるため,この問題に対する凸緩和の必要性を否定できる。 実データに対するタスクに適用した場合の既存手法と比較して,提案手法の優越性を示す数値実験を行った。

関連論文リスト

• MaxMatch: Semi-Supervised Learning with Worst-Case Consistency [149.03760479533855]
  半教師付き学習(SSL)のための最悪ケース整合正則化手法を提案する。 本稿では,ラベル付きトレーニングデータとラベル付きトレーニングデータとを別々に比較した経験的損失項からなるSSLの一般化について述べる。 この境界によって動機づけられたSSLの目的は、元のラベルのないサンプルと、その複数の拡張版との最大の矛盾を最小限に抑えるものである。
  論文  参考訳（メタデータ） (2022-09-26T12:04:49Z)
• New Tight Relaxations of Rank Minimization for Multi-Task Learning [161.23314844751556]
  2つの正規化項に基づく2つの新しいマルチタスク学習定式化を提案する。 本手法は,タスク間で共有される低ランク構造を正確に復元し,関連するマルチタスク学習方法より優れていることを示す。
  論文  参考訳（メタデータ） (2021-12-09T07:29:57Z)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。 オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。 本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
  論文  参考訳（メタデータ） (2021-11-23T18:10:48Z)
• Dictionary Learning Using Rank-One Atomic Decomposition (ROAD) [6.367823813868024]
  辞書学習は、訓練データを疎に表現できる辞書を求めることを目的としている。 Roadは、合成データと実データの両方で、他のベンチマークアルゴリズムより優れている。
  論文  参考訳（メタデータ） (2021-10-25T10:29:52Z)
• Label-Descriptive Patterns and their Application to Characterizing Classification Errors [31.272875287136426]
  最先端のディープラーニング手法は多くのタスクで人間のようなパフォーマンスを達成するが、それでもエラーを犯す。 これらのエラーを容易に解釈可能な言葉で特徴付けることは、モデルが体系的なエラーを起こす傾向にあるかどうかの洞察を与えるだけでなく、モデルを実行し改善する方法を与える。 本稿では,予測の正しさに応じて分割された入力データを簡潔に記述するパターンの小さなセットをマイニングすることにより,任意の分類器に対して,任意の分類を行うことができる手法を提案する。
  論文  参考訳（メタデータ） (2021-10-18T19:42:21Z)
• Information-Theoretic Generalization Bounds for Iterative Semi-Supervised Learning [81.1071978288003]
  特に,情報理論の原理を用いて,反復型SSLアルゴリズムのエミュレータ一般化誤差の振る舞いを理解することを目的とする。 我々の理論的結果は、クラス条件分散があまり大きくない場合、一般化誤差の上限は反復数とともに単調に減少するが、すぐに飽和することを示している。
  論文  参考訳（メタデータ） (2021-10-03T05:38:49Z)
• PUDLE: Implicit Acceleration of Dictionary Learning by Backpropagation [4.081440927534577]
  本稿では,PUDLE(Provable Unfolded Dictionary LEarning)による実験結果に関する最初の理論的証明を提供する。 我々は、損失の最小化、展開、収束のバックプロパゲーションについて強調する。 合成および画像復号化実験により,本研究の成果を補完する。
  論文  参考訳（メタデータ） (2021-05-31T18:49:58Z)
• Online Orthogonal Dictionary Learning Based on Frank-Wolfe Method [3.198144010381572]
  辞書学習は信号処理や機械学習で広く使われている教師なし学習手法である。 提案手法は,新しい問題定式化と収束解析を用いた効率的なオンラインアルゴリズム設計を含む。 合成データと実世界のセンサ読み取り実験により,提案手法の有効性と有効性を示す。
  論文  参考訳（メタデータ） (2021-03-02T05:49:23Z)
• Semi-Supervised Learning with Meta-Gradient [123.26748223837802]
  半教師付き学習における簡単なメタ学習アルゴリズムを提案する。 その結果,提案アルゴリズムは最先端の手法に対して良好に動作することがわかった。
  論文  参考訳（メタデータ） (2020-07-08T08:48:56Z)
• Good Classifiers are Abundant in the Interpolating Regime [64.72044662855612]
  補間分類器間のテストエラーの完全な分布を正確に計算する手法を開発した。 テストエラーは、最悪の補間モデルのテストエラーから大きく逸脱する、小さな典型的な$varepsilon*$に集中する傾向にある。 以上の結果から,統計的学習理論における通常の解析手法は,実際に観測された優れた一般化性能を捉えるのに十分な粒度にはならない可能性が示唆された。
  論文  参考訳（メタデータ） (2020-06-22T21:12:31Z)

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

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