Gradient Projection

The defining mechanism of gradient projection is the constraint satisfaction problem it solves during each training step. For a new task's gradient g, the algorithm projects it onto a feasible region defined by the condition that the loss on past tasks, computed from a stored episodic memory, does not increase. This is mathematically formulated as minimizing the angle between g and the updated gradient g̃, subject to inequality constraints: ⟨g̃, v_k⟩ ≥ 0 for all past task gradient vectors v_k stored in memory. This ensures the parameter update is interference-aware.

Gradient projection methods rely on a fixed-capacity episodic memory buffer M to retain a representative subset of examples from previous tasks. This buffer is critical for two reasons:

• Constraint Definition: The loss on these stored examples defines the feasible region for new gradients.
• Efficiency: Storing raw data is more sample-efficient for defining constraints than storing only gradient directions, as the loss landscape can be non-linear. The buffer is typically managed via reservoir sampling or herding to maintain a balanced representation of past data distributions within a limited memory budget.

The projection operation is solved as a Quadratic Program (QP). The objective is to find the new gradient g̃ closest to the proposed gradient g (in L2-norm) that satisfies all constraints. The dual of this QP often has a simpler form, leading to efficient solvers. In GEM, if all constraints are satisfied (i.e., g is already in the feasible cone), no projection occurs. If violated, the solution finds the minimal perturbation to g that makes it feasible. This makes the per-update computational cost dependent on the number of active constraints from past tasks.

A key advantage over simple regularization is the potential for positive backward transfer. By constraining updates to not increase past loss, gradient projection doesn't just preserve old knowledge—it can refine it. The projected gradient may have a component that actively reduces the loss on previous tasks, leading to improved performance on past data after learning new tasks. This contrasts with methods like Elastic Weight Consolidation (EWC) that primarily enforce stability (zero-forgetting) but do not actively seek improvement.

Gradient projection algorithms are inherently suited for online continual learning settings. They process data in a single pass or in small batches, updating constraints dynamically with each new task. The QP solver operates on a per-minibatch basis, making the approach compatible with stochastic gradient descent. Advanced variants like Averaged GEM (A-GEM) simplify the constraint to an average over the memory buffer, drastically reducing computational overhead and making large-scale online application more feasible.

The approach involves several practical trade-offs:

• Memory-Forgetting Trade-off: Performance is tightly coupled to the size and quality of the episodic memory buffer. A small buffer may not adequately represent past tasks.
• Computational Overhead: Solving the QP, though efficient for a moderate number of tasks, adds overhead compared to a standard SGD step.
• Task Boundary Assumption: Classic GEM assumes clear task boundaries to update the constraint set, which may not exist in pure domain-incremental or class-incremental streams without identifiers. Hybrid approaches with dynamic constraint updates are an area of active research.

The fundamental operation is a projection onto a convex cone. Given a new task's gradient vector g, the algorithm projects it onto a set of constraints that prevent an increase in the loss on past tasks. This is typically formulated as a Quadratic Programming (QP) problem: find the projected gradient g̃ closest to g such that G * g̃ ≤ 0, where G is a matrix whose rows are the gradient vectors of past tasks stored in memory. This ensures the update direction does not interfere with prior knowledge.

Gradient Episodic Memory (GEM) is the canonical gradient projection algorithm. It maintains a small episodic memory of exemplars from previous tasks. During training on a new task, it computes the proposed gradient g and solves the QP problem to find a projected gradient g̃ that satisfies the inequality constraints derived from the memory buffer. Key features:

• Efficient QP Solution: Uses a dual formulation for faster computation.
• Positive Backward Transfer: By allowing gradients that improve past task performance, it can enable positive backward transfer.
• Memory Management: Relies on reservoir sampling or herding to populate the episodic memory buffer.

Averaged Gradient Episodic Memory (A-GEM) is a computationally efficient approximation of GEM. Instead of enforcing constraints against each past task individually, it enforces a single constraint against the average gradient computed over all examples in the episodic memory. This reduces the QP problem to a simple, closed-form update:

• If the proposed gradient violates the average constraint, it is projected onto the half-space defined by the average gradient.
• This projection is a single vector operation, making A-GEM significantly faster than GEM while often retaining similar performance in mitigating forgetting.

Implementing gradient projection requires careful engineering:

• Memory Budget: The size of the episodic memory buffer is a critical hyperparameter, trading off retention performance against storage.
• QP Solver Overhead: For GEM, the QP solve, though efficient, adds computational overhead per batch compared to standard SGD.
• Gradient Computation: Requires storing and computing gradients for past task examples, increasing backward pass cost.
• Task Boundaries vs. Online: Classical GEM assumes known task boundaries to update the constraint matrix G. Truly online variants must update constraints dynamically.

Gradient projection differs fundamentally from regularization-based methods like EWC or SI:

• Mechanism: Projection actively modifies the update direction before applying it. Regularization adds a penalty term to the loss function.
• Guarantees: Projection can provide hard guarantees (no loss increase on memory examples) under a convex approximation. Regularization provides soft, probabilistic guarantees.
• Memory: Projection requires storing raw data exemplars for gradient computation. Regularization methods store parameter importance weights (scalars).
• Flexibility: Projection can explicitly promote positive backward transfer; regularization primarily focuses on stability.

While pioneered for supervised classification, the gradient projection paradigm extends to other domains:

• Reinforcement Learning: Projecting policy gradients to avoid degrading performance on previously mastered skills or environments.
• Continual Reinforcement Learning: Used in benchmarks like Continual World to prevent catastrophic forgetting in robotic control tasks.
• Online Recommendation Systems: Constraining updates to user preference models to prevent abrupt loss of accuracy on long-term user interests.
• Privacy: The projection mechanism can be integrated with differential privacy guarantees for continual learning on sensitive data streams.

The core mathematical mechanism in GEM. The algorithm formalizes the goal of non-interference as a set of inequality constraints: the angle between the new gradient and each past task's gradient must be non-negative. Finding the update direction becomes a constrained optimization problem: minimize the distance to the original new-task gradient subject to these constraints. This is solved efficiently via quadratic programming solvers.

The fundamental challenge that gradient projection directly addresses. Stability refers to a model's ability to retain knowledge from previous tasks. Plasticity is its capacity to learn new information. Naive sequential training maximizes plasticity at the cost of stability (catastrophic forgetting). Gradient projection algorithms explicitly manage this trade-off by constraining plasticity—allowing weight updates only in directions that preserve stability for past tasks.

The specific type of interference gradient projection aims to eliminate. Negative backward transfer (or catastrophic interference) occurs when learning a new task degrades performance on a previously learned task. This is measured as the difference in performance on an old task before and after training on a new task. Gradient projection algorithms are explicitly designed to achieve non-negative backward transfer, ensuring new learning does not harm old knowledge.

The fixed-size storage component critical to gradient projection methods. Unlike a traditional database, this buffer is actively managed:

• Sampling Strategy: Determines which past examples to store (e.g., reservoir sampling).
• Buffer Size: A key hyperparameter balancing memory cost with forgetting mitigation.
• Content: Typically stores raw input-output pairs (x, y). Variants like Dark Experience Replay (DER) also store the model's logit outputs for stronger regularization. The buffer provides the data needed to compute the gradient constraints for past tasks.