BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Babak Hassibi

Babak Hassibi contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.OCMachine Learningeess.SYInformation Theorymath.ITSystems and Controlmath.DS

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
16works
0followers
7topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

16 published item(s)

preprint2023arXiv

Feedback Capacity of MIMO Gaussian Channels

Finding a computable expression for the feedback capacity of channels with colored Gaussian, additive noise is a long standing open problem. In this paper, we solve this problem in the scenario where the channel has multiple inputs and multiple outputs (MIMO) and the noise process is generated as the output of a time-invariant state-space model. Our main result is a computable expression for the feedback capacity in terms of a finite-dimensional convex optimization. The solution to the feedback capacity problem is obtained by formulating the finite-block counterpart of the capacity problem as a \emph{sequential convex optimization problem} which leads in turn to a single-letter upper bound. This converse derivation integrates tools and ideas from information theory, control, filtering and convex optimization. A tight lower bound is realized by optimizing over a family of time-invariant policies thus showing that time-invariant inputs are optimal even when the noise process may not be stationary. The optimal time-invariant policy is used to construct a capacity-achieving and simple coding scheme for scalar channels, and its analysis reveals an interesting relation between a smoothing problem and the feedback capacity expression.

0 citations0 reviewsNo code linkedOpen access
preprint2023arXiv

Wasserstein Distributionally Robust Regret-Optimal Control in the Infinite-Horizon

We investigate the Distributionally Robust Regret-Optimal (DR-RO) control of discrete-time linear dynamical systems with quadratic cost over an infinite horizon. Regret is the difference in cost obtained by a causal controller and a clairvoyant controller with access to future disturbances. We focus on the infinite-horizon framework, which results in stability guarantees. In this DR setting, the probability distribution of the disturbances resides within a Wasserstein-2 ambiguity set centered at a specified nominal distribution. Our objective is to identify a control policy that minimizes the worst-case expected regret over an infinite horizon, considering all potential disturbance distributions within the ambiguity set. In contrast to prior works, which assume time-independent disturbances, we relax this constraint to allow for time-correlated disturbances, thus actual distributional robustness. While we show that the resulting optimal controller is non-rational and lacks a finite-dimensional state-space realization, we demonstrate that it can still be uniquely characterized by a finite dimensional parameter. Exploiting this fact, we introduce an efficient numerical method to compute the controller in the frequency domain using fixed-point iterations. This method circumvents the computational bottleneck associated with the finite-horizon problem, where the semi-definite programming (SDP) solution dimension scales with the time horizon. Numerical experiments demonstrate the effectiveness and performance of our framework.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Differentially Quantized Gradient Methods

Consider the following distributed optimization scenario. A worker has access to training data that it uses to compute the gradients while a server decides when to stop iterative computation based on its target accuracy or delay constraints. The server receives all its information about the problem instance from the worker via a rate-limited noiseless communication channel. We introduce the principle we call Differential Quantization (DQ) that prescribes compensating the past quantization errors to direct the descent trajectory of a quantized algorithm towards that of its unquantized counterpart. Assuming that the objective function is smooth and strongly convex, we prove that Differentially Quantized Gradient Descent (DQ-GD) attains a linear contraction factor of $\max\{σ_{\mathrm{GD}}, ρ_n 2^{-R}\}$, where $σ_{\mathrm{GD}}$ is the contraction factor of unquantized gradient descent (GD), $ρ_n \geq 1$ is the covering efficiency of the quantizer, and $R$ is the bitrate per problem dimension $n$. Thus at any $R\geq\log_2 ρ_n /σ_{\mathrm{GD}}$ bits, the contraction factor of DQ-GD is the same as that of unquantized GD, i.e., there is no loss due to quantization. We show that no algorithm within a certain class can converge faster than $\max\{σ_{\mathrm{GD}}, 2^{-R}\}$. Since quantizers exist with $ρ_n \to 1$ as $n \to \infty$ (Rogers, 1963), this means that DQ-GD is asymptotically optimal. The principle of differential quantization continues to apply to gradient methods with momentum such as Nesterov's accelerated gradient descent, and Polyak's heavy ball method. For these algorithms as well, if the rate is above a certain threshold, there is no loss in contraction factor obtained by the differentially quantized algorithm compared to its unquantized counterpart. Experimental results on least-squares problems validate our theoretical analysis.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Explicit Regularization via Regularizer Mirror Descent

Despite perfectly interpolating the training data, deep neural networks (DNNs) can often generalize fairly well, in part due to the "implicit regularization" induced by the learning algorithm. Nonetheless, various forms of regularization, such as "explicit regularization" (via weight decay), are often used to avoid overfitting, especially when the data is corrupted. There are several challenges with explicit regularization, most notably unclear convergence properties. Inspired by convergence properties of stochastic mirror descent (SMD) algorithms, we propose a new method for training DNNs with regularization, called regularizer mirror descent (RMD). In highly overparameterized DNNs, SMD simultaneously interpolates the training data and minimizes a certain potential function of the weights. RMD starts with a standard cost which is the sum of the training loss and a convex regularizer of the weights. Reinterpreting this cost as the potential of an "augmented" overparameterized network and applying SMD yields RMD. As a result, RMD inherits the properties of SMD and provably converges to a point "close" to the minimizer of this cost. RMD is computationally comparable to stochastic gradient descent (SGD) and weight decay, and is parallelizable in the same manner. Our experimental results on training sets with various levels of corruption suggest that the generalization performance of RMD is remarkably robust and significantly better than both SGD and weight decay, which implicitly and explicitly regularize the $\ell_2$ norm of the weights. RMD can also be used to regularize the weights to a desired weight vector, which is particularly relevant for continual learning.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Feedback capacity of Gaussian channels with memory

We consider the feedback capacity of a MIMO channel whose channel output is given by a linear state-space model driven by the channel inputs and a Gaussian process. The generality of our state-space model subsumes all previous studied models such as additive channels with colored Gaussian noise, and channels with an arbitrary dependence on previous channel inputs or outputs. The main result is a computable feedback capacity expression that is given as a convex optimization problem subject to a detectability condition. We demonstrate the capacity result on the auto-regressive Gaussian noise channel, where we show that even a single time-instance delay in the feedback reduces the feedback capacity significantly in the stationary regime. On the other hand, for large regression parameters (in the non-stationary regime), the feedback capacity can be approached with delayed feedback. Finally, we show that the detectability condition is satisfied for scalar models and conjecture that it is true for MIMO models.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Measurement-Feedback Control with Optimal Data-Dependent Regret

Inspired by online learning, data-dependent regret has recently been proposed as a criterion for controller design. In the regret-optimal control paradigm, causal controllers are designed to minimize regret against a hypothetical optimal noncausal controller, which selects the globally cost-minimizing sequence of control actions given noncausal access to the disturbance sequence. We extend regret-optimal control to the more challenging measurement-feedback setting, where the online controller must compete against the optimal noncausal controller without directly observing the state or the driving disturbance. We show that no measurement-feedback controller can have bounded competitive ratio or regret which is bounded by the pathlength of the measurement disturbance. We do derive, however, a controller whose regret has optimal dependence on the joint energy of the driving and measurement disturbances, and another controller whose regret has optimal dependence on the pathlength of the driving disturbance and the energy of the measurement disturbance. The key technique we introduce is a reduction from regret-optimal measurement-feedback control to $H_{\infty}$-optimal measurement-feedback control in a synthetic system. We present numerical simulations which illustrate the efficacy of our proposed control algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Optimal Competitive-Ratio Control

Inspired by competitive policy designs approaches in online learning, new control paradigms such as competitive-ratio and regret-optimal control have been recently proposed as alternatives to the classical $\mathcal{H}_2$ and $\mathcal{H}_\infty$ approaches. These competitive metrics compare the control cost of the designed controller against the cost of a clairvoyant controller, which has access to past, present, and future disturbances in terms of ratio and difference, respectively. While prior work provided the optimal solution for the regret-optimal control problem, in competitive-ratio control, the solution is only provided for the sub-optimal problem. In this work, we derive the optimal solution to the competitive-ratio control problem. We show that the optimal competitive ratio formula can be computed as the maximal eigenvalue of a simple matrix, and provide a state-space controller that achieves the optimal competitive ratio. We conduct an extensive numerical study to verify this analytical solution, and demonstrate that the optimal competitive-ratio controller outperforms other controllers on several large scale practical systems. The key techniques that underpin our explicit solution is a reduction of the control problem to a Nehari problem, along with a novel factorization of the clairvoyant controller's cost. We reveal an interesting relation between the explicit solutions that now exist for both competitive control paradigms by formulating a regret-optimal control framework with weight functions that can also be utilized for practical purposes.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Reinforcement Learning with Fast Stabilization in Linear Dynamical Systems

In this work, we study model-based reinforcement learning (RL) in unknown stabilizable linear dynamical systems. When learning a dynamical system, one needs to stabilize the unknown dynamics in order to avoid system blow-ups. We propose an algorithm that certifies fast stabilization of the underlying system by effectively exploring the environment with an improved exploration strategy. We show that the proposed algorithm attains $\tilde{\mathcal{O}}(\sqrt{T})$ regret after $T$ time steps of agent-environment interaction. We also show that the regret of the proposed algorithm has only a polynomial dependence in the problem dimensions, which gives an exponential improvement over the prior methods. Our improved exploration method is simple, yet efficient, and it combines a sophisticated exploration policy in RL with an isotropic exploration strategy to achieve fast stabilization and improved regret. We empirically demonstrate that the proposed algorithm outperforms other popular methods in several adaptive control tasks.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Thompson Sampling Achieves $\tilde O(\sqrt{T})$ Regret in Linear Quadratic Control

Thompson Sampling (TS) is an efficient method for decision-making under uncertainty, where an action is sampled from a carefully prescribed distribution which is updated based on the observed data. In this work, we study the problem of adaptive control of stabilizable linear-quadratic regulators (LQRs) using TS, where the system dynamics are unknown. Previous works have established that $\tilde O(\sqrt{T})$ frequentist regret is optimal for the adaptive control of LQRs. However, the existing methods either work only in restrictive settings, require a priori known stabilizing controllers, or utilize computationally intractable approaches. We propose an efficient TS algorithm for the adaptive control of LQRs, TS-based Adaptive Control, TSAC, that attains $\tilde O(\sqrt{T})$ regret, even for multidimensional systems, thereby solving the open problem posed in Abeille and Lazaric (2018). TSAC does not require a priori known stabilizing controller and achieves fast stabilization of the underlying system by effectively exploring the environment in the early stages. Our result hinges on developing a novel lower bound on the probability that the TS provides an optimistic sample. By carefully prescribing an early exploration strategy and a policy update rule, we show that TS achieves order-optimal regret in adaptive control of multidimensional stabilizable LQRs. We empirically demonstrate the performance and the efficiency of TSAC in several adaptive control tasks.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Regret-optimal control in dynamic environments

We consider control in linear time-varying dynamical systems from the perspective of regret minimization. Unlike most prior work in this area, we focus on the problem of designing an online controller which minimizes regret against the best dynamic sequence of control actions selected in hindsight (dynamic regret), instead of the best fixed controller in some specific class of controllers (static regret). This formulation is attractive when the environment changes over time and no single controller achieves good performance over the entire time horizon. We derive the state-space structure of the regret-optimal controller via a novel reduction to $H_{\infty}$ control and present a tight data-dependent bound on its regret in terms of the energy of the disturbance. Our results easily extend to the model-predictive setting where the controller can anticipate future disturbances and to settings where the controller only affects the system dynamics after a fixed delay. We present numerical experiments which show that our regret-optimal controller interpolates between the performance of the $H_2$-optimal and $H_{\infty}$-optimal controllers across stochastic and adversarial environments.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Adaptive Control and Regret Minimization in Linear Quadratic Gaussian (LQG) Setting

We study the problem of adaptive control in partially observable linear quadratic Gaussian control systems, where the model dynamics are unknown a priori. We propose LqgOpt, a novel reinforcement learning algorithm based on the principle of optimism in the face of uncertainty, to effectively minimize the overall control cost. We employ the predictor state evolution representation of the system dynamics and deploy a recently proposed closed-loop system identification method, estimation, and confidence bound construction. LqgOpt efficiently explores the system dynamics, estimates the model parameters up to their confidence interval, and deploys the controller of the most optimistic model for further exploration and exploitation. We provide stability guarantees for LqgOpt and prove the regret upper bound of $\tilde{\mathcal{O}}(\sqrt{T})$ for adaptive control of linear quadratic Gaussian (LQG) systems, where $T$ is the time horizon of the problem.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Logarithmic Regret Bound in Partially Observable Linear Dynamical Systems

We study the problem of system identification and adaptive control in partially observable linear dynamical systems. Adaptive and closed-loop system identification is a challenging problem due to correlations introduced in data collection. In this paper, we present the first model estimation method with finite-time guarantees in both open and closed-loop system identification. Deploying this estimation method, we propose adaptive control online learning (AdaptOn), an efficient reinforcement learning algorithm that adaptively learns the system dynamics and continuously updates its controller through online learning steps. AdaptOn estimates the model dynamics by occasionally solving a linear regression problem through interactions with the environment. Using policy re-parameterization and the estimated model, AdaptOn constructs counterfactual loss functions to be used for updating the controller through online gradient descent. Over time, AdaptOn improves its model estimates and obtains more accurate gradient updates to improve the controller. We show that AdaptOn achieves a regret upper bound of $\text{polylog}\left(T\right)$, after $T$ time steps of agent-environment interaction. To the best of our knowledge, AdaptOn is the first algorithm that achieves $\text{polylog}\left(T\right)$ regret in adaptive control of unknown partially observable linear dynamical systems which includes linear quadratic Gaussian (LQG) control.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Regret Minimization in Partially Observable Linear Quadratic Control

We study the problem of regret minimization in partially observable linear quadratic control systems when the model dynamics are unknown a priori. We propose ExpCommit, an explore-then-commit algorithm that learns the model Markov parameters and then follows the principle of optimism in the face of uncertainty to design a controller. We propose a novel way to decompose the regret and provide an end-to-end sublinear regret upper bound for partially observable linear quadratic control. Finally, we provide stability guarantees and establish a regret upper bound of $\tilde{\mathcal{O}}(T^{2/3})$ for ExpCommit, where $T$ is the time horizon of the problem.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Support Constrained Generator Matrices of Gabidulin Codes in Characteristic Zero

Gabidulin codes over fields of characteristic zero were recently constructed by Augot et al., whenever the Galois group of the underlying field extension is cyclic. In parallel, the interest in sparse generator matrices of Reed-Solomon and Gabidulin codes has increased lately, due to applications in distributed computations. In particular, a certain condition pertaining the intersection of zero entries at different rows, was shown to be necessary and sufficient for the existence of the sparsest possible generator matrix of Gabidulin codes over finite fields. In this paper we complete the picture by showing that the same condition is also necessary and sufficient for Gabidulin codes over fields of characteristic zero. Our proof builds upon and extends tools from the finite field case, combines them with a variant of the Schwartz-Zippel lemma over automorphisms, and provides a simple randomized construction algorithm whose probability of success can be arbitrarily close to one. In addition, potential applications for low-rank matrix recovery are discussed.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The Power of Linear Controllers in LQR Control

The Linear Quadratic Regulator (LQR) framework considers the problem of regulating a linear dynamical system perturbed by environmental noise. We compute the policy regret between three distinct control policies: i) the optimal online policy, whose linear structure is given by the Ricatti equations; ii) the optimal offline linear policy, which is the best linear state feedback policy given the noise sequence; and iii) the optimal offline policy, which selects the globally optimal control actions given the noise sequence. We fully characterize the optimal offline policy and show that it has a recursive form in terms of the optimal online policy and future disturbances. We also show that cost of the optimal offline linear policy converges to the cost of the optimal online policy as the time horizon grows large, and consequently the optimal offline linear policy incurs linear regret relative to the optimal offline policy, even in the optimistic setting where the noise is drawn i.i.d from a known distribution. Although we focus on the setting where the noise is stochastic, our results also imply new lower bounds on the policy regret achievable when the noise is chosen by an adaptive adversary.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Manifold Optimization Over the Set of Doubly Stochastic Matrices: A Second-Order Geometry

Convex optimization is a well-established research area with applications in almost all fields. Over the decades, multiple approaches have been proposed to solve convex programs. The development of interior-point methods allowed solving a more general set of convex programs known as semi-definite programs and second-order cone programs. However, it has been established that these methods are excessively slow for high dimensions, i.e., they suffer from the curse of dimensionality. On the other hand, optimization algorithms on manifold have shown great ability in finding solutions to nonconvex problems in reasonable time. This paper is interested in solving a subset of convex optimization using a different approach. The main idea behind Riemannian optimization is to view the constrained optimization problem as an unconstrained one over a restricted search space. The paper introduces three manifolds to solve convex programs under particular box constraints. The manifolds, called the doubly stochastic, symmetric and the definite multinomial manifolds, generalize the simplex also known as the multinomial manifold. The proposed manifolds and algorithms are well-adapted to solving convex programs in which the variable of interest is a multidimensional probability distribution function. Theoretical analysis and simulation results testify the efficiency of the proposed method over state of the art methods. In particular, they reveal that the proposed framework outperforms conventional generic and specialized solvers, especially in high dimensions.

0 citations0 reviewsNo code linkedOpen access