Research map / Learning theory and algorithms / Sample complexity
The Generalization Error of Dictionary Learning with Moreau Envelopes
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Remove the spurious coherence (incoherence) assumption on the dictionary D from prior k-sparse sample complexity analysis by using VC-theory shatter coefficient bounds instead of deterministic epsilon-nets | k-sparse dictionary learning generalization bound (indicator of k-sparse vectors with Moreau envelope loss) · theoretical bound over all unit-norm-column dictionaries | generalization bound order | Helped |
| Extend Moreau-envelope loss analysis to bounded lower semicontinuous regularizers (e.g., SCAD, MCP) via VC theory, giving uniform convergence and O(sqrt(log n / n)) rate | bounded lsc penalties g (SCAD, MCP, k-sparse indicator) · theoretical generalization bound | generalization bound order | Helped |
| Use continuous strictly increasing separable penalty g with Moreau envelope loss; the Lipschitz-based proof yields a log(d) factor (O(sqrt(log(nd)/n))) rather than the optimal rate | separable strictly increasing g · theoretical generalization bound | generalization bound order | Mixed |
| Apply the Lemma 2 refinement to remove the log(d) term at the cost of a strict sample-size condition | separable strictly increasing g bound · theoretical generalization bound | generalization bound order | Mixed |
| Restrict to the continuous bounded penalty case (MCP/SCAD) via assumption (29) rather than general continuous bounded penalties | MCP penalty with l0 Moreau envelope · theoretical generalization bound | validity of UCEM property | Hurt |
Closest papers by meaning
- Alternating minimization for dictionary learning with random initialization (NeurIPS 2017 · similarity 0.88)
- Global Identifiability of Overcomplete Dictionary Learning via L1 and Volume Minimization (ICLR 2025 · similarity 0.88)
- Global Identifiability of $\ell_1$-based Dictionary Learning via Matrix Volume Optimization (NeurIPS 2023 · similarity 0.88)
- A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Models (NeurIPS 2022 · similarity 0.87)
- On Learning Sparsely Used Dictionaries from Incomplete Samples (ICML 2018 · similarity 0.86)
- On the Sparsity-Storage-Accuracy Tradeoff in Parsimoniously Activated Dictionary Learning (NeurIPS 2026 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.