Extrapolation-based Prediction-Correction Methods for Time-varying Convex Optimization

• URL: http://arxiv.org/abs/2004.11709v4
• Date: Thu, 4 May 2023 10:51:50 GMT
• Title: Extrapolation-based Prediction-Correction Methods for Time-varying Convex Optimization
• Authors: Nicola Bastianello, Ruggero Carli, Andrea Simonetto
• Abstract summary: We discuss algorithms for online optimization based on the prediction-correction paradigm. We propose a novel and tailored prediction strategy, which we call extrapolation-based. We discuss the empirical performance of the algorithm when applied to signal processing, machine learning, and robotics problems.
• Score: 5.768816587293478
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we focus on the solution of online optimization problems that arise often in signal processing and machine learning, in which we have access to streaming sources of data. We discuss algorithms for online optimization based on the prediction-correction paradigm, both in the primal and dual space. In particular, we leverage the typical regularized least-squares structure appearing in many signal processing problems to propose a novel and tailored prediction strategy, which we call extrapolation-based. By using tools from operator theory, we then analyze the convergence of the proposed methods as applied both to primal and dual problems, deriving an explicit bound for the tracking error, that is, the distance from the time-varying optimal solution. We further discuss the empirical performance of the algorithm when applied to signal processing, machine learning, and robotics problems.

Related papers

• Maximum Optimality Margin: A Unified Approach for Contextual Linear Programming and Inverse Linear Programming [10.06803520598035]
  We develop a new approach to the problem called maximum optimality margin which the machine learning loss function by the optimality condition of the downstream optimization.
  arXiv  Detail & Related papers  (2023-01-26T17:53:38Z)
• Socio-cognitive Optimization of Time-delay Control Problems using Evolutionary Metaheuristics [89.24951036534168]
  Metaheuristics are universal optimization algorithms which should be used for solving difficult problems, unsolvable by classic approaches. In this paper we aim at constructing novel socio-cognitive metaheuristic based on castes, and apply several versions of this algorithm to optimization of time-delay system model.
  arXiv  Detail & Related papers  (2022-10-23T22:21:10Z)
• On the Convergence of Distributed Stochastic Bilevel Optimization Algorithms over a Network [55.56019538079826]
  Bilevel optimization has been applied to a wide variety of machine learning models. Most existing algorithms restrict their single-machine setting so that they are incapable of handling distributed data. We develop novel decentralized bilevel optimization algorithms based on a gradient tracking communication mechanism and two different gradients.
  arXiv  Detail & Related papers  (2022-06-30T05:29:52Z)
• Deep Equilibrium Assisted Block Sparse Coding of Inter-dependent Signals: Application to Hyperspectral Imaging [71.57324258813675]
  A dataset of inter-dependent signals is defined as a matrix whose columns demonstrate strong dependencies. A neural network is employed to act as structure prior and reveal the underlying signal interdependencies. Deep unrolling and Deep equilibrium based algorithms are developed, forming highly interpretable and concise deep-learning-based architectures.
  arXiv  Detail & Related papers  (2022-03-29T21:00:39Z)
• Teaching Networks to Solve Optimization Problems [13.803078209630444]
  We propose to replace the iterative solvers altogether with a trainable parametric set function. We show the feasibility of learning such parametric (set) functions to solve various classic optimization problems.
  arXiv  Detail & Related papers  (2022-02-08T19:13:13Z)
• Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
  We explore the connection between high-dimensional statistics and non-robust optimization in the presence of sparsity constraints. We develop novel and simple optimization formulations for these problems. As a corollary, we obtain that any first-order method that efficiently converges to station yields an efficient algorithm for these tasks.
  arXiv  Detail & Related papers  (2021-09-23T17:38:24Z)
• An Online Prediction Approach Based on Incremental Support Vector Machine for Dynamic Multiobjective Optimization [19.336520152294213]
  We propose a novel prediction algorithm based on incremental support vector machine (ISVM) We treat the solving of dynamic multiobjective optimization problems (DMOPs) as an online learning process. The proposed algorithm can effectively tackle dynamic multiobjective optimization problems.
  arXiv  Detail & Related papers  (2021-02-24T08:51:23Z)
• Integrated Optimization of Predictive and Prescriptive Tasks [0.0]
  We propose a new framework directly integrating predictive tasks under prescriptive tasks. We train the parameters of predictive algorithm within a prescription problem via bilevel optimization techniques.
  arXiv  Detail & Related papers  (2021-01-02T02:43:10Z)
• Parallelization Techniques for Verifying Neural Networks [52.917845265248744]
  We introduce an algorithm based on the verification problem in an iterative manner and explore two partitioning strategies. We also introduce a highly parallelizable pre-processing algorithm that uses the neuron activation phases to simplify the neural network verification problems.
  arXiv  Detail & Related papers  (2020-04-17T20:21:47Z)
• Distributed Averaging Methods for Randomized Second Order Optimization [54.51566432934556]
  We consider distributed optimization problems where forming the Hessian is computationally challenging and communication is a bottleneck. We develop unbiased parameter averaging methods for randomized second order optimization that employ sampling and sketching of the Hessian. We also extend the framework of second order averaging methods to introduce an unbiased distributed optimization framework for heterogeneous computing systems.
  arXiv  Detail & Related papers  (2020-02-16T09:01:18Z)
• Nonlinear Traffic Prediction as a Matrix Completion Problem with Ensemble Learning [1.8352113484137629]
  This paper addresses the problem of short-term traffic prediction for signalized traffic operations management. We focus on predicting sensor states in high-resolution (second-by-second) Our contributions can be summarized as offering three insights.
  arXiv  Detail & Related papers  (2020-01-08T13:10:40Z)

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.