Noise-Adaptive High-Probability Regret Bounds for Online Convex Optimization

Technical Summary: Noise-Adaptive High-Probability Regret Bounds for Online Convex Optimization

Problem Statement
This work addresses the problem of Online Convex Optimization (OCO) under three distinct but interconnected challenges: (1) achieving noise-adaptive high-probability regret bounds for strongly convex losses in the full-information setting; (2) determining the fundamental confidence cost (dependence on the failure probability $\delta$) when moving from full-information to bandit feedback; and (3) establishing simultaneous high-probability guarantees for both cumulative regret and long-run constraint violation in constrained OCO with stochastic constraints.

While classical results establish that Online Gradient Descent (OGD) achieves $O(\frac{G^2}{\alpha} \log T)$ expected regret for $\alpha$-strongly convex losses (where $G$ bounds gradient norms), high-probability guarantees are often insufficiently tight for safety-critical applications. Standard approaches rely on Azuma-Hoeffding's inequality, which yields a martingale deviation term scaling with the worst-case gradient bound $G$ and domain diameter $D$ (specifically $GD\sqrt{2T \log(1/\delta)}$). This bound is loose when the actual stochastic noise level $\sigma$ is significantly smaller than $G$, a common regime in regularized empirical risk minimization. Furthermore, existing literature lacks a unified treatment of noise adaptivity, feedback structure differences, and high-probability constraint satisfaction.

Methodology and Key Contributions

The paper resolves three open questions through novel concentration arguments and lower-bound constructions:

1. Noise-Adaptive High-Probability Bounds (Full Information):
   The authors prove that projected OGD with step size $\eta_t = 1/(\alpha t)$ achieves a high-probability regret bound where the martingale deviation scales with the noise level $\sigma$ rather than the gradient bound $G$.

   • Methodology: The analysis introduces an exponential supermartingale argument tailored for conditionally sub-Gaussian sequences. This technique bypasses the bounded-difference requirement inherent in Freedman's inequality, which typically necessitates truncating unbounded sub-Gaussian noise. By avoiding truncation, the authors preserve the martingale property and derive a bound where the deviation term is $O(\sigma D \sqrt{T \log(1/\delta)})$.
   • Result: The regret bound is $O(\frac{G^2}{\alpha} \log T + \sigma D \sqrt{T \log(1/\delta)})$. This yields a multiplicative improvement of $G/\sigma$ over the classical Azuma-Hoeffding baseline when $\sigma \ll G$. The proof utilizes independent probability budgets to separate the truncation of gradient norms from the martingale tail concentration.

2. Confidence Cost Separation (Bandit vs. Full Information):
   The paper establishes a minimax lower bound demonstrating a fundamental separation in the confidence cost between full-information and bandit feedback settings for strongly convex OCO.

   • Methodology: Using an epoch-based testing construction with additive Gaussian noise, the authors apply the Bretagnolle-Huber lemma and conditional coupling arguments to construct a hard instance.
   • Result: In the full-information setting, the high-probability regret scales as $\sqrt{\log(1/\delta)}$. In contrast, under bandit feedback (where only scalar loss values are observed), the regret scales linearly as $\log(1/\delta)$. This constitutes the first formal proof that the information-theoretic cost of confidence is strictly higher in the bandit setting for strongly convex problems.

3. Simultaneous High-Probability Guarantees (Constrained OCO):
   The authors provide the first algorithm achieving simultaneous high-probability control of cumulative regret and long-run constraint violation under stochastic constraints satisfying a Slater condition.

   • Methodology: The analysis employs a primal-dual OGD framework. The regret bound leverages Freedman's inequality (applicable due to almost-sure boundedness of constraint noise). The constraint violation analysis decomposes the cumulative violation into an expected component and a stochastic martingale component. The expected component is bounded via a saddle-point argument and Markov's inequality, while the stochastic component is controlled via Freedman's inequality.
   • Result: The algorithm achieves $O(\sqrt{T \log(m/\delta)})$ regret and $O(\frac{\sqrt{T}}{\zeta \delta_1} + m\sqrt{T \log(m/\delta_2)})$ long-run constraint violation. Notably, the violation bound retains a $1/\delta$ factor for the expected component (via Markov's inequality), while the stochastic deviation scales with $\sqrt{\log(1/\delta)}$.

Experimental Validation
Synthetic experiments corroborate the theoretical predictions:

• Noise Adaptivity: Empirical tail statistics confirm that the regret quantiles track the noise-adaptive bound ($\sigma$-dependent) and remain well below the Azuma-Hoeffding baseline ($G$-dependent) when $\sigma \ll G$.
• Confidence Cost: Experiments on 1D strongly convex problems demonstrate that the full-information regret grows as $\sqrt{\log(1/\delta)}$, while the bandit regret grows linearly with $\log(1/\delta)$, validating the information-theoretic separation.
• Constrained OCO: Joint distributions of regret and violation confirm the independent probability budgeting and the inverse-linear scaling of violation with the Slater gap $\zeta$.

Significance and Claims
The paper claims to resolve three specific open questions at the intersection of noise adaptivity, feedback structure, and constraint satisfaction in strongly convex OCO.

• It provides a noise-adaptive refinement of high-probability bounds, showing that the "price of confidence" can be decoupled from the worst-case gradient magnitude and tied instead to the actual noise level.
• It establishes a formal separation in confidence costs, proving that bandit feedback incurs a linear $\log(1/\delta)$ penalty compared to the square-root $\sqrt{\log(1/\delta)}$ penalty of full information.
• It offers the first simultaneous high-probability guarantees for both regret and constraint violation in the stochastic constrained setting, clarifying the statistical mechanisms (Markov vs. Freedman) governing each component.

The authors note that while the $1/\delta$ dependence in the constraint violation bound is tight for the current proof technique (relying on Markov's inequality for the expected component), improving this to $\log(1/\delta)$ remains an open problem requiring pathwise control of the primal-dual saddle-point inequality. Similarly, extending noise adaptivity to bandit settings with non-trivial bias-supermartingale interactions is identified as a direction for future work.