Infinitary and cyclic proof systems are proof systems for logical formulas with fixed-point operators or inductive definitions. A cyclic proof system is a restriction of the corresponding infinitary proof system. Hence, these proof systems are generally not the same, as in the cyclic system may be weaker than the infinitary system. For several logics, the infinitary proof systems are shown to be cut-free complete. However, cyclic proof systems are characterized with many unknown problems on the (cut-free) completeness or the cut-elimination property. In this study, we show that the provability of infinitary and cyclic proof systems are the same for some propositional logics with fixed-point operators or inductive definitions and that the cyclic proof systems are cut-free complete.
相關內容
We study the identification of binary choice models with fixed effects. We provide a condition called sign saturation and show that this condition is sufficient for the identification of the model. In particular, we can guarantee identification even with bounded regressors. We also show that without this condition, the model is not identified unless the error distribution belongs to a small class. The same sign saturation condition is also essential for identifying the sign of treatment effects. A test is provided to check the sign saturation condition and can be implemented using existing algorithms for the maximum score estimator.
Generative diffusion models apply the concept of Langevin dynamics in physics to machine leaning, attracting a lot of interests from engineering, statistics and physics, but a complete picture about inherent mechanisms is still lacking. In this paper, we provide a transparent physics analysis of diffusion models, formulating the fluctuation theorem, entropy production, equilibrium measure, and Franz-Parisi potential to understand the dynamic process and intrinsic phase transitions. Our analysis is rooted in a path integral representation of both forward and backward dynamics, and in treating the reverse diffusion generative process as a statistical inference, where the time-dependent state variables serve as quenched disorder akin to that in spin glass theory. Our study thus links stochastic thermodynamics, statistical inference and geometry based analysis together to yield a coherent picture about how the generative diffusion models work.
Understanding the capabilities of classical simulation methods is key to identifying where quantum computers are advantageous. Not only does this ensure that quantum computers are used only where necessary, but also one can potentially identify subroutines that can be offloaded onto a classical device. In this work, we show that it is always possible to generate a classical surrogate of a sub-region (dubbed a "patch") of an expectation landscape produced by a parameterized quantum circuit. That is, we provide a quantum-enhanced classical algorithm which, after simple measurements on a quantum device, allows one to classically simulate approximate expectation values of a subregion of a landscape. We provide time and sample complexity guarantees for a range of families of circuits of interest, and further numerically demonstrate our simulation algorithms on an exactly verifiable simulation of a Hamiltonian variational ansatz and long-time dynamics simulation on a 127-qubit heavy-hex topology.
This paper proposes multi-target filtering algorithms in which target dynamics are given in continuous time and measurements are obtained at discrete time instants. In particular, targets appear according to a Poisson point process (PPP) in time with a given Gaussian spatial distribution, targets move according to a general time-invariant linear stochastic differential equation, and the life span of each target is modelled with an exponential distribution. For this multi-target dynamic model, we derive the distribution of the set of new born targets and calculate closed-form expressions for the best fitting mean and covariance of each target at its time of birth by minimising the Kullback-Leibler divergence via moment matching. This yields a novel Gaussian continuous-discrete Poisson multi-Bernoulli mixture (PMBM) filter, and its approximations based on Poisson multi-Bernoulli and probability hypothesis density filtering. These continuous-discrete multi-target filters are also extended to target dynamics driven by nonlinear stochastic differential equations.
Approximating a univariate function on the interval $[-1,1]$ with a polynomial is among the most classical problems in numerical analysis. When the function evaluations come with noise, a least-squares fit is known to reduce the effect of noise as more samples are taken. The generic algorithm for the least-squares problem requires $O(Nn^2)$ operations, where $N+1$ is the number of sample points and $n$ is the degree of the polynomial approximant. This algorithm is unstable when $n$ is large, for example $n\gg \sqrt{N}$ for equispaced sample points. In this study, we blend numerical analysis and statistics to introduce a stable and fast $O(N\log N)$ algorithm called NoisyChebtrunc based on the Chebyshev interpolation. It has the same error reduction effect as least-squares and the convergence is spectral until the error reaches $O(\sigma \sqrt{{n}/{N}})$, where $\sigma$ is the noise level, after which the error continues to decrease at the Monte-Carlo $O(1/\sqrt{N})$ rate. To determine the polynomial degree, NoisyChebtrunc employs a statistical criterion, namely Mallows' $C_p$. We analyze NoisyChebtrunc in terms of the variance and concentration in the infinity norm to the underlying noiseless function. These results show that with high probability the infinity-norm error is bounded by a small constant times $\sigma \sqrt{{n}/{N}}$, when the noise {is} independent and follows a subgaussian or subexponential distribution. We illustrate the performance of NoisyChebtrunc with numerical experiments.
Adaptive cubic regularization methods for solving nonconvex problems need the efficient computation of the trial step, involving the minimization of a cubic model. We propose a new approach in which this model is minimized in a low dimensional subspace that, in contrast to classic approaches, is reused for a number of iterations. Whenever the trial step produced by the low-dimensional minimization process is unsatisfactory, we employ a regularized Newton step whose regularization parameter is a by-product of the model minimization over the low-dimensional subspace. We show that the worst-case complexity of classic cubic regularized methods is preserved, despite the possible regularized Newton steps. We focus on the large class of problems for which (sparse) direct linear system solvers are available and provide several experimental results showing the very large gains of our new approach when compared to standard implementations of adaptive cubic regularization methods based on direct linear solvers. Our first choice as projection space for the low-dimensional model minimization is the polynomial Krylov subspace; nonetheless, we also explore the use of rational Krylov subspaces in case where the polynomial ones lead to less competitive numerical results.
We propose a quadrature-based formula for computing the exponential function of matrices with a non-oscillatory integral on an infinite interval and an oscillatory integral on a finite interval. In the literature, existing quadrature-based formulas are based on the inverse Laplace transform or the Fourier transform. We show these expressions are essentially equivalent in terms of complex integrals and choose the former as a starting point to reduce computational cost. By choosing a simple integral path, we derive an integral expression mentioned above. Then, we can easily apply the double-exponential formula and the Gauss-Legendre formula, which have rigorous error bounds. As numerical experiments show, the proposed formula outperforms the existing formulas when the imaginary parts of the eigenvalues of matrices have large absolute values.
The problem of distributed matrix multiplication with straggler tolerance over finite fields is considered, focusing on field sizes for which previous solutions were not applicable (for instance, the field of two elements). We employ Reed-Muller-type codes for explicitly constructing the desired algorithms and study their parameters by translating the problem into a combinatorial problem involving sums of discrete convex sets. We generalize polynomial codes and matdot codes, discussing the impossibility of the latter being applicable for very small field sizes, while providing optimal solutions for some regimes of parameters in both cases.
This paper investigates logical consequence defined in terms of probability distributions, for a classical propositional language using a standard notion of probability. We examine three distinct probabilistic consequence notions, which we call material consequence, preservation consequence, and symmetric consequence. While material consequence is fully classical for any threshold, preservation consequence and symmetric consequence are subclassical, with only symmetric consequence gradually approaching classical logic at the limit threshold equal to 1. Our results extend earlier results obtained by J. Paris in a SET-FMLA setting to the SET-SET setting, and consider open thresholds beside closed ones. In the SET-SET setting, in particular, they reveal that probability 1 preservation does not yield classical logic, but supervaluationism, and conversely positive probability preservation yields subvaluationism.
Parameter inference is essential when interpreting observational data using mathematical models. Standard inference methods for differential equation models typically rely on obtaining repeated numerical solutions of the differential equation(s). Recent results have explored how numerical truncation error can have major, detrimental, and sometimes hidden impacts on likelihood-based inference by introducing false local maxima into the log-likelihood function. We present a straightforward approach for inference that eliminates the need for solving the underlying differential equations, thereby completely avoiding the impact of truncation error. Open-access Jupyter notebooks, available on GitHub, allow others to implement this method for a broad class of widely-used models to interpret biological data.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191