  This paper presents NCOTA-DGD, a Decentralized Gradient Descent (DGD)
algorithm that combines local gradient descent with a novel Non-Coherent
Over-The-Air (NCOTA) consensus scheme to solve distributed machine-learning
problems over wirelessly-connected systems. NCOTA-DGD leverages the waveform
superposition properties of the wireless channels: it enables simultaneous
transmissions under half-duplex constraints, by mapping local optimization
signals to a mixture of preamble sequences, and consensus via non-coherent
combining at the receivers. NCOTA-DGD operates without channel state
information at transmitters and receivers, and leverages the average channel
pathloss to mix signals, without explicit knowledge of the mixing weights
(typically known in consensus-based optimization algorithms). It is shown both
theoretically and numerically that, for smooth and strongly-convex problems
with fixed consensus and learning stepsizes, the updates of NCOTA-DGD converge
in Euclidean distance to the global optimum with rate $\mathcal O(K^{-1/4})$
for a target of $K$ iterations. NCOTA-DGD is evaluated numerically over a
logistic regression problem, showing faster convergence vis-\`a-vis running
time than implementations of the classical DGD algorithm over digital and
analog orthogonal channels.
