Approximation Guarantees of Local Search Algorithms via Localizability
  of Set Functions
  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.
