Motivated by emerging decentralized applications, the game of coding framework has been recently introduced to address scenarios where the adversary's control over coded symbols surpasses the fundamental limits of traditional coding theory. Still, the reward mechanism available in decentralized systems, motivates the adversary to act rationally. While the decoder, as the data collector (DC), has an acceptance/rejection mechanism, followed by an estimation module, the adversary aims to maximize its utility, as an increasing function of (1) the chance of acceptance (to increase the reward), and (2) estimation error. On the other hand, the decoder also adjusts its acceptance rule to maximize its own utility, as (1) an increasing function of the chance of acceptance (to keep the system functional), (2) decreasing function of the estimation error. Prior works within this framework rely on the assumption that the game is complete—that is, both the DC and the adversary are fully aware of each other's utility functions. However, in practice, the decoder is often unaware of the utility of the adversary. To address this limitation, we develop an algorithm enabling the DC to commit to a strategy that achieves within the vicinity of the equilibrium, without knowledge of the adversary's utility function. Our approach builds on an observation that at the equilibrium, the relationship between the probability of acceptance and the mean squared error (MSE) follows a predetermined curve independent of the specific utility functions of the players. By exploiting this invariant relationship, the DC can iteratively refine its strategy based on observable parameters, converging to a near-optimal solution. We provide theoretical guarantees on sample complexity and accuracy of the proposed scheme.

Coded computing has demonstrated promising results in addressing straggler resiliency in distributed computing systems. However, most coded computing schemes are designed for exact computation, requiring the number of responding servers to exceed a certain recovery threshold. Additionally, these schemes are tailored to highly structured functions. Recently, new coded computing schemes for general computing functions, where exact computation is replaced with approximate computation, have emerged. In these schemes, the availability of additional results leads to more accurate estimations of the computational tasks. This flexibility introduces new questions that need to be addressed. This paper considers a practically important scenario in the context of general coded computing, where each server may become a straggler with probability$p$, independently of others. We theoretically analyze the approximation error of two existing general coded computing schemes: Berrut Approximate Coded Computing (BACC) and Learning-Theoretic Coded Computing (LeTCC). Under the probabilistic straggler configuration, we demonstrate that the average approximation error for BACC and LeTCC converges to zero at rates of at least$\mathcal{O}\left(\log _{1 / p}^{4}(N) \cdot N^{-2}\right)$and$\mathcal{O}\left(\log _{1 / p}^{3}(N) \cdot N^{-3}\right)$, respectively. This is perhaps surprising, as earlier results do not indicate convergence when the number of stragglers scales with the total number of servers$N$. However, in this case, despite the average number of stragglers being$N p$, the independence of servers in becoming stragglers allows the approximation error to converge to zero. These theoretical results are validated through experiments on various computational tasks, including deep neural networks.

In this paper, we investigate the adversarial robustness of nonparametric regression, a fundamental problem in machine learning, under the setting where an adversary can arbitrarily corrupt a subset of the input data. While the robustness of parametric regression has been extensively studied, its nonparametric counterpart remains largely unexplored. We characterize the adversarial robustness in nonparametric regression, assuming the regression function belongs to the second-order Sobolev space (i.e., it is square integrable up to its second derivative). The contribution of this paper is two-fold: (i) we establish a minimax lower bound on the estimation error, revealing a fundamental limit that no estimator can overcome, and (ii) we show that, perhaps surprisingly, the classical smoothing spline estimator, when properly regularized, exhibits robustness against adversarial corruption. These results imply that if $o(n)$ out of $n$ samples are corrupted, the estimation error of the smoothing spline vanishes as $n \to \infty$. On the other hand, when a constant fraction of the data is corrupted, no estimator can guarantee vanishing estimation error, implying the optimality of the smoothing spline in terms of maximum tolerable number of corrupted samples.

Coded computing has emerged as a promising framework for tackling significant challenges in large-scale distributed computing, including the presence of slow, faulty, or compromised servers. In this approach, each worker node processes a combination of the data, rather than the raw data itself. The final result then is decoded from the collective outputs of the worker nodes. However, there is a significant gap between current coded computing approaches and the broader landscape of general distributed computing, particularly when it comes to machine learning workloads. To bridge this gap, we propose a novel foundation for coded computing, integrating the principles of learning theory, and developing a framework that seamlessly adapts with machine learning applications. In this framework, the objective is to find the encoder and decoder functions that minimize the loss function, defined as the mean squared error between the estimated and true values. Facilitating the search for the optimum decoding and functions, we show that the loss function can be upper-bounded by the summation of two terms: the generalization error of the decoding function and the training error of the encoding function. Focusing on the second-order Sobolev space, we then derive the optimal encoder and decoder. We show that in the proposed solution, the mean squared error of the estimation decays with the rate of $\mathcal{O}(S^3 N^{-3})$ and $\mathcal{O}(S^{\frac{8}{5}}N^{\frac{-3}{5}})$ in noiseless and noisy computation settings, respectively, where $N$ is the number of worker nodes with at most $S$ slow servers (stragglers). Finally, we evaluate the proposed scheme on inference tasks for various machine learning models and demonstrate that the proposed framework outperforms the state-of-the-art in terms of accuracy and rate of convergence.

MOTIVATION: The molecular mechanisms of self-organization that orchestrate embryonic cells to create astonishing patterns have been among major questions of developmental biology. It is recently shown that embryonic stem cells (ESCs), when cultured in particular micropatterns, can self-organize and mimic the early steps of pre-implantation embryogenesis. A systems-biology model to address this observation from a dynamical systems perspective is essential and can enhance understanding of the phenomenon. RESULTS: Here, we propose a multicellular mathematical model for pattern formation during in vitro gastrulation of human ESCs. This model enhances the basic principles of Waddington epigenetic landscape with cell-cell communication, in order to enable pattern and tissue formation. We have shown the sufficiency of a simple mechanism by using a minimal number of parameters in the model, in order to address a variety of experimental observations such as the formation of three germ layers and trophectoderm, responses to altered culture conditions and micropattern diameters and unexpected spotted forms of the germ layers under certain conditions. Moreover, we have tested different boundary conditions as well as various shapes, observing that the pattern is initiated from the boundary and gradually spreads towards the center. This model provides a basis for in-silico modeling of self-organization. AVAILABILITY AND IMPLEMENTATION: https://github.com/HFooladi/Self_Organization. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.