4
$\begingroup$

Suppose $ q $ and $ A $ are given and that $ q, p \in R^{N} $ and $ A \in R^{NxN} $, then how can I find the vector $ p $ such that $$ (q - p)^{T}A(q - p) $$ is minimized constraint to $ \sum_{i=1}^{N} |p_{i}| \leq 1 $ (thus the $ ||p||_{1} \leq 1 $ ) using projected gradient descent?

Is it also possible to apply projected gradient descent with the constraint of $ ||p||_{1} = 1 $ as well?

I can find the gradient of the cost function itself, but given the "updated" $p$ value, I need to project it via $argmin_{p^{*}} (||p - p^{*}||)$ where the $p^{*}$, which is what I want, is the updated p value projected into the feasible space, but I'm not sure how I can go about doing that part.

|cite|improve this question
$\endgroup$
  • $\begingroup$ If you are constrained to some manifold g(x)=0, you can just solve the rootfinding problem using something like Newton's method to project to the manifold. If your steps aren't large (i.e. the learning rate isn't too big) then each step will be close to the manifold and the projection won't be much of a change. $\endgroup$ – Chris Rackauckas Oct 27 '17 at 4:30
  • 1
    $\begingroup$ @ChrisRackauckas The problem is that this manifold isn't smooth, so standard Newton's method won't work. (A former colleague has done work on semismooth Newton methods for this, but afak it hasn't been published yet.) $\endgroup$ – Christian Clason Oct 27 '17 at 12:04
  • $\begingroup$ Oh, I forgot to add that A is a symmetric, positive semi-definite matrix $\endgroup$ – Mike Chen Oct 27 '17 at 17:29
1
$\begingroup$

So you want to solve $$ \min_{\|p\|_1 \leq 1} f(q). $$ with $f(p)=(p-q)^TA(p-q)$. If $A$ is symmetic positive semidefinite this is a smooth convex objective with a convex constraint and hence, this can be done by projected gradient by iterating $$ p^{n+1} = P(p^n - t_n 2A(p^n-q)) $$ where $P$ is the orthogonal projection onto the set $\{\|p\|_1\leq 1\}$. This projection can be computed pretty quick and algorithms for this are rediscovered basically every year. Maziar Sanjabi gave a link to one good source already. The $t_n$ are stepsizes and you can use $t_n = 1/(2\|A\|)$ (if I am not mistaken). If this is slow, a cheap acceleration is accelerated projected gradient descent (aka FISTA or Nesterov's accelerated gradient method).

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Is the step size of tn proportional to the reciprocal of the norm of the matrix A? or determinant? $\endgroup$ – Mike Chen Oct 30 '17 at 17:50
  • $\begingroup$ It's the norm of $A$ (the spectral norm, i.e. the largest eigenvalue of $A$ - this is because the matrix is symmetric positive semidefinite, otherwise it would be the square root of the largest singular value). $\endgroup$ – Dirk Oct 30 '17 at 18:07
  • $\begingroup$ By the way, is there a derivation of why I would be using P(p - tA(p-q) ) ? it seems like A(p-q) is the "gradient" portion in the gradient descent but seems quite counter-intuitive why I would just calculate A(p-q) $\endgroup$ – Mike Chen Nov 20 '17 at 16:48
  • $\begingroup$ And also because that if step size = 1/(largest eigenvalue of A) but if the largest eigenvalue of A is a positive value less than 1, then the step size would be larger than 1, which also sounds counterintuitive. $\endgroup$ – Mike Chen Nov 20 '17 at 18:28
  • $\begingroup$ Actually, the gradient is $2A(p-q)$ (corrected). I have no idea what your intuition is here, but that's how it is. Also, stepsizes can be very small or very large for any gradient method and their particular size is of no meaning (multiplying the objective by any positive constant scales the stepsizes arbitrarily). $\endgroup$ – Dirk Nov 20 '17 at 18:52
3
$\begingroup$

Unfortunately, there is no closed form expression for the projection to the $\ell^1$ ball; it is also not a componentwise operation. In principle, the projection onto the scaled unit ball $\alpha B_{\ell^1}$ for $\alpha>0$ is given by $$ \Pi(x) = \begin{cases} x & \|x\|_1 \leq \alpha \\ S_{\lambda(x)}(x) & \|x\|_1>\alpha\end{cases} $$ where $S_\lambda$ is the soft thresholding (or soft shrinkage) operator, which for $\lambda>0$ is given component-wise by $$ [S_\lambda(x)]_i = \begin{cases} x_i-\lambda & x_i\geq \lambda\\ 0 & |x_i| \leq \lambda \\ x_i+\lambda & x_i\leq -\lambda \end{cases} $$ and $\lambda(x)>0$ has to be chosen such that $\|S_{\lambda(x)}x\|_1=\alpha$ or, equivalently, that $$ \sum_i \max\{|x_i|-\lambda(x),0\} = \alpha. $$ This is a scalar (but nondifferentiable) root-finding problem, which can be solved using bisection, the algorithm given in the link in Maziar Sanjabi's answer (which is an efficient implementation based on partitioning the components of the vector $x$) or a semismooth Newton method (or any combinations thereof).

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I've taken a look at Maziar Sanjabi's link and those "approximations" were not accurate enough but the bisection method works really well and is just as quick ! $\endgroup$ – Mike Chen Nov 20 '17 at 18:25
0
$\begingroup$

You can use the algorithm in the following paper to project the gradient update to l1 norm ball: https://stanford.edu/~jduchi/projects/DuchiShSiCh08.pdf

|cite|improve this answer
$\endgroup$

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.