Randomization has shown catalyzing effects in linear algebra with promising perspectives for tackling computational challenges in large-scale problems. For solving a system of linear equations, we demonstrate the convergence of a broad class of algorithms that at each step pick a subset of $n$ equations at random and update the iterate with the orthogonal projection to the subspace those equations represent. We identify, in this context, a specific degree-$n$ polynomial that non-linearly transforms the singular values of the system towards equalization. This transformation to singular values and the corresponding condition number then characterizes the expected convergence rate of iterations. 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.
相關內容
Evolution strategies (ESs) are zeroth-order stochastic black-box optimization heuristics invariant to monotonic transformations of the objective function. They evolve a multivariate normal distribution, from which candidate solutions are generated. Among different variants, CMA-ES is nowadays recognized as one of the state-of-the-art zeroth-order optimizers for difficult problems. Albeit ample empirical evidence that ESs with a step-size control mechanism converge linearly, theoretical guarantees of linear convergence of ESs have been established only on limited classes of functions. In particular, theoretical results on convex functions are missing, where zeroth-order and also first-order optimization methods are often analyzed. In this paper, we establish almost sure linear convergence and a bound on the expected hitting time of an \new{ES family, namely the $(1+1)_\kappa$-ES, which includes the (1+1)-ES with (generalized) one-fifth success rule} and an abstract covariance matrix adaptation with bounded condition number, on a broad class of functions. The analysis holds for monotonic transformations of positively homogeneous functions and of quadratically bounded functions, the latter of which particularly includes monotonic transformation of strongly convex functions with Lipschitz continuous gradient. As far as the authors know, this is the first work that proves linear convergence of ES on such a broad class of functions.
We provide a systematic way to design computable bilinear forms which, on the class of subspaces $W^* \subseteq \mathcal{V}'$ that can be obtained by duality from a given finite dimensional subspace $W$ of an Hilbert space $\mathcal{V}$, are spectrally equivalent to the scalar product of $\mathcal{V}'$. Such a bilinear form can be used to build a stabilized discretization algorithm for the solution of an abstract saddle point problem allowing to decouple, in the choice of the discretization spaces, the requirements related to the approximation from the inf-sup compatibility condition, which, as we show, can not be completely avoided.
Consider the problem of covertly controlling a linear system. In this problem, Alice desires to control (stabilize or change the parameters of) a linear system, while keeping an observer, Willie, unable to decide if the system is indeed being controlled or not. We formally define the problem, under two different models: (i) When Willie can only observe the system's output (ii) When Willie can directly observe the control signal. Focusing on AR(1) systems, we show that when Willie observes the system's output through a clean channel, an inherently unstable linear system can not be covertly stabilized. However, an inherently stable linear system can be covertly controlled, in the sense of covertly changing its parameter. Moreover, we give direct and converse results for two important controllers: a minimal-information controller, where Alice is allowed to used only $1$ bit per sample, and a maximal-information controller, where Alice is allowed to view the real-valued output. Unlike covert communication, where the trade-off is between rate and covertness, the results reveal an interesting \emph{three--fold} trade--off in covert control: the amount of information used by the controller, control performance and covertness. To the best of our knowledge, this is the first study formally defining covert control.
To speed-up the solution to parametrized differential problems, reduced order models (ROMs) have been developed over the years, including projection-based ROMs such as the reduced-basis (RB) method, deep learning-based ROMs, as well as surrogate models obtained via a machine learning approach. Thanks to its physics-based structure, ensured by the use of a Galerkin projection of the full order model (FOM) onto a linear low-dimensional subspace, RB methods yield approximations that fulfill the physical problem at hand. However, to make the assembling of a ROM independent of the FOM dimension, intrusive and expensive hyper-reduction stages are usually required, such as the discrete empirical interpolation method (DEIM), thus making this strategy less feasible for problems characterized by (high-order polynomial or nonpolynomial) nonlinearities. To overcome this bottleneck, we propose a novel strategy for learning nonlinear ROM operators using deep neural networks (DNNs). The resulting hyper-reduced order model enhanced by deep neural networks, to which we refer to as Deep-HyROMnet, is then a physics-based model, still relying on the RB method approach, however employing a DNN architecture to approximate reduced residual vectors and Jacobian matrices once a Galerkin projection has been performed. Numerical results dealing with fast simulations in nonlinear structural mechanics show that Deep-HyROMnets are orders of magnitude faster than POD-Galerkin-DEIM ROMs, keeping the same level of accuracy.
In these lectures notes, we review our recent works addressing various problems of finding the nearest stable system to an unstable one. After the introduction, we provide some preliminary background, namely, defining Port-Hamiltonian systems and dissipative Hamiltonian systems and their properties, briefly discussing matrix factorizations, and describing the optimization methods that we will use in these notes. In the third chapter, we present our approach to tackle the distance to stability for standard continuous linear time invariant (LTI) systems. The main idea is to rely on the characterization of stable systems as dissipative Hamiltonian systems. We show how this idea can be generalized to compute the nearest $\Omega$-stable matrix, where the eigenvalues of the sought system matrix $A$ are required to belong a rather general set $\Omega$. We also show how these ideas can be used to compute minimal-norm static feedbacks, that is, stabilize a system by choosing a proper input $u(t)$ that linearly depends on $x(t)$ (static-state feedback), or on $y(t)$ (static-output feedback). In the fourth chapter, we present our approach to tackle the distance to passivity. The main idea is to rely on the characterization of stable systems as port-Hamiltonian systems. We also discuss in more details the special case of computing the nearest stable matrix pairs. In the last chapter, we focus on discrete-time LTI systems. Similarly as for the continuous case, we propose a parametrization that allows efficiently compute the nearest stable system (for matrices and matrix pairs), allowing to compute the distance to stability. We show how this idea can be used in data-driven system identification, that is, given a set of input-output pairs, identify the system $A$.
The full history recursive multilevel Picard approximation method for semilinear parabolic partial differential equations (PDEs) is the only method which provably overcomes the curse of dimensionality for general time horizons if the coefficient functions and the nonlinearity are globally Lipschitz continuous and the nonlinearity is gradient-independent. In this article we extend this result to locally monotone coefficient functions. Our results cover a range of semilinear PDEs with polynomial coefficient functions.
In the present paper, we study the analyticity of the leftmost eigenvalue of the linear elliptic partial differential operator with random coefficient and analyze the convergence rate of the quasi-Monte Carlo method for approximation of the expectation of this quantity. The random coefficient is assumed to be represented by an affine expansion $a_0(\boldsymbol{x})+\sum_{j\in \mathbb{N}}y_ja_j(\boldsymbol{x})$, where elements of the parameter vector $\boldsymbol{y}=(y_j)_{j\in \mathbb{N}}\in U^\infty$ are independent and identically uniformly distributed on $U:=[-\frac{1}{2},\frac{1}{2}]$. Under the assumption $ \|\sum_{j\in \mathbb{N}}\rho_j|a_j|\|_{L_\infty(D)} <\infty$ with some positive sequence $(\rho_j)_{j\in \mathbb{N}}\in \ell_p(\mathbb{N})$ for $p\in (0,1]$ we show that for any $\boldsymbol{y}\in U^\infty$, the elliptic partial differential operator has a countably infinite number of eigenvalues $(\lambda_j(\boldsymbol{y}))_{j\in \mathbb{N}}$ which can be ordered non-decreasingly. Moreover, the spectral gap $\lambda_2(\boldsymbol{y})-\lambda_1(\boldsymbol{y})$ is uniformly positive in $U^\infty$. From this, we prove the holomorphic extension property of $\lambda_1(\boldsymbol{y})$ to a complex domain in $\mathbb{C}^\infty$ and estimate mixed derivatives of $\lambda_1(\boldsymbol{y})$ with respect to the parameters $\boldsymbol{y}$ by using Cauchy's formula for analytic functions. Based on these bounds we prove the dimension-independent convergence rate of the quasi-Monte Carlo method to approximate the expectation of $\lambda_1(\boldsymbol{y})$. In this case, the computational cost of fast component-by-component algorithm for generating quasi-Monte Carlo $N$-points scales linearly in terms of integration dimension.
The aim of this work is to provide the first strong convergence result of numerical approximation of a general time-fractional second order stochastic partial differential equation involving a Caputo derivative in time of order $\alpha\in(\frac 12; 1)$ and driven simultaneously by a multiplicative standard Brownian motion and additive fBm with Hurst parameter $H\in(\frac 12, 1)$, more realistic to model the random effects on transport of particles in medium with thermal memory. We prove the existence and uniqueness results and perform the spatial discretization using the finite element and the temporal discretization using a fractional exponential integrator scheme. We provide the temporal and spatial convergence proofs for our fully discrete scheme and the result shows that the convergence orders depend on the regularity of the initial data, the power of the fractional derivative, and the Hurst parameter $H$.
The ongoing NIST standardization process has shown that Proof of Knowledge (PoK) based signatures have become an important type of possible post-quantum signatures. Regarding code-based cryptography, the original approach for PoK based signatures is the Stern protocol which allows to prove the knowledge of a small weight vector solving a given instance of the Syndrome Decoding (SD) problem over F2. It features a soundness error equal to 2/3. This protocol was improved a few years later by V\'eron who proposed a variation of the scheme based on the General Syndrome Decoding (GSD) problem which leads to better results in term of communication. A few years later, the AGS protocol introduced a variation of the V\'eron protocol based on Quasi-Cyclic (QC) matrices. The AGS protocol permits to obtain an asymptotic soundness error of 1/2 and an improvement in term of communications. In the present paper, we introduce the Quasi-Cyclic Stern PoK which constitutes an adaptation of the AGS scheme in a SD context, as well as several new optimizations for code-based PoK. Our main optimization on the size of the signature can't be applied to GSD based protocols such as AGS and therefore motivated the design of our new protocol. In addition, we also provide a special soundness proof that is compatible with the use of the Fiat-Shamir transform for 5-round protocols. This approach is valid for our protocol but also for the AGS protocol which was lacking such a proof. We compare our results with existing signatures including the recent code-based signatures based on PoK leveraging the MPC in the head paradigm. In practice, our new protocol is as fast as AGS while reducing its associated signature length by 20%. As a consequence, it constitutes an interesting trade-off between signature length and execution time for the design of a code-based signature relying only on the difficulty of the SD problem.
Minimax problems have gained tremendous attentions across the optimization and machine learning community recently. In this paper, we introduce a new quasi-Newton method for minimax problems, which we call $J$-symmetric quasi-Newton method. The method is obtained by exploiting the $J$-symmetric structure of the second-order derivative of the objective function in minimax problem. We show that the Hessian estimation (as well as its inverse) can be updated by a rank-2 operation, and it turns out that the update rule is a natural generalization of the classic Powell symmetric Broyden (PSB) method from minimization problems to minimax problems. In theory, we show that our proposed quasi-Newton algorithm enjoys local Q-superlinear convergence to a desirable solution under standard regularity conditions. Furthermore, we introduce a trust-region variant of the algorithm that enjoys global R-superlinear convergence. Finally, we present numerical experiments that verify our theory and show the effectiveness of our proposed algorithms compared to Broyden's method and the extragradient method on three classes of minimax problems.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191