Projected Gradient Methods

Projected Gradient Descent (PGD) is a practical and often intuitive algorithm for constrained optimization. This method extends the familiar gradient descent algorithm to handle problems where the solution must lie within a specific feasible set, $\mathcal{C}$.

The core idea is remarkably simple: perform a standard gradient descent update, and if this step takes you outside the feasible set $\mathcal{C}$, project the resulting point back onto the set. This approach is particularly effective when the projection onto $\mathcal{C}$ can be computed efficiently.

The Constrained Optimization Problem

Recall the general form of a constrained optimization problem that PGD addresses: $\min_{\mathbf{x}} f(\mathbf{x}) \quad \text{subject to} \quad \mathbf{x} \in \mathcal{C}$ Here, $f(\mathbf{x})$ is the objective function we want to minimize (often a loss function in machine learning), and $\mathcal{C}$ represents the feasible set defined by the constraints on the parameters $\mathbf{x}$. PGD assumes that $\mathcal{C}$ is a non-empty, closed, and convex set.

The Projection Operator

Central to PGD is the concept of the projection operator, denoted as $\Pi_{\mathcal{C}}$. For any point $\mathbf{y}$ in the parameter space, its projection onto the set $\mathcal{C}$ is defined as the point in $\mathcal{C}$ that is closest to $\mathbf{y}$ in terms of Euclidean distance: $\Pi_{\mathcal{C}}(\mathbf{y}) = \arg \min_{\mathbf{x} \in \mathcal{C}} ||\mathbf{x} - \mathbf{y}||_2^2$ Intuitively, $\Pi_{\mathcal{C}}(\mathbf{y})$ finds the "best approximation" of $\mathbf{y}$ within the allowed region $\mathcal{C}$.

The feasibility and efficiency of PGD hinge entirely on how easily this projection can be computed. Fortunately, for many common constraint sets encountered in machine learning, the projection has a simple closed-form solution or can be computed efficiently.

Examples of Projections

1. Box Constraints: If the feasible set is defined by element-wise lower and upper bounds, $\mathcal{C} = \{\mathbf{x} | l_i \le x_i \le u_i \text{ for all } i\}$, the projection is straightforward. For a point $\mathbf{y}$, the projection $\mathbf{x} = \Pi_{\mathcal{C}}(\mathbf{y})$ is computed by clipping each component: $x_i = \max(l_i, \min(y_i, u_i))$ A common special case is non-negativity constraints ($l_i=0, u_i=\infty$), where $x_i = \max(0, y_i)$.

2. Euclidean Ball (L2 Norm Ball): If the feasible set is a ball of radius $R$ centered at the origin, $\mathcal{C} = \{\mathbf{x} | ||\mathbf{x}||_2 \le R\}$, the projection is: $\Pi_{\mathcal{C}}(\mathbf{y}) = \begin{cases} \mathbf{y} & \text{if } ||\mathbf{y}||_2 \le R \\ R \frac{\mathbf{y}}{||\mathbf{y}||_2} & \text{if } ||\mathbf{y}||_2 > R \end{cases}$ If the point $\mathbf{y}$ is already inside or on the boundary of the ball, it remains unchanged. If it's outside, it gets scaled down radially to lie on the boundary.

3. Probability Simplex: If the feasible set requires parameters to be non-negative and sum to one, $\mathcal{C} = \{\mathbf{x} | \sum_i x_i = 1, x_i \ge 0\}$, the projection is more involved but efficient algorithms exist, often based on sorting and finding an appropriate threshold.

If the projection onto $\mathcal{C}$ is computationally expensive (e.g., requires solving another optimization problem), then PGD might not be the most practical choice.

The Projected Gradient Descent Algorithm

The PGD algorithm iteratively updates the parameters $\mathbf{x}$ using two steps:

1. Gradient Step: Compute an intermediate point $\mathbf{y}_{k+1}$ by taking a step in the negative gradient direction, just like standard gradient descent: $\mathbf{y}_{k+1} = \mathbf{x}_k - \eta_k \nabla f(\mathbf{x}_k)$ Here, $\mathbf{x}_k$ is the current parameter vector, $\nabla f(\mathbf{x}_k)$ is the gradient of the objective function at $\mathbf{x}_k$, and $\eta_k$ is the learning rate at iteration $k$.

2. Projection Step: Project the intermediate point $\mathbf{y}_{k+1}$ back onto the feasible set $\mathcal{C}$ to obtain the next iterate $\mathbf{x}_{k+1}$: $\mathbf{x}_{k+1} = \Pi_{\mathcal{C}}(\mathbf{y}_{k+1})$

This process is repeated until some convergence criterion is met (e.g., the change in $\mathbf{x}$ or $f(\mathbf{x})$ is small, or a maximum number of iterations is reached).

Visualization of a single PGD step. The gray shaded area represents the feasible set $\mathcal{C}$. Starting from $\mathbf{x}_k$, a gradient step leads to $\mathbf{y}_{k+1}$ outside $\mathcal{C}$. The projection $\Pi_{\mathcal{C}}$ maps $\mathbf{y}_{k+1}$ to the nearest point $\mathbf{x}_{k+1}$ within $\mathcal{C}$.

Learning Rate Selection

Choosing the learning rate $\eta_k$ follows similar principles as in unconstrained gradient descent. It can be fixed, follow a decay schedule (e.g., $\eta_k = \eta_0 / \sqrt{k}$), or be determined by a line search method adapted for the projection step. A common strategy is backtracking line search, where $\eta$ is reduced until the projected step satisfies certain conditions (e.g., sufficient decrease in $f(\mathbf{x})$).

Convergence Properties

When $f$ is convex and its gradient is Lipschitz continuous, and the feasible set $\mathcal{C}$ is closed and convex, PGD is guaranteed to converge to an optimal solution $\mathbf{x}^* \in \mathcal{C}$. The convergence rate is typically $O(1/k)$, similar to standard gradient descent. If $f$ is also strongly convex, linear convergence ($O(\rho^k)$ for some $\rho < 1$) can be achieved.

For non-convex functions $f$, PGD generally converges to a stationary point that satisfies first-order necessary conditions (related to KKT conditions), but global optimality is not guaranteed.

Applications in Machine Learning

PGD finds use in various machine learning scenarios involving constraints:

1. Non-negative Least Squares/Matrix Factorization: Problems like Non-negative Matrix Factorization (NMF) require factor matrices to have non-negative entries. PGD with projection onto the non-negative orthant ($\mathbf{x} \ge 0$) is a common approach.
2. Constrained Parameter Spaces: Training models where weights need to satisfy certain bounds (e.g., $|w_i| \le C$ or $||\mathbf{w}||_2 \le R$). PGD with box or L2 ball projection can enforce these constraints.
3. Regularization via Constraints: Sometimes, regularization is formulated as a constraint (e.g., minimize loss subject to $||\mathbf{w}||_1 \le \lambda$) instead of adding a penalty term. PGD can be applied if the projection onto the corresponding norm ball is feasible (projection onto the L1 ball is possible but more complex than L2).
4. Adversarial Example Generation (PGD Attack): In adversarial machine learning, PGD is a standard method for finding adversarial examples. It performs projected gradient ascent on the loss function with respect to the input data, subject to constraints that the perturbed input remains close to the original (e.g., within an $L_\infty$ or $L_2$ norm ball). The projection step ensures the perturbation stays within the allowed bounds.

Implementation Approaches and Limitations

Implementing PGD requires:

• A function to compute the gradient $\nabla f(\mathbf{x})$.
• A function to compute the projection $\Pi_{\mathcal{C}}(\mathbf{y})$.
• A strategy for selecting the learning rate $\eta_k$.

Pseudo-code for Projected Gradient Descent:

Initialize x_0 within C
Set learning rate strategy (e.g., fixed η or schedule)
k = 0
while not converged:
    # Compute gradient
    g_k = ∇f(x_k)

    # Gradient step
    y_{k+1} = x_k - η_k * g_k

    # Projection step
    x_{k+1} = Π_C(y_{k+1})

    # Update iteration count
    k = k + 1

Return x_k

The primary limitation of PGD is its reliance on an efficient projection operator. If $\mathcal{C}$ is defined by complex, coupled constraints (e.g., general linear or non-linear equalities/inequalities), computing the projection can be as hard as solving the original problem. In such cases, other methods like augmented Lagrangian or interior-point methods might be more suitable.

Furthermore, PGD can sometimes exhibit slow convergence, especially if the unconstrained gradient steps frequently point far away from the feasible set, causing the projection step to significantly shorten the effective step length. This can lead to "zig-zagging" behavior along the boundary of $\mathcal{C}$.

Despite these limitations, Projected Gradient Descent remains a valuable and widely used tool for optimization problems where parameters are subject to simple constraints, offering a natural extension of gradient descent that explicitly maintains feasibility throughout the optimization process.