Timezone: »

 
Poster
Zeroth-Order Hard-Thresholding: Gradient Error vs. Expansivity
William de Vazelhes · Hualin Zhang · Huimin Wu · Xiaotong Yuan · Bin Gu

Wed Nov 30 02:00 PM -- 04:00 PM (PST) @ Hall J #808
in Poster Session 4 »
$\ell_0$ constrained optimization is prevalent in machine learning, particularly for high-dimensional problems, because it is a fundamental approach to achieve sparse learning. Hard-thresholding gradient descent is a dominant technique to solve this problem. However, first-order gradients of the objective function may be either unavailable or expensive to calculate in a lot of real-world problems, where zeroth-order (ZO) gradients could be a good surrogate. Unfortunately, whether ZO gradients can work with the hard-thresholding operator is still an unsolved problem.To solve this puzzle, in this paper, we focus on the $\ell_0$ constrained black-box stochastic optimization problems, and propose a new stochastic zeroth-order gradient hard-thresholding (SZOHT) algorithm with a general ZO gradient estimator powered by a novel random support sampling. We provide the convergence analysis of SZOHT under standard assumptions. Importantly, we reveal a conflict between the deviation of ZO estimators and the expansivity of the hard-thresholding operator, and provide a theoretical minimal value of the number of random directions in ZO gradients. In addition, we find that the query complexity of SZOHT is independent or weakly dependent on the dimensionality under different settings. Finally, we illustrate the utility of our method on a portfolio optimization problem as well as black-box adversarial attacks.
Keywords: Stochastic Optimization · Hard-thresholding · Sparse learning · Zeroth-order
[ Paper]  [ Poster]  [ OpenReview] 

Author Information

William de Vazelhes (Mohamed bin Zayed University of Artificial Intelligence)
William de Vazelhes

PhD student at MBZUAI, working on optimization, in particular sparse optimization (hard-thresholding), and zeroth-order optimization

Hualin Zhang (NUIST)
Huimin Wu (Nanjing University of Information Science and Technology)
Xiaotong Yuan (Nanjing University of Information Science and Technology)
Bin Gu (Pittsburgh University)

More from the Same Authors