Search

Faced with massive data, subsampling is a commonly used technique to improve computational efficiency, and using nonuniform subsampling probabilities is an effective approach to improve estimation efficiency. For computational efficiency, subsampling is often implemented with replacement or through Poisson subsampling. However, no rigorous investigation has been performed to study the difference between the two subsampling procedures such as their estimation efficiency and computational convenience. This paper performs a comparative study on these two different sampling procedures. In the context of maximizing a general target function, we first derive asymptotic distributions for estimators obtained from the two sampling procedures. The results show that the Poisson subsampling may have a higher estimation efficiency. Based on the asymptotic distributions for both subsampling with replacement and Poisson subsampling, we derive optimal subsampling probabilities that minimize the variance functions of the subsampling estimators. These subsampling probabilities further reveal the similarities and differences between subsampling with replacement and Poisson subsampling. The theoretical characterizations and comparisons on the two subsampling procedures provide guidance to select a more appropriate subsampling approach in practice. Furthermore, practically implementable algorithms are proposed based on the optimal structural results, which are evaluated through both theoretical and empirical analyses. [ABSTRACT FROM AUTHOR]

We analyze the orthogonal greedy algorithm when applied to dictionaries $\mathbb {D}$ whose convex hull has small entropy. We show that if the metric entropy of the convex hull of $\mathbb {D}$ decays at a rate of $O\left({n^{-\frac {1}{2}-\alpha }}\right)$ for $\alpha > 0$ , then the orthogonal greedy algorithm converges at the same rate on the variation space of $\mathbb {D}$. This improves upon the well-known $O\left({n^{-\frac {1}{2}}}\right)$ convergence rate of the orthogonal greedy algorithm in many cases, most notably for dictionaries corresponding to shallow neural networks. These results hold under no additional assumptions on the dictionary beyond the decay rate of the entropy of its convex hull. In addition, they are robust to noise in the target function and can be extended to convergence rates on the interpolation spaces of the variation norm. We show empirically that the predicted rates are obtained for the dictionary corresponding to shallow neural networks with Heaviside activation function in two dimensions. Finally, we show that these improved rates are sharp and prove a negative result showing that the iterates generated by the orthogonal greedy algorithm cannot in general be bounded in the variation norm of $\mathbb {D}$. [ABSTRACT FROM AUTHOR]

We propose two modified versions of the classical gradient ascent method to compute the capacity of finite-state channels with Markovian inputs. For the case that the channel mutual information rate is strongly concave in a parameter taking values in a compact convex subset of some Euclidean space, our first algorithm proves to achieve polynomial accuracy in polynomial time and, moreover, for some special families of finite-state channels our algorithm can achieve exponential accuracy in polynomial time under some technical conditions. For the case that the channel mutual information rate may not be strongly concave, our second algorithm proves to be at least locally convergent. [ABSTRACT FROM AUTHOR]

We consider a distributed stochastic optimization problem in networks with finite number of nodes. Each node adjusts its action to optimize the global utility of the network, which is defined as the sum of local utilities of all nodes. While Gradient descent method is a common technique to solve such optimization problem, the computation of the gradient may require much information exchange. In this paper, we consider that each node can only have a noisy numerical observation of its local utility, of which the closed-form expression is not available. This assumption is quite realistic, especially when the system is either too complex or constantly changing. Nodes may exchange partially the observation of their local utilities to estimate the global utility at each timeslot. We propose a distributed algorithm based on stochastic perturbation, under the assumption that each node has only part of the local utilities of the other nodes. We use stochastic approximation tools to prove that our algorithm converges almost surely to the optimum, given that the objective function is smooth and strictly concave. The convergence rate is also derived, under the additional assumption of strongly concave objective function. It is shown that the convergence rate scales as O (K−0.5) after a sufficient number of iterations K > K0, which is the optimal rate order in terms of K for our problem. Although the proposed algorithm can be applied to general optimization problems, we perform simulations for a typical power control problem in wireless networks and present numerical results to corroborate our claims. [ABSTRACT FROM AUTHOR]

Using stochastic gradient search and the optimal filter derivative, it is possible to perform recursive maximum likelihood estimation in a non-linear state-space model. As the optimal filter and its derivative are analytically intractable for such a model, they need to be approximated numerically. In Poyiadjis et al. (G. Poyiadjis, A. Doucet, and S. S. Singh, Biometrika, vol. 98, no. 1, pp. 65–80, 2011), a recursive maximum likelihood algorithm based on a particle approximation to the optimal filter derivative has been proposed and studied through numerical simulations. This algorithm and its asymptotic behavior are here analyzed theoretically. Under regularity conditions, we show that the algorithm accurately estimates maxima of the underlying log-likelihood rate when the number of particles is sufficiently large. We also provide qualitative upper bounds on the estimation error in terms of the number of particles. [ABSTRACT FROM AUTHOR]

The capacity of noisy quantum channels characterizes the highest rate at which information can be reliably transmitted and it is therefore of practical as well as fundamental importance. Capacities of classical channels are computed using alternating optimization schemes, called Blahut-Arimoto algorithms. In this work, we generalize classical Blahut-Arimoto algorithms to the quantum setting. In particular, we give efficient iterative schemes to compute the capacity of channels with classical input and quantum output, the quantum capacity of less noisy channels, the thermodynamic capacity of quantum channels, as well as the entanglement-assisted capacity of quantum channels. We give rigorous a priori and a posteriori bounds on the estimation error by employing quantum entropy inequalities and demonstrate fast convergence of our algorithms in numerical experiments. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a powerful technique based on Leave-One-Out analysis to the study of low-rank matrix completion problems. Using this technique, we develop a general approach for obtaining fine-grained, entrywise bounds for iterative stochastic procedures in the presence of probabilistic dependency. We demonstrate the power of this approach in analyzing two of the most important algorithms for matrix completion: (i) the non-convex approach based on Projected Gradient Descent (PGD) for a rank-constrained formulation, also known as the Singular Value Projection algorithm, and (ii) the convex relaxation approach based on nuclear norm minimization (NNM). Using this approach, we establish the first convergence guarantee for the original form of PGD without regularization or sample splitting, and in particular shows that it converges linearly in the infinity norm. For NNM, we use this approach to study a fictitious iterative procedure that arises in the dual analysis. Our results show that NNM recovers an $d$ -by- $d$ rank- $r$ matrix with $\mathcal {O}(\mu r \log (\mu r) d\log d)$ observed entries. This bound has optimal dependence on the matrix dimension and is independent of the condition number. To the best of our knowledge, none of previous sample complexity results for tractable matrix completion algorithms satisfies these two properties simultaneously. [ABSTRACT FROM AUTHOR]

Strict Minimum Message Length (SMML) is an information-theoretic statistical inference method widely cited (but only with informal arguments) as providing estimations that are consistent for general estimation problems. It is, however, almost invariably intractable to compute, for which reason only approximations of it (known as MML algorithms) are ever used in practice. Using novel techniques that allow for the first time direct, non-approximated analysis of SMML solutions, we investigate the Neyman-Scott estimation problem, an oft-cited showcase for the consistency of MML, and show that even with a natural choice of prior neither SMML nor its popular approximations are consistent for it, thereby providing a counterexample to the general claim. This is the first known explicit construction of an SMML solution for a natural, high-dimensional problem. [ABSTRACT FROM AUTHOR]

Signal recovery from unitarily invariant measurements is investigated in this paper. A message-passing algorithm is formulated on the basis of expectation propagation (EP). A rigorous analysis is presented for the dynamics of the algorithm in the large system limit, where both input and output dimensions tend to infinity while the compression rate is kept constant. The main result is the justification of state evolution (SE) equations conjectured by Ma and Ping. This result implies that the EP-based algorithm achieves the Bayes-optimal performance that was originally derived via a non-rigorous tool in statistical physics and proved partially in a recent paper, when the compression rate is larger than a threshold. The proof is based on an extension of a conventional conditioning technique for the standard Gaussian matrix to the case of the Haar matrix. [ABSTRACT FROM AUTHOR]

We study the properties of the Frank–Wolfe algorithm to solve the m-Exact-Sparse reconstruction problem, where a signal $y$ must be expressed as a sparse linear combination of a predefined set of atoms, called dictionary. We prove that when the signal is sparse enough with respect to the coherence of the dictionary, then the iterative process implemented by the Frank–Wolfe algorithm only recruits atoms from the support of the signal, is the smallest set of atoms from the dictionary that allows for a perfect reconstruction of $y$. We also prove that under this same condition, there exists an iteration beyond which the algorithm converges exponentially. [ABSTRACT FROM AUTHOR]

In many different applications, it is important to determine the Hilbert transform of a given function. However, it is generally impossible to calculate it in closed form. Therefore Hilbert transform approximations are used. This paper studies the convergence and divergence behavior of general classes of such approximation methods. These classes are characterized by two very natural axioms and they include basically all known traditional numerical algorithms. The convergence of these methods is investigated on a family of signal spaces of continuous functions with finite energy. These spaces are parametrized by a number which measures the energy concentration in the low frequency components of the signal. It is shown that stable methods only exist on signal spaces with a sufficient energy concentration and this paper gives some explicit examples of convergent methods. On all other spaces in the family of signal spaces, every sampling-based Hilbert transform approximation shows a blowup behavior of its peak value, i.e., on these spaces, every sampling-based Hilbert transform approximation diverges. [ABSTRACT FROM AUTHOR]

We consider a discrete-time distributed averaging algorithm over multi-agent networks with measurement noises and time-varying random graphs. Each agent updates its state by a weighted sum of pairwise state differences between its neighbors and itself with both additive and multiplicative measurement noises. The network structure is modeled by a sequence of time-varying random digraphs, which may be spatially and temporally dependent. By stochastic Lyapunov method and the combination of algebraic graph theory and martingale convergence theory, we obtain sufficient conditions for stochastic approximation type algorithms to achieve mean square and almost sure average consensus. We prove that all states of the agents converge to a common random variable, whose mathematical expectation is the average of initial values, in mean square and almost surely if the sequence of digraphs is conditionally balanced and uniformly conditionally jointly connected. An upper bound of the variance of the limit random variable, that is, the mean square steady-state error for stochastic average consensus is given quantitatively related to the weights, the algorithm gain and the energy level of the noises. [ABSTRACT FROM AUTHOR]

We study the convergence of the iterative projected gradient (IPG) algorithm for arbitrary (possibly non-convex) sets when both the gradient and projection oracles are computed approximately. We consider different notions of approximation of which we show that the progressive fixed precision and the $(1+ \varepsilon)$ -optimal oracles can achieve the same accuracy as for the exact IPG algorithm. We show that the former scheme is also able to maintain the (linear) rate of convergence of the exact algorithm under the same embedding assumption. In contrast, the $(1+ \varepsilon)$ -approximate oracle requires a stronger embedding condition, moderate compression ratios and it typically slows down the convergence. We apply our results to accelerate solving a class of data driven compressed sensing problems, where we replace iterative exhaustive searches over large data sets by fast approximate nearest neighbor search strategies based on the cover tree data structure. For data sets with low intrinsic dimensions, our proposed algorithm achieves a complexity logarithmic in terms of the data set population as opposed to the linear complexity of a brute force search. By running several numerical experiments, we conclude similar observations as predicted by our theoretical analysis. [ABSTRACT FROM AUTHOR]

In this paper, we consider the filtering and smoothing recursions in nonparametric finite state space hidden Markov models (HMMs) when the parameters of the model are unknown and replaced by estimators. We provide an explicit and time uniform control of the filtering and smoothing errors in total variation norm as a function of the parameter estimation errors. We prove that the risk for the filtering and smoothing errors may be uniformly upper bounded by the \mathrm L^1 -risk of the estimators. It has been proved very recently that statistical inference for finite state space nonparametric HMMs is possible. We study how the recent spectral methods developed in the parametric setting may be extended to the nonparametric framework and we give explicit upper bounds for the \mathrm L^2 -risk of the nonparametric spectral estimators. In the case where the observation space is compact, this provides explicit rates for the filtering and smoothing errors in total variation norm. The performance of the spectral method is assessed with simulated data for both the estimation of the (nonparametric) conditional distribution of the observations and the estimation of the marginal smoothing distributions. [ABSTRACT FROM AUTHOR]

Impulsive noise features in many modern communication systems—ranging from wireless to molecular—and is often modeled by the $\alpha $ -stable distribution. At present, the capacity of $\alpha $ -stable noise channels is not well understood, with the exception of Cauchy noise ( $\alpha = 1$ ) with a logarithmic constraint and Gaussian noise ( $\alpha = 2$ ) with a power constraint. In this paper, we consider additive symmetric $\alpha $ -stable noise channels with $\alpha \in (1,2]$ . We derive bounds for the capacity with an absolute moment constraint. We then compare our bounds with a numerical approximation via the Blahut–Arimoto algorithm, which provides insight into the effect of noise parameters on the bounds. In particular, we find that our lower bound is in good agreement with the numerical approximation for $\alpha $ near 2. [ABSTRACT FROM AUTHOR]

We consider the problem of recovering a complete (i.e., square and invertible) matrix A0 , from Y \in \mathbb R ^n \times p with Y = \boldsymbol A0 X0 , provided X0 is sufficiently sparse. This recovery problem is central to theoretical understanding of dictionary learning, which seeks a sparse representation for a collection of input signals and finds numerous applications in modern signal processing and machine learning. We give the first efficient algorithm that provably recovers A0 when X0 has O \left ( n \right ) nonzeros per column, under suitable probability model for X0 . Our algorithmic pipeline centers around solving a certain nonconvex optimization problem with a spherical constraint, and hence is naturally phrased in the language of manifold optimization. In a companion paper, we have showed that with high probability, our nonconvex formulation has no “spurious” local minimizers and around any saddle point, the objective function has a negative directional curvature. In this paper, we take advantage of the particular geometric structure and describe a Riemannian trust region algorithm that provably converges to a local minimizer with from arbitrary initializations. Such minimizers give excellent approximations to the rows of X0 . The rows are then recovered by a linear programming rounding and deflation. [ABSTRACT FROM AUTHOR]

Carrier sense multiple access (CSMA), which resolves contentions over wireless networks in a fully distributed fashion, has recently gained a lot of attentions since it has been proved that appropriate control of CSMA parameters guarantees optimality in terms of stability (i.e., scheduling) and system-wide utility (i.e., scheduling and congestion control). Most CSMA-based algorithms rely on the popular Markov chain Monte Carlo technique, which enables one to find optimal CSMA parameters through iterative loops of simulation-and-update. However, such a simulation-based approach often becomes a major cause of exponentially slow convergence, being poorly adaptive to flow/topology changes. In this paper, we develop distributed iterative algorithms which produce approximate solutions with convergence in polynomial time for both stability and utility maximization problems. In particular, for the stability problem, the proposed distributed algorithm requires, somewhat surprisingly, only one iteration among links. Our approach is motivated by the Bethe approximation (introduced by Yedidia, Freeman, and Weiss) allowing us to express approximate solutions via a certain nonlinear system with polynomial size. Our polynomial convergence guarantee comes from directly solving the nonlinear system in a distributed manner, rather than multiple simulation-and-update loops in existing algorithms. We provide numerical results to show that the algorithm produces highly accurate solutions and converges much faster than the prior ones. [ABSTRACT FROM AUTHOR]

This paper provides a proof of global convergence of gradient search for low-rank matrix approximation. Such approximations have recently been of interest for large-scale problems, as well as for dictionary learning for sparse signal representations and matrix completion. The proof is based on the interpretation of the problem as an optimization on the Grassmann manifold and Fubiny–Study distance on this space. [ABSTRACT FROM PUBLISHER]

Inspired by ideas from the field of stochastic approximation, we propose a randomized algorithm to compute the capacity of a finite-state channel with a Markovian input. When the mutual information rate of the channel is concave with respect to the chosen parameterization, the proposed algorithm proves to be convergent to the capacity of the channel almost surely with the derived convergence rate. We also discuss the convergence behavior of the algorithm without the concavity assumption. [ABSTRACT FROM PUBLISHER]

This paper resolves a common complexity issue in the Bethe approximation of statistical physics and the belief propagation (BP) algorithm of artificial intelligence. The Bethe approximation and the BP algorithm are heuristic methods for estimating the partition function and marginal probabilities in graphical models, respectively. The computational complexity of the Bethe approximation is decided by the number of operations required to solve a set of nonlinear equations, the so-called Bethe equation. Although the BP algorithm was inspired and developed independently, Yedidia, Freeman, and Weiss showed that the BP algorithm solves the Bethe equation if it converges (however, it often does not). This naturally motivates the following question to understand limitations and empirical successes of the Bethe and BP methods: is the Bethe equation computationally easy to solve? We present a message-passing algorithm solving the Bethe equation in a polynomial number of operations for general binary graphical models of \(n\) variables, where the maximum degree in the underlying graph is \(O(\log n)\) . Equivalently, it finds a stationary point of the Bethe free energy function. Our algorithm can be used as an alternative to BP fixing its convergence issue and is the first fully polynomial-time approximation scheme for the BP fixed-point computation in such a large class of graphical models, whereas the approximate fixed-point computation is known to be polynomial parity arguments on directed graphs (PPAD-)hard in general. We believe that our technique is of broader interest to understand the computational complexity of the cavity method in statistical physics. [ABSTRACT FROM AUTHOR]

In this paper, a distributed stochastic approximation algorithm is studied. Applications of such algorithms include decentralized estimation, optimization, control or computing. The algorithm consists in two steps: a local step, where each node in a network updates a local estimate using a stochastic approximation algorithm with decreasing step size, and a gossip step, where a node computes a local weighted average between its estimates and those of its neighbors. Convergence of the estimates toward a consensus is established under weak assumptions. The approach relies on two main ingredients: the existence of a Lyapunov function for the mean field in the agreement subspace, and a contraction property of the random matrices of weights in the subspace orthogonal to the agreement subspace. A second-order analysis of the algorithm is also performed under the form of a central limit Theorem. The Polyak-averaged version of the algorithm is also considered. [ABSTRACT FROM AUTHOR]

It has recently been observed that the permanent of a nonnegative square matrix, i.e., of a square matrix containing only nonnegative real entries, can very well be approximated by solving a certain Bethe free energy function minimization problem with the help of the sum–product algorithm. We call the resulting approximation of the permanent the Bethe permanent. In this paper, we give reasons why this approach to approximating the permanent works well. Namely, we show that the Bethe free energy function is convex and that the sum–product algorithm finds its minimum efficiently. We then discuss the fact that the permanent is lower bounded by the Bethe permanent, and we comment on potential upper bounds on the permanent based on the Bethe permanent. We also present a combinatorial characterization of the Bethe permanent in terms of permanents of so-called lifted versions of the matrix under consideration. Moreover, we comment on possibilities to modify the Bethe permanent so that it approximates the permanent even better, and we conclude the paper with some observations and conjectures about permanent-based pseudocodewords and permanent-based kernels. [ABSTRACT FROM AUTHOR]

“Approximate message passing” (AMP) algorithms have proved to be effective in reconstructing sparse signals from a small number of incoherent linear measurements. Extensive numerical experiments further showed that their dynamics is accurately tracked by a simple one-dimensional iteration termed state evolution. In this paper, we provide rigorous foundation to state evolution. We prove that indeed it holds asymptotically in the large system limit for sensing matrices with independent and identically distributed Gaussian entries. While our focus is on message passing algorithms for compressed sensing, the analysis extends beyond this setting, to a general class of algorithms on dense graphs. In this context, state evolution plays the role that density evolution has for sparse graphs. The proof technique is fundamentally different from the standard approach to density evolution, in that it copes with a large number of short cycles in the underlying factor graph. It relies instead on a conditioning technique recently developed by Erwin Bolthausen in the context of spin glass theory. [ABSTRACT FROM AUTHOR]