# Why do increasing regularization weights make objective function not monotonically decrease?

I run modified non-negative matrix factorization (NMF) and tune the regularization weight from 1e5 to 1e13.

The table below shows errors from calculating cost function for 25 iterations of all weights. At weight 1e4, the objective function is monotonically decreased. But when I increase the weight more and more, the error profile of 25 iterations goes down and gradually up. What is happened here? By the way, I think I got the best result is at weight 5e10 but the error profile is not monotonically decreased. In this case, which weight I should choose?

Forgive me for not being an expert on NMF, but I am pretty experienced with other regularized techniques.

Regularization techniques usually use a form of gradient descent to find the optimal answer. In general, these are guaranteed to converge. However, they are not often guaranteed to do so monotonically.

The geometric interpretation of gradient descent is searching for the bottom of a bowl by walking down the sides of the bowl. Think about an image like this. The size of those steps depends on the algorithm used. It's usually computationally cheap to have a constant or monotonically decreasing step size. If the step size is too large, which is likely in the beginning of your algorithm, then you can "overshoot" your goal, and hence end up with an iteration larger than the previous one.

• It's not clear that you and the OP are interpreting the graphic or the question in the same way. I had taken this to be a plot of the optimum value of the objective as a function of the regularization weights (shown in the left column) and iteration in some search procedure (shown in the top row). The question seems to concern why the optimal value does not vary monotonically with the weights. What's needed is a basic explanation of what regularization actually does, akin to the bias-variance tradeoff in regularized linear models.
– whuber
Mar 15, 2018 at 13:52
• I think we're interpreting it the same way. The objective function's optimum value does not decrease monotonically for the reasons I stated. Clarification from OP would be appreciated though! Mar 15, 2018 at 14:13
• Thanks so much for both of your insights. I understand about gradient descent but here I am using multiplicative update which I do not have to define the step size. The update rule obtained from the paper said it is monotonically decreased. So I am unsure this is something that can happen when the weight is too much or my algorithm is wrong? If it is not wrong, which weight and how many iterations I should choose as the optimal point? I am quite new to this so I am sorry if my explanation is not clear. Please let me know if I can clarify something further more.
– Jan
Mar 15, 2018 at 15:08