Introduction
Solving large-scale systems of nonlinear equations, denoted as $f(x) = 0$, is a foundational task across scientific computing and engineering. Traditional approaches, such as Newton’s method, are often computationally prohibitive for massive datasets because they require the calculation and inversion of the full Jacobian matrix at every iteration. Stochastic alternatives, like the Kaczmarz method, offer a more efficient path by processing equations one at a time. However, standard Kaczmarz variants are typically restricted to linear systems and struggle to incorporate structural constraints, such as sparsity or requirements that the solution lie on a probability simplex.
This paper introduces the Nonlinear Bregman-Kaczmarz (NBK) method, a randomized algorithm designed to bridge these gaps. By combining local linearization with Bregman projections, the authors provide a unified framework that handles nonlinearities and respects the underlying geometry of the solution space without the need for manual learning rate tuning.
The Nonlinear Bregman-Kaczmarz (NBK) Algorithm
The NBK method operates by iteratively selecting a single component function $f_i(x)$ and performing a projection. The process involves three key components:
1. Local Linearization
In each step, the algorithm approximates the chosen nonlinear function $f_i(x)$ using a first-order Taylor expansion. This linear approximation creates a local hyperplane that the next iterate aims to satisfy.
2. Bregman Projections
Unlike standard Kaczmarz methods that use Euclidean projections (the "shortest path"), NBK employs Bregman projections. These projections are defined by a distance-generating function $\phi$ tailored to the specific constraints of the problem. For instance:
- Entropy functions are used to ensure solutions remain within a probability simplex.
- $\ell_1$ penalties are used to encourage sparse solutions. This geometric flexibility allows the algorithm to naturally enforce constraints that would otherwise require expensive separate projection steps.
3. Adaptive Step Sizes
A significant advantage of NBK over standard Stochastic Gradient Descent (SGD) is its adaptive step size $t_k$. Instead of relying on a manually tuned learning rate, NBK calculates an optimal step size by solving a simple one-dimensional convex optimization problem in each iteration. While this requires a few internal Newton steps, it renders the method essentially tuning-free and more robust to the scaling of the objective function.
Theoretical Unification and Properties
The authors demonstrate that NBK serves as a "grand unified theory" for several existing optimization techniques. By varying the distance-generating function $\phi$, the method recovers:
- Standard Nonlinear Kaczmarz (when using a quadratic distance).
- SGD with a Stochastic Polyak Step-size (SPS) (for certain non-negative functions).
A key insight of the research is the method's scaling invariance. If the distance function is multiplied by a constant, the algorithm's trajectory remains unchanged. This property makes NBK significantly more stable than standard mirror descent methods, which are often sensitive to hyperparameter selection.
Experimental Evaluation
The performance of NBK was evaluated across several structured problems, including multinomial quadratic equations and linear systems on the simplex. A notable test case was Left Stochastic Decomposition (LSD), a complex quadratic problem where matrix columns must lie on a simplex, which is frequently used in clustering applications.
The results indicate that NBK achieves linear convergence rates—where the error decreases exponentially—for classes of functions satisfying specific conditions, such as "star-convexity" or the "tangential cone condition." In practice, NBK outperformed the "Projections Onto Convex Sets" (POCS) method and standard Nonlinear Kaczmarz, particularly in scenarios involving redundant or highly correlated equations that typically slow down Kaczmarz-style solvers.
Discussion and Limitations
While NBK offers superior convergence and structural handling, it is not without trade-offs. The primary overhead is the computational cost of the 1D sub-problem for the step size, which requires the distance-generating function to be $C^2$-smooth. Additionally, while the method performs well on certain non-convex problems like LSD, rigorous theoretical guarantees are currently focused on convex or star-convex settings.
Future research may explore extending these Bregman techniques to handle inequality constraints or integrating momentum terms to further accelerate stochastic updates. By providing a robust, geometry-aware alternative to SGD, the Nonlinear Bregman-Kaczmarz method represents a significant step forward in solving complex, large-scale nonlinear systems.
Summary updated