0
$\begingroup$

When I try to solve a optimization problem by Riemannian stochastic variance reduced gradient algorithm(RSVRG), the formulation of problem like $\frac{1}{N}\sum_{i=1}^Nf_i(x)$ and $f_i(x)$ is a non-convex function. It can be expressed like $||\mathbf{x}||^2 - \gamma||a\mathbf{x}||^2$.

I found that the value of the function will get bigger and bigger with the iteration process. According to Stochastic Variance Reduction for Nonconvex Optimization's pseudocode, I think the reason for this problem is that the full gradient from the outer loop does not change in the inner loop, causing the x value of the inner loop to keep moving in a wrong direction.

I want to know whether this understanding is correct and whether there is a solution to this problem (I am not familiar with this field, I am afraid that limiting the gradient of the inner loop will change the original convergence).

$\endgroup$
6
  • $\begingroup$ It can also be due to excessively large step sizes. Have you tried to reduce them? $\endgroup$
    – fedja
    Aug 21, 2020 at 13:51
  • $\begingroup$ I have tried to use stepsize = stepsize_init / (1 + 0.01 * stepsize_init * iter) to modify the step size, but it did not work, does it mean that I should try some other formulas to reduce the step size. $\endgroup$
    – Rejur
    Aug 21, 2020 at 15:00
  • $\begingroup$ The stepsize_init in the denominator looks fairly strange. I believe it is a misprint, but if not, then you'd better change it to stepsize_init/(1+0.01*iter). Also, do you get the effect when setting $m=1$ (i.e., when doing the classical gradient descent)? In general, if you want someone to figure out what is going on, it is best to post all details: the exact functions and the parameters you are using. Then it will become possible to try to reproduce the effect. After all, you may have just some stupid programming error like $+$ instead of $-$ somewhere ;-) $\endgroup$
    – fedja
    Aug 21, 2020 at 17:48
  • $\begingroup$ There a re a lot of possible reasons, some of them mentioned in previous comments. But there is one super common mistake, applying the gradient in the wrong direction (or equivalently, getting its sign wrong). Are you trying to minimize or maximize the given function? if you are trying to maximize, then you need to insert the negative of the gradient in place of the gradient into the formula developed for minimization. $\endgroup$ Aug 21, 2020 at 21:36
  • $\begingroup$ Thank you for your current suggestions. Ok, I will make some attempts and release more details after collecting more situations. $\endgroup$
    – Rejur
    Aug 22, 2020 at 0:37

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.