Binary Signal Alignment: Optimal Solution is Polynomial-Time and Linear-Time Solution is Quasi-Optimal
- Award ID(s):
- 2118002
- PAR ID:
- 10501493
- Publisher / Repository:
- IEEE
- Date Published:
- ISBN:
- 979-8-3503-4485-1
- Page Range / eLocation ID:
- 8996 to 9000
- Format(s):
- Medium: X
- Location:
- Seoul, Korea, Republic of
- Sponsoring Org:
- National Science Foundation
More Like this
-
We develop an analytical framework to characterize the set of optimal ReLU neural networks by reformulating the non-convex training problem as a convex program. We show that the global optima of the convex parameterization are given by a polyhedral set and then extend this characterization to the optimal set of the non-convex training objective. Since all stationary points of the ReLU training problem can be represented as optima of sub-sampled convex programs, our work provides a general expression for all critical points of the non-convex objective. We then leverage our results to provide an optimal pruning algorithm for computing minimal networks, establish conditions for the regularization path of ReLU networks to be continuous, and develop sensitivity results for minimal ReLU networks.more » « less
-
We develop an analytical framework to characterize the set of optimal ReLU neural networks by reformulating the non-convex training problem as a convex program. We show that the global optima of the convex parameterization are given by a polyhedral set and then extend this characterization to the optimal set of the nonconvex training objective. Since all stationary points of the ReLU training problem can be represented as optima of sub-sampled convex programs, our work provides a general expression for all critical points of the non-convex objective. We then leverage our results to provide an optimal pruning algorithm for computing minimal networks, establish conditions for the regularization path of ReLU networks to be continuous, and develop sensitivity results for minimal ReLU networks.more » « less