亚洲男人的天堂2018av,欧美草比,久久久久久免费视频精选,国色天香在线看免费,久久久久亚洲av成人片仓井空

We give a simple and computationally efficient algorithm that, for any constant $\varepsilon>0$, obtains $\varepsilon T$-swap regret within only $T = \mathsf{polylog}(n)$ rounds; this is an exponential improvement compared to the super-linear number of rounds required by the state-of-the-art algorithm, and resolves the main open problem of [Blum and Mansour 2007]. Our algorithm has an exponential dependence on $\varepsilon$, but we prove a new, matching lower bound. Our algorithm for swap regret implies faster convergence to $\varepsilon$-Correlated Equilibrium ($\varepsilon$-CE) in several regimes: For normal form two-player games with $n$ actions, it implies the first uncoupled dynamics that converges to the set of $\varepsilon$-CE in polylogarithmic rounds; a $\mathsf{polylog}(n)$-bit communication protocol for $\varepsilon$-CE in two-player games (resolving an open problem mentioned by [Babichenko-Rubinstein'2017, Goos-Rubinstein'2018, Ganor-CS'2018]); and an $\tilde{O}(n)$-query algorithm for $\varepsilon$-CE (resolving an open problem of [Babichenko'2020] and obtaining the first separation between $\varepsilon$-CE and $\varepsilon$-Nash equilibrium in the query complexity model). For extensive-form games, our algorithm implies a PTAS for $\mathit{normal}$ $\mathit{form}$ $\mathit{correlated}$ $\mathit{equilibria}$, a solution concept often conjectured to be computationally intractable (e.g. [Stengel-Forges'08, Fujii'23]).

For a graph $ G = (V, E) $ with vertex set $ V $ and edge set $ E $, a function $ f : V \rightarrow \{0, 1, 2, . . . , diam(G)\} $ is called a \emph{broadcast} on $ G $. For each vertex $ u \in V $, if there exists a vertex $ v $ in $ G $ (possibly, $ u = v $) such that $ f (v) > 0 $ and $ d(u, v) \leq f (v) $, then $ f $ is called a \textit{dominating broadcast} on $ G $. The \textit{cost} of the dominating broadcast $f$ is the quantity $ \sum_{v\in V}f(v) $. The minimum cost of a dominating broadcast is the \textit{broadcast domination number} of $G$, denoted by $ \gamma_{b}(G) $. A \textit{multipacking} is a set $ S \subseteq V $ in a graph $ G = (V, E) $ such that for every vertex $ v \in V $ and for every integer $ r \geq 1 $, the ball of radius $ r $ around $ v $ contains at most $ r $ vertices of $ S $, that is, there are at most $ r $ vertices in $ S $ at a distance at most $ r $ from $ v $ in $ G $. The \textit{multipacking number} of $ G $ is the maximum cardinality of a multipacking of $ G $ and is denoted by $ mp(G) $. We show that, for any cactus graph $G$, $\gamma_b(G)\leq \frac{3}{2}mp(G)+\frac{11}{2}$. We also show that $\gamma_b(G)-mp(G)$ can be arbitrarily large for cactus graphs by constructing an infinite family of cactus graphs such that the ratio $\gamma_b(G)/mp(G)=4/3$, with $mp(G)$ arbitrarily large. This result shows that, for cactus graphs, we cannot improve the bound $\gamma_b(G)\leq \frac{3}{2}mp(G)+\frac{11}{2}$ to a bound in the form $\gamma_b(G)\leq c_1\cdot mp(G)+c_2$, for any constant $c_1<4/3$ and $c_2$. Moreover, we provide an $O(n)$-time algorithm to construct a multipacking of $G$ of size at least $ \frac{2}{3}mp(G)-\frac{11}{3} $, where $n$ is the number of vertices of the graph $G$.

A family of stabilizer-free $P_k$ virtual elements are constructed on triangular meshes. When choosing an accurate and proper interpolation, the stabilizer of the virtual elements can be dropped while the quasi-optimality is kept. The interpolating space here is the space of continuous $P_k$ polynomials on the Hsieh-Clough-Tocher macro-triangle, where the macro-triangle is defined by connecting three vertices of a triangle with its barycenter. We show that such an interpolation preserves $P_k$ polynomials locally and enforces the coerciveness of the resulting bilinear form. Consequently the stabilizer-free virtual element solutions converge at the optimal order. Numerical tests are provided to confirm the theory and to be compared with existing virtual elements.

The fractional differential equation $L^\beta u = f$ posed on a compact metric graph is considered, where $\beta>0$ and $L = \kappa^2 - \nabla(a\nabla)$ is a second-order elliptic operator equipped with certain vertex conditions and sufficiently smooth and positive coefficients $\kappa, a$. We demonstrate the existence of a unique solution for a general class of vertex conditions and derive the regularity of the solution in the specific case of Kirchhoff vertex conditions. These results are extended to the stochastic setting when $f$ is replaced by Gaussian white noise. For the deterministic and stochastic settings under generalized Kirchhoff vertex conditions, we propose a numerical solution based on a finite element approximation combined with a rational approximation of the fractional power $L^{-\beta}$. For the resulting approximation, the strong error is analyzed in the deterministic case, and the strong mean squared error as well as the $L_2(\Gamma\times \Gamma)$-error of the covariance function of the solution are analyzed in the stochastic setting. Explicit rates of convergences are derived for all cases. Numerical experiments for ${L = \kappa^2 - \Delta, \kappa>0}$ are performed to illustrate the results.

Learning nonparametric systems of Ordinary Differential Equations (ODEs) dot x = f(t,x) from noisy data is an emerging machine learning topic. We use the well-developed theory of Reproducing Kernel Hilbert Spaces (RKHS) to define candidates for f for which the solution of the ODE exists and is unique. Learning f consists of solving a constrained optimization problem in an RKHS. We propose a penalty method that iteratively uses the Representer theorem and Euler approximations to provide a numerical solution. We prove a generalization bound for the L2 distance between x and its estimator and provide experimental comparisons with the state-of-the-art.

Let $A$ be a sparse Hermitian matrix, $f(x)$ be a univariate function, and $i, j$ be two indices. In this work, we investigate the query complexity of approximating $\bra{i} f(A) \ket{j}$. We show that for any continuous function $f(x):[-1,1]\rightarrow [-1,1]$, the quantum query complexity of computing $\bra{i} f(A) \ket{j}\pm \varepsilon/4$ is lower bounded by $\Omega(\widetilde{\deg}_\varepsilon(f))$. The upper bound is at most quadratic in $\widetilde{\deg}_\varepsilon(f)$ and is linear in $\widetilde{\deg}_\varepsilon(f)$ under certain mild assumptions on $A$. Here the approximate degree $\widetilde{\deg}_\varepsilon(f)$ is the minimum degree such that there is a polynomial of that degree approximating $f$ up to additive error $\varepsilon$ in the interval $[-1,1]$. We also show that the classical query complexity is lower bounded by $\widetilde{\Omega}(2^{\widetilde{\deg}_{2\varepsilon}(f)/6})$. Our results show that the quantum and classical separation is exponential for any continuous function of sparse Hermitian matrices, and also imply the optimality of implementing smooth functions of sparse Hermitian matrices by quantum singular value transformation. The main techniques we used are the dual polynomial method for functions over the reals, linear semi-infinite programming, and tridiagonal matrices.

This paper develops the notion of \emph{Word Linear Complexity} ($WLC$) of vector valued sequences over finite fields $\ff$ as an extension of Linear Complexity ($LC$) of sequences and their ensembles. This notion of complexity extends the concept of the minimal polynomial of an ensemble (vector valued) sequence to that of a matrix minimal polynomial and shows that the matrix minimal polynomial can be used with iteratively generated vector valued sequences by maps $F:\ff^n\rightarrow\ff^n$ at a given $y$ in $\ff^n$ for solving the unique local inverse $x$ of the equation $y=F(x)$ when the sequence is periodic. The idea of solving a local inverse of a map in finite fields when the iterative sequence is periodic and its application to various problems of Cryptanalysis is developed in previous papers \cite{sule322, sule521, sule722,suleCAM22} using the well known notion of $LC$ of sequences. $LC$ is the degree of the associated minimal polynomial of the sequence. The generalization of $LC$ to $WLC$ considers vector valued (or word oriented) sequences such that the word oriented recurrence relation is obtained by matrix vector multiplication instead of scalar multiplication as considered in the definition of $LC$. Hence the associated minimal polynomial is matrix valued whose degree is called $WLC$. A condition is derived when a nontrivial matrix polynomial associated with the word oriented recurrence relation exists when the sequence is periodic. It is shown that when the matrix minimal polynomial exists $n(WLC)=LC$. Finally it is shown that the local inversion problem is solved using the matrix minimal polynomial when such a polynomail exists hence leads to a word oriented approach to local inversion.

We extend a certain type of identities on sums of $I$-Bessel functions on lattices, previously given by G. Chinta, J. Jorgenson, A Karlsson and M. Neuhauser. Moreover we prove that, with continuum limit, the transformation formulas of theta functions such as the Dedekind eta function can be given by $I$-Bessel lattice sum identities with characters. We consider analogues of theta functions of lattices coming from linear codes and show that sums of $I$-Bessel functions defined by linear codes can be expressed by complete weight enumerators. We also prove that $I$-Bessel lattice sums appear as solutions of heat equations on general lattices. As a further application, we obtain an explicit solution of the heat equation on $\mathbb{Z}^n$ whose initial condition is given by a linear code.

We consider inverse problems where the conditional distribution of the observation ${\bf y}$ given the latent variable of interest ${\bf x}$ (also known as the forward model) is known, and we have access to a data set in which multiple instances of ${\bf x}$ and ${\bf y}$ are both observed. In this context, algorithm unrolling has become a very popular approach for designing state-of-the-art deep neural network architectures that effectively exploit the forward model. We analyze the statistical complexity of the gradient descent network (GDN), an algorithm unrolling architecture driven by proximal gradient descent. We show that the unrolling depth needed for the optimal statistical performance of GDNs is of order $\log(n)/\log(\varrho_n^{-1})$, where $n$ is the sample size, and $\varrho_n$ is the convergence rate of the corresponding gradient descent algorithm. We also show that when the negative log-density of the latent variable ${\bf x}$ has a simple proximal operator, then a GDN unrolled at depth $D'$ can solve the inverse problem at the parametric rate $O(D'/\sqrt{n})$. Our results thus also suggest that algorithm unrolling models are prone to overfitting as the unrolling depth $D'$ increases. We provide several examples to illustrate these results.

An edge $e$ of a graph $G$ is called deletable for some orientation $o$ if the restriction of $o$ to $G-e$ is a strong orientation. Inspired by a problem of Frank, in 2021 H\"orsch and Szigeti proposed a new parameter for $3$-edge-connected graphs, called the Frank number, which refines $k$-edge-connectivity. The Frank number is defined as the minimum number of orientations of $G$ for which every edge of $G$ is deletable in at least one of them. They showed that every $3$-edge-connected graph has Frank number at most $7$ and that in case these graphs are also $3$-edge-colourable the parameter is at most $3$. Here we strengthen both results by showing that every $3$-edge-connected graph has Frank number at most $4$ and that every graph which is $3$-edge-connected and $3$-edge-colourable has Frank number $2$. The latter also confirms a conjecture by Bar\'at and Bl\'azsik. Furthermore, we prove two sufficient conditions for cubic graphs to have Frank number $2$ and use them in an algorithm to computationally show that the Petersen graph is the only cyclically $4$-edge-connected cubic graph up to $36$ vertices having Frank number greater than $2$.