Safe Convex Learning under Uncertain Constraints

2019/03/11 by Ilnura Usmanova, Andreas Krause, Usmanova, Ilnura +3 · 1 citation
Decision Sciences · Mathematics · #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Optimization and Control (math.OC) #Risk and Portfolio Optimization #Statistical Methods and Inference

paper · pdf · doi:10.48550/arxiv.1903.04626

openalex publication_date 2019/03/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We address the problem of minimizing a convex smooth function f(x) over a compact polyhedral set D given a stochastic zeroth-order constraint feedback model. This problem arises in safety-critical machine learning applications, such as personalized medicine and robotics. In such cases, one needs to ensure constraints are satisfied while exploring the decision space to find optimum of the loss function. We propose a new variant of the Frank-Wolfe algorithm, which applies to the case of uncertain linear constraints. Using robust optimization, we provide the convergence rate of the algorithm while guaranteeing feasibility of all iterates, with high probability.

Citations

• The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle
• Trading Regret for Efficiency: Online Convex Optimization with Long Term Constraints
• Robust Convex Optimization
• Distributionally robust joint chance constraints with second-order moment information
• Variance-Reduced and Projection-Free Stochastic Optimization

Cited by

• Safe Primal-Dual Optimization with a Single Smooth Constraint

Related

• Safe Learning under Uncertain Objectives and Constraints
• Convexification of Learning from Constraints
• Learning Decision-Focused Uncertainty Sets in Robust Optimization
• Safe Online Convex Optimization with Multi-Point Feedback
• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity