Time-Varying Convex Optimization with $O(n)$ Computational Complexity

• URL: http://arxiv.org/abs/2410.15009v2
• Date: Thu, 24 Oct 2024 20:09:31 GMT
• Title: Time-Varying Convex Optimization with $O(n)$ Computational Complexity
• Authors: M. Rostami, S. S. Kia,
• Abstract summary: We consider the problem of unconstrained convex optimization, where the cost function changes with time. Our proposed algorithms only require the first-order derivatives of the cost function with respect to the decision variable. Specifically, the proposed algorithms reduce computational cost from $(n3)$ to $O(n)$ per timestep.
• Score: 0.0
• License:
• Abstract: In this article, we consider the problem of unconstrained time-varying convex optimization, where the cost function changes with time. We provide an in-depth technical analysis of the problem and argue why freezing the cost at each time step and taking finite steps toward the minimizer is not the best tracking solution for this problem. We propose a set of algorithms that by taking into account the temporal variation of the cost aim to reduce the tracking error of the time-varying minimizer of the problem. The main contribution of our work is that our proposed algorithms only require the first-order derivatives of the cost function with respect to the decision variable. This approach significantly reduces computational cost compared to the existing algorithms, which use the inverse of the Hessian of the cost. Specifically, the proposed algorithms reduce the computational cost from $O(n^3)$ to $O(n)$ per timestep, where $n$ is the size of the decision variable. Avoiding the inverse of the Hessian also makes our algorithms applicable to non-convex optimization problems. We refer to these algorithms as $O(n)$-algorithms. These $O(n)$-algorithms are designed to solve the problem for different scenarios based on the available temporal information about the cost. We illustrate our results through various examples, including the solution of a model predictive control problem framed as a convex optimization problem with a streaming time-varying cost function.

Related papers

• Projection-free Algorithms for Online Convex Optimization with Adversarial Constraints [10.047668792033033]
  We study a generalization of the Online Convex Optimization (OCO) framework with time-varying adversarial constraints. In this problem, after selecting a feasible action from the convex decision set $X,$ a convex constraint function is revealed alongside the cost function in each round. We propose a *projection-free* online policy which makes a single call to a Linear Program (LP) solver per round.
  arXiv  Detail & Related papers  (2025-01-28T13:04:32Z)
• Pathwise optimization for bridge-type estimators and its applications [49.1574468325115]
  Pathwise methods allow to efficiently compute the full path for penalized estimators. We apply these algorithms to the penalized estimation of processes observed at discrete times.
  arXiv  Detail & Related papers  (2024-12-05T10:38:29Z)
• First-Order Dynamic Optimization for Streaming Convex Costs [0.0]
  We develop an approach to track the optimal solution with a bounded error. Our algorithm is executed only by using the first-order derivatives of the cost function.
  arXiv  Detail & Related papers  (2023-10-11T22:41:00Z)
• Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
  We show that randomization is necessary to obtain a dimension-free dimension-free algorithm. Our algorithm yields the first deterministic dimension-free algorithm for optimizing ReLU networks.
  arXiv  Detail & Related papers  (2023-02-16T13:57:19Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  We exploit between first-order algorithms for constrained optimization and non-smooth systems to design a new class of accelerated first-order algorithms. An important property of these algorithms is that constraints are expressed in terms of velocities instead of sparse variables.
  arXiv  Detail & Related papers  (2023-02-01T08:50:48Z)
• A Near-Optimal Algorithm for Univariate Zeroth-Order Budget Convex Optimization [4.608510640547952]
  We prove near-optimal optimization error guarantees for Dy Search. We show that the classical dependence on the global Lipschitz constant in the error bounds is an artifact of the granularity of the budget.
  arXiv  Detail & Related papers  (2022-08-13T19:57:04Z)
• Divide and Learn: A Divide and Conquer Approach for Predict+Optimize [50.03608569227359]
  The predict+optimize problem combines machine learning ofproblem coefficients with a optimization prob-lem that uses the predicted coefficients. We show how to directlyexpress the loss of the optimization problem in terms of thepredicted coefficients as a piece-wise linear function. We propose a novel divide and algorithm to tackle optimization problems without this restriction and predict itscoefficients using the optimization loss.
  arXiv  Detail & Related papers  (2020-12-04T00:26:56Z)
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic [142.1492359556374]
  Bilevel optimization is a class of problems which exhibit a two-level structure. We propose a two-timescale approximation (TTSA) algorithm for tackling such a bilevel problem. We show that a two-timescale natural actor-critic policy optimization algorithm can be viewed as a special case of our TTSA framework.
  arXiv  Detail & Related papers  (2020-07-10T05:20:02Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  We study the problem of minimizing the population loss given i.i.d. samples from a distribution over convex loss functions. A recent work of Bassily et al. has established the optimal bound on the excess population loss achievable given $n$ samples. We describe two new techniques for deriving convex optimization algorithms both achieving the optimal bound on excess loss and using $O(minn, n2/d)$ gradient computations.
  arXiv  Detail & Related papers  (2020-05-10T19:52:03Z)
• Constrained Multiagent Rollout and Multidimensional Assignment with the Auction Algorithm [0.0]
  We consider an extension of the rollout algorithm that applies to constrained deterministic dynamic programming. We show that if the base produces a feasible solution, the rollout algorithm has a cost improvement property. We show that the cost improvement property is maintained with an alternative implementation that has greatly reduced computational requirements.
  arXiv  Detail & Related papers  (2020-02-18T07:09:06Z)

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.