# Exploiting Problem Structure in Optimization under Uncertainty via Online Convex Optimization

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Sep 2017.

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

- [Integrated Conditional Estimation-Optimization](https://mlsanity.com/paper/2110.12351/) (2021)
- [No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimization](https://mlsanity.com/paper/2111.11309/) (2021)
- [Accelerating Imitation Learning with Predictive Models](https://mlsanity.com/paper/1806.04642/) (2018)
- [Adaptive Composite Online Optimization: Predictions in Static and Dynamic Environments](https://mlsanity.com/paper/2205.00446/) (2022)
- [Proximal Point Method for Online Saddle Point Problem](https://mlsanity.com/paper/2407.04591/) (2024)
- [A Modular Algorithm for Non-Stationary Online Convex-Concave Optimization](https://mlsanity.com/paper/2509.07901/) (2025)
- [Online Saddle Point Problem and Online Convex-Concave Optimization](https://mlsanity.com/paper/2312.06957/) (2023)
- [Distributed Fractional Bayesian Learning for Adaptive Optimization](https://mlsanity.com/paper/2404.11354/) (2024)
- [Rate Analysis of Coupled Distributed Stochastic Approximation for Misspecified Optimization](https://mlsanity.com/paper/2404.13669/) (2024)
- [Simultaneous Learning and Optimization via Misspecified Saddle Point Problems](https://mlsanity.com/paper/2510.05241/) (2025)
- [Risk-Averse Wasserstein Distributionally Robust Online Learning](https://mlsanity.com/paper/2602.20403/) (2026)

## Abstract (arXiv)

In this paper, we consider two paradigms that are developed to account for uncertainty in optimization models: robust optimization (RO) and joint estimation-optimization (JEO). We examine recent developments on efficient and scalable iterative first-order methods for these problems, and show that these iterative methods can be viewed through the lens of online convex optimization (OCO). The standard OCO framework has seen much success for its ability to handle decision-making in dynamic, uncertain, and even adversarial environments. Nevertheless, our applications of interest present further flexibility in OCO via three simple modifications to standard OCO assumptions: we introduce two new concepts of weighted regret and online saddle point problems and study the possibility of making lookahead (anticipatory) decisions. Our analyses demonstrate that these flexibilities introduced into the OCO framework have significant consequences whenever they are applicable. For example, in the strongly convex case, minimizing unweighted regret has a proven optimal bound of O(log(T)/T), whereas we show that a bound of O(1/T) is possible when we consider weighted regret. Similarly, for the smooth case, considering 1-lookahead decisions results in a O(1/T) bound, compared to O(1/√T) in the standard OCO setting. Consequently, these OCO tools are instrumental in exploiting structural properties of functions and resulting in improved convergence rates for RO and JEO. In certain cases, our results for RO and JEO match the best known or optimal rates in the corresponding problem classes without data uncertainty.