Subgradient Descent Learns Orthogonal Dictionaries

Abstract

This paper concerns dictionary learning, i.e., sparse coding, a fundamental representation learning problem. We show that a subgradient descent algorithm, with random initialization, can provably recover orthogonal dictionaries on a natural nonsmooth, nonconvex ${\ell }_1$ minimization formulation of the problem, under mild statistical assumptions on the data. This is in contrast to previous provable methods that require either expensive computation or delicate initialization schemes. Our analysis develops several tools for characterizing landscapes of nonsmooth functions, which might be of independent interest for provable training of deep networks with nonsmooth activations (e.g., ReLU), among numerous other applications. Preliminary experiments corroborate our analysis and show that our algorithm works well empirically in recovering orthogonal dictionaries.

References in corpus (6)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Learning One-hidden-layer Neural Networks with Landscape Design
• Simple, Efficient, and Neural Algorithms for Sparse Coding
• Provably Correct Automatic Subdifferentiation for Qualified Programs
• Learning ReLU Networks via Alternating Minimization
• Nonconvex Robust Low-rank Matrix Recovery

Cited by in corpus (14)

• From Symmetry to Geometry: Tractable Nonconvex Problems
• Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements
• Weakly Convex Optimization over Stiefel Manifold Using Riemannian Subgradient-Type Methods
• Blind Data Detection in Massive MIMO via ${\ell }_3$-norm Maximization over the Stiefel Manifold
• Complete Dictionary Learning via ${\ell }_p$-norm Maximization
• Complete Dictionary Learning via ${\ell }^4$-Norm Maximization over the Orthogonal Group
• Nonconvex Robust Low-rank Matrix Recovery
• Efficient Sparse Coding using Hierarchical Riemannian Pursuit
• Riemannian Perspective on Matrix Factorization
• Manifold Gradient Descent Solves Multi-Channel Sparse Blind Deconvolution Provably and Efficiently
• Manifold Proximal Point Algorithms for Dual Principal Component Pursuit and Orthogonal Dictionary Learning
• Multichannel Sparse Blind Deconvolution on the Sphere
• Sign-RIP: A Robust Restricted Isometry Property for Low-rank Matrix Recovery
• Stochastic Approximation for Online Tensorial Independent Component Analysis