ABSTRACT. BHRS1 -- This paper presents an online method that learns optimal decisions for a discrete time Markov decision problem with an opportunistic structure. The state at time t is a pair (S(t),W(t)) where S(t) takes values in a finite set S of basic states, and {W(t)} is an i.i.d. sequence of random vectors that affect the system and that have an unknown distribution. Every slot t the controller observes (S(t), W (t)) and chooses a control action A(t). The triplet (S(t), W (t), A(t)) determines a vector of costs and the transition probabilities for the next state S(t+1). The goal is to minimize the time average of an objective function subject to additional time average cost constraints. We develop an algorithm that acts on a corresponding virtual system where S(t) is replaced by a decision variable. An equivalence between virtual and actual systems is established by enforcing a collection of time averaged global balance equations. For any desired ε > 0, we prove the algorithm achieves an ε-optimal solution on the virtual system with a convergence time of O(1/ε^2). The actual system runs at the same time, its actions are informed by the virtual system, and its conditional transition probabilities and costs are proven to be the same as the virtual system at every instant of time. Also, its unconditional probabilities and costs are shown in simulation to closely match the virtual system. Our simulations consider online control of a robot that explores a region of interest. Objects with varying rewards appear and disappear and the robot learns what areas to explore and what objects to collect and deliver to a home base.

ABSTRACT. BHRS1: In this paper, we study reinforcement learning from human feedback (RLHF) under an episodic Markov decision process with a general trajectory-wise reward model. We developed RLHF algorithms without explicit reward model inference, which is a critical intermediate step in the contemporary RLHF paradigms for training large language models (LLM). The algorithm identifies the optimal policy directly from human preference information. This end-to-end RLHF may deliver improved performance by avoiding pitfalls in reward inferring such as overfit and distribution shift.

ABSTRACT. This presentation focuses on the problem of shuffled linear regression, where the correspondence between predictors and responses in a linear model is obfuscated by a latent permutation and one needs to jointly estimate the permutation and regression coefficients. This problem finds applications in various areas ranging from robotics, multi-target tracking, signal processing, to data integration and de-anonymization. While the statistical and computational facets of shuffled linear regression have been a subject of extensive research over the past decade, the precise statistical thresholds for recovery have remained elusive. In this talk, I will describe our latest progress in establishing these precise thresholds for both perfect and near-perfect recovery. Our proof builds upon a careful analysis of the maximum likelihood estimator (MLE) divided into the large-error regime and the small-error regime. From the computational perspective, the MLE represents a specific instance of the NP-hard quadratic assignment problem. No polynomial-time algorithms are known to succeed close to the statistical limits, except for noiseless or low-dimensional settings. The talk is based on joint work with Leon Lufkin and Yihong Wu from Yale University. The preprint is available at https://arxiv.org/abs/2402.09693

ABSTRACT. BHRS1 The Transform Method based on the Drift Method has been developed in the last four years for heavy-traffic analysis in a variety of queueing systems, including the single-server queue, load-balancing system, input-queued switch, generalized switch under complete resource pooling, and ride-sharing. These are studied in discrete time under i.i.d. arrival and potential service process. In this talk, I will introduce a generalization to the Transform Method, where we allow a Markov-modulated arrival and service process. The key is in carefully designing the test function, which includes the queue length and a correction due to the Markov-modulated nature of the arrival process. In this talk, I will present a simple case, but the methodology can be generalized to more complex queueing networks.

ABSTRACT. BHRS1: Local memory systems play a crucial role in today’s networks: keeping popular content close to users improves performance by reducing the latency of fetching an item from a more costly central location. Caching policies that retain recently requested items are effective to deal with bursts of requests; in particular timer-based (TTL) caching policies are of this nature, and have well understood properties. However, in some scenarios, traffic is more regular, reflected in the fact that the hazard rate function of inter-request times is increasing. For this situation we propose the strategy of Timer-based Pre-fetching, a dual of TTL caching. We characterize the optimal Pre-fetching timers as the solution to a convex optimization problem, showing this approach improves upon caching strategies. We also analyze the large scale behavior of the optimal policy, which amounts to threshold policy in the hazard rates, and give asymptotic performance results for a general class of arrival processes.

ABSTRACT. This paper considers causal bandits (CBs) for the sequential design of interventions in a causal system. The objective is to optimize a reward function via minimizing a measure of cumulative regret with respect to the best sequence of interventions in hindsight. The paper advances the results on CBs in three directions. First, the structural causal models (SCMs) are assumed to be \emph{unknown} and drawn arbitrarily from a general class $\mcF$ of Lipschitz-continuous functions. Existing results are often focused on (generalized) linear SCMs. Second, the interventions are assumed to be \emph{generalized soft} with any desired level of granularity, resulting in an infinite number of possible interventions. The existing literature, in contrast, generally adopts \emph{atomic} and \emph{hard} interventions. Third, we provide general upper \emph{and} lower bounds on regret. The upper bounds subsume (and improve) known bounds for special cases. The lower bounds are generally hitherto unknown. These bounds are characterized as functions of the (i)~graph parameters, (ii)~eluder dimension of the space of SCMs, denoted by $\operatorname{dim}(\mcF)$, and (iii)~the covering number of the function space, denoted by $\cn(\mcF)$. Specifically, the cumulative achievable regret over horizon $T$ is $\mcO(K d^{L-1}\sqrt{T\operatorname{dim}(\mcF) \log(\cn(\mcF))})$, where $K$ is related to the Lipschitz constants, $d$ is the graph’s maximum in-degree, and $L$ is the length of the longest causal path. The upper bound is further refined for special classes of SCMs (neural network, polynomial, and linear), and their corresponding lower bounds are provided.

ABSTRACT. Methods in the field of quickest change detection rapidly detect in real-time a change in the data-generating distribution of an online data stream. Existing methods have been able to detect this change point when the densities of the pre- and post-change distributions are known. Recent work has extended these results to the case where the pre- and post-change distributions are known only by their score functions. This work considers the case where the pre- and post-change score functions are known only to correspond to distributions in two disjoint sets. This work employs a pair of "least-favorable" distributions to robustify the existing score-based quickest change detection algorithm, the properties of which are studied. This paper calculates the least-favorable distributions for specific model classes and provides methods of estimating the least-favorable distributions for common constructions. Simulation results are provided demonstrating the performance of our robust change detection algorithm.

ABSTRACT. We consider the stochastic linear bandit problem with several arms over T rounds, where the dimension d of the covariate vectors is potentially larger than T, although each arm-specific parameter vector has at most s non-zero components. First, we study the single-arm case, focusing on the cumulative estimation error of the parameter vector. We show that Lasso has a sub-optimal dependence on d and T in terms of worst-case error in the online estimation setup. Further, we establish the minimax optimality of the thresholded Lasso, which first estimates the support of the parameter vector by thresholding the Lasso estimator and then runs least squares on the selected support. Second, we consider the bandit setup, using the thresholded Lasso as the main estimation method. We propose a three-stage algorithm for arm selection and derive an upper bound of order s(log(d)+log(T))log(s) on its cumulative regret. Finally, we establish a matching lower bound up to a log(s) multiplicative term, which shows the near minimax optimality of the proposed method. We note that our analysis avoids the restrictive "beta-min" condition.

ABSTRACT. We present a procedure based on higher criticism (Dohono \& Jin 2004) to address the sparse multi-stream quickest change-point detection problem. Namely, we aim to detect a change in the distribution of the multi-stream that might occur in some unknown time instant. The change itself, if occurs, only affecting a few data streams out of potentially many while those affected streams, if exist, are unknown to us in advance. Our procedure involves testing for a change point in individual streams and combining multiple tests using higher criticism. As a by-product, our procedure also indicates a set of streams suspected to be affected by the change. We characterize the information-theoretic detection limit under a Gaussian heteroscedastic mean shift when individual tests are based on the LR or GLR and show that our procedure attains this limit; this limit coincides with existing results in the homoscedastic case. We demonstrate the effectiveness of our method compared to other procedures using numerical evaluations.

ABSTRACT. In this article, we focus on solving a class of distributed optimization problems involving n agents with the local objective function at every agent i given by the difference of two convex functions f_i and g_i (difference-of-convex (DC) form), where f_i and g_i are potentially nonsmooth. The agents communicate via a directed graph containing n nodes. We create smooth approximations of the functions f_i and g_i and develop a distributed algorithm utilizing the gradients of the smooth surrogates and a finite-time approximate consensus protocol. We term this algorithm as DDC-Consensus. The developed DDC-Consensus algorithm allows for non-symmetric directed graph topologies and can be synthesized distributively. We establish that the DDC-Consensus algorithm converges to a stationary point of the nonconvex distributed optimization problem. The performance of the DDC-Consensus algorithm is evaluated via a simulation study to solve a nonconvex DC-regularized distributed least squares problem. The numerical results corroborate the efficacy of the proposed algorithm.

ABSTRACT. Dual formulations for optimization problems provide a new way to view the same problem, revealing its structure and bounding optimal solutions. A strong dual formulation constructs a problem that can be solved in place of or alongside the primal and converges on the same solution. In this paper we examine the general dual framework for nonlinear programs suggested by Everett and developed by Gould. This is leveraged to provide a novel strong dual formulation for general integer linear programming with qualitatively different structure from similar strong dual formulations. In particular, the dual problem optimizes three variables subject to a bounded, exponential number of constraints. The zero duality gap as well as small domain may prove useful in developing new techniques for solving integer linear programs.

ABSTRACT. Across many tasks in data science, it is necessary to estimate a signal from corrupted measurements. Perhaps the most pervasive and commonly used technique to address such problems is variational regularization. This consists of solving an optimization problem where one must minimize the sum of a data fidelity term and a regularizer, a penalty term chosen to encourage certain structure in solutions. While there is a suite of regularizers one could choose from, we currently lack a systematic understanding from a modeling perspective of what types of geometries should be preferred in a regularizer for a given data source. In particular, given a data distribution, what is the "optimal" regularizer for such data? Moreover, what aspects about the data govern whether the regularizer enjoys certain properties, such as convexity? Using ideas from star geometry, Brunn-Minkowski theory, and variational analysis, I show that we can characterize the optimal regularizer for a given distribution and establish conditions under which this optimal regularizer is convex. Moreover, I will describe results establishing the robustness of our approach, such as convergence of optimal regularizers with increasing sample size and statistical learning guarantees with applications to several classes of regularizers of interest.

ABSTRACT. Iterative algorithms are the workhorses of modern signal processing and statistical learning, and are widely used to fit complex models to random data. While the choice of an algorithm and its hyperparameters determines both the speed and fidelity of the learning pipeline, it is common for this choice to be made heuristically, either by expensive trial-and-error or by comparing upper bounds on convergence rates of various candidate algorithms. Motivated by these issues, we develop a principled framework that produces sharp, iterate-by-iterate characterizations ("state evolutions") of solution quality for complex iterative algorithms on several nonconvex model-fitting problems with random data. Such sharp predictions can provide precise separations between families of algorithms while also revealing nonstandard convergence phenomena. We will present the general framework and showcase it on some canonical models in statistical machine learning.

ABSTRACT. Kernel-based machine learning methods (such as support vector machines and kernel regression) can be viewed as a generalization of group decision-making, based on nearest neighbor labels in the feature space. For this reason, for many machine learning tasks in which data is separable over a known distance topology, kernel-based methods can learn extremely successfully, rivaling and sometimes surpassing that of neural networks.However, for scalability reasons, kernel-based methods are often not considered for very large dataset tasks; e.g. with $n$ training samples, the computational complexity is prohibitive in both training ($O(n^3)$) and inference ($O(n^2)$).

We consider a scalable approach to very large kernel SVMs by viewing the kernel values as weights in an undirected graph, and use an approximate method to solve this linear system using bounded memory and complexity costs. This approximates a kernel biased toward using nearest neighbor label information, which is a common approach in inference over very large graphs. Specifically, by leveraging the approximate page-rank method (APPR), we bound the set of nonzeros *of the intermediary variables* and demonstrate it does not scale with $n$, the size of the graph. Overall, this new method more gracefully showcases the transition between a graph-based majority vote method (cheap, low performance) and a full kernel SVM method (high performance, unscalable) and illustrates potential use in large-scale applications.

ABSTRACT. Feedback control typically relies on an estimate of the system state provided by an estimation scheme. These estimates, however, are always affected by errors that have non-negligible impacts on control performance. Various stabilizing and safety-critical control frameworks address this issue, but all require some characterization of the current estimation error to determine when to apply more or less conservative control inputs. Current methods of bounding these errors either take a very coarse worst-case bound or employ computationally expensive time-varying set-valued methods. In this talk we discuss new deterministic worst-case error bounds for a state estimation scheme for nonlinear systems. Crucially, the error bounds can be efficiently computed in real-time and shrink or grow depending on the current system behavior and the current measurement quality.

ABSTRACT. Self- and event-triggered control methods aim at minimizing the use of sensors and actuators. In this work, we consider the case of non-collocated sensors and actuators, and we address the problem of minimizing the number of sensor-to-actuator transmissions while satisfying some constraints on system states or input/output gain. For finite horizon problems, a linear time-varying controller with memory can be represented as a block-lower-triangular matrix. We show that the rank of this matrix exactly captures the minimum number of messages needed to be sent from the sensors to actuators to implement such a controller. Moreover, we introduce a novel matrix factorization called causal factorization that gives the required implementation. Finally, we show that the rank of the controller is the same as the rank of the Youla parameter, enabling the Youla parametrization (or analogous parametrizations) to be used to design the controller, which reduces the overall design problem into a rank minimization one over a convex set. Our results show that for the considered objective, when considering linear time-varying controllers with memory, controller implementation benefits from having some computation on the sensor side (encoder) and some on the actuator side (decoder) as opposed to being fully collocated with the sensor or actuator.

ABSTRACT. A set is strongly invariant for a dynamical system if all solutions from the set remain in the set. When the dynamics are somewhat irregular, for example given by non-Lipschitz differential equations or by differential inclusions, properties of the dynamics on the set are not enough to ensure strong invariance. Well-known conditions for strong invariance involve "subtangential" velocities, which can be expressed in terms of tangent cones to the set, and Lipschitz continuity of the possibly-multivalued dynamics.

This talk presents novel sufficient conditions for strong forward invariance of closed or compact sets, given in terms of Lyapunov-like functions. These functions are positive definite with respect to the invariant set, are reasonably smooth, and --- usually --- don't increase too fast. The setting is of differential inclusions, where uniqueness of solutions need not be ensured. Connections of these functions to usual Lyapunov functions, for differential inclusions and hybrid dynamics, and to barrier functions that exclude finite-time blow up of solutions, are explored in the proofs. The results come from joint work with A. Teel and R. Sanfelice.

ABSTRACT. We study topological entropy of a cascade interconnection of switched nonlinear subsystems. An upper bound is constructed for the entropy of the overall cascade system, in terms of an average of the matrix measures of Jacobian matrices of individual subsystems, weighted by the active rate of each mode. The upper bound is independent of the Jacobian matrices between different subsystems and is closely related to individual entropy bounds for subsystems. A numerical example is provided to illustrate the properties and relations of the overall and individual bounds for entropy.

ABSTRACT. Ensuring fair predictions across many distinct subpopulations in the training data can be prohibitive for large models. Recently, simple linear last layer retraining strategies, in combination with data augmentation methods such as upweighting, downsampling and mixup, have been shown to achieve state-of-the-art performance for worst-group accuracy, which quantifies accuracy for the least prevalent subpopulation. For linear last layer retraining and the abovementioned augmentations, we present the optimal worst-group accuracy when modeling the distribution of the latent representations (input to the last layer) as Gaussian for each subpopulation. We evaluate and verify our results for both synthetic and large publicly available datasets.

ABSTRACT. We highlight recent findings at the interface of information theory and differential privacy. First, we introduce a new differential privacy (DP) accountant called the saddle-point accountant (SPA). Our approach is inspired by the saddle-point method -- a ubiquitous numerical technique in statistics. We then overview results on optimizing differential privacy mechanisms when data is queried many times, i.e., the "large-composition" regime. We describe two new family of privacy mechanisms optimized for this regime: "Cactus Mechanisms," which are found by solving a convex optimization problem, and "Schrödinger mechanisms," which are analytical mechanisms optimized for the large composition and small sensitivity regime.

This is joint work with Wael Alghamdi (Harvard University), Juan Felipe Gomez (Harvard University), Shahab Asoodeh (McMaster University), Oliver Kosut (Arizona State University), and Lalitha Sankar (Arizona State University)

ABSTRACT. We consider the redundancy of the exact channel synthesis problem under an i.i.d. assumption. Existing results provide an upper bound on the unnormalized redundancy that is logarithmic in the block length. We show, via an improved scheme, that the logarithmic term can be halved for most channels and eliminated for all others. For full-support discrete memoryless channels, we show that this is the best possible.

ABSTRACT. This paper considers the task of estimating the principal eigenvector of a positive semi-definite matrix using the power method subjected to random row erasures at each iteration. This can be used to model applications where large matrix operations are distributed across multiple servers, some of which may fail to respond at each iteration. We analyze the simple strategy of only updating coordinates corresponding to non-erased rows, and demonstrate that, presuming a good initialization, the power method with erasures still converges exponentially fast to the principal eigenvector. The rate of convergence is governed by a modified spectral gap, which is a function of the original spectral gap and the fraction of erased rows. Accompanying numerical results validate our bounds, and demonstrate that, in certain regimes, our approach outperforms techniques such as coded computation and Oja's algorithm.

ABSTRACT. The Wasserstein distance, rooted in optimal transport (OT) theory, is a geometrically driven discrepancy measure between probability distributions, which features in a variety of machine learning tasks. However, it is highly sensitive to data poisoning attacks, where a potentially adversarial process manipulates training data prior to observation. To address this limitation, we study the problem of robust distribution estimation under the Wasserstein distance. Given $n$ samples from an unknown distribution $\mu$, of which $\epsilon n$ are adversarially corrupted, we seek an estimate for $\mu$ with minimal Wasserstein error.

We draw upon two frameworks from OT and robust statistics: partial OT (POT) and minimum distance estimation (MDE). We prove new structural properties for POT and use them to show that MDE under a partial Wasserstein distance achieves the minimax-optimal robust estimation risk in many settings. Along the way, we derive a novel dual form for POT that adds a sup-norm penalty to the classic Kantorovich dual for standard OT. Since the popular Wasserstein generative adversarial network (WGAN) framework implements Wasserstein MDE via Kantorovich duality, our penalized dual enables large-scale generative modeling with contaminated datasets via an elementary modification to WGAN. Numerical experiments demonstrating the efficacy of our approach in mitigating the impact of adversarial corruptions are provided. This poses our MDE under POT framework as a promising approach for both the theory and practice of robust statistics.

ABSTRACT. Traditional reinforcement learning from human feedback (RLHF) approaches relying on parametric models like the Bradley-Terry model fall short in capturing the intransitivity and irrationality in human preferences. Recent advancements suggest that directly working with preference probabilities can yield a more accurate reflection of human preferences, enabling more flexible and accurate language model alignment. In this paper, we propose a self-play- based method for language model alignment, which treats the problem as a constant-sum two-player game aimed at identifying the Nash equilibrium policy. Our approach, dubbed Self-Play Preference Optimization (SPPO), approximates the Nash equilibrium through iterative policy updates and enjoys a theoretical convergence guarantee. Our method can effectively increase the log-likelihood of the chosen response and decrease that of the rejected response, which cannot be trivially achieved by symmetric pairwise loss such as Direct Preference Optimization (DPO) and Identity Preference Optimization (IPO). In our experiments, using only 60k prompts (without responses) from the UltraFeedback dataset and without any prompt augmentation, by leveraging a pre-trained preference model PairRM with only 0.4B parameters, SPPO can obtain a model from fine-tuning Mistral-7B-Instruct-v0.2 that achieves the state-of-the-art length- controlled win-rate of 28.53% against GPT-4-Turbo on AlpacaEval 2.0. It also outperforms the (iterative) DPO and IPO on MT-Bench and the Open LLM Leaderboard. Starting from a stronger base model Llama-3-8B-Instruct, we are able to achieve a length-controlled win rate of 38.77%. Notably, the strong performance of SPPO is achieved without additional external supervision (e.g., responses, preferences, etc.) from GPT-4 or other stronger language models.

ABSTRACT. Large foundation models pretrained on raw web-scale data are not readily deployable without additional step of extensive alignment to human preferences. Such alignment is typically done by collecting large amounts of pairwise comparisons from humans ("Do you prefer output A or B?") and learning a reward model or a policy with the Bradley-Terry-Luce (BTL) model as a proxy for a human's underlying implicit preferences. These methods generally suffer from assuming a universal preference shared by all humans, which lacks the flexibility of adapting to plurality of opinions and preferences. In this work, we propose PAL, a framework to model human preference complementary to existing pretraining strategies, which incorporates plurality from the ground up. We propose using the ideal point model as a lens to view alignment using preference comparisons. Together with our novel reformulation and using mixture modeling, our framework captures the plurality of population preferences while simultaneously learning a common preference latent space across different preferences, which can few-shot generalize to new, unseen users. Our approach enables us to use the penultimate-layer representation of large foundation models and simple MLP layers to learn reward functions that are on-par with the existing large state-of-the-art reward models, thereby enhancing efficiency of reward modeling significantly. We show that PAL achieves competitive reward model accuracy compared to strong baselines on 1) Language models with Summary dataset ; 2) Image Generative models with Pick-a-Pic dataset ; 3) A new semisynthetic heterogeneous dataset generated using Anthropic Personas. Finally, our experiments also highlight the shortcoming of current preference datasets that are created using rigid rubrics which wash away heterogeneity, and call for more nuanced data collection approaches.

ABSTRACT. The proliferation of harmful content and misinformation on social networks necessitates content moderation policies to maintain platform health. One such policy is shadow banning, which limits content visibility. The danger of shadow banning is that it can be misused by social media platforms to manipulate opinions. Here we present an optimization based approach to shadow banning that can shape opinions into a desired distribution and scale to large networks. Simulations on real network topologies show that our shadow banning policies can shift opinions and increase or decrease opinion polarization. We find that if one shadow bans with the aim of shifting opinions in a certain direction, the resulting shadow banning policy can appear neutral. This shows the potential for social media platforms to misuse shadow banning without being detected. Our results demonstrate the power and danger of shadow banning for opinion manipulation in social networks.

ABSTRACT. Motivated by Q-learning, we study nonsmooth contractive stochastic approximation (SA) with constant stepsize. We establish the weak convergence of the iterates to a stationary limit distribution in Wasserstein distance. Furthermore, we propose a prelimit coupling technique for establishing steady-state convergence and characterize the limit of the stationary distribution as the stepsize goes to zero. As an intermediate step, we show that the general nonsmooth contractive SA is asymptotically equivalent to the contractive SA with only additive Gaussian noise. This universal result is of independent interest and can be a powerful tool for analyzing SA. By steady-state convergence result, we derive that the asymptotic bias of nonsmooth SA is proportional to the square root of the stepsize, which stands in sharp contrast to smooth SA. This bias characterization allows for the use of Richardson-Romberg extrapolation for bias reduction in nonsmooth SA.

ABSTRACT. Linear feature extraction at the presence of nonlinear dependencies among the data is a fundamental challenge in unsupervised learning. We propose using a Gram-Schmidt (GS) type orthogonalization process over function spaces in order to detect and remove redundant dimensions. Specifically, by applying the GS process over a family of functions which presumably captures the nonlinear dependencies in the data, we construct a series of covariance matrices that can either be used to identify new large-variance directions, or to remove those dependencies from the principal components. In the former case, we provide information-theoretic guarantees in terms of entropy reduction. In the latter, we prove that under certain assumptions the resulting algorithms detect and remove nonlinear dependencies whenever those dependencies lie in the linear span of the chosen function family. Both proposed methods extract linear features from the data while removing nonlinear redundancies. We provide simulation results on synthetic and real-world datasets which show improved performance over state-of-the-art feature extraction algorithms.

ABSTRACT. In postselected discrimination of a quantum state when n copies of the states are available, the error can be made arbitrary small by designing appropriate measurements. In this paper, we investigate usability of such error-minimizing measurements. We first characterize such error-minimizing joint measurements on n-copies of the state. We show that as far as error is concerned, minimum error can be obtained by performing a set of separate measurements on individual copies, thus removing the need to perform a joint measurement. We then characterize the acceptance of these measurements that represent the probability that the decision is not rejected. We derive an upper bound on the acceptance and show that it decreases exponentially with n. This indicates that acceptance in such error minimizing measurements vanishes with n. We conclude that although such a measurement achieves vanishing error as n tends to infinity, the probability that it makes a decision also vanishes, which limits the utility of these measurements for postselected state discrimination. In the end, we have derived error exponents for finite acceptance and shown that the benefit of postselection vanishes in asymmetric case and reduces in symmetric case.

ABSTRACT. This paper aims to outline the effectiveness of modern universal gate quantum computers when utilizing dif- ferent configurations to solve the B-SAT(Boolean Satisfiability) problem. The quantum computing experiments are performed using Grover’s Search algorithm to find a valid solution. The experiments are performed under different variations to demon- strate their effects on the results. Changing the number of shots, qubit mapping, and using a different quantum processor are all among the experimental variables. The study also branches into a dedicated experiment highlighting a peculiar behavior that IBM quantum processors exhibit when running circuits with a certain number of shots.

ABSTRACT. In this paper we study $\gamma$ partial correction over a $t$-user arbitrarily varying multiple-access channel (AV-MAC). We first present necessary channel conditions for the $\gamma$ partially correcting authentication capacity region to have nonempty interior. We then give a block length extension scheme which preserves positive rate tuples from a short code with zero probability of $\gamma$ partial correction error, noting that the flexibility of $\gamma$ partial correction prevents pure codeword concatenation from being successful. Finally, we offer a case study of a particular AV-MAC satisfying the necessary conditions for partial correction.

ABSTRACT. A ternary barrier channel is a non-symmetric error model defined previously to address emerging applications. Conveniently, it admits a code-construction method comprising two binary constituent codes. In this paper we propose a decoding algorithm that decodes the two constituent codes jointly by message passing on a graph representing the two codes' parity-check constraints. The messages exchanged by the algorithm are likelihoods calculated from incoming messages, and they are derived in the paper based on the exact dependence between the binary values of the two codewords. Simulation results demonstrate that the proposed decoder has superior error-rate performance compared to prior decoding approaches.

ABSTRACT. Recently, Lin and Pryadko presented the quantum two-block group algebra codes, a generalization of bicycle codes obtained from Cayley graphs of non-Abelian groups. We notice that their construction is naturally suitable to obtain a quantum equivalent of the well-known classical Margulis code. In this paper, we first present an alternative description of the two-block group algebra codes using the left-right Cayley complex; then, we show how to modify the construction of Margulis to get a two-block algebra code. Finally, we construct several quantum Margulis codes and evaluate their performance with numerical simulations.

ABSTRACT. Electrical power systems are transitioning from fuel-based generation to renewable generation and transmission interfaced by power electronics. We first review the so-called dual-port grid-forming control paradigm that (i) subsumes common functions of grid-forming and grid-following control into a simple controller, and (ii) admits insightful end-to-end stability conditions. While these results cover a wide range of network topologies, emerging technologies, and legacy technologies, they crucially hinge on a particular control implementation and resource dynamics. Next, we discuss recent results that characterize a wider class of dynamics to which our end-to-end stability conditions apply independent of network topology.

ABSTRACT. Positive- and negative-sequence equivalent-circuit models are put forth to capture the operation of grid-forming (GFM) inverters in unbalanced steady-state operating conditions acknowledging the impact of current limiting. The particular control architecture examined adopts droop control (for primary control), nested inner-current and outer-voltage control (in the stationary reference frame), and it is adaptable to two different types of current limiting (current-reference saturation and virtual-impedance limiting). We anticipate the proposed models to be of interest in modeling, analysis, and simulation of GFM inverters in unbalanced settings that may arise, e.g., in the face of faults. Validation of the equivalent-circuit models is pursued via comparison with full-order electromagnetic-transient (EMT) simulations for representative balanced and unbalanced faults.

ABSTRACT. We describe a hierarchical feedback-based optimization control architecture for coordination of Distributed Energy Resources (DERs) in Distribution Networks (DNs). At a high level, the proposed control system enables the DN, in aggregate, to quickly respond to power set-point requests from the transmission level while maintaining local DN constraints. More granularly, the design achieves this while allowing for multiple independently-managed areas within the DN to optimize their local resources and maintain privacy over local measurements and model information; the only required information sharing is set-point passing between physically adjacent areas within the DN. Theoretical and extensive simulation results support the proposal. We then describe how the proposal may be seamlessly integrated into recently designed estimation-based fast frequency controllers, providing a systematic path towards transmission-distribution coordination for the provision of ancillary services.

ABSTRACT. With the increasing adoption of inverter-based resources (IBRs) in power systems, oscillation instability has become a significant challenge for system operators worldwide. This paper analyzes the nonlinear behavior associated with the oscillatory dynamics of grid-following (GFL) inverters connected to the grid, using the theory of Hopf bifurcation. We focus on understanding the impacts of parameter variations on the geometry of the Hopf bifurcation. The normal vectors to the Hopf bifurcation hypersurface are calculated after analytically restructuring the DAE model into an ODE for the GFL inverter. These normal vectors are then used to estimate the shortest distance to bifurcation in the parameter space and assess the sensitivity of the stability margin to parameters. This information guides the identification of the most influential parameters that affect stability and adapting controllable parameters to enhance the stability margin. The method is demonstrated using a single-inverter infinite-bus system. It is shown that the normal vector is effective in estimating the stability margin, and results indicate that the proportional gains in GFL control, in particular the one associated with the current control loop, are most effective in improving the stability margin.

ABSTRACT. This talk will present an energy function-based method for large-signal stability assessment of grid-forming (GFM) and grid-following (GFL) inverter based resources (IBRs) leveraging equivalent-circuit representations of all involved control- and physical-layer dynamics. A variety of control architectures are featured in the modeling and analysis framework. A composite energy function for the IBR is obtained by summing up individual energy contributions inferred from the circuit representation. The approach can readily be generalized to different primary controls, output-filter arrangements, and current limiters since it is based on a circuit-theoretic foundation. Numerical simulations will be presented to validate the efficacy of the approach in estimating the critical clearing time following a large-signal disturbance.

ABSTRACT. In this work, we ask what the minimum data-rate is for a possibly nonlinear control law acting on a linear system to emulate the closed-loop behaviour of a desired linear control law. This result gives an implicit estimate for the information flow in the feedback path of the closed-loop linear system. We formally introduce the notion ofemulation and control law, and we present a data-rate theorem. Remarkably, we note that the minimum data-rate varies discontinuously with the parameters of the open and closed-loop systems. This feature is new since the usual data-rate theorem, which only requires stabilization instead of emulation, gives a continuously varying minimum data-rate.

ABSTRACT. Multistationarity -- the existence of multiple equilibrium points -- is a common phenomenon in dynamical systems from a variety of fields, including neuroscience, opinion dynamics, systems biology, and power systems. A recently proposed generalization of contraction theory, called $k$-contraction, is a promising approach for analyzing the asymptotic behaviour of multistationary systems. In particular, all bounded trajectories of a time-invariant 2-contracting system converge to an equilibrium point, but the system may have multiple equilibrium points where more than one is locally stable. An important challenge is to study $k$-contraction in large-scale interconnected systems. Inspired by a recent small-gain theorem for 2-contraction by Angeli et al., we derive a new sufficient condition for 2-contraction in a feedback interconnection of two nonlinear dynamical systems. Our condition is based on combining the representation of multiplicative [additive] compound matrices using Kronecker products [sums] and a hierarchical approach for proving standard contraction. We demonstrate our results by proving a simple sufficient condition for $2$-contraction in a network of FitzHugh-Nagumo neurons.

ABSTRACT. The talk addresses the problem of remote robust state estimation. The remote observer is assumed to receive its data over a communication channel with finite bit-rate capacity. A conventional approach to deal with the communication constraints is to equip the sensor (sender) and the receiver with the system model (digital twin), while transmitting the deviations of the true states from those of the model. This approach requires good knowledge of the model and may not be realistic in applications where the model is known with some accuracy. In the talk, we assume that the model of the true system is uncertain and satisfies an incremental dissipation inequality in the context of incremental input-to-state stability. Under this assumption, we define a notion of remote robust observability via communication constraints and provide a tractable estimate of the required data rate. This estimate can be evaluated using conventional LMI techniques. An example based on the Lozi chaotic map is presented. The data rate estimate for this example is proven to be tight.

ABSTRACT. Reachability analysis is a fundamental problem in control theory, which examines how a system’s trajectories evolve over time. Reachability analysis has a long and rich history, with numerous techniques developed in the literature to estimate a system’s reachable sets. However, many of these classical methods are computationally intensive, and there is a growing need for fast and scalable reachability techniques in various control applications. In this talk, we review two computationally efficient approaches for reachability analysis: contraction-based reachability and monotone-based reachability. Using tools and techniques from non-Euclidean contraction theory, we establish a theoretical connection between these two frameworks and compare their accuracy. We then utilize this result to study the reachability of fixed-point equations.

ABSTRACT. We study the problem of Symmetric Private Information Retrieval (SPIR) in a scenario involving $L$ non-replicated and colluding servers, and $M$ independent files. In this setting, communication takes place through a noisy multiple-access channel and a noiseless public channel. %, each split into $L$ segments, are stored across different servers. The client must retrieve one of the $M$ files such that $(i)$ the client's choice must not be revealed to any server; $(ii)$ the client must not learn any information about non-selected files. Our primary contribution is showing an achievable rate for this SPIR problem, and showing that positive rates can still be achieved even when all servers collude, without requiring common randomness shared among servers. The key idea involves first proving an achievable rate for the special case with $M=2$ files. Then, we iteratively apply our coding scheme $M-1$ times to generalize our achievable rate to $M>2$ files. Furthermore, by distributing files across multiple servers, we demonstrate on an example that our derived achievable rate can outperform single-server settings.

ABSTRACT. Joint communication and sensing (JCAS) is one of the promising technologies envisioned for future generations of wireless systems. Several attempts have been made to formulate the problem from an information-theoretic perspective, assuming underlying discrete memoryless channels and leveraging classical rate-distortion trade-offs. However, communication channels often have memory and strategies to improve data rates with the help of sensing in such scenarios is not yet well understood. In this paper, we consider a generic system model for joint communication and sensing, and present a novel and greedy-type strategy to achieve optimal average rate, assuming a channel model with memory. In particular, in the considered channel model, the channel state follows a finite state Markov chain. We also characterize how the solutions to communication and sensing problems complement each other in such scenarios. To the best of authors' knowledge, this is the first attempt towards understanding rate-optimized strategies in JCAS systems involving channels with memory from a communication-theoretic perspective.

ABSTRACT. Contraction coefficients for Kullback-Leibler (KL) divergence are channel-dependent constants that are used to sharpen data processing inequalities for KL divergence into strong data processing inequalities. In this work, we present a method to analytically compute the KL contraction coefficients of product $q$-ary symmetric channels. Although such contraction coefficients have many applications in information theory as well as probability and statistics more broadly, deriving exact values is considered to be challenging for complex channels such as product channels. While recent discoveries have reduced the search space of the optimization problems defining contraction coefficients significantly, the problem is still far from trivial. We find that the symmetry inherent in channels such as the $q$-ary symmetric channel allows for further simplification, making an exact closed-form expression for contraction coefficients for KL divergence possible to derive. We begin by obtaining the KL contraction coefficients of product binary symmetric channels, and then generalize our results to larger alphabets. Our methods are not specific to product $q$-ary symmetric channels and can be used for wider classes of channels that satisfy certain symmetry properties.

ABSTRACT. Existing bounds on the maximum channel coding rate achievable at finite block lengths are not always meaningful at moderate lengths and for low-noise channels, even when the channel model is simple. We offer a new framework for deriving achievability and converse bounds, along with a simple and accurate approximation, based on guesswork and the GRAND family of decoding algorithms. This approach is theoretically applicable to any channel model; we use it to produce implicit but computable bounds for the binary symmetric channel and the binary additive white Gaussian noise channel. Our approach for the latter is based on a 1-bit quantization of the soft information and offers quantitative insight into the marginal value of this amount of information compared to hard decision and full soft information decoding. For moderate lengths and low-noise settings, our results for both channel models improve on the state-of-the-art.

ABSTRACT. We present an interpretation of Deepcode, a learned feedback code that showcases higher-order error correction relative to an earlier interpretable model. By interpretation, we mean succinct analytical encoder and decoder expressions (albeit with learned parameters) in which the role of feedback in achieving error correction is easy to understand. By higher-order, we mean that longer sequences of large noise values are acted upon by the encoder (which has access to these through the feedback) and used in error correction at the decoder in a two-stage decoding process.

ABSTRACT. Quantum computing hardware is progressing at a rapid pace. This progress brings increasing interest in quantum algorithms that can leverage the capabilities of this hardware, including recently emerging features such as mid-circuit measurements. In this talk, I will consider how mid-circuit measurements could open the prospect of feedback-based quantum algorithms (FQAs) leveraging real-time feedback. I will begin with a review of FQAs, including a discussion of their foundations in quantum Lyapunov control theory. I will then present recent work exploring how mid-circuit measurements could enable real-time extensions of FQAs, by drawing on other branches of control theory and reinforcement learning. A variety of numerical illustrations will be shown that investigate the performance of these real-time feedback-based quantum algorithms towards solving problems in optimization and quantum simulation. Sandia National Labs is managed and operated by NTESS under DOE NNSA contract DENA0003525. SAND2024-09254A.

ABSTRACT. Numerical optimization problems abound across the quantum information science landscape. General-purpose numerical optimization methods often fail to identify high-quality solutions in a reasonable time. This talk highlights how newly developed specialized optimization methods can exploit problem structure to more efficiently solve some QIS problem instances. This talk provides an overview of these methods and highlights their application to problems in optimizing circuit synthesis, entanglement, and quantum Fisher information. Hopefully, these examples will spark discussions for future collaborations.

ABSTRACT. Geometrically local quantum codes, comprised of qubits and checks embedded in RD with local check operators, have been a subject of significant interest. A key challenge is identifying the optimal code construction that maximizes both dimension and distance. Recent advancements have produced several constructions, but these either depend on specific good quantum low-density parity-check (qLDPC) codes or are limited to three dimensions. In this work, we introduce a construction that can transform any good qLDPC code into an optimal geometrically local quantum code. Our approach hinges on a novel procedure that extracts a two-dimensional structure from an arbitrary three-term chain complex. We expect that this procedure will find broader applications in areas such as weight reduction and the geometric realization of chain complexes.

ABSTRACT. We present the classically assisted non-orthogonal eigensolver (CANOE) algorithm. CANOE utilizes a wavefunction that is a superposition of both classically stored and quantumly stored wavefunctions. By using the techniques of non-orthogonal configuration interaction (NOCI), the non-orthogonal variational quantum eigensolver (NOVQE), and quantum Kyrlov methods, we construct a generalized eigenvalue problem in the combined space of the non-orthogonal classical and quantum wavefunctions. The tools of classical shadows allows us to efficiently measure the necessary overlaps between the small number of quantum and large classical wavefunctions to construct the generalized eigenvalue problem. We provide initial results on ground state estimation problems in quantum chemistry, a discussion of the resource costs for larger systems, and provide an outlook for CANOE.

ABSTRACT. The universality of 2-qubit unitary transformations is one of the cornerstones of quantum computing, with many applications and implications extending beyond this field. However, it has been shown that this universality does not hold in the presence of global continuous symmetries such as U(1) and SU(2): generic symmetric unitaries on a composite system cannot be implemented, even approximately, using local symmetric unitaries on the subsystems. Further investigations have revealed that the restrictions imposed by the locality of interactions vary significantly for different symmetry groups. While there is currently no comprehensive theory for general symmetry groups, recent work has developed the theory of symmetric quantum circuits for the case of Abelian symmetries.

In this talk, I will first give an overview of this ongoing project. In the second part, I will focus on the special case of energy-conserving unitaries, also known as Hamming-weight conserving unitaries, i.e., those that conserve the sum of Pauli Z operators on all qubits. I will present explicit circuit synthesis methods for realizing all such unitaries with XY interaction alone, using 2 ancilla qubits. In particular, I will discuss the properties of circuits containing only the square-root-of-iSWAP gates.

ABSTRACT. A non-local quantum game involves a referee (Alice) playing against two or more players (Bob and Charlie) whose goal is to meet a joint condition to win the game. The players can devise a joint strategy in preparation for the game but not communicate once the game starts, which makes the game non-local. Communication during the game is only between the referee and the players. Optimal strategies often involve shared entanglement, and their success is limited by entanglement monogamy. This talk focuses on hidden coset guessing, a recently proposed game concerning unclonable cryptography. We know that the probability of Bob and Charlie winning decreases as the number of game rounds increases. This talk derives the winning probability and optimal strategies for some game variants.

ABSTRACT. Schrödinger bridge--a stochastic dynamical generalization of optimal mass transport--exhibits a learning-control duality. Viewed as a stochastic control problem, the Schrödinger bridge finds an optimal control policy that steers a given joint state statistics to another while minimizing the total control effort subject to controlled diffusion and deadline constraints. Viewed as a stochastic learning problem, the Schrödinger bridge finds the most-likely distribution-valued trajectory connecting endpoint distributional observations, i.e., solves the two point boundary-constrained maximum likelihood problem over the manifold of probability distributions. Recent works have shown that solving the Schrödinger bridge problem with state cost requires finding the Markov kernel associated with a reaction-diffusion PDE where the state cost appears as a state-dependent reaction rate. We explain how ideas from Weyl calculus in quantum mechanics, specifically the Weyl operator and the Weyl symbol, can help determine such Markov kernels. We illustrate these ideas by explicitly finding the Markov kernel for the case of quadratic state cost via Weyl calculus, recovering our earlier results but avoiding tedious computation with Hermite polynomials.

ABSTRACT. We introduce a class of generative models that unifies flows and diffusions. These models are constructed through the use of a continuous-time stochastic process known as a stochastic interpolant, which bridges two arbitrary probability densities exactly in finite time. We show that the time-dependent density of the stochastic interpolant satisfies a first-order transport equation, as well as an infinite family of forward and backward Fokker-Planck equations with tunable diffusion coefficients. This viewpoint leads to both deterministic and stochastic generative models based on ordinary or stochastic differential equations with an adjustable level of noise that can be optimized to maximize performance. We discuss how the resulting drift functions can be characterized variationally and learned efficiently over flexible parametric classes such as neural networks. We highlight the advantages of our formalism and the tradeoffs between deterministic and stochastic sampling with numerical examples in image generation, image inpainting, probabilistic forecasting of dynamical systems, and few-step sampling.

ABSTRACT. We study the global convergence of a Fisher-Rao policy gradient flow for infinite-horizon entropy-regularised Markov decision processes with Polish state and action space. The flow is a continuous-time analogue of a policy mirror descent method. We establish the global well-posedness of the gradient flow and demonstrate its exponential convergence to the optimal policy. Moreover, we prove the flow is stable with respect to gradient evaluation, offering insights into the performance of a natural policy gradient flow with log-linear policy parameterisation. To overcome challenges stemming from the lack of the convexity of the objective function and the discontinuity arising from the entropy regulariser, we leverage the performance difference lemma and the duality relationship between the gradient and mirror descent flows.

ABSTRACT. This paper is concerned with the problem of nonlinear filtering, i.e., computing the conditional distribution of the state of a stochastic dynamical system given a history of noisy partial observations. Conventional sequential importance resampling (SIR) particle filters suffer from fundamental limitations, in scenarios involving degenerate likelihoods or high-dimensional states, due to the weight degeneracy issue. In this paper, we explore an alternative method, which is based on estimating the Brenier optimal transport (OT) map from the current prior distribution of the state to the posterior distribution at the next time step. Unlike SIR particle filters, the OT formulation does not require the analytical form of the likelihood. Moreover, it allows us to harness the approximation power of neural networks to model complex and multi-modal distributions and employ stochastic optimization algorithms to enhance scalability. Extensive numerical experiments are presented that compare the OT method to the SIR particle filter and the ensemble Kalman filter, evaluating the performance in terms of sample efficiency, high-dimensional scalability, and the ability to capture complex and multi-modal distributions.

ABSTRACT. Nonlinear balanced truncation is a model order reduction technique that reduces the dimension of nonlinear systems on nonlinear manifolds and preserves either open- or closed-loop observability and controllability aspects of the nonlinear system. Three computational challenges have so far prevented its deployment on large-scale systems: (a) the computation of Hamilton-Jacobi-(Bellman) equations that are needed for characterization of controllability and observability aspects, (b) a scalable strategy to compute the nonlinear coordinate transformation to balance the system, and (c) efficient model reduction and reduced-order model (ROM) simulation on the resulting nonlinear balanced manifolds. We present a novel unifying and scalable approach to balanced truncation for large-scale control-affine nonlinear systems that consider a Taylor-series based approach to solve both a class of parametrized Hamilton-Jacobi-Bellman equations as well as the balancing transforms. This specific tensor structure for the coefficients of the Taylor series (tensors themselves) allows for scalability up to thousands of states. The talk will illustrate the strength and scalability of the algorithm on several semi-discretized nonlinear partial differential equations, including a nonlinear heat equation, vibrating beams, Burgers' equation and the Kuramoto-Sivashinsky equation.

ABSTRACT. In this paper, we propose a novel solution for sampling from a continuously valued multi-variate probability distribution, either explicitly known (up to a normalization factor) or represented via ground truth samples. Our method initiates the target distribution from a delta function positioned at the origin of the state space and optimally grows it. We frame the problem as a stochastic optimal control challenge of the path-integral type, where the cost-to-go function includes a quadratic term in the control, a quadratic term in the state vector, and a terminal term. This formulation allows for an analytical solution and leads to the development of several sampling algorithms, both with and without the use of neural networks. We compare these algorithms to existing state-of-the-art methods in terms of accuracy and complexity, demonstrating their performance on benchmark examples of varying sizes.

ABSTRACT. We present a new approach to solving MDPs, reward balancing, which avoids direct computation of the value function and instead seeks to progressively equalize rewards associated with different states. While reward balancing achieves identical geometric convergence rate as value iteration in the worst case, its convergence rate is faster on MDPs whose transition matrices have positive diagonals. We discuss geometric interpretations of this method as well sample complexities associated with using reward balancing to solve unknown MDPs through trial and error.

ABSTRACT. We consider the problem of estimating the asymptotic variance of a function defined on a Markov chain, an important step for statistical inference of the stationary mean. We design the first recursive estimator that requires O(1) computation at each step, does not require storing any historical samples or any prior knowledge of run-length, and has optimal O(1/n) rate of convergence for the mean-squared error (MSE) with provable finite sample guarantees. Here, n refers to the total number of samples generated. The previously best-known rate of convergence in MSE was O(log n/n), achieved by jackknifed estimators, which also do not enjoy these other desirable properties. Our estimator is based on linear stochastic approximation of an equivalent formulation of the asymptotic variance in terms of the solution of the Poisson equation.

We generalize our estimator in several directions, including estimating the covariance matrix for vector-valued functions, estimating the stationary variance of a Markov chain, and approximately estimating the asymptotic variance in settings where the state space of the underlying Markov chain is large. We also show applications of our estimator in average reward reinforcement learning (RL), where we work with asymptotic variance as a risk measure to model safety-critical applications. We design a temporal-difference type algorithm tailored for policy evaluation in this context. We consider both the tabular and linear function approximation settings. Our work paves the way for developing actor-critic style algorithms for variance-constrained RL.

ABSTRACT. This paper addresses the minimization of (locally strongly) convex, locally smooth functions over a network of agents without a centralized server. Existing decentralized algorithms require knowledge of problem and network parameters, such as the Lipschitz constant of the global gradient and/or network connectivity, for hyperparameter tuning. Agents usually cannot access this information, leading to conservative selections and slow convergence or divergence. This paper introduces a decentralized algorithm that eliminates the need for specific parameter tuning. Our approach employs an operator splitting technique with a novel variable metric, enabling a local backtracking line-search to adaptively select the stepsize without global information or extensive communications. This results in favorable convergence guarantees and dependence on optimization and network parameters compared to existing nonadaptive methods. Notably, our method is the first adaptive decentralized algorithm that achieves linear convergence for (locally) strongly convex (locally) smooth functions. Numerical experiments on machine learning problems demonstrate superior performance in convergence speed and scalability.

ABSTRACT. Networked Markov Decision Processes (MDPs) pose a significant challenge to efficient learning due to the exponential growth of the overall state-action space with the number of agents. Recent works have attempted to address this by leveraging the locally decaying structure of the dynamics to develop localized policies that depend only on a truncated portion of the state-action graph. However, these approaches are limited to finite state-action spaces, leaving the more realistic and challenging scenario of large or continuous state-action spaces in networked MDPs as an open problem. In this work, we leverage recent advances in spectral representation of Q-value functions, which have enabled efficient learning for single-agent MDPs, to derive a networked version of a localized spectral representation for the Q-function of each agent, utilizing the exponential decay structure of network dynamics. Building on these local spectral representations, we design efficient algorithms for networked MDPS whose state-action space can be large-size or even continuous. We illustrate the efficacy of our approach with a series of representative experiments.

ABSTRACT. We consider the problem of classification with a peer-to-peer network of heterogeneous and partially informative agents, each receiving local data generated by an underlying true class, and equipped with a classifier that can only distinguish between a subset of the entire set of classes. We propose an iterative algorithm that uses the posterior probabilities of the local classifier and recursively updates each agent's local belief on all the possible classes, based on its local signals and belief information from its neighbors. We then adopt a distributed min-rule to update each agent’s global belief and enable learning of the true class for all agents. We show that under certain assumptions, the beliefs on the true class converge to 1 asymptotically almost surely. We provide the asymptotic convergence rate and demonstrate the performance of our algorithm through simulation with image data.

ABSTRACT. Barrier functions constitute an effective tool for assessing and enforcing safety-critical constraints on dynamical systems. To this end, one is required to find a function $h$ that satisfies a Lyapunov-like differential condition, thereby ensuring the invariance of its zero super-level set $h_{\ge 0}$. This methodology, however, does not prescribe a general method for finding the function $h$ that satisfies such differential conditions, which, in general, can be a daunting task. In this paper, we seek to overcome this limitation by developing a generalized barrier condition that makes the search for $h$ easier. We do this in two steps. First, we develop integral barrier conditions that reveal equivalent asymptotic behavior to the differential ones, but without requiring differentiability of $h$. Subsequently, we further replace the stringent invariance requirement on $h\geq0$ with a more flexible concept known as recurrence. A set is ($\tau$-)recurrent if every trajectory that starts in the set returns to it (within $\tau$ seconds) infinitely often. We show that, under mild conditions, a simple sign distance function can satisfy our relaxed condition and that the ($\tau$-)recurrence of the super-level set $h_{\geq 0}$ is sufficient to guarantee the system's safety.

ABSTRACT. In this article, we introduce an adaptive online model update algorithm designed for predictive control applications in networked systems, particularly focusing on power distribution systems. Unlike traditional methods that depend on historical data for offline model identification, our approach utilizes real-time data for continuous model updates. This method integrates seamlessly with existing online control and optimization algorithms and provides timely updates in response to real-time changes. This methodology offers significant advantages, including a reduction in the communication network bandwidth requirements by minimizing the data exchanged at each iteration and enabling the model to adapt after disturbances. Furthermore, our algorithm is tailored for non-linear convex models, enhancing its applicability to practical scenarios. The efficacy of the proposed method is validated through a numerical study, demonstrating improved control performance using a synthetic IEEE test case.

ABSTRACT. We study the problem of mixed $H_2 / H_\infty$ control in the infinite-horizon setting. We identify the optimal causal controller that minimizes the $\Htwo$-cost of the closed-loop system subject to an $H_\infty$ constraint. Megretski proved that the optimal mixed $H_2 / H_\infty$ controller is non-rational whenever the constraint is active, without giving an explicit construction of the controller. In this work, we provide the first exact closed-form solution to the infinite-horizon mixed $H_2 / H_\infty$ control in the frequency domain. While the optimal controller is non-rational, our formulation provides a finite-dimensional parameterization of the optimal controller. Leveraging this fact, we introduce an efficient iterative algorithm that finds the optimal causal controller in the frequency domain. We show that this algorithm is convergent when the system is scalar and present numerical evidence for exponential convergence of the proposed algorithm. Finally, we show how to find the best (in $H_\infty$ norm) fixed-order rational approximations of the optimal mixed $H_2 / H_\infty$ controller, and study its performance.

ABSTRACT. In this work, we present an explicit solution to the distributed H2 optimal control problem. It's assumed that the plant and the controller are interconnected dynamic systems, interacting over the same directed network with reliable links, which satisfies the quadratic invariance condition. The resulting control structure involves both sparsity and delays.

We provide an algorithm that uses the solution of the discrete-time algebraic Riccati Equations (DARE) for standard H2 optimal controller to initiate the Youla Paramterization and cast the distributed H2 problem into a convex model matching problem. We find the optimal Youla parameter that parameterized the optimal distributed \H2 controller in finite computations by solving an extra discrete-time algebraic Riccati Equations (DARE) associated with the vectorized closed loop maps compared to standard centralized \(\mathcal{H}_2\) problems. Employing the backward recursion of Riccati equations, we can find the optimal solution explicitly. Besides the algorithm, we also provide a novel theorem that enables us to check the existence of stabilizing controllers in the wanted structure. This theorem can be useful for generic network distributed control problems other than \(\mathcal{H}_2\).

Finally, we validate this methodology on a 4-car platoon system and compare it to the optimal centralized controller, the optimal delay-free structured controller, and a decentralized PID controller.

ABSTRACT. In this paper, we present a novel hypothesis testing framework to model an attacker’s decision-making during the reconnaissance phase and employ the framework to design strategic deception strategies that can provide the attacker with optimally falsified information structures. We characterize the criterion for such structures to “blind” the attacker, i.e., to completely confuse it, as well as the optimal falsification strategy when the attacker cannot be blinded. We also characterize optimal information acquisition costs that can be imposed on the attacker to maximally “sludge” its decision-making process during the reconnaissance phase. Numerical results have been presented to gain important insights into the developed strategies.

ABSTRACT. Information density and its exponential form, known as lift, play a central role in information privacy leakage measures. $\alpha$-lift is the power-mean of lift, which is tunable between the worst-case measure max-lift ($\alpha=\infty$) and more relaxed versions ($\alpha<\infty$). This paper investigates the optimization problem of the privacy-utility tradeoff (PUT) where $\alpha$-lift and mutual information are privacy and utility measures, respectively. Due to the nonlinear nature of $\alpha$-lift for $\alpha<\infty$, finding the optimal solution is challenging. Therefore, we propose a heuristic algorithm to estimate the optimal utility for each value of $\alpha$, inspired by the optimal solution for $\alpha=\infty$ and the convexity of $\alpha$-lift with respect to the lift, which we prove. The numerical results show the superiority of the algorithm compared to a previous algorithm in the literature and indicate the effective range of $\alpha$ and privacy budget $\eps$ with good PUT performance.

ABSTRACT. This paper presents a framework for designing Private Information Retrieval (PIR) schemes in settings where the data is stored in a coded form (using MDS codes) and in the presence of collusion between servers. The framework is based on polynomial codes and provides a simple and efficient way to construct PIR schemes for several PIR problems and a broad range of system parameters.

We prove that our framework has the best-known download rate and achieves asymptotic capability for strictly linear PIR schemes. One of the distinguishing features of this framework is its simplicity and ease of implementation, making it an attractive choice for practical retrieval schemes. We demonstrate the flexibility of our framework by demonstrating its use in solving private linear computation problems.

ABSTRACT. We study the trade-off between communication rate and privacy for distributed batch matrix multiplication of two independent sequences of matrices A and B with uniformly distributed entries. In our setting, B is publicly accessible by all the servers while A must remain private. The user is interested in finding the product AB with the responses from the k fastest servers. For a given parameter α ∈ [0, 1], our privacy constraint must ensure that any set of ℓ colluding servers cannot learn more than a fraction α of A. Additionally, we study the trade-off between the amount of local randomness needed at the encoder and privacy, which to the best of our knowledge no previous work has characterized. Finally, we establish the optimal trade-offs when the matrices are square and identify a linear relationship between information leakage and communication rate.

ABSTRACT. This study investigates the distributed fact-checking problem, where a series of fact-checkers (agents) with interconnected influence evaluate a sequence of statements from a source. Each statement has a hidden binary label (true or false), and each agent assigns their own true or false label to the statement. The agents' opinions follow a hidden directed chain, with a leader followed by ordered followers.

Our goals are to: (i) recover the directed chain (the relative order of agents), and (ii) decode the true label of each statement. We demonstrate that if the source is biased, the directed chain can be recovered through the observation of agents' labels. However, an unbiased source allows recovery of only the undirected influence chain. For the latter, we propose two low-complexity algorithms to recover the undirected chain, along with a decoder to estimate the true statement label based on observed agent opinions.