This paper addresses the problem of distributed training of a machine learning model over the nodes of a wireless communication network. Existing distributed training methods are not explicitly designed for these networks, which usually have physical limitations on bandwidth, delay, or computation, thus hindering or even blocking the training tasks. To address such a problem, we consider a general class of algorithms where the training is performed by iterative distributed computations across the nodes. We assume that the nodes have some background traffic and communicate using the slotted-ALOHA protocol. We propose an iteration-termination criterion to investigate the trade-off between achievable training performance and the overall cost of running the algorithms. We show that, given a total running budget, the training performance becomes worse as either the background communication traffic or the dimension of the training problem increases. We conclude that a co-design of distributed optimization algorithms and communication protocols is essential for the success of machine learning over wireless networks and edge computing.