5 papers
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…
T-semidefinite programming relaxation with third-order tensors for constrained polynomial optimization
Hiroki Marumo, Sunyoung Kim, Makoto Yamashita
We study T-semidefinite programming (SDP) relaxation for constrained polynomial optimization problems (POPs). T-SDP relaxation for unconstrained POPs was introduced by Zheng, Huang…
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…