Adaptive Sparse Online Learning through Asymmetric Truncated Gradient
Zhong Chen · 2024
The goal of sparse online learning is to induce sparsity in the weights of online learning algorithms, ensuring the prediction model only contains a limited size of active features. However, the adaptability of sparse online learning has been ignored by most existing studies. In this work, we propose a novel adaptive sparse online learning framework named Asymmetric Truncated Gradient (ATG) for handling high dimensional data streams, which is implemented by an adaptive sparsity-promoting strategy to truncate the gradients in an online fashion. Our main idea is to exploit adaptive sparse learning for the current weight vector by introducing an extra parameter in TG to asymmetrically control the sparsity level for positive and negative weights, achieving adaptive sparse solutions of the online weight updating. Compared with projection-based or$\ell_{1}$-norm based sparsity-introducing mechanisms, our proposed ATG algorithm is able to achieve stable sparse solutions by considering the sparsity structure of the current weight vector. Theoretical regret bound analysis of ATG provides a solid mathematical support for its wide applications. Extensive empirical studies have demonstrated the effectiveness and efficiency of the proposed ATG method.