Research map / Learning theory and algorithms / Matrix and tensor methods
Efficient Low Rank Convex Bounds for Pairwise Discrete Graphical Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (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 changed | Where | Measured | Effect |
|---|---|---|---|
| Replace dualized exactly-one constraints (LR-LAS) with block-coordinate descent with Newton updates (LR-BCD) | Burer-Monteiro SDP bound for pairwise MAP · Random complete-graph instances (100-1000 vars, 3-10 states) | CPU time: often by more than two orders of magnitude faster than LR-LAS | Helped |
| Use BCD over exactly-one constraints instead of dualized penalty | Burer-Monteiro SDP bound for pairwise MAP · Random instances | lower bound tightness | Mixed |
| Use dualized penalty approach (LR-LAS) instead of TRW-S for time-constrained tasks | Integer solution quality over time · 100 variables, 5 states instance | integer solution cost vs time | Mixed |
| Use BCD with Newton updates on random instances at large rank | LR-BCD · Real fish instance | optimality gap: from 100% (TRW-S) to 16.1% (LR-BCD) | Helped |
| Replace dualized constraints with BCD (LR-BCD) on the real fish instance where LR-LAS was run | Burer-Monteiro SDP bound · Real fish instance | runtime: LR-BCD took 68.6 minutes while LR-LAS did not finish after several hours | Helped |
| Lower the rank used by LR-LAS to intermediate values (ablation) | LR-LAS · 100 variables, 5 states instance | integer solution quality over time | Helped |
| Use very low rank for LR-BCD (ablation) | LR-BCD · 500 variables, 3 states instance | relative error vs cpu-time | Mixed |
Closest papers by meaning
- Relative Interior Rule in Block-Coordinate Descent (CVPR 2020 · similarity 0.89)
- Convergence of Some Convex Message Passing Algorithms to a Fixed Point (ICML 2024 · similarity 0.88)
- Inference in Graphical Models via Semidefinite Programming Hierarchies (NeurIPS 2017 · similarity 0.88)
- The Burer-Monteiro SDP method can fail even above the Barvinok-Pataki bound (NeurIPS 2022 · similarity 0.87)
- The non-convex Burer-Monteiro approach works on smooth semidefinite programs (NeurIPS 2016 · similarity 0.86)
- Stability-based Generalization Analysis of Randomized Coordinate Descent for Pairwise Learning (AAAI 2025 · similarity 0.84)
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.