Subgradient Method for System Identification with Non-Smooth Objectives

• URL: http://arxiv.org/abs/2503.16673v1
• Date: Thu, 20 Mar 2025 19:39:47 GMT
• Title: Subgradient Method for System Identification with Non-Smooth Objectives
• Authors: Baturalp Yalcin, Javad Lavaei,
• Abstract summary: This paper investigates a subgradient-based algorithm to solve the system identification problem for linear time-invariant systems with non-smooth objectives.<n>This is the first work to analyze subgradient algorithms for system identification with non-smooth objectives.
• Score: 16.328866317851187
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: This paper investigates a subgradient-based algorithm to solve the system identification problem for linear time-invariant systems with non-smooth objectives. This is essential for robust system identification in safety-critical applications. While existing work provides theoretical exact recovery guarantees using optimization solvers, the design of fast learning algorithms with convergence guarantees for practical use remains unexplored. We analyze the subgradient method in this setting where the optimization problems to be solved change over time as new measurements are taken, and we establish linear convergence results for both the best and Polyak step sizes after a burn-in period. Additionally, we characterize the asymptotic convergence of the best average sub-optimality gap under diminishing and constant step sizes. Finally, we compare the time complexity of standard solvers with the subgradient algorithm and support our findings with experimental results. This is the first work to analyze subgradient algorithms for system identification with non-smooth objectives.

Related papers

• Fast sparse optimization via adaptive shrinkage [0.6226609932118122]
  We develop a proximal method, based on logarithmic regularization, which turns out to be an iterative shrinkage-thresholding algorithm. This adaptivity substantially enhances the trajectory of the algorithm, in a way that yields faster convergence. We validate its fast convergence via numerical experiments and we discuss the performance with respect to state-of-the-art algorithms.
  arXiv  Detail & Related papers  (2025-01-21T15:58:21Z)
• A Primal-dual algorithm for image reconstruction with ICNNs [3.4797100095791706]
  We address the optimization problem in a data-driven variational framework, where the regularizer is parameterized by an input- neural network (ICNN) While gradient-based methods are commonly used to solve such problems, they struggle to effectively handle nonsmoothness. We show that a proposed approach outperforms subgradient methods in terms of both speed and stability.
  arXiv  Detail & Related papers  (2024-10-16T10:36:29Z)
• A New Inexact Proximal Linear Algorithm with Adaptive Stopping Criteria for Robust Phase Retrieval [6.407536646154451]
  This paper considers the robust retrieval problem, which can be cast as a nonsmooth and non optimization problem. We propose a new inexact proximal linear algorithm with the subproblem being solved in two contributions.
  arXiv  Detail & Related papers  (2023-04-25T02:29:33Z)
• Adaptive Stochastic Optimisation of Nonconvex Composite Objectives [2.1700203922407493]
  We propose and analyse a family of generalised composite mirror descent algorithms. With adaptive step sizes, the proposed algorithms converge without requiring prior knowledge of the problem. We exploit the low-dimensional structure of the decision sets for high-dimensional problems.
  arXiv  Detail & Related papers  (2022-11-21T18:31:43Z)
• ARES: An Efficient Algorithm with Recurrent Evaluation and Sampling-Driven Inference for Maximum Independent Set [48.57120672468062]
  This paper introduces an efficient algorithm for the Maximum Independent Set (MIS) problem, incorporating two innovative techniques. The proposed algorithm outperforms state-of-the-art algorithms in terms of solution quality, computational efficiency, and stability.
  arXiv  Detail & Related papers  (2022-08-16T14:39:38Z)
• Log Barriers for Safe Black-box Optimization with Application to Safe Reinforcement Learning [72.97229770329214]
  We introduce a general approach for seeking high dimensional non-linear optimization problems in which maintaining safety during learning is crucial. Our approach called LBSGD is based on applying a logarithmic barrier approximation with a carefully chosen step size. We demonstrate the effectiveness of our approach on minimizing violation in policy tasks in safe reinforcement learning.
  arXiv  Detail & Related papers  (2022-07-21T11:14:47Z)
• An Adaptive Incremental Gradient Method With Support for Non-Euclidean Norms [19.41328109094503]
  We propose and analyze several novel adaptive variants of the popular SAGA algorithm. We establish its convergence guarantees under general settings. We improve the analysis of SAGA to support non-Euclidean norms.
  arXiv  Detail & Related papers  (2022-04-28T09:43:07Z)
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
  We study a class of algorithms for solving bilevel optimization problems in both deterministic and deterministic settings. We exploit a warm-start strategy to amortize the estimation of the exact gradient. By using this framework, our analysis shows these algorithms to match the computational complexity of methods that have access to an unbiased estimate of the gradient.
  arXiv  Detail & Related papers  (2021-11-29T15:10:09Z)
• 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)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)
• A Dynamical Systems Approach for Convergence of the Bayesian EM Algorithm [59.99439951055238]
  We show how (discrete-time) Lyapunov stability theory can serve as a powerful tool to aid, or even lead, in the analysis (and potential design) of optimization algorithms that are not necessarily gradient-based. The particular ML problem that this paper focuses on is that of parameter estimation in an incomplete-data Bayesian framework via the popular optimization algorithm known as maximum a posteriori expectation-maximization (MAP-EM) We show that fast convergence (linear or quadratic) is achieved, which could have been difficult to unveil without our adopted S&C approach.
  arXiv  Detail & Related papers  (2020-06-23T01:34:18Z)

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.