Safe Online Convex Optimization with Heavy-Tailed Observation Noises

Yunhao Yang, Bo Xue, Yunzhi Hao, Ying Li, Yuanyu Wan

TL;DR

This paper tackles the challenge of "safe" online learning where decisions must adhere to unknown constraints. The authors introduce novel algorithms that effectively handle "heavy-tailed" noise in observing these constraints, a more realistic scenario than previously assumed, achieving improved regret bounds with high probability.

What Problem Does This Paper Address?

Online learning is a powerful paradigm for making sequential decisions in dynamic environments, with applications ranging from spam filtering to portfolio management. A crucial aspect is minimizing "regret," the difference between the total loss incurred by the learning algorithm and the loss of the best possible fixed decision. However, many real-world applications require decisions to satisfy additional "safety constraints." These constraints, often linear, are frequently unknown to the learner and must be estimated.

Previous work on "Safe Online Convex Optimization" (SOCO) addressed this by assuming that observations of these constraints are corrupted by "sub-Gaussian noise." This assumption allows for algorithms like SO-PGD, which achieve a reasonable regret bound. However, this assumption is often violated in practice. Many real-world phenomena, such as financial market fluctuations or neural activity, exhibit "heavy-tailed" noise, meaning extreme events are more likely than predicted by sub-Gaussian distributions. This heavy-tailed noise can undermine the theoretical guarantees of existing SOCO algorithms. This paper aims to bridge this gap by developing SOCO algorithms that are robust to heavy-tailed observation noises.

Methods

The paper proposes two novel algorithms, SOCO with Median of Means (SOMM) and SOCO with Truncated Means (SOTM), as variants of the existing SO-PGD algorithm. The core innovation lies in how they handle the estimation of the unknown safety constraints under heavy-tailed noise during an initial "safe exploration" phase.

  • SOCO with Median of Means (SOMM): This algorithm addresses heavy-tailed noise by performing multiple estimations of the constraint parameters during the exploration phase. Instead of relying on a single estimate, it computes several estimates and then takes the median of these estimates. This "median-of-means" technique is known to be robust to outliers and extreme values, making it suitable for heavy-tailed distributions.
  • SOCO with Truncated Means (SOTM): This approach also focuses on improving the estimation during the exploration phase. It introduces a "truncation criterion" to filter out extreme values in the observed constraint data. By carefully truncating the noisy observations, SOTM aims to retain useful information for parameter estimation while discarding potentially misleading extreme values.

Both algorithms then proceed to a second "exploitation" phase, where they use the estimated safety constraints to perform standard online convex optimization (like OGD) while ensuring decisions remain within the estimated safe set with high probability.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Heavy-tailed noise is a critical practical concern: The paper highlights that the sub-Gaussian noise assumption, common in prior SOCO work, is often unrealistic. Real-world data frequently exhibits heavy tails, necessitating robust algorithms.
  • Median-of-means and truncation are powerful tools for heavy-tailed noise: The paper successfully adapts established techniques from bandit problems (median-of-means and truncation) to the more complex SOCO setting, demonstrating their effectiveness in improving constraint estimation.
  • High-probability guarantees are achievable: By carefully employing these robust estimation techniques, the authors achieve theoretical guarantees that hold with high probability, a significant improvement over simply applying existing methods to heavy-tailed noise.
  • Balancing exploration and exploitation under uncertainty: The core challenge remains balancing the need to explore and learn about unknown constraints with the need to make safe and low-regret decisions. The proposed algorithms offer refined strategies for this balance.

Key Results

The paper establishes theoretical guarantees for its proposed algorithms, SOMM and SOTM. Both algorithms achieve a regret bound of $O(T \cdot c_{\epsilon})$ with high probability, where $c_{\epsilon} = (1+\epsilon)/(1+2\epsilon)$ and $\epsilon \in (0,1]$ characterizes the heavy-tailedness of the noise. This is a significant improvement over previous results that might not hold with high probability under heavy-tailed noise. Specifically, the dependence on the probability parameter $\delta$ in the confidence interval of the estimated constraints is reduced from sublinear to polylogarithmic, enabling high-probability guarantees.

Limitations and Future Work

  • Prior information on noise: The current algorithms require some prior knowledge about the heavy-tailed noise distribution (e.g., the parameter $\epsilon$ and bounds on moments). The authors note that recent advances in heavy-tailed bandits have explored adaptive algorithms that do not require such prior information.
  • Adaptive algorithms for SOCO: A promising future direction is to develop adaptive SOCO algorithms that can automatically adjust to the characteristics of the heavy-tailed noise without explicit prior knowledge. This would further enhance the practicality and applicability of these methods.
  • Computational complexity: While theoretical guarantees are provided, the practical computational complexity of the median-of-means and truncation steps, especially for high-dimensional problems, might be a consideration.

Summary updated

BibTeX
@inproceedings{yang2025safe,
  author = {Yunhao Yang and Bo Xue and Yunzhi Hao and Ying Li and Yuanyu Wan},
  title = {{Safe Online Convex Optimization with Heavy-Tailed Observation Noises}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i21.34357},
}
Figure