Abstract
Nowadays machine learning tasks deal with sheer volumes of data a possibly incomplete, decentralized, and streaming nature that necessitate on-the-fly processing for real-time decision making. Conventional inference analytics mine such "Big Data" by leveraging their intrinsic parsimony, e.g., via models that include rank sparsity regularization or priors. Convex nuclear and ? 1-norm surrogates are typically adopted and offer well-documented guarantees in recovering informative low-dimensional structure from high-dimensional data. However, the computational complexity of the resulting algorithms tends to scale poorly due to the nuclear norms entangled structure, which also hinders streaming and decentralized analytics. To overcome this computational challenge, this chapter discusses a framework that leverages a bilinear characterization of the nuclear norm to bring separability at the expense of nonconvexity. This challenge notwithstanding, under mild conditions stationary points of the nonconvex program provably coincide with the optimum of the convex counterpart. Using this idea along with the theory of alternating minimization, lightweight algorithms are developed with low communication overhead for in-network processing. Provably convergent online subspace trackers that are suitable for streaming analytics are developed as well. Remarkably, even under the constraints imposed by decentralized computing and sequential data acquisition, one can still attain the performance offered by the prohibitively complex batch analytics.
Original language | English (US) |
---|---|
Title of host publication | Cooperative and Graph Signal Processing |
Subtitle of host publication | Principles and Applications |
Publisher | Elsevier |
Pages | 777-797 |
Number of pages | 21 |
ISBN (Electronic) | 9780128136782 |
ISBN (Print) | 9780128136775 |
DOIs | |
State | Published - Jun 20 2018 |
Keywords
- Big data
- Bilinear decomposition
- Decentralized optimization
- Large-scale machine learning
- Low rank
- Matrix completion
- Nuclear norm
- Sparsity
- Streaming data
- Subspace learning