sparse polynomial optimization – Optimization Online

Order-2 Tightness of Block-Sparse SOS Relaxations for One-Layer ReLU Network Verification with a Matching Input-Sharing Graph

Published: 2026/07/22

Godai Azuma
Sunyoung Kim
Makoto Yamashita

Data Science Theory, Quadratic Programming, Semi-definite Programming input-sharing graph., ReLU network verification, semidefinite programming, sparse polynomial optimization, sums-of-squares relaxation

Azuma, Kim, and Yamashita formulated the verification problem for one-layer ReLU networks as a quadratically constrained quadratic program and established tight semidefinite relaxations for the edgeless case and for one-unit settings. In this work, we represent the sharing pattern of undecided ReLUs over a box input set through an input-sharing graph and focus on the … Read more