This paper characterizes the trade-offs between information and energy transmission over an additive white Gaussian noise channel in the finite block-length regime with finite sets of channel input symbols. These trade-offs are characterized using impossibility and achievability bounds on the information transmission rate, energy transmission rate, decoding error probability (DEP) and energy outage probability (EOP) for a finite block-length code. Given a set of channel input symbols, the impossibility results identify the tuples of information rate, energy rate, DEP and EOP that cannot be achieved by any code using the given set of channel inputs. A novel method for constructing a family of codes that satisfy a target information rate, energy rate, DEP and EOP is also proposed. The achievability bounds identify the set of tuples of information rate, energy rate, DEP and EOP that can be simultaneously achieved by the constructed family of codes. The proposed construction matches the impossibility bounds for the information rate, energy rate, and the EOP. However, for a given information rate, energy rate and EOP, the achieved DEP is higher than the impossibility bound due to the choice of the decoding sets made during the code construction.
In this paper, we present a coded computation (CC) scheme for distributed computation of the inference phase of machine learning (ML) tasks, specifically, the task of image classification. Building upon Agrawal et al.~2022, the proposed scheme combines the strengths of deep learning and Lagrange interpolation technique to mitigate the effect of straggling workers, and recovers approximate results with reasonable accuracy using outputs from any $R$ out of $N$ workers, where $R\leq N$. Our proposed scheme guarantees a minimum recovery threshold $R$ for non-polynomial problems, which can be adjusted as a tunable parameter in the system. Moreover, unlike existing schemes, our scheme maintains flexibility with respect to worker availability and system design. We propose two system designs for our CC scheme that allows flexibility in distributing the computational load between the master and the workers based on the accessibility of input data. Our experimental results demonstrate the superiority of our scheme compared to the state-of-the-art CC schemes for image classification tasks, and pave the path for designing new schemes for distributed computation of any general ML classification tasks.
We study parameterisation-independent closed planar curve matching as a Bayesian inverse problem. The motion of the curve is modelled via a curve on the diffeomorphism group acting on the ambient space, leading to a large deformation diffeomorphic metric mapping (LDDMM) functional penalising the kinetic energy of the deformation. We solve Hamilton's equations for the curve matching problem using the Wu-Xu element [S. Wu, J. Xu, Nonconforming finite element spaces for $2m^\text{th}$ order partial differential equations on $\mathbb{R}^n$ simplicial grids when $m=n+1$, Mathematics of Computation 88 (316) (2019) 531-551] which provides mesh-independent Lipschitz constants for the forward motion of the curve, and solve the inverse problem for the momentum using Bayesian inversion. Since this element is not affine-equivalent we provide a pullback theory which expedites the implementation and efficiency of the forward map. We adopt ensemble Kalman inversion using a negative Sobolev norm mismatch penalty to measure the discrepancy between the target and the ensemble mean shape. We provide several numerical examples to validate the approach.
This article investigates uncertainty quantification of the generalized linear lasso~(GLL), a popular variable selection method in high-dimensional regression settings. In many fields of study, researchers use data-driven methods to select a subset of variables that are most likely to be associated with a response variable. However, such variable selection methods can introduce bias and increase the likelihood of false positives, leading to incorrect conclusions. In this paper, we propose a post-selection inference framework that addresses these issues and allows for valid statistical inference after variable selection using GLL. We show that our method provides accurate $p$-values and confidence intervals, while maintaining high statistical power. In a second stage, we focus on the sparse logistic regression, a popular classifier in high-dimensional statistics. We show with extensive numerical simulations that SIGLE is more powerful than state-of-the-art PSI methods. SIGLE relies on a new method to sample states from the distribution of observations conditional on the selection event. This method is based on a simulated annealing strategy whose energy is given by the first order conditions of the logistic lasso.
This paper focuses on the problem of coflow scheduling with precedence constraints in identical parallel networks, which is a well-known $\mathcal{NP}$-hard problem. Coflow is a relatively new network abstraction used to characterize communication patterns in data centers. Both flow-level scheduling and coflow-level scheduling problems are examined, with the key distinction being the scheduling granularity. The proposed algorithm effectively determines the scheduling order of coflows by employing the primal-dual method. When considering workload sizes and weights that are dependent on the network topology in the input instances, our proposed algorithm for the flow-level scheduling problem achieves an approximation ratio of $O(\chi)$ where $\chi$ is the coflow number of the longest path in the directed acyclic graph (DAG). Additionally, when taking into account workload sizes that are topology-dependent, the algorithm achieves an approximation ratio of $O(R\chi)$, where $R$ represents the ratio of maximum weight to minimum weight. For the coflow-level scheduling problem, the proposed algorithm achieves an approximation ratio of $O(m\chi)$, where $m$ is the number of network cores, when considering workload sizes and weights that are topology-dependent. Moreover, when considering workload sizes that are topology-dependent, the algorithm achieves an approximation ratio of $O(Rm\chi)$. In the coflows of multi-stage job scheduling problem, the proposed algorithm achieves an approximation ratio of $O(\chi)$. Although our theoretical results are based on a limited set of input instances, experimental findings show that the results for general input instances outperform the theoretical results, thereby demonstrating the effectiveness and practicality of the proposed algorithm.
It is known that results on universal sampling discretization of the square norm are useful in sparse sampling recovery with error measured in the square norm. In this paper we demonstrate how known results on universal sampling discretization of the uniform norm and recent results on universal sampling representation allow us to provide good universal methods of sampling recovery for anisotropic Sobolev and Nikol'skii classes of periodic functions of several variables. The sharpest results are obtained in the case of functions on two variables, where the Fibonacci point sets are used for recovery.
Approximating significance scans of searches for new particles in high-energy physics experiments as Gaussian fields is a well-established way to estimate the trials factors required to quantify global significances. We propose a novel, highly efficient method to estimate the covariance matrix of such a Gaussian field. The method is based on the linear approximation of statistical fluctuations of the signal amplitude. For one-dimensional searches the upper bound on the trials factor can then be calculated directly from the covariance matrix. For higher dimensions, the Gaussian process described by this covariance matrix may be sampled to calculate the trials factor directly. This method also serves as the theoretical basis for a recent study of the trials factor with an empirically constructed set of Asmiov-like background datasets. We illustrate the method with studies of a $H \rightarrow \gamma \gamma$ inspired model that was used in the empirical paper.
This paper introduces a novel paradigm for constructing linearly implicit and high-order unconditionally energy-stable schemes for general gradient flows, utilizing the scalar auxiliary variable (SAV) approach and the additive Runge-Kutta (ARK) methods. We provide a rigorous proof of energy stability, unique solvability, and convergence. The proposed schemes generalizes some recently developed high-order, energy-stable schemes and address their shortcomings. On the one other hand, the proposed schemes can incorporate existing SAV-RK type methods after judiciously selecting the Butcher tables of ARK methods \cite{sav_li,sav_nlsw}. The order of a SAV-RKPC method can thus be confirmed theoretically by the order conditions of the corresponding ARK method. Several new schemes are constructed based on our framework, which perform to be more stable than existing SAV-RK type methods. On the other hand, the proposed schemes do not limit to a specific form of the nonlinear part of the free energy and can achieve high order with fewer intermediate stages compared to the convex splitting ARK methods \cite{csrk}. Numerical experiments demonstrate stability and efficiency of proposed schemes.
In this work, a novel analysis of a hybrid discontinuous Galerkin method for the Helmholtz equation is presented. It uses wavenumber, mesh size and polynomial degree independent stabilisation parameters leading to impedance traces between elements. With analysis techniques based on projection operators unique discrete solvability without a resolution condition and optimal convergence rates with respect to the mesh size are proven. The considered method is tailored towards enabling static condensation and the usage of iterative solvers.
We present an efficient matrix-free geometric multigrid method for the elastic Helmholtz equation, and a suitable discretization. Many discretization methods had been considered in the literature for the Helmholtz equations, as well as many solvers and preconditioners, some of which are adapted for the elastic version of the equation. However, there is very little work considering the reciprocity of discretization and a solver. In this work, we aim to bridge this gap. By choosing an appropriate stencil for re-discretization of the equation on the coarse grid, we develop a multigrid method that can be easily implemented as matrix-free, relying on stencils rather than sparse matrices. This is crucial for efficient implementation on modern hardware. Using two-grid local Fourier analysis, we validate the compatibility of our discretization with our solver, and tune a choice of weights for the stencil for which the convergence rate of the multigrid cycle is optimal. It results in a scalable multigrid preconditioner that can tackle large real-world 3D scenarios.
It is always well believed that modeling relationships between objects would be helpful for representing and eventually describing an image. Nevertheless, there has not been evidence in support of the idea on image description generation. In this paper, we introduce a new design to explore the connections between objects for image captioning under the umbrella of attention-based encoder-decoder framework. Specifically, we present Graph Convolutional Networks plus Long Short-Term Memory (dubbed as GCN-LSTM) architecture that novelly integrates both semantic and spatial object relationships into image encoder. Technically, we build graphs over the detected objects in an image based on their spatial and semantic connections. The representations of each region proposed on objects are then refined by leveraging graph structure through GCN. With the learnt region-level features, our GCN-LSTM capitalizes on LSTM-based captioning framework with attention mechanism for sentence generation. Extensive experiments are conducted on COCO image captioning dataset, and superior results are reported when comparing to state-of-the-art approaches. More remarkably, GCN-LSTM increases CIDEr-D performance from 120.1% to 128.7% on COCO testing set.