Relaxed Majorization-Minimization for Non-smooth and Non-convex Optimization
This work addresses optimization challenges in machine learning for problems with non-smooth and non-convex functions, offering a more general and effective approach, though it appears incremental as it builds on existing majorization-minimization methods.
The authors tackled the problem of non-smooth and non-convex optimization by proposing a new majorization-minimization method that relaxes conditions on surrogate functions, enabling direct approximation of non-smooth objectives. They applied this method to robust matrix factorization, achieving state-of-the-art performance and ensuring convergence to stationary points without extra assumptions.
We propose a new majorization-minimization (MM) method for non-smooth and non-convex programs, which is general enough to include the existing MM methods. Besides the local majorization condition, we only require that the difference between the directional derivatives of the objective function and its surrogate function vanishes when the number of iterations approaches infinity, which is a very weak condition. So our method can use a surrogate function that directly approximates the non-smooth objective function. In comparison, all the existing MM methods construct the surrogate function by approximating the smooth component of the objective function. We apply our relaxed MM methods to the robust matrix factorization (RMF) problem with different regularizations, where our locally majorant algorithm shows advantages over the state-of-the-art approaches for RMF. This is the first algorithm for RMF ensuring, without extra assumptions, that any limit point of the iterates is a stationary point.