We study complexity classes of local problems on regular trees from the perspective of distributed local algorithms and descriptive combinatorics. We show that, surprisingly, some deterministic local complexity classes from the hierarchy of distributed computing exactly coincide with well studied classes of problems in descriptive combinatorics. Namely, we show that a local problem admits a continuous solution if and only if it admits a local algorithm with local complexity $O(\log^* n)$, and a Baire measurable solution if and only if it admits a local algorithm with local complexity $O(\log n)$.
相關內容
Established approaches to obtain generalization bounds in data-driven optimization and machine learning mostly build on solutions from empirical risk minimization (ERM), which depend crucially on the functional complexity of the hypothesis class. In this paper, we present an alternate route to obtain these bounds on the solution from distributionally robust optimization (DRO), a recent data-driven optimization framework based on worst-case analysis and the notion of ambiguity set to capture statistical uncertainty. In contrast to the hypothesis class complexity in ERM, our DRO bounds depend on the ambiguity set geometry and its compatibility with the true loss function. Notably, when using maximum mean discrepancy as a DRO distance metric, our analysis implies generalization bounds whose dependence on the hypothesis class appears the minimal possible: The bound depends solely on the true loss function, independent of any other candidates in the hypothesis class. To our best knowledge, it is the first generalization bound of this type in the literature, and we hope our findings can open the door for a better understanding of DRO, especially its benefits on loss minimization and other machine learning applications.
Joint Resource Allocation to Minimize Execution Time of Federated Learning in Cell-Free Massive MIMO
Due to its communication efficiency and privacy-preserving capability, federated learning (FL) has emerged as a promising framework for machine learning in 5G-and-beyond wireless networks. Of great interest is the design and optimization of new wireless network structures that support the stable and fast operation of FL. Cell-free massive multiple-input multiple-output (CFmMIMO) turns out to be a suitable candidate, which allows each communication round in the iterative FL process to be stably executed within a large-scale coherence time. Aiming to reduce the total execution time of the FL process in CFmMIMO, this paper proposes choosing only a subset of available users to participate in FL. An optimal selection of users with favorable link conditions would minimize the execution time of each communication round, while limiting the total number of communication rounds required. Toward this end, we formulate a joint optimization problem of user selection, transmit power, and processing frequency, subject to a predefined minimum number of participating users to guarantee the quality of learning. We then develop a new algorithm that is proven to converge to the neighbourhood of the stationary points of the formulated problem. Numerical results confirm that our proposed approach significantly reduces the FL total execution time over baseline schemes. The time reduction is more pronounced when the density of access point deployments is moderately low.
Graph signal processing is a framework to handle graph structured data. The fundamental concept is graph shift operator, giving rise to the graph Fourier transform. While the graph Fourier transform is a centralized procedure, distributed graph signal processing algorithms are needed to address challenges such as scalability and privacy. In this paper, we develop a theory of distributed graph signal processing based on the classical notion of message passing. However, we generalize the definition of a message to permit more abstract mathematical objects. The framework provides an alternative point of view that avoids the iterative nature of existing approaches to distributed graph signal processing. Moreover, our framework facilitates investigating theoretical questions such as solubility of distributed problems.
We describe a kernel of size 9k-8 for the NP-hard problem of computing the Tree Bisection and Reconnect (TBR) distance k between two unrooted binary phylogenetic trees. We achieve this by extending the existing portfolio of reduction rules with three novel new reduction rules. Two of the rules are based on the idea of topologically transforming the trees in a distance-preserving way in order to guarantee execution of earlier reduction rules. The third rule extends the local neighbourhood approach introduced in (Kelk and Linz, Annals of Combinatorics 24(3), 2020) to more global structures, allowing new situations to be identified when deletion of a leaf definitely reduces the TBR distance by one. The bound on the kernel size is tight up to an additive term. Our results also apply to the equivalent problem of computing a Maximum Agreement Forest (MAF) between two unrooted binary phylogenetic trees. We anticipate that our results will be more widely applicable for computing agreement-forest based dissimilarity measures.
Graph neural networks (GNNs) have recently achieved state-of-the-art performance in many graph-based applications. Despite the high expressive power, they typically need to perform an expensive recursive neighborhood expansion in multiple training epochs and face a scalability issue. Moreover, most of them are inflexible since they are restricted to fixed-hop neighborhoods and insensitive to actual receptive field demands for different nodes. We circumvent these limitations by introducing a scalable and flexible Graph Attention Multilayer Perceptron (GAMLP). With the separation of the non-linear transformation and feature propagation, GAMLP significantly improves the scalability and efficiency by performing the propagation procedure in a pre-compute manner. With three principled receptive field attention, each node in GAMLP is flexible and adaptive in leveraging the propagated features over the different sizes of reception field. We conduct extensive evaluations on the three large open graph benchmarks (e.g., ogbn-papers100M, ogbn-products and ogbn-mag), demonstrating that GAMLP not only achieves the state-of-art performance, but also additionally provide high scalability and efficiency.
Gene expression datasets are usually of high dimensionality and therefore require efficient and effective methods for identifying the relative importance of their attributes. Due to the huge size of the search space of the possible solutions, the attribute subset evaluation feature selection methods tend to be not applicable, so in these scenarios feature ranking methods are used. Most of the feature ranking methods described in the literature are univariate methods, so they do not detect interactions between factors. In this paper we propose two new multivariate feature ranking methods based on pairwise correlation and pairwise consistency, which we have applied in three gene expression classification problems. We statistically prove that the proposed methods outperform the state of the art feature ranking methods Clustering Variation, Chi Squared, Correlation, Information Gain, ReliefF and Significance, as well as feature selection methods of attribute subset evaluation based on correlation and consistency with multi-objective evolutionary search strategy.
Federated data analytics is a framework for distributed data analysis where a server compiles noisy responses from a group of distributed low-bandwidth user devices to estimate aggregate statistics. Two major challenges in this framework are privacy, since user data is often sensitive, and compression, since the user devices have low network bandwidth. Prior work has addressed these challenges separately by combining standard compression algorithms with known privacy mechanisms. In this work, we take a holistic look at the problem and design a family of privacy-aware compression mechanisms that work for any given communication budget. We first propose a mechanism for transmitting a single real number that has optimal variance under certain conditions. We then show how to extend it to metric differential privacy for location privacy use-cases, as well as vectors, for application to federated learning. Our experiments illustrate that our mechanism can lead to better utility vs. compression trade-offs for the same privacy loss in a number of settings.
The energy consumption of wireless networks is a growing concern. In massive MIMO systems, which are being increasingly deployed as part of the 5G roll-out, the power amplifiers in the base stations have a large impact in terms of power demands. Most of the current massive MIMO precoders are designed to minimize the transmit power. However, the efficiency of the power amplifiers depend on their operating regime with respect to their saturation regime, and the consumed power proves to be non-linearly related to the transmit power. Power consumption-based equivalents of maximum ratio transmission, zero-forcing, and regularized zero-forcing precoders are therefore proposed. We show how the structure of the solutions radically changes. While all antennas should be active in order to minimize the transmit power, we find on the contrary that a smaller number of antennas should be activated if the objective is the power consumed by the power amplifiers.
Exponential generalization bounds with near-tight rates have recently been established for uniformly stable learning algorithms. The notion of uniform stability, however, is stringent in the sense that it is invariant to the data-generating distribution. Under the weaker and distribution dependent notions of stability such as hypothesis stability and $L_2$-stability, the literature suggests that only polynomial generalization bounds are possible in general cases. The present paper addresses this long standing tension between these two regimes of results and makes progress towards relaxing it inside a classic framework of confidence-boosting. To this end, we first establish an in-expectation first moment generalization error bound for potentially randomized learning algorithms with $L_2$-stability, based on which we then show that a properly designed subbagging process leads to near-tight exponential generalization bounds over the randomness of both data and algorithm. We further substantialize these generic results to stochastic gradient descent (SGD) to derive improved high-probability generalization bounds for convex or non-convex optimization problems with natural time decaying learning rates, which have not been possible to prove with the existing hypothesis stability or uniform stability based results.
This paper focuses on improving the resource allocation algorithm in terms of packet delivery ratio (PDR), i.e., the number of successfully received packets sent by end devices (EDs) in a long-range wide-area network (LoRaWAN). Setting the transmission parameters significantly affects the PDR. Employing reinforcement learning (RL), we propose a resource allocation algorithm that enables the EDs to configure their transmission parameters in a distributed manner. We model the resource allocation problem as a multi-armed bandit (MAB) and then address it by proposing a two-phase algorithm named MIX-MAB, which consists of the exponential weights for exploration and exploitation (EXP3) and successive elimination (SE) algorithms. We evaluate the MIX-MAB performance through simulation results and compare it with other existing approaches. Numerical results show that the proposed solution performs better than the existing schemes in terms of convergence time and PDR.
小貼士
登錄享
相關主題
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191