Safe Learning under Uncertain Objectives and Constraints

2020/06/23 by Mohammad Fereydounian, Fereydounian, Mohammad, Zebang Shen +7 · 1 citation
Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #FOS: Mathematics #Fuzzy Systems and Optimization #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Risk and Portfolio Optimization

paper · pdf · doi:10.48550/arxiv.2006.13326

openalex publication_date 2020/06/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper, we consider non-convex optimization problems under unknown yet safety-critical constraints. Such problems naturally arise in a variety of domains including robotics, manufacturing, and medical procedures, where it is infeasible to know or identify all the constraints. Therefore, the parameter space should be explored in a conservative way to ensure that none of the constraints are violated during the optimization process once we start from a safe initialization point. To this end, we develop an algorithm called Reliable Frank-Wolfe (Reliable-FW). Given a general non-convex function and an unknown polytope constraint, Reliable-FW simultaneously learns the landscape of the objective function and the boundary of the safety polytope. More precisely, by assuming that Reliable-FW has access to a (stochastic) gradient oracle of the objective function and a noisy feasibility oracle of the safety polytope, it finds an ε-approximate first-order stationary point with the optimal O(1/ε²) gradient oracle complexity (resp. O(1/ε³) (also optimal) in the stochastic gradient setting), while ensuring the safety of all the iterates. Rather surprisingly, Reliable-FW only makes O((d²/ε²)log 1/δ) queries to the noisy feasibility oracle (resp. O((d²/ε⁴)log 1/δ) in the stochastic gradient setting) where d is the dimension and δ is the reliability parameter, tightening the existing bounds even for safe minimization of convex functions. We further specialize our results to the case that the objective function is convex. A crucial component of our analysis is to introduce and apply a technique called geometric shrinkage in the context of safe optimization.

Citations

• Trading Regret for Efficiency: Online Convex Optimization with Long Term Constraints
• A Stochastic Approximation Method
• Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization
• Robust Convex Optimization
• Distributionally robust joint chance constraints with second-order moment information
• Projection-free Online Learning
• Variance-Reduced and Projection-Free Stochastic Optimization
• A Low Complexity Algorithm with O(√(T)) Regret and O(1) Constraint Violations for Online Convex Optimization with Long Term Constraints
• Stochastic Conditional Gradient++

Cited by

• Safe Primal-Dual Optimization with a Single Smooth Constraint

Related

• Safe Convex Learning under Uncertain Constraints
• Safe Online Convex Optimization with Unknown Linear Safety Constraints
• Log Barriers for Safe Black-box Optimization with Application to Safe Reinforcement Learning
• Distributionally Safe Reinforcement Learning under Model Uncertainty: A Single-Level Approach by Differentiable Convex Programming
• On Safety in Safe Bayesian Optimization