PROJECTED GRADIENT DESCENT

• Gradient-based optimization is widely used in various fields.
• Many problems include constraints that must be satisfied.
• Projected Gradient Descent (PGD) extends standard gradient descent by ensuring iterates remain feasible within a given constraint set.

Constrained Minimization

Let $f:D(f)\to \mathbb{R}$ be convex and let $X\subseteq D(f)$ be a convex set. A point $x\in X$ is a minimizer of $f$ over $X$ if:

Lemma 1

If $f:D(f)\to \mathbb{R}$ is convex and differentiable over an open domain $D(f)\subseteq {\mathbb{R}}^n$ and $X\subseteq D(f)$ is a convex set, then a point $x^{\ast }\in X$ is a minimizer of $f$ over $X$ if and only if:

Definition of Projected Gradient Descent

Consider the constrained optimization problem:

where $X$ is a feasible convex set. The Projected Gradient Descent (PGD) iterates are given by:

where $P_X(\cdot )$ is the projection operator.

Projected Gradient Descent Algorithm

Initialization

Choose an initial point $x_0\in X$.

Iterative Steps

For $k=0,1,2,\dots$:

1. Compute the gradient:$$g_k=\mathrm{\nabla }f(x_k)$$
2. Take a gradient step:$$y_k=x_k-{\gamma }_k{g}_k$$
3. Project onto the feasible set $X$:$$x_{k+1}=P_X(y_k)$$

Repeat until convergence.

Theorem 1: Step Size Selection

If $f(x)$ is convex and $L$-smooth

then the Projected Gradient Method converges for step sizes satisfying:

A common choice is:

Theorem 2: Convergence Rate

Let $f:{\mathbb{R}}^n\to \mathbb{R}$ be convex and differentiable, $X\subseteq {\mathbb{R}}^n$ closed and convex, and let $x^{\ast }$ be a minimizer of $f$ over $X$. Suppose that:

• $\parallel x_0-x^{\ast }\parallel \le R$ with $x_0\in X$.
• $\parallel \mathrm{\nabla }f(x)\parallel \le B$ for all $x\in X$.

Where $B$ is the Lipschitz constant of the gradient.

Choosing the constant step size:

Projected Gradient Descent yields:

Looks the same as the Gradient Descent convergence rate!

Theorem 3: Convergence Rate (Smooth Case)

Let $f:{\mathbb{R}}^n\to \mathbb{R}$ be convex and differentiable, and let $X\subseteq {\mathbb{R}}^n$ be a closed convex set. Suppose there is a minimizer $x^{\ast }$ of $f$ over $X$ and that $f$ is smooth over $X$ with parameter $L$. Choosing the step size:

Projected Gradient Descent yields:

Looks similar to the Gradient Descent smooth case!

Theorem 4: Error Bound

If $f:{\mathbb{R}}^n\to \mathbb{R}$ is convex and differentiable, and $f$ is $L$-smooth and strongly convex with parameter $\mu >0$, then choosing:

Projected Gradient Descent satisfies:

1. Geometric Decrease in Distance to $x^{\ast }$:

   $$\parallel x_{k+1}-x^{\ast }{\parallel }^2\le (1-\frac{\mu }{L})\parallel x_k-x^{\ast }{\parallel }^2,k\ge 0.$$

2. Exponential Decrease in Function Value:

   $$f(x_K)-f(x^{\ast })\le \frac{L}{2}{(1-\frac{\mu }{L})}^K\parallel x_0-x^{\ast }{\parallel }^2,K>0.$$

Thus, error decreases exponentially as iterations proceed.

Summary:

• Projected Gradient Descent (PGD) is an extension of gradient descent for constrained problems.
• It ensures that iterates remain feasible within the constraint set $X$.
• The projection step ensures valid updates.
• Step sizes are chosen to ensure convergence based on properties of the function (e.g., smoothness).
• Convergence rate depends on problem smoothness and strong convexity.

PGD is widely used in optimization, machine learning, and constrained convex problems. 🚀