The role of optimization geometry in single neuron learning

Nicholas M. Boffi, Stephen Tu, Jean-Jacques E. Slotine

Introduction

In modern deep learning, the choice of optimizer—such as Adam or AdaGrad—often dictates the generalization performance of a model. While these optimizers deviate from standard Euclidean gradient descent, a rigorous theoretical understanding of why certain "geometries" improve learning in non-linear, non-convex settings has remained elusive. This paper addresses this gap by introducing the Reflectron, a generalized optimization framework for single neurons (Generalized Linear Models, or GLMs). By matching the optimization geometry to the underlying data structure, the authors demonstrate that generalization error can be reduced from polynomial to logarithmic dependence on the input dimension.

The Reflectron Framework

The Reflectron generalizes the classic GLM-tron algorithm by decoupling the search direction from the standard Euclidean metric. It employs two primary components:

  1. Potential Functions ($\psi$): Instead of standard squared distances, the Reflectron uses strongly convex potential functions to define a Bregman divergence. This allows the optimizer to measure "distance" in a way that respects specific data properties like sparsity.
  2. Pseudogradients: The algorithm utilizes a simplified update rule that remains computationally efficient while providing strong convergence guarantees.

The researchers analyzed this framework through continuous-time "flows" and proved that practical discrete-time versions (Forward-Euler discretization) maintain the same statistical advantages.

Beating the Curse of Dimensionality

A central finding of this work is that aligning the optimization geometry with the feature space geometry can drastically improve scaling. For instance, using an entropic potential for sparse data allows the generalization error to scale with $\sqrt{\log d / n}$ rather than the standard $\sqrt{d / n}$.

Test error as a function of dimension d. Non-Euclidean geometries (p-norm, hypentropy) exhibit logarithmic scaling compared to the polynomial scaling of the standard GLM-tron.

As shown in the figure above, as the dimension $d$ increases, the test error for the standard Euclidean GLM-tron grows significantly faster than for the $p$-norm or hypentropy variants, which exploit the underlying sparsity of the problem.

Implicit Bias and Sparse Recovery

The paper proves that the Reflectron naturally converges to a solution that minimizes the Bregman divergence from its starting point. This "implicit bias" means the optimizer's shape determines which solution is found among the many that fit the training data.

Weight recovery for a sparse GLM. The hypentropy Reflectron accurately identifies true non-zero weights, whereas the standard GLM-tron fails to achieve sparsity.

In high-dimensional experiments ($d=10,000$), the hypentropy Reflectron recovered sparse solutions that closely matched the ground truth, whereas the standard GLM-tron produced dense solutions with significant noise. This empirical validation confirms that the choice of geometry can act as an implicit regularizer, effectively recovering sparse structures without explicit $\ell_1$ penalties.

Conclusion and Future Directions

The Reflectron framework provides a powerful lens for understanding how optimization geometry influences learning. While currently focused on single-layer GLMs, these insights suggest that the "logarithmic dimension" benefits might extend to deeper architectures. Future work will involve classifying the natural feature space geometry of large-scale datasets and extending pseudogradient analysis to multi-layer networks to further simplify the theoretical landscape of deep learning.

Summary updated

Abstract

Recent numerical experiments have demonstrated that the choice of optimization geometry used during training can impact generalization performance when learning expressive nonlinear model classes such as deep neural networks. These observations have important implications for modern deep learning but remain poorly understood due to the difficulty of the associated nonconvex optimization problem. Towards an understanding of this phenomenon, we analyze a family of pseudogradient methods for learning generalized linear models under the square loss - a simplified problem containing both nonlinearity in the model parameters and nonconvexity of the optimization which admits a single neuron as a special case. We prove non-asymptotic bounds on the generalization error that sharply characterize how the interplay between the optimization geometry and the feature space geometry sets the out-of-sample performance of the learned model. Experimentally, selecting the optimization geometry as suggested by our theory leads to improved performance in generalized linear model estimation problems such as nonlinear and nonconvex variants of sparse vector recovery and low-rank matrix sensing.
BibTeX
@inproceedings{boffi2022role,
  author = {Nicholas M. Boffi and Stephen Tu and Jean-Jacques E. Slotine},
  title = {{The role of optimization geometry in single neuron learning}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2022},
}
Figure