We consider the classical \emph{spherical} perceptrons and study their capacities. The famous zero-threshold case was solved in the sixties of the last century (see, \cite{Wendel62,Winder,Cover65}) through the high-dimensional combinatorial considerations. The general threshold, $\kappa$, case though turned out to be much harder and stayed out of reach for the following several decades. A substantial progress was then made in \cite{SchTir02} and \cite{StojnicGardGen13} where the \emph{positive} threshold ($\kappa\geq 0$) scenario was finally fully settled. While the negative counterpart ($\kappa\leq 0$) remained out of reach, \cite{StojnicGardGen13} did show that the random duality theory (RDT) is still powerful enough to provide excellent upper bounds. Moreover, in \cite{StojnicGardSphNeg13}, a \emph{partially lifted} RDT variant was considered and it was shown that the upper bounds of \cite{StojnicGardGen13} can be lowered. After recent breakthroughs in studying bilinearly indexed (bli) random processes in \cite{Stojnicsflgscompyx23,Stojnicnflgscompyx23}, \emph{fully lifted} random duality theory (fl RDT) was developed in \cite{Stojnicflrdt23}. We here first show that the \emph{negative spherical perceptrons} can be fitted into the frame of the fl RDT and then employ the whole fl RDT machinery to characterize the capacity. To be fully practically operational, the fl RDT requires a substantial numerical work. We, however, uncover remarkable closed form analytical relations among key lifting parameters. Such a discovery enables performing the needed numerical calculations to obtain concrete capacity values. We also observe that an excellent convergence (with the relative improvement $\sim 0.1\%$) is achieved already on the third (second non-trivial) level of the \emph{stationarized} full lifting.
相關內容
We consider the classical problems of interpolating a polynomial given a black box for evaluation, and of multiplying two polynomials, in the setting where the bit-lengths of the coefficients may vary widely, so-called unbalanced polynomials. Writing s for the total bit-length and D for the degree, our new algorithms have expected running time $\tilde{O}(s \log D)$, whereas previous methods for (resp.) dense or sparse arithmetic have at least $\tilde{O}(sD)$ or $\tilde{O}(s^2)$ bit complexity.
Improving a 2003 result of Bohman and Holzman, we show that for $n \geq 1$, the Shannon capacity of the complement of the $2n+1$-cycle is at least $(2^{r_n} + 1)^{1/r_n} = 2 + \Omega(2^{-r_n}/r_n)$, where $r_n = \exp(O((\log n)^2))$ is the number of partitions of $2(n-1)$ into powers of $2$.
By interpreting planar polynomial curves as complex-valued functions of a real parameter, an inner product, norm, metric function, and the notion of orthogonality may be defined for such curves. This approach is applied to the complex pre-image polynomials that generate planar Pythagorean-hodograph (PH) curves, to facilitate the implementation of bounded modifications of them that preserve their PH nature. The problems of bounded modifications under the constraint of fixed curve end points and end tangent directions, and of increasing the arc length of a PH curve by a prescribed amount, are also addressed.
The broad class of multivariate unified skew-normal (SUN) distributions has been recently shown to possess fundamental conjugacy properties. When used as priors for the vector of parameters in general probit, tobit, and multinomial probit models, these distributions yield posteriors that still belong to the SUN family. Although such a core result has led to important advancements in Bayesian inference and computation, its applicability beyond likelihoods associated with fully-observed, discretized, or censored realizations from multivariate Gaussian models remains yet unexplored. This article covers such an important gap by proving that the wider family of multivariate unified skew-elliptical (SUE) distributions, which extends SUNs to more general perturbations of elliptical densities, guarantees conjugacy for broader classes of models, beyond those relying on fully-observed, discretized or censored Gaussians. Such a result leverages the closure under linear combinations, conditioning and marginalization of SUE to prove that such a family is conjugate to the likelihood induced by general multivariate regression models for fully-observed, censored or dichotomized realizations from skew-elliptical distributions. This advancement substantially enlarges the set of models that enable conjugate Bayesian inference to general formulations arising from elliptical and skew-elliptical families, including the multivariate Student's t and skew-t, among others.
We analyze a Discontinuous Galerkin method for a problem with linear advection-reaction and $p$-type diffusion, with Sobolev indices $p\in (1, \infty)$. The discretization of the diffusion term is based on the full gradient including jump liftings and interior-penalty stabilization while, for the advective contribution, we consider a strengthened version of the classical upwind scheme. The developed error estimates track the dependence of the local contributions to the error on local P\'eclet numbers. A set of numerical tests supports the theoretical derivations.
Sine-skewed circular distributions are identifiable and have easily-computable trigonometric moments and a simple random number generation algorithm, whereas they are known to have relatively low levels of asymmetry. This study proposes a new family of circular distributions that can be skewed more significantly than that of existing models. It is shown that a subfamily of the proposed distributions is identifiable with respect to parameters and all distributions in the subfamily have explicit trigonometric moments and a simple random number generation algorithm. The maximum likelihood estimation for model parameters is considered and its finite sample performances are investigated by numerical simulations. Some real data applications are illustrated for practical purposes.
A method for analyzing non-asymptotic guarantees of numerical discretizations of ergodic SDEs in Wasserstein-2 distance is presented by Sanz-Serna and Zygalakis in ``Wasserstein distance estimates for the distributions of numerical approximations to ergodic stochastic differential equations". They analyze the UBU integrator which is strong order two and only requires one gradient evaluation per step, resulting in desirable non-asymptotic guarantees, in particular $\mathcal{O}(d^{1/4}\epsilon^{-1/2})$ steps to reach a distance of $\epsilon > 0$ in Wasserstein-2 distance away from the target distribution. However, there is a mistake in the local error estimates in Sanz-Serna and Zygalakis (2021), in particular, a stronger assumption is needed to achieve these complexity estimates. This note reconciles the theory with the dimension dependence observed in practice in many applications of interest.
In the realm of cost-sharing mechanisms, the vulnerability to Sybil strategies -- also known as false-name strategies, where agents create fake identities to manipulate outcomes -- has not yet been studied. In this paper, we delve into the details of different cost-sharing mechanisms proposed in the literature, highlighting their non-Sybil-resistant nature. Furthermore, we prove that a Sybil-proof cost-sharing mechanism for public excludable goods under mild conditions is at least $(n+1)/2-$approximate. This finding reveals an exponential increase in the worst-case social cost in environments where agents are restricted from using Sybil strategies. To circumvent these negative results, we introduce the concept of \textit{Sybil Welfare Invariant} mechanisms, where a mechanism does not decrease its welfare under Sybil-strategies when agents choose weak dominant strategies and have subjective prior beliefs over other players' actions. Finally, we prove that the Shapley value mechanism for symmetric and submodular cost functions holds this property, and so deduce that the worst-case social cost of this mechanism is the $n$th harmonic number $\mathcal H_n$ under equilibrium with Sybil strategies, matching the worst-case social cost bound for cost-sharing mechanisms. This finding suggests that any group of agents, each with private valuations, can fund public excludable goods both permissionless and anonymously, achieving efficiency comparable to that of permissioned and non-anonymous domains, even when the total number of participants is unknown.
This paper focuses on the inverse elastic impedance and the geometry problem by a Cauchy data pair on the access part of the boundary in a two-dimensional case. Through the decomposition of the displacement, the problem is transform the solution of into a coupled boundary value problem that involves two scalar Helmholtz equations. Firstly, a uniqueness result is given, and a non-iterative algorithm is proposed to solve the data completion problem using a Cauchy data pair on a known part of the solution domain's boundary. Next, we introduce a Newton-type iterative method for reconstructing the boundary and the impedance function using the completion data on the unknown boundary, which is governed by a specific type of boundary conditions. Finally, we provide several examples to demonstrate the effectiveness and accuracy of the proposed method.
We hypothesize that due to the greedy nature of learning in multi-modal deep neural networks, these models tend to rely on just one modality while under-fitting the other modalities. Such behavior is counter-intuitive and hurts the models' generalization, as we observe empirically. To estimate the model's dependence on each modality, we compute the gain on the accuracy when the model has access to it in addition to another modality. We refer to this gain as the conditional utilization rate. In the experiments, we consistently observe an imbalance in conditional utilization rates between modalities, across multiple tasks and architectures. Since conditional utilization rate cannot be computed efficiently during training, we introduce a proxy for it based on the pace at which the model learns from each modality, which we refer to as the conditional learning speed. We propose an algorithm to balance the conditional learning speeds between modalities during training and demonstrate that it indeed addresses the issue of greedy learning. The proposed algorithm improves the model's generalization on three datasets: Colored MNIST, Princeton ModelNet40, and NVIDIA Dynamic Hand Gesture.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191