AI Paper Atlas

Research map / Learning theory and algorithms / Submodular and game algorithms

Quadratic Decomposable Submodular Function Minimization: Theory and Practice

Pan Li, Niao He, Olgica Milenkovic

JMLR 2020 · Learning theory and algorithms › Submodular and game algorithms · approach: Monotone submodular maximization · 9 citations (OpenAlex)

Read the paperCheck your idea against 137,217 papers

AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Measured effects reported in the paper

What was changedWhereMeasuredEffect
use QRCD with the exact projection for undirected hyperedges (SPE) instead of PDHGPDHG · Synthetic hypergraph SSL (l = 1)classification error rate (%): 9.05 -> 2.93Improved
use QDSFM objective with QRCD-SPE instead of the DSFM objective (DRCD)DRCD · Synthetic hypergraph SSL (l = 1)classification error rate (%): 44.7 -> 2.93Improved
use QRCD-SPE instead of InvLapInvLap · Synthetic hypergraph SSL (l = 1)classification error rate (%): 8.17 -> 2.93Improved
use QRCD-SPE instead of QAP-SPEQAP-SPE · Synthetic hypergraph SSL (l = 1)classification error rate (%): 14.9 -> 2.93Improved
use QRCD-SPE instead of SGDSGD · Synthetic hypergraph SSL (l = 1)classification error rate (%): 5.79 -> 2.93Improved
use QRCD-SPE instead of QRCD-MNP or QRCD-FW on synthetic hypergraphsQRCD-MNP / QRCD-FW · Synthetic hypergraph SSLCPU time: 100 to 1000 times slowerImproved
use conic MNP subroutine instead of FW, AMP or PWMP in QRCDQRCD · Synthetic QDSFM (N = 100, R = 100)primal gapImproved
use conic PWMP with smaller theta (0.25, 0.5 versus 1) (ablation)QRCD-PWMP · Synthetic QDSFM (N = 100, R = 100)primal gapHurt
scale up submodular function by s in {1, 2, 5, 10, 20} (ablation)conic MNP, FW, AMP, PWMP projections · Single submodular function (theta = 0.25, N = 100)CPU timeHurt
vary beta from 10^-3 to 10^3 in the QDSFM objective (ablation)QRCD · Synthetic QDSFM hypergraph SSLgap ratioMixed
use InvLap instead of QRCD-SPE on large real hypergraphsInvLap · UCI Mushroom, Covertype45, Covertype67running time (s): 22, 114 and 1802 secondsHurt

Closest papers by meaning

Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy