Particle Stochastic Dual Coordinate Ascent: Exponential convergent algorithm for mean field neural network optimization

Kazusato Oko, Taiji Suzuki, Atsushi Nitanda, Denny WuICLR 2022 · OpenReview

Introduction

Training neural networks is notoriously challenging due to their highly non-convex loss landscapes. To theoretically understand why deep learning succeeds, researchers typically analyze two regimes: the Neural Tangent Kernel (NTK) and Mean Field Analysis.

While the NTK regime allows for straightforward convergence proofs by treating the network as a linear approximation, it fails to capture true "feature learning"—parameters barely move from their initialization. Conversely, the Mean Field regime allows parameters to move significantly, enabling genuine feature learning. In the infinite-width limit, this optimization problem becomes convex in the space of parameter distributions.

However, a major gap exists in practical application. Most mean field theories only apply to continuous-time or infinite-width settings. Existing practical algorithms for finite-width networks in this regime, such as Particle Dual Averaging (PDA), only achieve polynomial convergence rates ($O(1/t)$). This paper bridges that gap by introducing Particle-SDCA (P-SDCA), the first gradient-based optimization algorithm for two-layer neural networks in the mean field regime that achieves an exponential (linear) convergence rate ($O(\exp(-Ct))$).

Methodology

P-SDCA adapts the classical Stochastic Dual Coordinate Ascent (SDCA) algorithm to the infinite-dimensional space of parameter measures. The approach relies on several key innovations:

  • Dual Problem Formulation: The authors transform the original non-convex primal problem into a convex dual problem within the space of measures.
  • Coordinate-wise Updates: Instead of updating all parameters simultaneously (full-batch), P-SDCA randomly selects a single data point for a coordinate-wise proximal gradient update, which is computationally much cheaper.
  • The Particle Method: Because the exact dual update requires an intractable integral over the entire parameter space, the authors approximate the distribution using a finite set of "particles" (neurons) initialized via Langevin dynamics (ULA or MALA).
  • Importance Re-weighting: To mitigate the high computational cost of re-sampling these neurons at every step, the algorithm employs an importance re-weighting scheme. Neurons are only re-sampled periodically (every $\tilde{n}$ steps), and their weights are updated in the interim.
Complexity comparison of optimization methods

Key Insights and Results

The theoretical and practical advantages of P-SDCA are substantial, as demonstrated through rigorous analysis and numerical experiments on synthetic regression and MNIST datasets.

  • Decoupled Complexity: P-SDCA successfully decouples the dependency on the sample size ($n$) and the condition number. This makes it significantly more efficient for large-scale datasets compared to standard full-batch gradient methods.
  • Empirical Convergence Speed: In numerical experiments, P-SDCA demonstrated clear linear convergence on log-scale plots. It significantly outperformed PDA and standard SGD in reaching the global optimum of the regularized objective and achieved lower test errors on teacher-student regression tasks.
  • Measurable Feature Learning: Using a binary classification task on MNIST (distinguishing "2" from "4"), the authors tracked the evolution of singular values in the weight matrices. P-SDCA showed a marked increase in "kernel alignment" over time, confirming that the model adaptively extracts informative features aligned with the labels—a capability absent in NTK-based SGD.
  • Favorable Scaling: Remarkably, the number of particles required to reach a specific accuracy scales only linearly with the required precision, and the sampling cost scales poly-logarithmically. Furthermore, unlike many McKean–Vlasov dynamics analyses, P-SDCA converges with a fixed, non-vanishing step size.

Limitations and Future Directions

While P-SDCA represents a significant leap forward, the authors note a few limitations and areas for future research:

  • Regularization Sensitivity: The sampling complexity (via the log-Sobolev constant) depends exponentially on the inverse of the regularization strength ($1/\lambda_2$). While tuning the re-sampling interval helps mitigate this, it remains a theoretical bottleneck.
  • Architecture Limits: The current analysis is strictly limited to two-layer (one hidden layer) neural networks. Extending this framework to deep, multi-layer architectures is a major open challenge.
  • Potential for Acceleration: In classical convex optimization, SDCA is not strictly "rate optimal." Incorporating Nesterov-style acceleration into this particle framework could yield even faster algorithms in the future.

Summary updated

Abstract

We introduce Particle-SDCA, a gradient-based optimization algorithm for two-layer neural networks in the mean field regime that achieves exponential convergence rate in regularized empirical risk minimization. The proposed algorithm can be regarded as an infinite dimensional extension of Stochastic Dual Coordinate Ascent (SDCA) in the probability space: we exploit the convexity of the dual problem, for which the coordinate-wise proximal gradient method can be applied. Our proposed method inherits advantages of the original SDCA, including (i) exponential convergence (with respect to the outer iteration steps), and (ii) better dependency on the sample size and condition number than the full-batch gradient method. One technical challenge in implementing the SDCA update is the intractable integral over the entire parameter space at every step. To overcome this limitation, we propose a tractable \textit{particle method} that approximately solves the dual problem, and an importance re-weighted technique to reduce the computational cost. The convergence rate of our method is verified by numerical experiments.
BibTeX
@inproceedings{oko2022particle,
  author = {Kazusato Oko and Taiji Suzuki and Atsushi Nitanda and Denny Wu},
  title = {{Particle Stochastic Dual Coordinate Ascent: Exponential convergent algorithm for mean field neural network optimization}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=PQQp7AJwz3},
}
Figure