A randomized Kaczmarz method was recently proposed for phase retrieval, which has been shown numerically to exhibit empirical performance over other state-of-the-art phase retrieval algorithms both in terms of the sampling complexity and in terms of computation time. While the rate of convergence has been studied well in the real case where the signals and measurement vectors are all real-valued, there is no guarantee for the convergence in the complex case. In fact, the linear convergence of the randomized Kaczmarz method for phase retrieval in the complex setting is left as a conjecture by Tan and Vershynin. In this paper, we provide the first theoretical guarantees for it. We show that for random measurements $\mathbf{a}_j \in \mathbb{C}^n, j=1,\ldots,m $ which are drawn independently and uniformly from the complex unit sphere, or equivalent are independent complex Gaussian random vectors, when $m \ge Cn$ for some universal positive constant $C$, the randomized Kaczmarz scheme with a good initialization converges linearly to the target solution (up to a global phase) in expectation with high probability. This gives a positive answer to that conjecture.
相關內容
In the framework of inverse linear problems on infinite-dimensional Hilbert space, we prove the convergence of the conjugate gradient iterates to an exact solution to the inverse problem in the most general case where the self-adjoint, non-negative operator is unbounded and with minimal, technically unavoidable assumptions on the initial guess of the iterative algorithm. The convergence is proved to always hold in the Hilbert space norm (error convergence), as well as at other levels of regularity (energy norm, residual, etc.) depending on the regularity of the iterates. We also discuss, both analytically and through a selection of numerical tests, the main features and differences of our convergence result as compared to the case, already available in the literature, where the operator is bounded.
We consider Model-Agnostic Meta-Learning (MAML) methods for Reinforcement Learning (RL) problems, where the goal is to find a policy using data from several tasks represented by Markov Decision Processes (MDPs) that can be updated by one step of stochastic policy gradient for the realized MDP. In particular, using stochastic gradients in MAML update steps is crucial for RL problems since computation of exact gradients requires access to a large number of possible trajectories. For this formulation, we propose a variant of the MAML method, named Stochastic Gradient Meta-Reinforcement Learning (SG-MRL), and study its convergence properties. We derive the iteration and sample complexity of SG-MRL to find an $\epsilon$-first-order stationary point, which, to the best of our knowledge, provides the first convergence guarantee for model-agnostic meta-reinforcement learning algorithms. We further show how our results extend to the case where more than one step of stochastic policy gradient method is used at test time. Finally, we empirically compare SG-MRL and MAML in several deep RL environments.
In this paper we analyse full discretizations of an initial boundary value problem (IBVP) related to reaction-diffusion equations. To avoid possible order reduction, the IBVP is first transformed into an IBVP with homogeneous boundary conditions (IBVPHBC) via a lifting of inhomogeneous Dirichlet, Neumann or mixed Dirichlet-Neumann boundary conditions. The IBVPHBC is discretized in time via the deferred correction method for the implicit midpoint rule and leads to a time-stepping scheme of order $2p+2$ of accuracy at the stage $p=0,1,2,\cdots $ of the correction. Each semi-discretized scheme results in a nonlinear elliptic equation for which the existence of a solution is proven using the Schaefer fixed point theorem. The elliptic equation corresponding to the stage $p$ of the correction is discretized by the Galerkin finite element method and gives a full discretization of the IBVPHBC. This fully discretized scheme is unconditionally stable with order $2p+2$ of accuracy in time. The order of accuracy in space is equal to the degree of the finite element used when the family of meshes considered is shape-regular while an increment of one order is proven for quasi-uniform family of meshes. Numerical tests with a bistable reaction-diffusion equation having a strong stiffness ratio and a linear reaction-diffusion equation addressing order reduction are performed and demonstrate the unconditional convergence of the method. The orders 2,4,6,8 and 10 of accuracy in time are achieved.
We give an analogue of the ElGamal encryption system based on the Markovski algorithm [4; 5].
Regula Falsi, or the method of false position, is a numerical method for finding an approximate solution to f(x) = 0 on a finite interval [a, b], where f is a real-valued continuous function on [a, b] and satisfies f(a)f(b) < 0. Previous studies proved the convergence of this method under certain assumptions about the function f, such as both the first and second derivatives of f do not change the sign on the interval [a, b]. In this paper, we remove those assumptions and prove the convergence of the method for all continuous functions.
The statistical finite element method (StatFEM) is an emerging probabilistic method that allows observations of a physical system to be synthesised with the numerical solution of a PDE intended to describe it in a coherent statistical framework, to compensate for model error. This work presents a new theoretical analysis of the statistical finite element method demonstrating that it has similar convergence properties to the finite element method on which it is based. Our results constitute a bound on the Wasserstein-2 distance between the ideal prior and posterior and the StatFEM approximation thereof, and show that this distance converges at the same mesh-dependent rate as finite element solutions converge to the true solution. Several numerical examples are presented to demonstrate our theory, including an example which test the robustness of StatFEM when extended to nonlinear quantities of interest.
A second order accurate, linear numerical method is analyzed for the Landau-Lifshitz equation with large damping parameters. This equation describes the dynamics of magnetization, with a non-convexity constraint of unit length of the magnetization. The numerical method is based on the second-order backward differentiation formula in time, combined with an implicit treatment of the linear diffusion term and explicit extrapolation for the nonlinear terms. Afterward, a projection step is applied to normalize the numerical solution at a point-wise level. This numerical scheme has shown extensive advantages in the practical computations for the physical model with large damping parameters, which comes from the fact that only a linear system with constant coefficients (independent of both time and the updated magnetization) needs to be solved at each time step, and has greatly improved the numerical efficiency. Meanwhile, a theoretical analysis for this linear numerical scheme has not been available. In this paper, we provide a rigorous error estimate of the numerical scheme, in the discrete $\ell^{\infty}(0,T; \ell^2) \cap \ell^2(0,T; H_h^1)$ norm, under suitable regularity assumptions and reasonable ratio between the time step-size and the spatial mesh-size. In particular, the projection operation is nonlinear, and a stability estimate for the projection step turns out to be highly challenging. Such a stability estimate is derived in details, which will play an essential role in the convergence analysis for the numerical scheme, if the damping parameter is greater than 3.
We build a sharp approximation of the whole distribution of the sum of iid heavy-tailed random vectors, combining mean and extreme behaviors. It extends the so-called 'normex' approach from a univariate to a multivariate framework. We propose two possible multi-normex distributions, named $d$-Normex and MRV-Normex. Both rely on the Gaussian distribution for describing the mean behavior, via the CLT, while the difference between the two versions comes from using the exact distribution or the EV theorem for the maximum. The main theorems provide the rate of convergence for each version of the multi-normex distributions towards the distribution of the sum, assuming second order regular variation property for the norm of the parent random vector when considering the MRV-normex case. Numerical illustrations and comparisons are proposed with various dependence structures on the parent random vector, using QQ-plots based on geometrical quantiles.
Randomization has been shown to be beneficial to iterative methods for solving large-scale systems of linear equations, notably the Kaczmarz algorithm. We analyze the convergence of a broad class of pursuit algorithms that at each step pick $n$ members at random, from a system of linear equations, and update the iterate using the orthogonal projection to the intersection of the hyperplanes they represent. We identify, in this context, a specific degree-$n$ polynomial that non-linearly transforms the singular values of the system. This transformation to singular values and the corresponding condition number then characterizes the convergence rate, in expectation, of the pursuit. As a consequence, our results specify the convergence rate of the stochastic gradient descent algorithm, in terms of the mini-batch size $n$, when used for solving systems of linear equations.
We consider the problem of upper bounding the expected log-likelihood sub-optimality of the maximum likelihood estimate (MLE), or a conjugate maximum a posteriori (MAP) for an exponential family, in a non-asymptotic way. Surprisingly, we found no general solution to this problem in the literature. In particular, current theories do not hold for a Gaussian or in the interesting few samples regime. After exhibiting various facets of the problem, we show we can interpret the MAP as running stochastic mirror descent (SMD) on the log-likelihood. However, modern convergence results do not apply for standard examples of the exponential family, highlighting holes in the convergence literature. We believe solving this very fundamental problem may bring progress to both the statistics and optimization communities.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191