Graph neural networks (GNNs) have recently emerged as powerful tools for solving complex optimization problems, often being employed to approximate solution mappings. Empirical evidence shows that even shallow GNNs (with fewer than ten layers) can achieve strong performance in predicting optimal solutions to linear programming (LP) problems. This finding is somewhat counter-intuitive, as LPs are global optimization problems, while shallow GNNs predict based on local information. Although previous theoretical results suggest that GNNs have the expressive power to solve LPs, they require deep architectures whose depth grows at least polynomially with the problem size, and thus leave the underlying principle of this empirical phenomenon still unclear. In this paper, we examine this phenomenon through the lens of distributed computing and average-case analysis. We establish that the expressive power of GNNs for LPs is closely related to well-studied distributed algorithms for LPs. Specifically, we show that any $d$-round distributed LP algorithm can be simulated by a $d$-depth GNN, and vice versa. In particular, by designing a new distributed LP algorithm and then unrolling it, we prove that constant-depth, constant-width GNNs suffice to solve sparse binary LPs effectively. Here, in contrast with previous analyses focusing on worst-case scenarios, in which we show that GNN depth must increase with problem size by leveraging an impossibility result about distributed LP algorithms, our analysis shifts the focus to the average-case performance, and shows that constant GNN depth then becomes sufficient no matter how large the problem size is. Our theory is validated by numerical results.

We propose Adam-mini, an optimizer that achieves on-par or better performance than AdamW with $50$% less memory footprint. Adam-mini reduces memory by cutting down the learning rate resources in Adam (i.e., $1/\sqrt{v}$). By delving into the Hessian structure of neural nets, we find Adam’s $v$ might not function at its full potential as effectively as we expected. We find that $\geq 99.9$% of these learning rates in $v$ could be harmlessly removed if we (1) carefully partition the parameters into blocks following our proposed principle on Hessian structure; (2) assign a single but good learning rate to each parameter block. We then provide one simple way to find good learning rates and propose Adam-mini. Empirically, we verify that Adam-mini performs on par or better than AdamW on various language models sized from 39M to 13B for pre-training, supervised fine-tuning, and RLHF. The reduced memory footprint of Adam-mini also alleviates communication overheads among GPUs, thereby increasing throughput. For instance, Adam-mini achieves $49.6$% higher throughput than AdamW when pre-training Llama 2-7B on $2\times$ A800-80GB GPUs, which saves 33% wall-clock time for pre-training.

Large reasoning models (LRMs) like OpenAI-o1 have shown impressive capabilities in natural language reasoning. However, these models frequently demonstrate inefficiencies or inaccuracies when tackling complex mathematical operations. While integrating computational tools such as Code Interpreters (CIs) offers a promising solution, it introduces a critical challenge: a conflict between the model's internal, probabilistic reasoning and the external, deterministic knowledge provided by the CI, which often leads models to unproductive deliberation. To overcome this, we introduce CoRT (Code-Optimized Reasoning Training), a post-training framework designed to teach LRMs to effectively utilize CIs. We propose **Hint-Engineering**, a new data synthesis strategy that strategically injects diverse hints at optimal points within reasoning paths. This approach generates high-quality, code-integrated reasoning data specifically tailored to optimize LRM-CI interaction. Using this method, we have synthesized 30 high-quality samples to post-train models ranging from 1.5B to 32B parameters through supervised fine-tuning. CoRT further refines the multi-round interleaving of external CI usage and internal thinking by employing rejection sampling and reinforcement learning. Our experimental evaluations demonstrate CoRT's effectiveness, yielding absolute improvements of 4\% and 8\% on DeepSeek-R1-Distill-Qwen-32B and DeepSeek-R1-Distill-Qwen-1.5B, respectively, across five challenging mathematical reasoning datasets. Moreover, CoRT significantly enhances efficiency, reducing token usage by approximately 30\% for the 32B model and 50\% for the 1.5B model compared to pure natural language reasoning baselines. The models and code are available at: [this url](https://github.com/ChengpengLi1003/CoRT).

Solving large-scale linear programming (LP) problems is an important task in various areas such as communication networks, power systems, finance and logistics. Recently, two distinct approaches have emerged to expedite LP solving: (i) First-order methods (FOMs); (ii) Learning to optimize (L2O). In this work, we propose an FOM-unrolled neural network (NN) called PDHG-Net, and propose a two-stage L2O method to solve large-scale LP problems. The new architecture PDHG-Net is designed by unrolling the recently emerged PDHG method into a neural network, combined with channel-expansion techniques borrowed from graph neural networks. We prove that the proposed PDHG-Net can recover PDHG algorithm, thus can approximate optimal solutions of LP instances with a polynomial number of neurons. We propose a two-stage inference approach: first use PDHG-Net to generate an approximate solution, and then apply PDHG algorithm to further improve the solution. Experiments show that our approach can significantly accelerate LP solving, achieving up to a 3$\times$ speedup compared to FOMs for large-scale LP problems.

Graph neural networks (GNNs) have recently emerged as powerful tools for addressing complex optimization problems. It has been theoretically demonstrated that GNNs can universally approximate the solution mapping functions of linear programming (LP) problems. However, these theoretical results typically require GNNs to have large parameter sizes. Conversely, empirical experiments have shown that relatively small GNNs can solve LPs effectively, revealing a significant discrepancy between theoretical predictions and practical observations. In this work, we aim to bridge this gap by providing a theoretical foundation for the effectiveness of small-size GNNs. We prove that polylogarithmic-depth, constant-width GNNs are sufficient to solve packing and covering LPs, two widely used classes of LPs. Our proof leverages the capability of GNNs to simulate a variant of the gradient descent algorithm on a carefully selected potential function. Additionally, we introduce a new GNN architecture, termed GD-Net. Experimental results demonstrate that GD-Net significantly outperforms conventional GNN structures while using fewer parameters.

SGD performs worse than Adam by a significant margin on Transformers, but the reason remains unclear. In this work, we provide an explanation through the lens of Hessian: (i) Transformers are "heterogeneous'': the Hessian spectrum across parameter blocks vary dramatically, a phenomenon we call "block heterogeneity"; (ii) Heterogeneity hampers SGD: SGD performs worse than Adam on problems with block heterogeneity. To validate (i) and (ii), we check various Transformers, CNNs, MLPs, and quadratic problems, and find that SGD can perform on par with Adam on problems without block heterogeneity, but performs worse than Adam when the heterogeneity exists. Our initial theoretical analysis indicates that SGD performs worse because it applies one single learning rate to all blocks, which cannot handle the heterogeneity among blocks. This limitation could be ameliorated if we use coordinate-wise learning rates, as designed in Adam.

Recently, federated learning (FL), which replaces data sharing with model sharing, has emerged as an efficient and privacy-friendly machine learning paradigm. One of the main challenges in FL is the huge communication cost for model aggregation. Many compression/quantization schemes have been proposed to reduce the communication cost of model aggregation, with remarkable results. However, the following two questions remain unanswered: What are the performance limits of model aggregation? How much can FL convergence performance be improved by modifying existing model aggregation schemes? In this paper, we manage to answer these two questions. Specifically, for the first question, we put forth a general model aggregation performance analysis framework based on the rate-distortion theory. We then derive an inner bound of the rate-distortion region of model aggregation. For the second question, we develop an algorithm to search for the minimum achievable aggregation distortion, which, combined with the achievability scheme of the derived inner bound, induces a method to approximate the limits of FL convergence performance numerically. Numerical results demonstrate that the baseline model aggregation schemes still have great potential for further improvement.

Recently, federated learning (FL), which replaces data sharing with model sharing, has emerged as an efficient and privacy-friendly machine learning (ML) paradigm. One of the main challenges in FL is the huge communication cost for model aggregation. Many compression/quantization schemes have been proposed to reduce the communication cost for model aggregation. However, the following question remains unanswered: What is the fundamental trade-off between the communication cost and the FL convergence performance? In this paper, we manage to answer this question. Specifically, we first put forth a general framework for model aggregation performance analysis based on the rate-distortion theory. Under the proposed analysis framework, we derive an inner bound of the rate-distortion region of model aggregation. We then conduct an FL convergence analysis to connect the aggregation distortion and the FL convergence performance. We formulate an aggregation distortion minimization problem to improve the FL convergence performance. Two algorithms are developed to solve the above problem. Numerical results on aggregation distortion, convergence performance, and communication cost demonstrate that the baseline model aggregation schemes still have great potential for further improvement.

In recent years, an increasing number of multiobjective evolutionary algorithms (MOEAs) have been developed for solving multiobjective optimization problems (MOPs). However, a special type of network-oriented MOPs, termed network multiobjective optimization problems (NMOPs), remains largely unexplored. In this paper, we put forth a general formulation for NMOPs, and propose the network decomposition-combination multiobjective optimization method (NDCMOM) for solving them. NDCMOM adopts a network decomposition mechanism, which breaks the NMOP down to a series of MOPs with smaller scales. The solutions to the NMOP can be obtained by combining the solutions to these smaller-scale MOPs. This decomposition-combination mechanism significantly improves the optimization efficiency. Experiments are conducted to demonstrate that the proposed NDCMOM outperforms the state-of-the-art MOEAs on large-scale NMOPs.

The unmanned aerial vehicle (UAV) cellular communications is a promising technique to boost coverage and realize intelligent applications. The communication power consumption is a major challenge faced by the UAV cellular networks. In this work, we consider a single UAV user equipment (UE) connected with a terrestrial base station (BS), and focus on the uplink (UL) performance. Through theoretical analysis, we find an optimal power control factor in terms of the communication energy efficiency, when the distance between the UAV and the BS is small.

In this paper, we study the multiuser detection (MUD) problem for a grant-free massive-device multiple access (MaDMA) system, where a large number of single-antenna user devices transmit sporadic data to a multi-antenna base station (BS). Specifically, we put forth two MUD schemes, termed random sparsity learning multiuser detection (RSL-MUD) and structured sparsity learning multiuser detection (SSL-MUD) for the time-slotted and non-time-slotted grant-free MaDMA systems, respectively. In RSL-MUD, active users generate and transmit data packets with random sparsity. In SSL-MUD, we introduce a sliding-window-based detection framework, and the user signals in each observation window naturally exhibit structured sparsity. We show that by exploiting the sparsity embedded in the user signals, we can recover the user activity state, the channel, and the user data in a single phase, without using pilot signals for channel estimation and/or active user identification. To this end, we develop a message-passing-based statistical inference framework for the BS to blindly detect the user data without any prior knowledge of the identities and the channel state information (CSI) of active users. The simulation results show that our RSL-MUD and SSL-MUD schemes significantly outperform their counterpart schemes in both reducing the transmission overhead and improving the error behavior of the system.

The study of full duplex (FD) is important because it has been identified as one of the candidate technologies for the 5th-generation (5G) networks. Small cell networks (SCNs) are envisioned to embrace the FD transmission technology in order to increase the spectral efficiency of wireless systems. In this paper, for the first time, we consider FD communications in a realistic small cell networks (SCN) scenario, where base stations (BSs) can select FD or half-duplex (HD) mode according to the real-time downlink (DL)/uplink (UL) traffic. We present analytical results on the probabilities of BS mode selection, which match the simulation results well.

In this work, we study the non-time-slotted massive-device multiple access (MaDMA) problem where massive user devices transmit sporadic data to a multi-antenna base station (BS). We develop a structured sparsity learning based multiuser detection (SSL-MUD) scheme. By exploiting the structured sparsity naturally embedded in user signals, our SSL-MUD scheme is able to blindly detect the user packets without any prior knowledge of the user activity state (UAS) and the channel state information (CSI), and hence significantly reduces the transmission overhead. For the blind signal detection at the BS, we put forth the turbo bilinear generalized approximate message passing (Turbo-BiG-AMP) algorithm. Simulation results demonstrate that the Turbo-BiG- AMP algorithm significantly outperforms the existing compressed sensing based approach and achieves a performance comparable to that of the oracle linear minimum mean-square error (Oracle- LMMSE) algorithm (which assumes perfect knowledge of UAS and CSI at the BS).

In this paper, we study the cache-aided cloud radio access network (C-RAN) with wireless fronthaul, where multiple cache-enabled users are served by multiple cache-enabled transmitters that are connected to a cloud processor through a wireless fronthaul link. We put forth a caching-and-delivery scheme that combines network-coded fronthaul transmission with cache-aided interference management. By broadcasting network-coded messages, the cloud processor provides additional information of the requested files to the transmitters, so as to reduce the edge delivery time. Based on our scheme, an achievable normalized delivery time (NDT) is derived with respect to the cache sizes and the fronthaul capacity.

In this paper, we analyze the coverage probability and the area spectral efficiency (ASE) for the uplink (UL) of dense small cell networks (SCNs) considering a practical path loss model incorporating both line-of-sight (LoS) and non-line-ofsight (NLoS) transmissions. Compared with the existing work, we adopt the following novel approaches in this paper: 1) we assume a practical user association strategy (UAS) based on the smallest path loss, or equivalently the strongest received signal strength; 2) we model the positions of both base stations (BSs) and the user equipments (UEs) as two independent homogeneous Poisson point processes; and 3) the correlation of BSs' and UEs' positions is considered, thus making our analytical results more accurate. The performance impact of LoS and NLoS transmissions on the ASE for the UL of dense SCNs is shown to be significant, both quantitatively and qualitatively, compared with existing work that does not differentiate LoS and NLoS transmissions. In particular, existing work predicted that a larger UL power compensation factor would always result in a better ASE in the practical range of BS density, i.e., 101~ 103BSs/km2. However, our results show that a smaller UL power compensation factor can greatly boost the ASE in the UL of dense SCNs, i.e., 102~ 103BSs/km2, while a larger UL power compensation factor is more suitable for sparse SCNs, i.e., 101 ~ 102 BSs/km2.

In this paper, we study the degrees of freedom (DoF) of the symmetric multi-relay multiple-input multiple-output Y channel, where three user nodes, each with M antennas, communicate via K geographically separated relay nodes, each with N antennas. For this model, we establish a general DoF achievability framework based on linear precoding and post-processing methods. The framework poses a nonlinear problem with respect to user precoders, user post-processors, and relay precoders. To solve this problem, we adopt an uplink-downlink asymmetric strategy, where the user precoders are designed for signal alignment and the user post-processors are used for interference neutralization. With the user precoder and post-processor designs fixed as such, the original problem then reduces to a problem of relay precoder design. To address the solvability of the system, we propose a general method for solving matrix equations. Together with the techniques of antenna disablement and symbol extension, an achievable DoF of the considered model is derived for an arbitrary setup of (K, M, N). We show that for K ≥ 2, the optimal DoF is achieved for (M/N) ∈ [0, max{(√(3K/3)), 1}) ∪ [((3K + (9K2- 12K)1/2)/6), ∞). We also show that the uplink-downlink asymmetric design proposed in this paper considerably outperforms the conventional approach based on uplink-downlink symmetry.

© 2002-2012 IEEE. In this paper, we analyze the coverage probability and the area spectral efficiency (ASE) for the uplink (UL) of dense small cell networks (SCNs) considering a practical path loss model incorporating both line-of-sight (LoS) and non-line-of-sight (NLoS) transmissions. Compared with the existing work, we adopt the following novel approaches in this paper: 1) we assume a practical user association strategy (UAS) based on the smallest path loss, or equivalently the strongest received signal strength; 2) we model the positions of both base stations (BSs) and the user equipments (UEs) as two independent homogeneous Poisson point processes; and 3) the correlation of BSs' and UEs' positions is considered, thus making our analytical results more accurate. The performance impact of LoS and NLoS transmissions on the ASE for the UL of dense SCNs is shown to be significant, both quantitatively and qualitatively, compared with existing work that does not differentiate LoS and NLoS transmissions. In particular, existing work predicted that a larger UL power compensation factor would always result in a better ASE in the practical range of BS density, i.e., 10-1∼ 10-3 BSs/km2. However, our results show that a smaller UL power compensation factor can greatly boost the ASE in the UL of dense SCNs, i.e., 10-2∼ 10-3 BSs/km2 , while a larger UL power compensation factor is more suitable for sparse SCNs, i.e., 10-1∼ 10-2,BSs/km-2.

We study the degrees of freedom (DoF) of a symmetric multi-relay multiple-input multiple-output (MIMO) Y channel, where three users, each equipped with M antennas, exchange messages via multiple geographically separated relay nodes, each with N antennas. We formulate a general DoF achievability problem assuming the use of linear precoding and post-processing. To solve this problem, we present a new uplink-downlink asymmetric strategy where the user precoders are designed for signal alignment and the user post-processors are used for interference neutralization. Based on that, we derive an achievable DoF of the considered model for an arbitrary antenna setup. The optimality of the derived DoF is established under certain antenna configurations. Also, we show that our design considerably outperforms the conventional uplink-downlink symmetric design.

Abstract In side‐channel attacks, information about any intermediate data except the target data will be considered as noise, namely, the “algorithmic noise.” Algorithmic noise is always assumed to be independent of the target data. As a result, it is thought to be an equivalence of physical noise. Numerous investigations are built on this intuitive assumption. In this paper, we claim that this assumption is not always true and find the algorithm (e.g., SIMON) for which the algorithmic noise is dependent on the target data. On this condition, we reconsider the issue of success rate estimation and build a modified statistical model to accurately estimate the success rate when the algorithmic noise is dependent on the target data. Finally, experimental results for SIMON algorithm validate the soundness of our methodology. It is also worth mentioning that SIMON is a candidate proposed by the National Security Agency as the standard light‐weight block cipher. Copyright © 2016 John Wiley & Sons, Ltd.

In this paper two-path relay channels with direct link between the source and the destination are considered. We present a decode-and-forward cooperative transmission scheme based on nested lattice codes. The proposed scheme performs complete inter-relay interference (IRI) cancellation at the relays as well as successive decoding at the destination, which efficiently combines the signals from the source and the relays. We derive the achievable rates of the proposed scheme, and show that our scheme considerably outperforms the existing schemes in the literature.