Toward the Optimal Construction of a Loss Function Without Spurious Local Minima for Solving Quadratic Equations

Zhenzhen Li, Jian-Feng Cai, Ke WeiIEEE Trans. Information Theory 2020 · OpenReview

Abstract

The problem of finding a vector x which obeys a set of quadratic equations |a <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</sub> <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">T</sup> x| <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> = y <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</sub> , k = 1, <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">⋯</sub> , m, plays an important role in many applications. In this paper we consider the case when both x and ak are real-valued vectors of length n. A new loss function is constructed for this problem, which combines the smooth quadratic loss function with an activation function. Under the Gaussian measurement model, we establish that with high probability the target solution x is the only minimizer (up to a global sign) of the new loss function provided m ≳ n. Moreover, the loss function always has a negative directional curvature around its saddle points.
BibTeX
@article{li2020toward,
  author = {Zhenzhen Li and Jian-Feng Cai and Ke Wei},
  title = {{Toward the Optimal Construction of a Loss Function Without Spurious Local Minima for Solving Quadratic Equations}},
  journal = {IEEE Trans. Information Theory},
  year = {2020},
  url = {https://openreview.net/forum?id=fXQJFQohUp},
}
Figure