🔢 mathematics

A Non-Monotone Preconditioned Trust-Region Method for Neural Network Training

This paper introduces a non-monotone variant of the Additively Preconditioned Trust-Region Strategy (NAPTS) for large-scale neural network training, which utilizes a nonlinear additive Schwarz preconditioner and a windowed acceptance criterion to reduce CPU time by 30% and significantly decrease rejected steps compared to the original method.

Original authors: Andrea Angino, Bindi Çapriqi, Shega Likaj, Ken Trotti, Rolf Krause

Published 2026-05-15

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Andrea Angino, Bindi Çapriqi, Shega Likaj, Ken Trotti, Rolf Krause

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a massive, complex robot (a Neural Network) to recognize pictures of cats and dogs. This robot has millions of tiny knobs (parameters) that need to be turned just right to get the job done.

The paper introduces a new, smarter way to turn these knobs, called NAPTS. To understand why it's special, let's look at the problems with the old ways and how this new method fixes them.

The Problem: The "Too Many Cooks" Dilemma

In the past, to train these robots fast, scientists split the work up. Imagine you have a huge puzzle, and you give different sections to different people (computers) to solve at the same time. This is called Domain Decomposition.

However, there was a catch. When everyone worked on their own section, they sometimes made moves that looked good locally but messed up the whole picture.

The Old Guard (APTS): This method was like a strict teacher. If a move didn't immediately lower the "error score" (make the robot smarter), the teacher would say, "No! Throw that away and try again." This caused a lot of wasted time rejecting good ideas just because they didn't work instantly.
The Simple Way (SGD/Adam): These are the standard methods everyone uses. They are fast but require a lot of manual tuning (like constantly adjusting the volume on a radio to find the right station) and don't use the "multi-device" setup as efficiently.

The Solution: The "Window of Opportunity" (NAPTS)

The authors created NAPTS (Non-monotone Additively Preconditioned Trust-Region Strategy). Here is how it works, using a simple analogy:

1. The Team Approach (Parallel Subdomains)
Imagine the robot is a long assembly line. Instead of one person checking the whole line, you have three teams.

Team A fixes the first part.
Team B fixes the middle.
Team C fixes the end.
They all work at the same time. NAPTS lets them do this efficiently by sharing just the right amount of information (like passing a baton) so they don't step on each other's toes.

2. The "Sliding Window" Rule (Non-Monotone)
This is the big innovation.

The Old Rule: "You must be better than you were right now." If you take a step and the score gets slightly worse for a second, you are rejected.
The NAPTS Rule: "You must be better than you were at your best point in the last 100 steps."

Think of it like a hiker climbing a foggy mountain.

Strict Method: If you take a step and slip down a tiny bit, you stop and turn back immediately. You might miss a path that goes down a little to go up a lot later.
NAPTS Method: The hiker looks back at the highest point they reached in the last hour. If their current spot is lower than that, they keep going, even if they took a small step down. They trust that the "big picture" is improving, even if the immediate step wasn't perfect.

This allows the algorithm to accept "coarse" steps (big, rough adjustments) that might temporarily increase the error but are necessary to escape a local trap and find a much better solution later.

The Results: Faster and Smarter

The paper tested this on a standard image recognition task (CIFAR-10) using powerful computers. Here is what they found:

Less Rejection: The old strict method (APTS) rejected about 13,000 steps. NAPTS only rejected about 1,900. It stopped wasting time throwing away good ideas.
Speed: Because it stopped rejecting steps so often, NAPTS finished an "epoch" (a full round of training) about 30% faster than the old APTS method.
Accuracy: It didn't just get faster; it actually learned better, achieving higher accuracy on the test images than the standard methods.

In a Nutshell

The paper proposes a new training method that treats the neural network like a team of specialists working in parallel. Instead of being a strict boss who fires anyone who makes a tiny mistake, it acts like a wise coach who looks at the team's progress over the last hour. This "sliding window" approach allows the team to take bolder, more effective steps, resulting in a robot that learns faster and makes fewer mistakes, all while using less computer time.

Technical Summary: A Non-Monotone Preconditioned Trust-Region Method for Neural Network Training

Problem Statement
Training deep neural networks (NNs) at scale presents challenges regarding hyperparameter tuning, the exploitation of multi-device pipelines, and the handling of nonconvex, noisy objective functions. While first-order methods like Stochastic Gradient Descent (SGD) and Adam are standard, they rely heavily on manual step-size and momentum scheduling and do not naturally leverage model-parallelism where a network is split into sequential blocks across devices. Conversely, Domain Decomposition (DD) methods offer a way to partition parameters into subdomains for parallel updates, but they require robust globalization strategies to ensure convergence in nonconvex settings. Previous approaches, such as the Additively Preconditioned Trust-Region Strategy (APTS), utilize trust-region (TR) mechanisms but often suffer from high rejection rates of coarse-space steps, leading to expensive recomputation of search directions.

Methodology: NAPTS
The paper proposes the Non-monotone Additively Preconditioned Trust-Region Strategy (NAPTS), an extension of the APTS framework that integrates non-monotone trust-region (NTR) principles. The method operates through three distinct phases per iteration:

Parallel Subdomain Updates: The NN parameter space is partitioned into non-overlapping subdomains $\{C_d\}_{d=1}^N$ . At each iteration $k$ , a global forward and backward pass caches activation values and downstream gradients. Each subdomain then performs $\ell$ local constrained Adam (CAdam) steps in parallel. These local steps are computed using cached boundary information to approximate block-gradients, ensuring subdomains operate independently while respecting global information. The local steps are lifted and combined additively to form a global trial step $s_k$ .
Non-Monotone Globalization: Unlike standard TR methods that require strict monotonic decrease of the objective function, NAPTS employs a sliding window of the most recent $\nu$ $ν$ successful iterations. It defines a reference index $r(k)$ $r (k)$ corresponding to the highest objective value within this window. Step acceptance is determined by a combined agreement ratio $\rho_k = \max\{\rho^c_k, \rho^h_k\}$ $ρ_{k} = max {ρ_{k}^{c}, ρ_{k}^{h}}$ , where:
- $\rho^c_k$ measures the agreement between the actual and predicted decrease for the current step.
- $\rho^h_k$ measures the agreement relative to the historical reference value $f(\theta_{r(k)})$ and a cumulative history term $\sigma^h_k$ .
  This mechanism allows the acceptance of steps that temporarily increase the objective function ( $f(\theta_k + s_k) > f(\theta_k)$ ) if they align with long-term descent trends, thereby reducing the rejection of effective coarse-space directions.
Correction and Smoothing: If the trial step is rejected, a correction step $c_k$ is computed as a convex combination of a steepest descent step and the original proposal, avoiding the waste of previously computed gradient information. A final NTR update refines the iterate and adjusts the trust-region radius $\Delta_k$ .

Key Contributions

Non-Monotone APTS (NAPTS): The primary contribution is the integration of NTR principles into the APTS framework. This specifically addresses the issue of aggressive coarse-space step rejection in noisy, nonconvex NN training landscapes.
Controlled Non-Monotonicity: The paper introduces a windowed acceptance criterion that permits controlled objective increases. This prevents the "indiscriminate" acceptance of steps while still allowing the algorithm to persist with coarse-space directions that might be temporarily non-improving but globally beneficial.
Efficient Parallelism: The method maintains the additive Schwarz structure, allowing for parallel subdomain training without inter-subdomain communication during local iterations, only requiring global synchronization for gradient caching and step aggregation.

Results
Experiments were conducted on the CIFAR-10 dataset using a convolutional NN (1.2M parameters) trained on four Nvidia A100 GPUs.

Performance: NAPTS achieved a training time of 115.88 seconds per epoch, representing a 30% reduction in CPU time compared to the standard APTS (169.14s/epoch) and a further improvement over the aggressive-acceptance variant APTS $_A$ (152.39s/epoch).
Rejection Rates: The method significantly reduced the number of rejected steps. NAPTS recorded approximately 1,921 total rejected iterations, compared to 13,972 for APTS and 6,648 for APTS $_A$ . This indicates that the non-monotone mechanism successfully retains effective coarse-space proposals that would otherwise be discarded.
Accuracy: While baseline TR and NTR methods struggled to reach high validation accuracy, the preconditioned variants (APTS and NAPTS) achieved substantially higher validation accuracies and lower training losses, suggesting improved optimization without compromising generalization.

Significance
The paper claims that NAPTS offers a robust globalization strategy specifically suited for the nonconvex and noisy nature of large-scale neural network training. By relaxing the strict monotonicity requirement, the method avoids the computational cost of repeatedly rejecting and recomputing search directions. The authors posit that this approach effectively leverages domain decomposition for model parallelism while providing automatic step-size adaptation through trust regions, reducing the need for manual hyperparameter tuning associated with first-order methods. The results suggest that NAPTS preserves the accuracy of preconditioned methods while substantially improving computational efficiency.

The Problem: The "Too Many Cooks" Dilemma

The Solution: The "Window of Opportunity" (NAPTS)

The Results: Faster and Smarter

In a Nutshell

Technical Summary: A Non-Monotone Preconditioned Trust-Region Method for Neural Network Training

More like this