Andrew Lamperski

Andrew Lamperski, John C. Doyle

This paper gives a new solution to the output feedback H_2 model matching problem for a large class of delayed information sharing patterns. Existing methods for such problems typically reduce the decentralized problem to a centralized problem of higher state dimension. In contrast, the controller given in this paper is constructed from the solutions to the centralized control and estimation Riccati equations for the original system. The problem is solved by decomposing the controller into two components. One is centralized, but delayed, while the other is decentralized with finite impulse response (FIR). It is then shown that the optimal controller can be constructed through a combination of centralized spectral factorization and quadratic programming.

Yuping Zheng, Andrew Lamperski

Spectral estimation is an important tool in time series analysis, with applications including economics, astronomy, and climatology. The asymptotic theory for non-parametric estimation is well-known but the development of non-asymptotic theory is still ongoing. Our recent work obtained the first non-asymptotic error bounds on the Bartlett and Welch methods with restrictive assumptions. In this work, we derive non-asymptotic error bounds for both Bartlett and Welch estimators for $L$-mixing time-series data with unknown means, and the results cover the special case with known zero means. The class of $L$-mixing processes contains common models in time series analysis, including autoregressive processes and measurements of geometrically ergodic Markov chains. Our new error bounds are of $O(\frac{1}{\sqrt{k}})$, where $k$ is the number of data segments used in the algorithm. Such bounds are the tightest among the existing work on non-asymptotic analysis of classical spectrum estimators with or without zero-mean assumptions.

Andrew Lamperski

Spectrum estimation is a fundamental methodology in the analysis of time-series data, with applications including medicine, speech analysis, and control design. The asymptotic theory of spectrum estimation is well-understood, but the theory is limited when the number of samples is fixed and finite. This paper gives non-asymptotic error bounds for a broad class of spectral estimators, both pointwise (at specific frequencies) and in the worst case over all frequencies. The general method is used to derive error bounds for the classical Blackman-Tukey, Bartlett, and Welch estimators. In particular, these are first non-asymptotic error bounds for Bartlett and Welch estimators.

Yuping Zheng, Andrew Lamperski

Langevin algorithms are gradient descent methods augmented with additive noise, and are widely used in Markov Chain Monte Carlo (MCMC) sampling, optimization, and machine learning. In recent years, the non-asymptotic analysis of Langevin algorithms for non-convex learning has been extensively explored. For constrained problems with non-convex losses over a compact convex domain with IID data variables, the projected Langevin algorithm achieves a deviation of $O(T^{-1/4} (\log T)^{1/2})$ from its target distribution [27] in $1$-Wasserstein distance. In this paper, we obtain a deviation of $O(T^{-1/2} \log T)$ in $1$-Wasserstein distance for non-convex losses with $L$-mixing data variables and polyhedral constraints (which are not necessarily bounded). This improves on the previous bound for constrained problems and matches the best-known bound for unconstrained problems.

Tyler Lekang, Andrew Lamperski

Classical results in neural network approximation theory show how arbitrary continuous functions can be approximated by networks with a single hidden layer, under mild assumptions on the activation function. However, the classical theory does not give a constructive means to generate the network parameters that achieve a desired accuracy. Recent results have demonstrated that for specialized activation functions, such as ReLUs and some classes of analytic functions, high accuracy can be achieved via linear combinations of randomly initialized activations. These recent works utilize specialized integral representations of target functions that depend on the specific activation functions used. This paper defines mollified integral representations, which provide a means to form integral representations of target functions using activations for which no direct integral representation is currently known. The new construction enables approximation guarantees for randomly initialized networks for a variety of widely used activation functions.

Andrew Lamperski, Tyler Lekang

Neural networks are regularly employed in adaptive control of nonlinear systems and related methods of reinforcement learning. A common architecture uses a neural network with a single hidden layer (i.e. a shallow network), in which the weights and biases are fixed in advance and only the output layer is trained. While classical results show that there exist neural networks of this type that can approximate arbitrary continuous functions over bounded regions, they are non-constructive, and the networks used in practice have no approximation guarantees. Thus, the approximation properties required for control with neural networks are assumed, rather than proved. In this paper, we aim to fill this gap by showing that for sufficiently smooth functions, ReLU networks with randomly generated weights and biases achieve $L_{\infty}$ error of $O(m^{-1/2})$ with high probability, where $m$ is the number of neurons. It suffices to generate the weights uniformly over a sphere and the biases uniformly over an interval. We show how the result can be used to get approximations of required accuracy in a model reference adaptive control application.

Mikil Foss, Andrew Lamperski

Estimating the Kullback-Leibler (KL) divergence between random variables is a fundamental problem in statistical analysis. For continuous random variables, traditional information-theoretic estimators scale poorly with dimension and/or sample size. To mitigate this challenge, a variety of methods have been proposed to estimate KL divergences and related quantities, such as mutual information, using neural networks. The existing theoretical analyses show that neural network parameters achieving low error exist. However, since they rely on non-constructive neural network approximation theorems, they do not guarantee that the existing algorithms actually achieve low error. In this paper, we propose a KL divergence estimation algorithm using a shallow neural network with randomized hidden weights and biases (i.e. a random feature method). We show that with high probability, the algorithm achieves a KL divergence estimation error of $O(m^{-1/2}+T^{-1/3})$, where $m$ is the number of neurons and $T$ is both the number of steps of the algorithm and the number of samples.

Yuping Zheng, Andrew Lamperski

Stochastic gradient descent (SGD) is the main algorithm behind a large body of work in machine learning. In many cases, constraints are enforced via projections, leading to projected stochastic gradient algorithms. In recent years, a large body of work has examined the convergence properties of projected SGD for non-convex losses in asymptotic and non-asymptotic settings. Strong quantitative guarantees are available for convergence measured via Moreau envelopes. However, these results cannot be compared directly with work on unconstrained SGD, since the Moreau envelope construction changes the gradient. Other common measures based on gradient mappings have the limitation that convergence can only be guaranteed if variance reduction methods, such as mini-batching, are employed. This paper presents an analysis of projected SGD for non-convex losses over compact convex sets. Convergence is measured via the distance of the gradient to the Goldstein subdifferential generated by the constraints. Our proposed convergence criterion directly reduces to commonly used criteria in the unconstrained case, and we obtain convergence without requiring variance reduction. We obtain results for data that are independent, identically distributed (IID) or satisfy mixing conditions ($L$-mixing). In these cases, we derive asymptotic convergence and $O(N^{-1/3})$ non-asymptotic bounds in expectation, where $N$ is the number of steps. In the case of IID sub-Gaussian data, we obtain almost-sure asymptotic convergence and high-probability non-asymptotic $O(N^{-1/5})$ bounds. In particular, these are the first non-asymptotic high-probability bounds for projected SGD with non-convex losses.

Andrew Lamperski

Langevin algorithms are gradient descent methods with additive noise. They have been used for decades in Markov chain Monte Carlo (MCMC) sampling, optimization, and learning. Their convergence properties for unconstrained non-convex optimization and learning problems have been studied widely in the last few years. Other work has examined projected Langevin algorithms for sampling from log-concave distributions restricted to convex compact sets. For learning and optimization, log-concave distributions correspond to convex losses. In this paper, we analyze the case of non-convex losses with compact convex constraint sets and IID external data variables. We term the resulting method the projected stochastic gradient Langevin algorithm (PSGLA). We show the algorithm achieves a deviation of $O(T^{-1/4}(\log T)^{1/2})$ from its target distribution in 1-Wasserstein distance. For optimization and learning, we show that the algorithm achieves $ε$-suboptimal solutions, on average, provided that it is run for a time that is polynomial in $ε^{-1}$ and slightly super-exponential in the problem dimension.

Jianjun Yuan, Andrew Lamperski

Recursive least-squares algorithms often use forgetting factors as a heuristic to adapt to non-stationary data streams. The first contribution of this paper rigorously characterizes the effect of forgetting factors for a class of online Newton algorithms. For exp-concave and strongly convex objectives, the algorithms achieve the dynamic regret of $\max\{O(\log T),O(\sqrt{TV})\}$, where $V$ is a bound on the path length of the comparison sequence. In particular, we show how classic recursive least-squares with a forgetting factor achieves this dynamic regret bound. By varying $V$, we obtain a trade-off between static and dynamic regret. In order to obtain more computationally efficient algorithms, our second contribution is a novel gradient descent step size rule for strongly convex functions. Our gradient descent rule recovers the order optimal dynamic regret bounds described above. For smooth problems, we can also obtain static regret of $O(T^{1-β})$ and dynamic regret of $O(T^βV^*)$, where $β\in (0,1)$ and $V^*$ is the path length of the sequence of minimizers. By varying $β$, we obtain a trade-off between static and dynamic regret.

Tyler Lekang, Andrew Lamperski

In this paper, we present simple algorithms for Dueling Bandits. We prove that the algorithms have regret bounds for time horizon T of order O(T^rho ) with 1/2 <= rho <= 3/4, which importantly do not depend on any preference gap between actions, Delta. Dueling Bandits is an important extension of the Multi-Armed Bandit problem, in which the algorithm must select two actions at a time and only receives binary feedback for the duel outcome. This is analogous to comparisons in which the rater can only provide yes/no or better/worse type responses. We compare our simple algorithms to the current state-of-the-art for Dueling Bandits, ISS and DTS, discussing complexity and regret upper bounds, and conducting experiments on synthetic data that demonstrate their regret performance, which in some cases exceeds state-of-the-art.

Jianjun Yuan, Andrew Lamperski

We propose algorithms for online principal component analysis (PCA) and variance minimization for adaptive settings. Previous literature has focused on upper bounding the static adversarial regret, whose comparator is the optimal fixed action in hindsight. However, static regret is not an appropriate metric when the underlying environment is changing. Instead, we adopt the adaptive regret metric from the previous literature and propose online adaptive algorithms for PCA and variance minimization, that have sub-linear adaptive regret guarantees. We demonstrate both theoretically and experimentally that the proposed algorithms can adapt to the changing environments.

Jianjun Yuan, Andrew Lamperski

We propose the algorithms for online convex optimization which lead to cumulative squared constraint violations of the form $\sum\limits_{t=1}^T\big([g(x_t)]_+\big)^2=O(T^{1-β})$, where $β\in(0,1)$. Previous literature has focused on long-term constraints of the form $\sum\limits_{t=1}^Tg(x_t)$. There, strictly feasible solutions can cancel out the effects of violated constraints. In contrast, the new form heavily penalizes large constraint violations and cancellation effects cannot occur. Furthermore, useful bounds on the single step constraint violation $[g(x_t)]_+$ are derived. For convex objectives, our regret bounds generalize existing bounds, and for strongly convex objectives we give improved regret bounds. In numerical experiments, we show that our algorithm closely follows the constraint boundary leading to low cumulative violation.

Andrew Lamperski, Laurent Lessard

This work presents the solution to a class of decentralized linear quadratic state-feedback control problems, in which the plant and controller must satisfy the same combination of delay and sparsity constraints. Using a novel decomposition of the noise history, the control problem is split into independent subproblems that are solved using dynamic programming. The approach presented herein both unifies and generalizes many existing results.

Andrew Lamperski, John C. Doyle

This paper gives a new solution to the output feedback H2 problem for quadratically invariant communication delay patterns. A characterization of all stabilizing controllers satisfying the delay constraints is given and the decentralized H2 problem is cast as a convex model matching problem. The main result shows that the model matching problem can be reduced to a finite-dimensional quadratic program. A recursive state-space method for computing the optimal controller based on vectorization is given.

Andrew Lamperski

This paper studies the stability of sampled and networked control systems with sampling and communication times governed by probabilistic clocks. The clock models have few restrictions, and can be used to model numerous phenomena such as deterministic sampling, jitter, and transmission times of packet dropping networks. Moreover, the stability theory can be applied to an arbitrary number of clocks with different distributions, operating asynchronously. The paper gives Lyapunov-type sufficient conditions for stochastic stability of nonlinear networked systems. For linear systems, the paper gives necessary and sufficient conditions for exponential mean square stability, based on linear matrix inequalities. In both the linear and nonlinear cases, the Lyapunov inequalities are constructed from a simple linear combination of the classical inequalities from continuous and discrete time. Crucially, the stability theorems only depend on the mean sampling intervals. Thus, they can be applied with only limited statistical information about the clocks. The Lyapunov theorems are then applied to systems with multirate sampling, asynchronous communication, delays, and packet losses.