In this paper, a new algorithm for distributed multi-target tracking in a sensor network is proposed. The main feature of that algorithm, combining the SPSA techniques and iterative averaging ("consensus algorithm"), is the ability to solve distributed optimization problems in presence of signals with fully uncertain distribution; the only assumption is the signal's boundedness. As an example, we consider the multi-target tracking problem, in which the unknown signals include measurement errors and unpredictable target's maneuvers; statistical properties of these signals are unknown. A special choice of weights in the algorithm enables its application to targets exhibiting different behaviors. An explicit estimate of the residual's covariance matrix is obtained, which may be considered as a performance index of the algorithm. Theoretical results are illustrated by numerical simulations.