6 papers · 1 filter
Order-2 Tightness of Block-Sparse SOS Relaxations for One-Layer ReLU Network Verification with a Matching Input-Sharing Graph
Godai Azuma, Sunyoung Kim, Makoto Yamashita
Azuma, Kim, and Yamashita formulated the verification problem for one-layer ReLU networks as a quadratically constrained quadratic program and established tight semidefinite relaxa…
Tight Conic Relaxations for Rank-one Doubly Nonnegative Matrix Completion
Godai Azuma, Sunyoung Kim, Makoto Yamashita
We study tight conic relaxations for a quadratically constrained quadratic programming (QCQP) formulation of rank-one doubly nonnegative (DNN) matrix completion. Motivated by spars…
Tight Semidefinite Relaxations for Verifying Robustness of Neural Networks
Godai Azuma, Sunyoung Kim, Makoto Yamashita
For verifying the safety of neural networks (NNs), Fazlyab et al. (2019) introduced a semidefinite programming (SDP) approach called DeepSDP. This formulation can be viewed as the…
Exact Matrix Completion via High-Rank Matrices in Sum-of-Squares Relaxations
Godai Azuma, Sunyoung Kim, Makoto Yamashita
We study exact matrix completion from partially available data with hidden connectivity patterns. Exact matrix completion was shown to be possible recently by Cosse and Demanet in…
Exact SDP relaxations for quadratic programs with bipartite graph structures
Godai Azuma, Mituhiro Fukuda, Sunyoung Kim +1
For nonconvex quadratically constrained quadratic programs (QCQPs), we first show that, under certain feasibility conditions, the standard semidefinite (SDP) relaxation is exact fo…
Exact SDP relaxations of quadratically constrained quadratic programs with forest structures
Godai Azuma, Mituhiro Fukuda, Sunyoung Kim +1
We study the exactness of the semidefinite programming (SDP) relaxation of quadratically constrained quadratic programs (QCQPs). With the aggregate sparsity matrix from the data ma…