# An interesting first order method

Consider the problem of minimizing $$f(x)+g(x)$$ over $$\mathbb{R}^n$$, both are smooth, and the following first order method: $$x_{k+1}= \operatorname{argmin}_x\left \{ \nabla f(x_k)^T(x-x_k) + \frac{1}{\alpha^{p-1} p} \|x-(x_k - \alpha \nabla g(x_k))\|_p^p \right \}$$

Is it a special case of some known method?

What about the stochastic setting, when $$f(x) = \frac{1}{m} \sum_{i=1}^m f_i(x)$$, replacing $$\nabla f$$ by $$\nabla f_i$$, where $$i$$ is chosen at random?

Note that it is easy to see that for $$p=2$$, we obtain exactly the (stochastic) gradient method with step-size $$\alpha$$.

The method was coded by mistake, instead of a more natural method which we aimed to test, $$x_{k+1}= \operatorname{argmin}_x \left\{ [\nabla f(x_k) + \nabla g(x_k)]^T(x-x_k) + \frac{1}{\alpha^{p-1} p} \|x-x_k\|_p^p \right \}$$ with $$p=3$$. The stochastic version of the 'mistake' turned out to perform much better than the stochastic version of the more natural method above.

• Do you have examples of specific pairs of functions $f$ and $g$ on which the 'mistake' performed better than the original method? Did the 'mistake' also outperform the method $x_{k+1}=x_k-\alpha\nabla f(x_k)-\alpha\nabla g(x_k)$ on any of these pairs of functions? May 1, 2019 at 11:09
• @AngelaRichardson $f$ is an average of functions of the form $\log(\exp(p(x))+1)$ where $p$ is a 3rd degree multivariate polynomial, and $g$ is the squared Eurclidean norm. The regular gradient descent you asked about performs poorly, and we thought that changing the approximating model from quadratic to cubic would improve the performance. It indeed did so. As I pointed out, the regular gradient method corresponds to the quadratic model. May 1, 2019 at 12:59
• I can't make the link but this might be related to $\alpha$-divergences minimization, you may take a look at en.wikipedia.org/wiki/F-divergence#Instances_of_f-divergences but on this field, google scholar will help more then google. May 4, 2019 at 7:54
• It looks like a modified proximal gradient method where the proximal is defined with respect to a different norm; similar to what @P.Quinton mentioned, it must be related to Bregman divergences. May 4, 2019 at 15:02
• What is weird is that the distance is not from $x_k$. May 4, 2019 at 16:13