Stochastic $L^\natural$-convex Function Minimization
Haixiang Zhang, Zeyu Zheng, Javad Lavaei
Abstract
We study an extension of the stochastic submodular minimization problem, namely, the stochastic $L^\natural$-convex minimization problem. We develop the first polynomial-time algorithms that return a near-optimal solution with high probability. We design a novel truncation operation to further reduce the computational complexity of the proposed algorithms. When applied to a stochastic submodular function, the computational complexity of the proposed algorithms is lower than that of the existing stochastic submodular minimization algorithms. In addition, we provide a strongly polynomial approximate algorithm. The algorithm execution also does not require any prior knowledge about the objective function except the $L^\natural$-convexity. A lower bound on the computational complexity that is required to achieve a high probability error bound is also derived. Numerical experiments are implemented to demonstrate the efficiency of our theoretical findings.
BibTeX
@inproceedings{
zhang2021stochastic,
title={Stochastic \$L{\textasciicircum}{\textbackslash}natural\$-convex Function Minimization},
author={Haixiang Zhang and Zeyu Zheng and Javad Lavaei},
booktitle={Advances in Neural Information Processing Systems},
editor={A. Beygelzimer and Y. Dauphin and P. Liang and J. Wortman Vaughan},
year={2021},
url={https://openreview.net/forum?id=0hggPuM2b2}
}