Timezone: »

 
Poster
Quadratic Decomposable Submodular Function Minimization
Pan Li · Niao He · Olgica Milenkovic

Tue Dec 04 07:45 AM -- 09:45 AM (PST) @ Room 210 #3
in Tue Poster Session A »

We introduce a new convex optimization problem, termed quadratic decomposable submodular function minimization. The problem is closely related to decomposable submodular function minimization and arises in many learning on graphs and hypergraphs settings, such as graph-based semi-supervised learning and PageRank. We approach the problem via a new dual strategy and describe an objective that may be optimized via random coordinate descent (RCD) methods and projections onto cones. We also establish the linear convergence rate of the RCD algorithm and develop efficient projection algorithms with provable performance guarantees. Numerical experiments in semi-supervised learning on hypergraphs confirm the efficiency of the proposed algorithm and demonstrate the significant improvements in prediction accuracy with respect to state-of-the-art methods.

Keywords: Convex Optimization · Semi-Supervised Learning · Submodular Optimization
[ Paper] 

Author Information

Pan Li (University of Illinois Urbana-Champaign)
Niao He (UIUC)
Olgica Milenkovic (University of Illinois at Urbana-Champaign)

More from the Same Authors