Reparameterizing Mirror Descent as Gradient Descent

Ehsan Amid, Manfred K. Warmuth

This paper bridges a significant gap between two fundamental optimization families: Gradient Descent (GD) and Mirror Descent (MD). By showing that many Mirror Descent updates are simply Gradient Descent in disguise, the authors provide a roadmap for building more efficient neural networks that naturally favor sparse solutions.

The Challenge: Optimization Geometry in Deep Learning

In deep learning, Gradient Descent is the undisputed king. However, GD assumes a "flat" Euclidean geometry. For certain problems—specifically when the target solution is sparse (mostly zeros)—other algorithms like Mirror Descent (MD) are provably more efficient.

The challenge is that modern deep learning software stacks (like PyTorch or TensorFlow) are built around GD and backpropagation. MD requires a "link function" (or mirror map) to transform parameters before updating them, which doesn't always fit neatly into standard training loops. Furthermore, there has been a long-standing question in the field: Does the way we parameterize a model (its architecture) change what it learns, even if the underlying math is the same? This paper tackles both the practical implementation of MD and the theoretical understanding of this "implicit bias."

Bridging the Gap: Methods and Reparameterization

The authors focus on Continuous-time Mirror Descent (CMD), analyzing the updates as differential equations. Their key contributions center on translating these updates into standard GD.

1. The Reparameterization Theorem: They prove that a CMD update on a parameter $w$ can be perfectly matched by a GD update on a new parameter $u$, provided there is a specific mapping $w = q(u)$.

2. Tempered Updates and the $\tau$ Spectrum: They introduce a family of "tempered" updates using a "tempered logarithm" ($\log_\tau$). This creates a continuous spectrum of optimization geometries.

  • When $\tau = 0$, the optimization equates to standard Gradient Descent.
  • When $\tau = 1$, it yields Exponentiated Gradient (EG), which is ideal for sparse targets.
The tempered logarithm function for various values of tau, illustrating the continuous spectrum between standard Gradient Descent and Exponentiated Gradient.

By introducing the temperature parameter $\tau$, researchers can "tune" the implicit bias of their model, interpolating between the $L_2$ norm (standard GD) and the $L_1$ norm (sparsity-inducing) by sliding $\tau$ between 0 and 1.

Architecture is Optimization

Perhaps the most profound insight from the paper is that the structure of a neural network is a choice of optimization geometry. By simply changing how we write the equations for our weights (e.g., using $w = u^2$ instead of $w = u$), we change GD into a version of Mirror Descent.

They demonstrate this through "Architectural Mapping." A specific "spindly" two-layer network trained with GD behaves exactly like a single-layer network trained with Mirror Descent.

A spindly two-layer network architecture that naturally implements a sparsity-favoring update through reparameterization.

Because MD can be written as GD on a reparameterized network, you can implement these advanced optimization techniques using standard backpropagation without modifying the underlying optimizer code.

Key Results and Theoretical Insights

Using synthetic underdetermined linear regression problems (where there are more features than data points), the authors test which "norm" (or bias) the algorithm converges to when many solutions are possible.

  • Equivalence Conditions (Theorem 2): The paper provides the exact mathematical conditions under which a reparameterization $w = q(u)$ makes GD on $u$ equivalent to MD on $w$.
  • Implicit Bias (Theorem 4): In the case of underdetermined linear regression, the authors prove that their "tempered" updates converge to the solution with the minimum $L_{2-\tau}$ norm. This confirms that reparameterization successfully shifts the model's bias toward sparsity as $\tau$ increases.
  • Natural Gradient Connection: The paper also shows that CMD is essentially a form of Natural Gradient Descent where the "metric" is defined by the Hessian of the mirror map.

Limitations and Future Work

While the theoretical framework is robust, the authors note a few limitations:

  • Discretization Gap: The equivalence is proven for continuous time. In practice, we use discrete steps (learning rates). While the discrete versions closely track each other empirically, proving strict equivalence in discrete time remains an open problem.
  • Complexity of Deep Nets: The analysis is most straightforward for linear models or the final layers of networks. Extending this precise understanding of implicit bias to very deep, non-linear architectures is a major future direction.
  • Matrix Case: The current paper focuses on vectors. Extending this to matrix-valued parameters (useful for tasks like collaborative filtering) is highlighted as a promising next step.

Summary updated

Abstract

Most of the recent successful applications of neural networks have been based on training with gradient descent updates. However, for some small networks, other mirror descent updates learn provably more efficiently when the target is sparse. We present a general framework for casting a mirror descent update as a gradient descent update on a different set of parameters. In some cases, the mirror descent reparameterization can be described as training a modified network with standard backpropagation. The reparameterization framework is versatile and covers a wide range of mirror descent updates, even cases where the domain is constrained. Our construction for the reparameterization argument is done for the continuous versions of the updates. Finding general criteria for the discrete versions to closely track their continuous counterparts remains an interesting open problem.
BibTeX
@inproceedings{amid2020reparameterizing,
  author = {Ehsan Amid and Manfred K. Warmuth},
  title = {{Reparameterizing Mirror Descent as Gradient Descent}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=dC8koOuXLG},
}
Figure