Online non-convex learning for river pollution source identification

Wenjie Huang, Jing Jiang, Xiao Liu

Abstract

Identifying the source of river pollution in real-time is a critical task for environmental emergency response. This paper develops novel gradient-based online learning algorithms to estimate the released mass, location, and time of an instantaneous pollution source based on downstream sensor data. Formulated as a non-convex loss minimization problem, the proposed framework introduces vectorized adaptive step sizes to handle the varying magnitudes of the three target parameters. To address the challenges of non-convexity, we incorporate a perturbation module to escape saddle points and a multi-start strategy to ensure global convergence. Theoretical analysis demonstrates an $O(N)$ local regret bound. Experimental results on synthetic data and real-life field data from the Truckee River show that our algorithms significantly outperform traditional offline methods in both speed and estimation accuracy.

Introduction

When a chemical spill or sewage leakage occurs in a river system, the window for effective mitigation is narrow. Emergency responders require immediate answers to three fundamental questions: How much was released? Where did the spill occur? And when did it start? Traditionally, this is treated as an "inverse problem" using the Advection-Dispersion Equation (ADE), which models how pollutants migrate and spread over time.

However, existing identification methods often fall short in emergency scenarios. Most are designed for offline analysis, requiring a complete dataset before processing can begin. Furthermore, the mathematical landscape of pollution migration is inherently non-convex, meaning standard optimization algorithms frequently get trapped in local minima or "saddle points"—flat regions that appear to be solutions but are not the true global minimum. Finally, the variables involved (mass, location, and time) exist on vastly different scales, making uniform optimization difficult. This paper introduces an online learning framework designed to overcome these hurdles.

Methodology

Online Gradient-Based Learning

Unlike traditional batch processing, our approach treats source identification as an online learning problem. As each new sensor reading arrives, the model updates its estimates of the source parameters. This allows for "anytime" identification, where the accuracy of the estimate improves dynamically as more data streams in.

Vectorized Adaptive Step Sizes

A core innovation of this work is the use of Adaptive Time-smoothed Online Gradient Descent (ATGD). In standard gradient descent, a single learning rate is applied to all parameters. In environmental modeling, however, a step size appropriate for updating a location (measured in kilometers) may be completely ineffective for updating mass (measured in kilograms). Our algorithm assigns different, adaptive step sizes to each dimension, ensuring the search doesn't stall on one parameter while diverging on another.

Escaping Saddle Points

To navigate the "bumpy" non-convex loss landscape, we developed the Adaptive Perturbed Time-smoothed Online Gradient Descent (APTGD) algorithm. This version includes a perturbation module that adds a small amount of random noise when the gradient becomes too small. This "kick" allows the algorithm to escape saddle points and continue searching for the true global minimizer. To further enhance robustness, we implement multi-start versions (MTGD and MPTGD) that initiate several search paths simultaneously from different initial guesses.

Sensor Optimization

Beyond the optimization algorithms, the framework includes a statistical mechanism to determine the minimum number of sensors required to achieve a specific confidence level. This provides a practical tool for environmental agencies to balance the cost of sensor deployment against the need for high-precision results.

Experimental Validation

Synthetic and Field Data

The researchers validated the models using two distinct datasets:

  1. Synthetic Data: 1,000 pairs of artificial concentration data generated via the ADE model to verify theoretical regret bounds.
  2. Truckee River Field Data: Rhodamine WT dye concentration data from a travel time study conducted on the Truckee River (California/Nevada). This dataset includes 82 concentration readings detected across four downstream sampling sites.

Performance Results

The proposed algorithms demonstrated superior performance across several metrics:

  • Efficiency: The ATGD algorithm was found to be more than 10 times faster than standard Time-smoothed Gradient Descent (TGD) due to its adaptive line-search technique.
  • Accuracy: On the Truckee River data, the Multi-start Perturbed (MPTGD) version achieved a released time estimation error of just 1.40%, a massive improvement over the 14.42% error rate seen in standard methods.
  • Theoretical Rigor: The authors proved an $O(N)$ local regret bound, indicating that the algorithm's performance gap compared to an ideal hindsight solution grows only linearly with time—a significant achievement for non-convex online settings.

Discussion and Managerial Insights

The results highlight that in environmental modeling, magnitude matters. The vectorization of step sizes is essential for handling the physical units of disparate parameters. Furthermore, the inclusion of the perturbation module suggests that many previous "optimal" solutions in environmental literature may have simply been stuck in saddle points.

For decision-makers, these algorithms offer a way to move from reactive to proactive pollution management. The ability to update estimates in real-time as data arrives allows for faster containment and more accurate liability assessment.

Limitations and Future Work

While the gradient-based approach is highly effective, calculating gradients for extremely complex, high-dimensional ADE models can be computationally intensive. Future research will explore "bandit" versions of these algorithms that require only the concentration readings (function values) rather than gradients. Additionally, extending the model to handle complex river networks with multiple tributaries and identifying multiple or continuous pollution sources remain important next steps for the field.

Summary updated

Abstract

In this article, novel gradient-based online learning algorithms are developed to investigate an important environmental application: real-time river pollution source identification, which aims at estimating the released mass, location, and time of a river pollution source based on downstream sensor data monitoring the pollution concentration. The pollution is assumed to be instantaneously released once. The problem can be formulated as a non-convex loss minimization problem in statistical learning, and our online algorithms have vectorized and adaptive step sizes to ensure high estimation accuracy in three dimensions which have different magnitudes. In order to keep the algorithm from sticking in the saddle points of non-convex loss, the “escaping from saddle points” module and multi-start setting are derived to further improve the estimation accuracy by searching for the global minimizer of the loss functions. This can be shown theoretically and experimentally as the O(N) local regret of the algorithms and the high probability cumulative regret bound O(N) under a particular error bound condition in loss functions. A real-life river pollution source identification example shows the superior performance of our algorithms compared with existing methods in terms of estimation accuracy. Managerial insights for the decision maker to use the algorithms are also provided.
BibTeX
@inproceedings{huang2020online,
  author = {Wenjie Huang and Jing Jiang and Xiao Liu},
  title = {{Online non-convex learning for river pollution source identification}},
  booktitle = {IISE},
  year = {2020},
}
Figure