Loading...
On Iterative Hard-Thresholding: Gradient Estimation and Non-Convex Projections
Vazelhes, William
Vazelhes, William
Files
Author
Supervisor
Department
Machine Learning
Embargo End Date
2024-01-01
Type
Dissertation
Date
2024
License
Language
English
Collections
Research Projects
Organizational Units
Journal Issue
Abstract
The primary contribution of this thesis is to analyze several new extensions of the Iterative Hard-Thresholding (IHT) algorithm. We first focus on analyzing a zeroth-order extension of IHT, zeroth-order hard-thresholding (ZOHT): in particular, we analyze the conflict between the error of the zeroth-order gradient estimator, and the expansivity of the hard-thresholding operator. We prove global convergence guarantees in the restricted strongly convex (RSC) and restricted smooth (RSS) setting, for such algorithm. We then analyze the convergence of variance-reduction variants of the ZOHT algorithm (in the RSC and RSS settings), and analyze how the conditions on the number of random directions are improved. We then propose a variant of the original proof of convergence of ZOHT in the non-convex and discontinuous setting, useful for instance in a reinforcement learning setting. Then, we analyze a generalization of IHT which can tackle additional convex constraints verifying mild assumptions, in the zeroth-order and first-order (stochastic and deterministic) settings: when doing so, we also revisits previous proofs of convergence in risk for IHT, providing simpler proofs for existing results, removing the original system error present in the first proof of ZOHT, and extending the convergence result of all those algorithms to the case with extra constraints. Finally, we analyze an algorithm for sparse recovery, IRKSN (Iterative Regularization with k-Support Norm), inspired by a dual perspective on IHT, and show that its provides different conditions for recovery than IHT and usual sparse recovery algorithms based on the ?1 norm, therefore providing a useful complement to those algorithms for sparse recovery.
Citation
W. Vazelhes, "On Iterative Hard-Thresholding: Gradient Estimation and Non-Convex Projections", PhD Dissertation, Machine Learning, MBZUAI, Abu Dhabi, UAE, 2024