Trading Regret for Efficiency: Online Convex Optimization with Long Term Constraints

Abstract

In this paper we propose a framework for solving constrained online convex optimization problem. Our motivation stems from the observation that most algorithms proposed for online convex optimization require a projection onto the convex set $\mathcal{K}$ from which the decisions are made. While for simple shapes (e.g. Euclidean ball) the projection is straightforward, for arbitrary complex sets this is the main computational challenge and may be inefficient in practice. In this paper, we consider an alternative online convex optimization problem. Instead of requiring decisions belong to $\mathcal{K}$ for all rounds, we only require that the constraints which define the set $\mathcal{K}$ be satisfied in the long run. We show that our framework can be utilized to solve a relaxed version of online learning with side constraints addressed in \cite{DBLP:conf/colt/MannorT06} and \cite{DBLP:conf/aaai/KvetonYTM08}. By turning the problem into an online convex-concave optimization problem, we propose an efficient algorithm which achieves $\tilde{\mathcal{O}}(\sqrt{T})$ regret bound and $\tilde{\mathcal{O}}(T^{3/4})$ bound for the violation of constraints. Then we modify the algorithm in order to guarantee that the constraints are satisfied in the long run. This gain is achieved at the price of getting $\tilde{\mathcal{O}}(T^{3/4})$ regret bound. Our second algorithm is based on the Mirror Prox method \citep{nemirovski-2005-prox} to solve variational inequalities which achieves $\tilde{\mathcal{O}}(T^{2/3})$ bound for both regret and the violation of constraints when the domain $\K$ can be described by a finite number of linear constraints. Finally, we extend the result to the setting where we only have partial access to the convex set $\mathcal{K}$ and propose a multipoint bandit feedback algorithm with the same bounds in expectation as our first algorithm.

References in corpus (1)

• A Stochastic View of Optimal Regret through Minimax Duality

Cited by in corpus (40)

• An Online Convex Optimization Approach to Dynamic Network Resource Allocation
• Bandit Convex Optimization for Scalable and Dynamic IoT Management
• Proximity Without Consensus in Online Multi-Agent Optimization
• Regret and Cumulative Constraint Violation Analysis for Distributed Online Constrained Convex Optimization
• Exploration-Exploitation in Constrained MDPs
• Distributed Constrained Online Learning
• Optimization-Based Ramping Reserve Allocation of BESS for AGC Enhancement
• Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds
• A Low Complexity Algorithm with $O(\sqrt{T})$ Regret and $O(1)$ Constraint Violations for Online Convex Optimization with Long Term Constraints
• Decentralized Online Learning for Noncooperative Games in Dynamic Environments
• An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraints
• Conservative Stochastic Optimization with Expectation Constraints
• Distributed Online Linear Regression
• Online Stochastic Optimization with Wasserstein Based Non-stationarity
• Delay-Tolerant Constrained OCO with Application to Network Resource Allocation
• The Online Saddle Point Problem and Online Convex Optimization with Knapsacks
• Distributed Online Convex Optimization with Time-Varying Coupled Inequality Constraints
• Online Stochastic Optimization with Multiple Objectives
• Distributed Online Convex Optimization with an Aggregative Variable
• Regret and Cumulative Constraint Violation Analysis for Online Convex Optimization with Long Term Constraints
• Online Continuous DR-Submodular Maximization with Long-Term Budget Constraints
• Exploiting Smoothness in Statistical Learning, Sequential Prediction, and Stochastic Optimization
• Safe Learning under Uncertain Objectives and Constraints
• Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints
• Learning Aided Optimization for Energy Harvesting Devices with Outdated State Information
• Pricing Mechanism for Resource Sustainability in Competitive Online Learning Multi-Agent Systems
• Distributed Online Optimization with Long-Term Constraints
• Online optimization and regret guarantees for non-additive long-term constraints
• Online Convex Optimization with Continuous Switching Constraint
• Asynchronous Optimization over Weakly Coupled Renewal Systems
• ODDO: Online Duality-Driven Optimization
• On Sample Complexity of Projection-Free Primal-Dual Methods for Learning Mixture Policies in Markov Decision Processes
• Joint Online Learning and Decision-making via Dual Mirror Descent
• A Stochastic Primal-Dual Method for Optimization with Conditional Value at Risk Constraints
• Safe Convex Learning under Uncertain Constraints
• Opportunistic Scheduling over Renewal Systems: An Empirical Method
• Online Convex Optimization with Perturbed Constraints
• Online Convex Optimization in Changing Environments and its Application to Resource Allocation
• Fairness-Aware Online Meta-learning
• Hierarchical Online Convex Optimization