Online Non-convex Optimization with Long-term Non-convex Constraints

• URL: http://arxiv.org/abs/2311.02426v3
• Date: Sun, 12 May 2024 17:18:28 GMT
• Title: Online Non-convex Optimization with Long-term Non-convex Constraints
• Authors: Shijie Pan, Wenjie Huang,
• Abstract summary: A novel Follow-the-Perturbed-Leader type algorithm is proposed and analyzed for solving general long-term constrained optimization problems in online manner. The proposed algorithm is applied to tackle a long-term (extreme value) constrained river pollutant source identification problem.
• Score: 2.033434950296318
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A novel Follow-the-Perturbed-Leader type algorithm is proposed and analyzed for solving general long-term constrained optimization problems in online manner, where the objective and constraints are arbitrarily generated and not necessarily convex. In each period, random linear perturbation and strongly concave perturbation are incorporated in primal and dual directions, respectively, to the offline oracle, and a global minimax point is searched as the solution. Based on a proposed expected static cumulative regret, we derive the first sublinear $O(T^{8/9})$ regret complexity for this class of problems. The proposed algorithm is applied to tackle a long-term (extreme value) constrained river pollutant source identification problem, validate the theoretical results and exhibit superior performance compared to existing methods.

Related papers

• Self-supervised Equality Embedded Deep Lagrange Dual for Approximate Constrained Optimization [5.412875005737914]
  We propose deeprange dual embedding (DeepLDE) as a fast optimal approximators incorporating neural networks (NNs) We prove the convergence of DeepLDE and primal, nondual-learning method to impose inequality constraints. We show that the proposed DeepLDE solutions achieve the optimal Lag gap among all the smallest NN-based approaches.
  arXiv  Detail & Related papers  (2023-06-11T13:19:37Z)
• Primal-Dual Contextual Bayesian Optimization for Control System Online Optimization with Time-Average Constraints [21.38692458445459]
  This paper studies the problem of online performance optimization of constrained closed-loop control systems. A primal-dual contextual Bayesian optimization algorithm is proposed that achieves sublinear cumulative regret with respect to the dynamic optimal solution.
  arXiv  Detail & Related papers  (2023-04-12T18:37:52Z)
• A Sequential Quadratic Programming Method with High Probability Complexity Bounds for Nonlinear Equality Constrained Stochastic Optimization [2.3814052021083354]
  It is assumed that constraint function values and derivatives are available, but only programming approximations of the objective function and its associated derivatives can be computed. A high-probability bound on the iteration complexity of the algorithm to approximate first-order stationarity is derived.
  arXiv  Detail & Related papers  (2023-01-01T21:46:50Z)
• Algorithm for Constrained Markov Decision Process with Linear Convergence [55.41644538483948]
  An agent aims to maximize the expected accumulated discounted reward subject to multiple constraints on its costs. A new dual approach is proposed with the integration of two ingredients: entropy regularized policy and Vaidya's dual. The proposed approach is shown to converge (with linear rate) to the global optimum.
  arXiv  Detail & Related papers  (2022-06-03T16:26:38Z)
• Simultaneously Achieving Sublinear Regret and Constraint Violations for Online Convex Optimization with Time-varying Constraints [26.473560927031176]
  We develop a novel virtual-queue-based online algorithm for online convex optimization (OCO) problems with long-term and time-varying constraints. Our algorithm is the first parameter-free algorithm to simultaneously achieve sublinear dynamic regret and constraint violations.
  arXiv  Detail & Related papers  (2021-11-15T12:23:31Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  The problem of constrained decision process (CMDP) is investigated, where an agent aims to maximize the expected accumulated discounted reward subject to multiple constraints. A new utilities-dual convex approach is proposed with novel integration of three ingredients: regularized policy, dual regularizer, and Nesterov's gradient descent dual. This is the first demonstration that nonconcave CMDP problems can attain the lower bound of $mathcal O (1/epsilon)$ for all complexity optimization subject to convex constraints.
  arXiv  Detail & Related papers  (2021-10-20T02:57:21Z)
• Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep Unrolling [86.85697555068168]
  Two-stage algorithmic optimization plays a critical role in various engineering and scientific applications. There still lack efficient algorithms, especially when the long-term and short-term variables are coupled in the constraints. We show that PDD-SSCA can achieve superior performance over existing solutions.
  arXiv  Detail & Related papers  (2021-05-05T03:36:00Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  Motivated by recent increased interest in analysis of optimization algorithms for non- optimization in deep networks and other problems in data, we give an overview of recent results of theoretical optimization algorithms for non- optimization.
  arXiv  Detail & Related papers  (2020-12-11T08:28:51Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  We propose a generalization extraient spaces which converges to a stationary point. The algorithm applies not only to general $p$-normed spaces, but also to general $p$-dimensional vector spaces.
  arXiv  Detail & Related papers  (2020-10-31T21:35:42Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  We introduce a novel algorithm improving over the state-of-the-art along multiple dimensions. We establish minimax optimality for any learning horizon in the special case of non-contextual linear bandits.
  arXiv  Detail & Related papers  (2020-10-23T09:12:47Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.