Approximation Guarantees of Local Search Algorithms via Localizability of Set Functions

Kaito Fujii
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:3327-3336, 2020.

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 \emph{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.

Cite this Paper


BibTeX
@InProceedings{pmlr-v119-fujii20a, title = {Approximation Guarantees of Local Search Algorithms via Localizability of Set Functions}, author = {Fujii, Kaito}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {3327--3336}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/fujii20a/fujii20a.pdf}, url = {https://proceedings.mlr.press/v119/fujii20a.html}, 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 \emph{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.} }
Endnote
%0 Conference Paper %T Approximation Guarantees of Local Search Algorithms via Localizability of Set Functions %A Kaito Fujii %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-fujii20a %I PMLR %P 3327--3336 %U https://proceedings.mlr.press/v119/fujii20a.html %V 119 %X 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 \emph{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.
APA
Fujii, K.. (2020). Approximation Guarantees of Local Search Algorithms via Localizability of Set Functions. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:3327-3336 Available from https://proceedings.mlr.press/v119/fujii20a.html.

Related Material