# Analysis of Dual-Based PID Controllers through Convolutional Mirror Descent

arXiv: https://arxiv.org/abs/2202.06152 · HTML: https://mlsanity.com/paper/2202.06152/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 58 references that are in the map.
- First posted on arXiv 12 Feb 2022.

## Builds on (most cited first, 20 of 20)

- [On the Convergence of Adam and Beyond](https://mlsanity.com/paper/1904.09237/) (2019)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights](https://mlsanity.com/paper/1503.01243/) (2015)
- [A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach](https://mlsanity.com/paper/1901.08511/) (2019)
- [The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization](https://mlsanity.com/paper/1807.03907/) (2018)
- [Closing the Generalization Gap of Adaptive Gradient Methods in Training Deep Neural Networks](https://mlsanity.com/paper/1806.06763/) (2018)
- [Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent](https://mlsanity.com/paper/1407.1537/) (2014)
- [The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2011.10124/) (2020)
- [Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2002.10421/) (2020)
- [Bid Optimization by Multivariable Control in Display Advertising](https://mlsanity.com/paper/1905.10928/) (2019)
- [A new regret analysis for Adam-type algorithms](https://mlsanity.com/paper/2003.09729/) (2020)
- [Simple and Fast Algorithm for Binary Integer and Online Linear Programming](https://mlsanity.com/paper/2003.02513/) (2020)
- [A geometric alternative to Nesterov's accelerated gradient descent](https://mlsanity.com/paper/1506.08187/) (2015)
- [Feedback Control of Real-Time Display Advertising](https://mlsanity.com/paper/1603.01055/) (2016)
- [Primal Beats Dual on Online Packing LPs in the Random-Order Model](https://mlsanity.com/paper/1311.2578/) (2013)
- [Multiplicative Pacing Equilibria in Auction Markets](https://mlsanity.com/paper/1706.07151/) (2017)
- [Nostalgic Adam: Weighting more of the past gradients when designing the adaptive learning rate](https://mlsanity.com/paper/1805.07557/) (2018)
- [How the Experts Algorithm Can Help Solve LPs Online](https://mlsanity.com/paper/1407.5298/) (2014)
- [Dynamic Bidding Strategies with Multivariate Feedback Control for Multiple Goals in Display Advertising](https://mlsanity.com/paper/2007.00426/) (2020)

## Built on by (most cited first, 3 of 3)

- [Infrequent Resolving Algorithm for Online Linear Programming](https://mlsanity.com/paper/2408.00465/) (2024)
- [Bandits for Sponsored Search Auctions under Unknown Valuation Model: Case Study in E-Commerce Advertising](https://mlsanity.com/paper/2304.00999/) (2023)
- [A Lightweight MPC Bidding Framework for Brand Auction Ads](https://mlsanity.com/paper/2603.07721/) (2026)

## Abstract (arXiv)

Dual-based proportional-integral-derivative (PID) controllers are often employed in practice to solve online allocation problems with global constraints, such as budget pacing in online advertising. However, controllers are used in a heuristic fashion and come with no provable guarantees on their performance. This paper provides the first regret bounds on the performance of dual-based PID controllers for online allocation problems. We do so by first establishing a fundamental connection between dual-based PID controllers and a new first-order algorithm for online convex optimization called Convolutional Mirror Descent (CMD), which updates iterates based on a weighted moving average of past gradients. CMD recovers, in a special case, online mirror descent with momentum and optimistic mirror descent. We establish sufficient conditions under which CMD attains low regret for general online convex optimization problems with adversarial inputs. We leverage this new result to give the first regret bound for dual-based PID controllers for online allocation problems. As a byproduct of our proofs, we provide the first regret bound for CMD for non-smooth convex optimization, which might be of independent interest.