Particle dual averaging: optimization of mean field neural network with global convergence rate analysis*

Atsushi Nitanda, Denny Wu, Taiji Suzuki

TL;DR

This paper introduces the Particle Dual Averaging (PDA) method, a novel algorithm for optimizing neural networks in the "mean field regime." PDA provides the first quantitative global convergence guarantees for this challenging setting, offering a theoretical foundation for understanding how deep learning can learn features beyond simple kernel methods.

What Problem Does This Paper Address?

Neural networks, especially deep ones, often exhibit impressive performance that goes beyond what classical kernel methods can explain. One theoretical framework for understanding this phenomenon is the "mean field regime," where the network's behavior can be viewed as an optimization problem over probability distributions. While this regime is theoretically attractive for its ability to capture "feature learning" (where the network learns useful representations of the data), obtaining rigorous, quantitative convergence guarantees for optimization algorithms in this setting has been a major challenge. Existing methods often rely on strong assumptions or continuous-time approximations, limiting their practical applicability. This paper aims to bridge this gap by developing an algorithm with provable convergence rates for optimizing neural networks in the mean field regime.

Methods

The core contribution is the Particle Dual Averaging (PDA) algorithm. PDA combines two key ideas:

  1. Inner Loop: Langevin Algorithm: PDA uses the Langevin algorithm to draw samples from an approximate stationary distribution. This is a standard technique for sampling from probability distributions, particularly those defined by potentials.
  2. Outer Loop: Dual Averaging: The algorithm then uses a generalized version of the "dual averaging" method (originally developed for convex optimization) to optimize this distribution. This outer loop iteratively updates the distribution towards the optimal one.

Essentially, PDA can be seen as extending the Langevin algorithm to handle complex, non-linear optimization problems on the space of probability distributions, which is crucial for the mean field regime of neural networks. The authors adapt finite-dimensional convex optimization theory to the infinite-dimensional space of probability measures.

Datasets

The paper uses synthetic datasets for experiments, including:

  • Synthetic student-teacher settings: Used for both regression and classification tasks, where labels are generated from a teacher model with added noise.
  • MNIST dataset: Used for binary classification (separating odd vs. even digits).

Key Insights and Ideas

  • Bridging the Gap: PDA provides a theoretical bridge between the well-understood "kernel regime" and the more complex "mean field regime," offering a path to understand feature learning in deep networks.
  • Dual Averaging for Distributions: The paper successfully extends the powerful dual averaging optimization framework from finite-dimensional spaces to the infinite-dimensional space of probability distributions.
  • Langevin as a Building Block: The Langevin algorithm, typically used for sampling, is repurposed as a crucial component within a larger optimization framework (PDA).
  • Quantitative Guarantees: For the first time, the paper provides quantitative, polynomial-time convergence guarantees for optimizing two-layer neural networks in the mean field regime, even under more general settings than previous work.

Key Results

  • Theoretical Guarantees: The paper establishes quantitative global convergence rates for PDA in minimizing regularized objectives for two-layer mean field neural networks. Specifically, they show that the algorithm achieves an $\epsilon$-accurate solution in $O(\epsilon^{-3})$ iterations.
  • Particle Complexity: The analysis also accounts for the finite-particle approximation error, showing that a polynomial number of particles is sufficient.
  • Empirical Validation: Numerical simulations on neural networks of reasonable size support the theoretical findings, demonstrating the $O(T^{-1})$ convergence rate of the outer loop and showing PDA's effectiveness in learning useful features.
  • Feature Learning Demonstration: Experiments visualize how PDA can learn useful features, aligning parameters with the target function's structure, which is a key advantage over kernel methods.

Limitations and Future Work

  • Two-Layer Networks: The theoretical analysis is primarily focused on two-layer neural networks. Extending the guarantees to deeper or more complex architectures is a significant future direction.
  • Regularization Dependence: The convergence rate's dependence on the entropy regularization parameter ($\lambda_2$) can be exponential, which might limit its effectiveness under very weak regularization.
  • Computational Cost: While PDA offers theoretical advantages, the practical implementation and computational cost, especially with a large number of particles, might still be a challenge.
  • Specific Problem Instances: The authors plan to investigate specific problem instances where convergence rates can be obtained under vanishing regularization.
  • Accelerated Variants: Exploring accelerated variants of PDA to further improve convergence speed is another promising avenue.
  • Broader Applications: The authors believe PDA can be applied to other optimization problems involving entropic regularized nonlinear functionals beyond neural networks.

Summary updated

Abstract

Abstract We propose the particle dual averaging (PDA) method, which generalizes the dual averaging method in convex optimization to the optimization over probability distributions with quantitative runtime guarantee. The algorithm consists of an inner loop and outer loop: the inner loop utilizes the Langevin algorithm to approximately solve for a stationary distribution, which is then optimized in the outer loop. The method can thus be interpreted as an extension of the Langevin algorithm to naturally handle nonlinear functional on the probability space. An important application of the proposed method is the optimization of neural network in the mean field regime, which is theoretically attractive due to the presence of nonlinear feature learning, but quantitative convergence rate can be challenging to obtain. By adapting finite-dimensional convex optimization theory into the space of measures, we analyze PDA in regularized empirical/expected risk minimization, and establish quantitative global convergence in learning two-layer mean field neural networks under more general settings. Our theoretical results are supported by numerical simulations on neural networks with reasonable size.
BibTeX
@article{nitanda2022particle,
  author = {Atsushi Nitanda and Denny Wu and Taiji Suzuki},
  title = {{Particle dual averaging: optimization of mean field neural network with global convergence rate analysis*}},
  journal = {Journal of Statistical Mechanics Theory and Experiment},
  year = {2022},
  doi = {10.1088/1742-5468/ac98a8},
}
Figure