Timezone: »

Stochastic $L^\natural$-convex Function Minimization
Haixiang Zhang · Zeyu Zheng · Javad Lavaei

Thu Dec 09 08:30 AM -- 10:00 AM (PST) @
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.

Author Information

Haixiang Zhang (University of California, Berkeley)
Zeyu Zheng (University of California Berkeley)
Javad Lavaei (University of California, Berkeley)

More from the Same Authors