Timezone: »

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

Thu Dec 09 08:30 AM -- 10:00 AM (PST) @
in Poster Session 6 »
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.
Keywords: Optimization

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