Discounted regret measures the performance of an online learner by assigning exponentially decaying weights to past losses, reflecting the greater importance of recent losses in non-stationary online learning. While previous work obtains uniform discounted regret bounds over a continuous range of discount factors using a specialized meta-algorithm, its results are limited to convex functions. In this paper, we demonstrate that strongly adaptive regret bounds can directly imply uniform discounted regret guarantees for convex, strongly convex, and exp-concave loss functions. Our key observation is that discounted regret against a fixed comparator admits an exact decomposition into a convex combination of interval regrets. For convex functions, this reduction yields an $O(\sqrt{\log T/(1-λ)})$ discounted regret bound for all discount factors $λ\in(0,1)$, matching the previous rate over a broader range of discount factors. For strongly convex and exp-concave functions, we provide regret bounds of $O\left(\log T\left(1+\log\frac{1}{1-λ}\right)\right)$.
In this paper, we investigate decentralized online convex optimization with compressed communication, where $n$ learners over a network jointly minimize a sequence of global loss functions based only on their local losses and compressed messages from their neighbors. The best known regret bounds for this problem are $O(ω^{-1/2}nρ^{-1}\sqrt{T\ln n})$ and $O(ω^{-1}nρ^{-2}\ln n\ln T)$ for convex and strongly convex loss functions, respectively, where $ρ\in(0,1)$ is the spectral gap of the communication matrix and $ω\in(0,1]$ is the compression quality factor. Compared with the corresponding lower bounds of $Ω(ω^{-1/2}nρ^{-1/4}\sqrt{T})$ and $Ω(ω^{-1}nρ^{-1/2}\ln T)$, these upper bounds exhibit polynomial gaps in their dependence on $ρ^{-1}$. To close these gaps, we first develop Ascent-gossip, which combines an online compression strategy with a Chebyshev recursion and attains a faster consensus rate than existing compressed gossip methods. Furthermore, by adopting Ascent-gossip, we propose an online algorithm that achieves optimal regret bounds of $\widetilde O(ω^{-1/2}nρ^{-1/4}\sqrt{T})$ and $\widetilde O(ω^{-1}nρ^{-1/2}\ln T)$ for convex and strongly convex loss functions, respectively. Up to logarithmic factors in $n$ and $ρ^{-1}$, these results match the lower bounds in terms of $T$, $n$, $ρ$, and $ω$.