Stochastic Iterative Hard Thresholding for Graph-structured Sparsity Optimization
arXiv:1905.03652
Abstract
Stochastic optimization algorithms update models with cheap per-iteration costs sequentially, which makes them amenable for large-scale data analysis. Such algorithms have been widely studied for structured sparse models where the sparsity information is very specific, e.g., convex sparsity-inducing norms or -norm. However, these norms cannot be directly applied to the problem of complex (non-convex) graph-structured sparsity models, which have important application in disease outbreak and social networks, etc. In this paper, we propose a stochastic gradient-based method for solving graph-structured sparsity constraint problems, not restricted to the least square loss. We prove that our algorithm enjoys a linear convergence up to a constant error, which is competitive with the counterparts in the batch learning setting. We conduct extensive experiments to show the efficiency and effectiveness of the proposed algorithms.
published in ICML-2019
References in corpus (12)
- Adam: A Method for Stochastic Optimization
- SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
- Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
- Structured Variable Selection with Sparsity-Inducing Norms
- Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
- How to Escape Saddle Points Efficiently
- Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)
- Detection of an anomalous cluster in a network
- On Iterative Hard Thresholding Methods for High-dimensional M-Estimation
- RSG: Beating Subgradient Method without Smoothness and Strong Convexity
- Dual Iterative Hard Thresholding: From Non-convex Sparse Minimization to Non-smooth Concave Maximization
- Sample Efficient Stochastic Gradient Iterative Hard Thresholding Method for Stochastic Sparse Linear Regression with Limited Attribute Observation