Interpolating Between Gradient Descent and Exponentiated Gradient Using Reparameterized Gradient Descent

Ehsan Amid, Manfred K. Warmuth

Introduction

In deep learning, Gradient Descent (GD) is the standard optimization algorithm. However, for specific tasks like sparse learning, Mirror Descent (MD) algorithms—such as Exponentiated Gradient (EG)—often demonstrate superior performance. Historically, MD and GD were viewed as distinct optimization paradigms requiring different algorithmic implementations. This research bridges that gap by demonstrating that many MD updates can be mathematically reparameterized as standard GD updates. By altering the model's parameterization, researchers can leverage standard backpropagation to perform sophisticated mirror descent, effectively controlling implicit bias through architecture.

The Reparameterization Framework

The core contribution of this work is the Reparameterization Theorem. It posits that for a model with parameters $w$, one can define a new set of parameters $u$ such that $w = q(u)$. If the function $q$ is chosen such that its Jacobian relates specifically to the Hessian of the MD potential function, performing standard GD on $u$ becomes mathematically identical to performing MD on $w$ in continuous time.

A neural network architecture where weights are reparameterized to induce specific optimization behaviors.

To handle weights that can be both positive and negative, the authors employ a "$\pm$-trick," representing each weight as the difference between two non-negative components ($w = w_+ - w_-$), which are then individually reparameterized.

Tempered Updates and Interpolation

The authors introduce "tempered" updates using a temperature parameter $\tau \in [0, 2)$. This parameter allows for a smooth interpolation between different optimization geometries:

  • $\tau = 0$: The system behaves like standard Gradient Descent, linked to $L_2$ norms.
  • $\tau = 1$: The system behaves like Exponentiated Gradient, linked to entropic divergences and $L_1$ norms.
The tempered logarithm $\log_\tau x$ interpolates between linear and logarithmic scales as $\tau$ varies, corresponding to different optimization regimes.

This interpolation provides a continuous spectrum between the "Euclidean world" of GD and the "Simplex world" of EG, allowing for fine-tuned control over the sparsity of the resulting model.

Key Insights: Architecture as Optimization

The most significant takeaway is that architecture is optimization. The choice of network architecture—specifically how neurons are parameterized—directly dictates the implicit bias of the learner. By changing a linear neuron to a reparameterized one (e.g., using the power law shown in Figure 2), the entire geometry of the learning process is transformed. This implies that standard backpropagation is sufficient to achieve the benefits of Mirror Descent, provided the right reparameterization function $q(u)$ is defined.

Results and Convergence

The theoretical framework was validated using underdetermined linear regression ($N < d$), a standard setting for studying implicit bias. The authors proved that their tempered updates converge to the solution that minimizes the $L_{2-\tau}$ norm. This confirms that reparameterized GD successfully inherits the sparse-seeking properties of MD. The mathematical equivalence holds strictly in continuous-time mirror descent (CMD), providing a rigorous foundation for these architectural choices.

Limitations and Future Work

While the continuous-time proofs are robust, a "discretization gap" exists. In practice, optimization occurs in discrete steps, and the trajectories of standard GD and MD may diverge. Future research is needed to establish criteria for when these discrete versions remain close. Additionally, while the theory applies to single layers, extending these insights to deep, multi-layer non-linear networks and matrix-valued parameters remains an open area of exploration.

Summary updated

BibTeX
@inproceedings{amid2020interpolating,
  author = {Ehsan Amid and Manfred K. Warmuth},
  title = {{Interpolating Between Gradient Descent and Exponentiated Gradient Using Reparameterized Gradient Descent}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=dC8koOuXLG},
}
Figure