1
$\begingroup$

In Machine Learning optimization problems - a "regularization" term is often added to the optimization problem to reduce overfitting:

enter image description here

I have noticed that in the case of the L2-Norm regularization, this term (i.e. a function) can be considered as a Convex Term as it is basically "quadratic" in nature.

My Question: In the L2-Norm case, the optimization problem without this regularization term is likely a Non-Convex problem - but we then add a Convex Term to this problem. Do we know if doing this (i.e. adding the Convex Term to a Non-Convex Optimization Problem) automatically makes the optimization problem as Convex?

I do not think that this is the case, seeing as:

  • Convex Optimization Problems are generally easier to solve than Non-Convex Optimization Problems

  • Anecdotally, I have heard of Regularized Loss Functions (e.g. for Neural Networks) that are considered to be "very difficult" optimization problems - even though they have this Convex Term. This informally leads me to believe that in the case of L2 Regularization, the fundamental optimization problem remains Non-Convex.

However, "anecdotal and informal logic" is generally never acceptable in understanding mathematics.

Can someone please comment on this?

Thanks!

$\endgroup$
5
  • 1
    $\begingroup$ Certainly not automatically; if lambda is small enough then your equation will be indistinguishable from the original. $\endgroup$ Commented Mar 13, 2022 at 18:03
  • 1
    $\begingroup$ Non-convex plus convex is non convex. One of the main issues with the optimization problems for Neural Networks is the large amount of data and the large amount of variables/constraints. But it also true that the costs may be pretty ugly. $\endgroup$
    – KBS
    Commented Mar 13, 2022 at 18:24
  • $\begingroup$ Thank you everyone for your replies! Much Apprecaited! $\endgroup$
    – stats_noob
    Commented Mar 13, 2022 at 19:21
  • $\begingroup$ @KBS That is a good rule of thumb but is not always true. $\endgroup$
    – RobPratt
    Commented Mar 13, 2022 at 19:48
  • $\begingroup$ @RobPratt Yes, you are right. $\endgroup$
    – KBS
    Commented Mar 13, 2022 at 20:22

1 Answer 1

4
$\begingroup$

Yes, adding a large enough convex term can make a problem convex. For example, consider the nonconvex function $-x^2$ and the convex function $x^2$. For constant $\lambda \ge 1$, the sum $-x^2 + \lambda x^2=(\lambda-1)x^2$ is convex.

This is also a standard trick in binary quadratic programming, where $x_i$ is a binary decision variable and the objective is to minimize the multivariate quadratic function $$\sum_i \sum_j q_{ij} x_i x_j + \sum_i c_i x_i$$ subject to linear constraints. Let $\lambda$ be the absolute value of the smallest (negative) eigenvalue of $Q=(q_{ij})$. Then adding $\lambda(x_i^2-x_i)$, which is $0$ when $x_i$ is binary, makes the objective function convex.

$\endgroup$
4
  • $\begingroup$ @ RobPratt: Thank you so much for your answer! How "large" is "large enough"? In the case of the L2 Norm regularization problem that I posted - does this L2 Norm regularization term automatically make this optimization problem as Convex? Thank you so much! $\endgroup$
    – stats_noob
    Commented Mar 13, 2022 at 19:50
  • $\begingroup$ If you have time - could you please take a look at this related question over here? math.stackexchange.com/questions/4402076/… Thank you so much! $\endgroup$
    – stats_noob
    Commented Mar 13, 2022 at 19:51
  • $\begingroup$ Is there a typo on the binary QP addition term, i.e., it should be the negative of what's there, i.e., need to be adding positive number to the diagonal? $\endgroup$ Commented Mar 15, 2022 at 17:19
  • $\begingroup$ @MarkL.Stone Yes, corrected. Thanks! $\endgroup$
    – RobPratt
    Commented Mar 15, 2022 at 17:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .