Reply to Reviewer VXbB
Dear Reviewer VXbB,
Thank you for your insightful question! We are happy to discuss this in detail. Please see our answers below:
> First, I have hoped for a more formal discussion why Example 1 is not PL.
We can show this by a simple example (satisfying conditions in Theorem 1) as follows.
Let $\{( {x}^{(i)},y^{(i)})\}_{i=1}^2$ be a training data set where $ {x}^{(i)} \in \mathbb{R}$ is the input data and $y^{(i)} \in \mathbb{R}$ is the output data for $i = 1, 2$. Let us choose $z(\theta; i) = w_2 {x}^{(i)}$, so $h(w;i) = w_1 (w_2 {x}^{(i)}) + b$, where $w = [ w_1 ; w_2 ; b ] \in \mathbb{R}^3$. (This is a small two-layer neural network).
We have $f(w ; i) = \frac{1}{2} || h(w;i) - y^{(i)} ||^2 = \frac{1}{2} ( w_1 (w_2 {x}^{(i)}) + b - y^{(i)} )^2$ for $i = 1, 2$.
Note that $F(w) = \frac{1}{n} \sum_{i=1}^n f(w ; i)$ and $\nabla F(w) = \frac{1}{n} \sum_{i=1}^n \nabla f(w ; i)$.
We have $\nabla f (w; i) = [ w_2 {x}^{(i)} ( w_1 w_2 {x}^{(i)} + b - y^{(i)} ) ; w_1 {x}^{(i)} ( w_1 w_2 {x}^{(i)} + b - y^{(i)} ) ; w_1 w_2 {x}^{(i)} + b - y^{(i)} ]$
To demonstrate a specific case, we consider the data $x^{(1)} = 1$, $x^{(2)} = 0$, $y^{(1)} = 1$, $y^{(2)} = 2$. (Other data may work as well).
We observe that, $w_* = [ 1 ; -1 ; 2 ]$ is the optimal solution of $F$ since $F_* = \frac{1}{2} \sum_{i=1}^2 \frac{1}{2} ( w_1^* (w_2^* {x}^{(i)}) + b^* - y^{(i)} )^2 = \frac{1}{2} \cdot \frac{1}{2} [(1 \cdot (-1) \cdot 1 + 2 - 1)^2 + (1 \cdot (-1) \cdot 0 + 2 - 2)^2] = 0$.
On the other hand, there exists a stationary point $\hat{w} = [ 0 ; 0 ; 3/2 ]$ such that $\nabla F(\hat{w}) = \frac{1}{2} \sum_{i=1}^2 \nabla f(\hat{w} ; i) = \frac{1}{2} ( [ 0 \cdot 1 ( 0 \cdot 0 \cdot 1 + 3/2 - 1 ) ; 0 \cdot 1 ( 0 \cdot 0 \cdot 1 + 3/2 - 1 ) ; 0 \cdot 0 \cdot 1 + 3/2 - 1 ] + [ 0 \cdot 0 ( 0 \cdot 0 \cdot 0 + 3/2 - 2 ) ; 0 \cdot 0 ( 0 \cdot 0 \cdot 0 + 3/2 - 2 ) ; 0 \cdot 0 \cdot 0 + 3/2 - 2 ] ) = [ 0 ; 0 ; 0 ]$
while $F(\hat{w}) = \frac{1}{2} \cdot \frac{1}{2} [ (0 \cdot 0 \cdot 1 + 3/2 - 1)^2 + (0 \cdot 0 \cdot 0 + 3/2 - 2)^2 ] = 0.125 \neq F_*$.
Therefore, this example does not satisfy the PL condition on $F$ since it does not satisfy $|| \nabla F(\hat{w})||^2 \geq 2 \mu [F({\hat{w}})-F_*]$ for $\mu > 0$. Note that this is just an example to demonstrate that the general network in Theorem 1 does not necessarily satisfy the PL condition on $F$, but it satisfies our proposed Assumption 3.
> Second, since assuming Assumptions 3 & 5 is neither stronger, nor weaker than PL, but leads to a worse convergence rate, it is unclear why one should use Assumptions 3 & 5. Giving some important example that is covered by new assumptions but not covered by PL might solve this concern.
An example that helps to demonstrate our theory is the class of convex functions (but non-strongly convex). Note that the non-strongly convexity on $F$ cannot imply the PL condition on $F$. The example in Theorem 1 contains a class of non-strongly convex problem (e.g. $z (\theta ; i ) = x^{(i)}$), so the Assumptions 3 and 5 hold. While our theory obtains the same rate of convergences as the class of non-strongly convex problems, it does not restrict the problem to be convex. Thus, we believe our theoretical setting will be one of the directions to investigate non-convex problems with special structures.
We hope our answers address all of your questions. Again, we are grateful for your positive assessment of our paper. We hope you find this direction is interesting and support us.
Sincerely,
Authors