Search

We consider the distributed optimization problem for the sum of convex functions where the underlying communications network connecting agents at each time is drawn at random from a collection of directed graphs. We propose a modified version of the subgradient-push algorithm that is provably almost surely convergent to an optimizer on any such sequence of random directed graphs, establishing the first of this kind.

We provide a set of counterexamples for the monotonicity of the Newton–Hewer method (Hewer, 1971) for solving the discrete-time algebraic Riccati equation in dynamic settings, drawing a contrast with the Riccati difference equation (Caines and Mayne, 1970).

This paper studies the approximation of optimal control policies by quantized (discretized) policies for a very general class of Markov decision processes (MDPs). The problem is motivated by applications in networked control systems, computational methods for MDPs, and learning algorithms for MDPs. We consider the finite-action approximation of stationary policies for a discrete-time Markov decision process with discounted and average costs under a weak continuity assumption on the transition probability, which is a significant relaxation of conditions required in earlier literature. The discretization is constructive, and quantized policies are shown to approximate optimal deterministic stationary policies with arbitrary precision. The results are applied to the fully observed reduction of a partially observed Markov decision process, where weak continuity is a much more reasonable assumption than more stringent conditions such as strong continuity or continuity in total variation., Comment: 19 pages

Subspace constrained mean shift (SCMS) is a non-parametric, iterative algorithm that has recently been proposed to find principal curves and surfaces based on a new definition involving the gradient and Hessian of a kernel probability density estimate. Although simulation results using synthetic and real data have demonstrated the usefulness of the SCMS algorithm, a rigorous study of its convergence is still missing. This paper aims to take initial steps in this direction by showing that the SCMS algorithm inherits some important convergence properties of the mean shift (MS) algorithm. In particular, the monotonicity and convergence of the density estimate values along the sequence of output values of the algorithm is shown. Also, it is shown that the distance between consecutive points of the output sequence converges to zero, as does the projection of the gradient vector onto the subspace spanned by the D − d eigenvectors corresponding to the D-d largest eigenvalues of the local inverse covariance matrix. These last two properties provide theoretical guarantees for stopping criteria. By modifying the projection step, three variations of the SCMS algorithm are proposed and the running times and performance of the resulting algorithms are compared.

Probabilistic ‘distances’ (also called divergences), which in some sense assess how ‘close’ two probability distributions are from one another, have been widely employed in probability, statistics, information theory, and related fields. Of particular importance due to their generality and applicability are the Renyi divergence measures. This paper presents closed-form expressions for the Renyi and Kullback–Leibler divergences for nineteen commonly used univariate continuous distributions as well as those for multivariate Gaussian and Dirichlet distributions. In addition, a table summarizing four of the most important information measure rates for zero-mean stationary Gaussian processes, namely Renyi entropy, differential Shannon entropy, Renyi divergence, and Kullback–Leibler divergence, is presented. Lastly, a connection between the Renyi divergence and the variance of the log-likelihood ratio of two distributions is established, thereby extending a previous result by Song [J. Stat. Plan. Infer. 93 (2001)] on the relation between Renyi entropy and the log-likelihood function. A table with the corresponding variance expressions for the univariate distributions considered here is also included.

We obtain minimax lower and upper bounds for the expected distortion redundancy of empirically designed vector quantizers. We show that the mean-squared distortion of a vector quantizer designed from n independent and identically distributed (i.i.d.) data points using any design algorithm is at least /spl Omega/(n/sup -1/2/) away from the optimal distortion for some distribution on a bounded subset of /spl Rscr//sup d/. Together with existing upper bounds this result shows that the minimax distortion redundancy for empirical quantizer design, as a function of the size of the training data, is asymptotically on the order of n/sup -1/2/. We also derive a new upper bound for the performance of the empirically optimal quantizer.