Research map / Optimization / Nonconvex and smooth optimization
Convex and Bilevel Optimization for Neural-Symbolic Inference and Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a bilevel value-function learning framework for NeSy energy-based models with a smoothed (Moreau envelope) formulation and a dual block coordinate descent inference algorithm for NeuPSL that enables fast warm-started learning.
Problem
Gradient-based parameter learning for neural-symbolic energy-based models whose inference is non-smooth and constrained, so minimizer-based losses lack tractable gradients; NeuPSL inference is also slow in learning loops.
Approach
Formulate NeSy-EBM learning as a bilevel value-function problem with relaxed constraints, smooth the constrained energy via its Moreau envelope, optimize with augmented Lagrangian; reformulate NeuPSL inference as a regularized LCQP solved by dual block coordinate descent that yields dual variables giving gradients directly and exploits warm starts.
Key results
- Dual BCD inference reaches roughly 100x speedup over ADMM in cumulative learning time on DDI (19.65 s vs about 4,554 s for SP learning).
- Bilevel MSE/BCE learning gives up to 16 percentage points gain over value-based losses on MNIST-Addition (BCE).
- On Cora, BCE bilevel training reaches 81.07% vs 74.16% for SP among HL-MRF models (over 6 points).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use bilevel MSE/BCE instead of value-based Energy/SP loss | NeuPSL · Epinions | AUROC: 79.85 ± 1.62 -> 81.18 ± 2.21 | Helped |
| Use bilevel MSE/BCE instead of value-based Energy/SP loss | NeuPSL · Cora | Accuracy: 74.16 ± 2.32 -> 81.07 ± 1.31 | Helped |
| Use bilevel MSE/BCE instead of value-based Energy/SP loss | NeuPSL · Debate | AUROC: 64.68 ± 11.05 -> 65.33 ± 11.98 | No clear effect |
| Use bilevel MSE/BCE instead of value-based Energy/SP loss | NeuPSL · 4Forums | AUROC: 63.15 ± 6.40 -> 64.85 ± 6.01 | Helped |
| Use bilevel MSE/BCE training | Deep NeuPSL · Citeseer | Accuracy: 67.42 ± 0.66 -> 69.64 ± 1.33 | Helped |
| Use bilevel MSE/BCE training | Deep NeuPSL · Cora | Accuracy: 80.32 ± 1.11 -> 81.48 ± 1.45 | Helped |
| Use bilevel BCE instead of value-based Energy | NeuPSL · MNIST-Add1, 300 additions | Accuracy: 87.96 ± 01.58 -> 88.84 ± 02.07 | Helped |
| Use bilevel BCE instead of value-based Energy | NeuPSL · MNIST-Add2, 150 additions | Accuracy: 59.20 ± 32.79 -> 76.00 ± 2.61 | Helped |
| Use dual BCD instead of ADMM for inference during learning | NeuPSL · DDI, SP learning | cumulative inference time (seconds): 4,554 ± 13 -> 19.65 ± 0.30 | Helped |
| Use dual BCD instead of ADMM for inference during learning | NeuPSL · MNIST-Add2, SP learning | cumulative inference time (seconds): TIME-OUT -> 804 ± 106 | Helped |
| Use lock-free parallel dual BCD instead of connected-component parallel dual BCD | NeuPSL inference · Yelp | inference time (seconds): 48.44 ± 3.82 -> 7.58 ± 0.48 | Helped |
| Use lock-free parallel dual BCD instead of connected-component parallel dual BCD | NeuPSL inference · MNIST-Add2 | inference time (seconds): 29.09 ± 8.00 -> 1,189 ± 16 | Hurt |
Surprising findings
- Lock-free parallel dual BCD is faster than connected-component parallel dual BCD on most datasets despite inexact steplength subproblems.
- Energy-loss training on Cora (54.30%) performs far worse than SP (74.16%) in the non-deep HL-MRF setting.
Limitations
- Framework limited to NeSy-EBMs with the stated smoothness and singleton-minimizer assumptions.
- Non-differentiable value functions are not handled; approximate inference is not explored for gradients.
- Dual BCD implemented only for LCQP-structured NeSy systems such as NeuPSL.
Experimental setup
Datasets: Debate 4Forums Epinions DDI Yelp Citeseer Cora MNIST-Addition
Benchmarks: Debate 4Forums Epinions DDI Yelp Citeseer Cora MNIST-Addition
Metrics: AUROC accuracy MAE runtime in seconds
Baselines: ADMM Gurobi subgradient descent energy loss structured perceptron loss DeepStochLog GCN CNN LTN DeepProblog
Builds on: NeuPSL NeSy energy-based models ADMM bound-constrained augmented Lagrangian
Closest papers by meaning
- Verification Learning: Make Unsupervised Neuro-Symbolic System Feasible (ICML 2025 · similarity 0.86)
- EM-NeSy: Expectation Maximization for Neurosymbolic Learning (NeurIPS 2026 · similarity 0.85)
- DOLPHIN: A Programmable Framework for Scalable Neurosymbolic Learning (ICML 2025 · similarity 0.85)
- Federated Neuro-Symbolic Learning (ICML 2024 · similarity 0.85)
- A learnability analysis on neuro-symbolic learning (NeurIPS 2025 · similarity 0.84)
- SMILE: Bridging Continuous Optimization and Discrete Symbolic Recovery (NeurIPS 2026 · 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.