5
$\begingroup$

The Adam optimizer is often used for training neural networks; it typically avoids the need for hyperparameter search over parameters like the learning rate, etc. The Adam optimizer is an improvement on gradient descent.

I have a situation where I want to use projected gradient descent (see also here). Basically, instead of trying to minimize a function $f(x)$, I want to minimize $f(x)$ subject to the requirement that $x \ge 0$. Projected gradient descent works by clipping the value of $x$ after each iteration of gradient descent: each negative entry is replaced with 0, after each step.

Unfortunately, projected gradient descent seems to interact poorly with the Adam optimizer. I'm guessing that Adam's exponential moving average of the gradients gets messed up by the clipping. And plain projected gradient descent has hyperparameters that can be tuned.

Is there a version of Adam that can be used with projected gradient descent? I'm looking for a method that is an improvement on projected gradient descent, in the same way that Adam is an improvement on ordinary gradient descent (e.g., doesn't require hyperparameter tuning). Is there any such algorithm?

$\endgroup$
1
  • $\begingroup$ I have the exact same question. There are some theoretical guarantees for projected gradient descent (vanilla version), and also for adaptive algorithms, e.g.: arxiv.org/abs/1904.09237 proves convergence of ADAM even with a projection. But I have not seen any examples of people discussing this in practice. Have you? $\endgroup$ – becko Jun 17 '20 at 0:01
1
$\begingroup$

tl;dr: You should project the gradients before feeding them to Adam. You should also do the clipping afterwards in case of non-linear constraints and to avoid accumulation of numerical errors.

First, assuming normal SGD, for the specific case of (approximately) linear equality constraints, this can be done by

  1. projecting the gradient to the tangent space
  2. taking a step into that direction and
  3. projecting down again to the admissible set (only to correct for errors, numerical ones or due to non-linear constraints): $$ g_p = \pi_\top(g; x_n) \\ x_{n+1} = \pi_C(x_n - \alpha g_p) $$ where $g$ is the unprojected gradient, $\pi_\top(\,\cdot\,;x_n)$ projects to the tangent space at the current location $x_n$, $\pi_C(\,\cdot\,)$ projects to the admissible set, and $\alpha$ is the SGD learning rate.

In the general case, you will need to (also see the comments below and this thread)

  1. identify the search direction by taking an $\epsilon$ step in the true (negative) gradient direction
  2. project the result down to the admissible set $C$
  3. rescale appropriately to get an estimate of the projected gradient
  4. take the actual update step into that direction
  5. project down again to the admissible set.

The full update (for normal SGD) therefore becomes: $$ \widehat{g}_p = {\textstyle\frac{1}{\epsilon}}(x_n - \pi_C(x_n - \epsilon g)) \qquad [\text{steps 1–3}]\\ x_{n+1} = \pi_C(x_n - \alpha \widehat{g}_p)~, \qquad [\text{steps 4 and 5}] $$ where $g$ is the original gradient, $0<\epsilon\ll1$ is a small constant, $\widehat{g}_p$ is the estimate of the projected gradient, $\alpha$ is the SGD learning rate, and $\pi_C$ projects to the admissible set $C$.

Note that taking a small step $\epsilon$ computes a numerical approximation of the tangent space, which will work in a broader range of cases (e.g. for non-differentiable constraints). If you can, it will always be better (more exact and numerically stable) to analytically project the gradient. But this will obviously depend on your specific problem.

For Adam, you would use the projected gradient $g_p$ or its estimate $\widehat{g}_p$ and feed it to Adam. Adam then does its thing (estimating first/second moments, rescale/normalise gradients) and do a preliminary update step $$ \widetilde{x}_{n+1} = x_n - \alpha \widetilde{g}_p~, $$ where $\widetilde{g}_p$ is Adam's modified version of the projected gradient (based on the current and past gradients you fed it), and $\alpha$ is its learning rate. Last thing to do is the final projection: $$ x_n = \pi_C(\widetilde{x}_{n+1})~. $$

Background: The problem is not the exponential moving average but Adam's gradient normalisation based on the second moment. Essentially, the average gradient is rescaled by its average magnitude, which (for unconstraint problems) results in nice behaviour: If the magnitude is consistently small, gradients are scaled up to speed up convergence; if its huge, they are scaled down to avoid overshooting; if gradients are noisy around zero (small average gradient but large average magnitude), they are also scaled down, allowing for a precise convergence.

However, for projected gradients, this is a problem. The magnitude of the original gradient may be much larger than the magnitude of the projected gradient (especially close to an optimum on one of the constraints). If you do not project the gradients before feeding them the Adam, it will happily rescale everything with the magnitude of the original gradient, which basically means that things cannot ever converge. However, if you feed it the projected gradient, it will "see" its small magnitude, rescale it appropriately and things should be fine.

Edit: For linear equality constraints, it does not make a difference whether you first go into the unprojected gradient direction ($g$ below) and then project down, or you first project the gradient ($g_p$ below) and then take a step into that direction. For non-linear equality constraints, you would need to perform a second projection in the second case to correct for the errors due to the curvature.

For Adam, however, it makes a big difference because in the first case it sees a much larger gradient than in the second case. Adam tries to always make the effective gradient unit size, so it will scale down excessively in the first case.

projected gradient

$\endgroup$
18
  • $\begingroup$ Thank you for the answer! I want to check whether I understand. The standard projected gradient descent update rule (without Adam) is $x_{n+1} = \pi(x_n - \alpha \nabla f(x_n))$, where $\pi$ is the projection step. If I understand correctly, you are suggesting I compute $g = (x_n - \pi(x_n - \alpha \nabla f(x_n))/\alpha$, then feeding $g$ into Adam instead of $\nabla f(x_n)$? Is that right? What should I use as $\alpha$? (You refer to "projected gradient", but projected gradient descent does projection on the updated $x_n$, not on the gradient itself, hence why I'm asking.) $\endgroup$ – D.W. Apr 17 at 21:23
  • $\begingroup$ I expanded my answer a bit... Yes, effectively I am suggesting exactly what you said. If the projection is very involved, you probably have to do it that way. Otherwise you can directly project the gradient down to the tangent space at $x_n$. The problems with the "standard" approach as well as this alternative are also mentioned in this thread. With the adaptive gradients from Adam these problems are getting even worse for the reasons I explained. $\endgroup$ – user2700143 Apr 20 at 21:50
  • $\begingroup$ Concerning the learning rate, for the projection as you wrote it, you basically want $\alpha$ as small as possible, which in the limit $\alpha\rightarrow0$ precisely corresponds to projecting to the tangent space. If you are asking about the learning rate of Adam, that very much depends on your loss function / optimisation landscape and how noisy your gradients are. It's hard to give general advice here. As a simple rule of thumb: As large as possible without the loss going crazy with first converging but then shooting up again :D $\endgroup$ – user2700143 Apr 20 at 21:56
  • $\begingroup$ Projecting the gradient and then applying it is not equivalent to applying the gradient and then projecting the result. $x_{n+1} = \pi(x_n - \alpha \nabla f(x_n))$ is not the same as $x_{n+1} = x_n - \alpha \pi(\nabla f(x_n))$. Consider the case where $x_n$ is on one side of the constraint and $x_n - \alpha \nabla f(x_n)$ is on the other side of the constraint -- that case is not considered in your picture, and those two methods yield different results in that case. They are different even for linear constraints. $\endgroup$ – D.W. Apr 20 at 22:15
  • $\begingroup$ Yes, that's correct, I should have been more precise: They are (approximately) equivalent for (approximately) linear equality constraints (or if $x_n$ lies on the constraint for other reasons). As I said, generally, you will need to do what you suggested, also because the tangent space may be ill-defined, e.g. for non-differentiable constraints. $\endgroup$ – user2700143 Apr 21 at 8:19
1
$\begingroup$

tl;dr: All gradient descent-based methods have an update rule similar to Adam's, so I think they'd all give you some grief. I don't know of any optimizers tailored to your application (but maybe you could invent one!)

Long answer:

According to this, Adam has four hyperparameters that typically don't require much tuning (although of course model hyperparameters will still need to be tuned, such as number of hidden units per layer, etc.)

  • alpha. Also referred to as the learning rate or step size. The proportion that weights are updated (e.g. 0.001). Larger values (e.g. 0.3) results in faster initial learning before the rate is updated. Smaller values (e.g. 1.0E-5) slow learning right down during training
  • beta1. The exponential decay rate for the first moment estimates (e.g. 0.9).
  • beta2. The exponential decay rate for the second-moment estimates (e.g. 0.999). This value should be set close to 1.0 on problems with a sparse gradient (e.g. NLP and computer vision problems).
  • epsilon. Is a very small number to prevent any division by zero in the implementation (e.g. 10E-8).

There are several other optimizers out there, such as AdaGrad and RMSprop. The idea from the 2015 paper on Adam was that by doing a combination of AdaGrad and RMSprop, you get a better optimizer (Adam).

The algorithm for Adam is explained in the 2015 paper (Algorithm 1). The exponential smoothing portion applies specifically to the (biased) estimates of the first and second moment. The only time your actual parameter value plays a role is in the calculation of the gradient, and then in the update.

In the update step (last part of the while loop in Algorithm 1), you perform this calculation:

x_t = x_{t-1} - alpha*(unbiased estimate of the first moment)/(sqrt(unbiased estimate of the second moment) + epsilon)

If you restrict x to be greater than or equal to 0, then if x_{t-1} ever becomes zero, you can no longer update (the subtraction of alpha*(stuff) would result in something less than 0, which you then clip to be 0, which means you'd get 0 as the result in each subsequent update step).

Maybe that's the source of the issue? If so, I would recommend restricting your entire parameter space to be above zero. That is, in your initializer, make sure the initial values are all positive (i.e. don't use Glorot/Xavier initialization, because you could get initial values less than 0, as this initializer is based on the Normal distribution).

$\endgroup$
1
  • $\begingroup$ Essentially you're trying to do nonlinear optimization (based on a neural network) with linear constraints (x >= 0). So try looking for resources on "nonlinear optimization with linear constraints". $\endgroup$ – StatsSorceress Dec 9 '18 at 17:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.