Approximation Guarantees of Local Search Algorithms via Localizability of Set Functions
arXiv:2006.01400
Abstract
This paper proposes a new framework for providing approximation guarantees of local search algorithms. Local search is a basic algorithm design technique and is widely used for various combinatorial optimization problems. To analyze local search algorithms for set function maximization, we propose a new notion called localizability of set functions, which measures how effective local improvement is. Moreover, we provide approximation guarantees of standard local search algorithms under various combinatorial constraints in terms of localizability. The main application of our framework is sparse optimization, for which we show that restricted strong concavity and restricted smoothness of the objective function imply localizability, and further develop accelerated versions of local search algorithms. We conduct experiments in sparse regression and structure learning of graphical models to confirm the practical efficiency of the proposed local search algorithms.
References in corpus (7)
- Learning with Structured Sparsity
- Non-monotone submodular maximization under matroid and knapsack constraints
- Learning-based Compressive Subsampling
- On Iterative Hard Thresholding Methods for High-dimensional M-Estimation
- On Learning Discrete Graphical Models Using Greedy Methods
- Fast Semidifferential-based Submodular Function Optimization
- Fast greedy algorithms for dictionary selection with generalized sparsity constraints