  Conventionally, in a differentially private additive noise mechanism,
independent and identically distributed (i.i.d.) noise samples are added to
each coordinate of the response. In this work, we formally present the addition
of noise which is independent, but not identically distributed (i.n.i.d.)
across the coordinates to achieve tighter privacy-accuracy trade-off by
exploiting coordinate-wise disparity. In particular, we study the i.n.i.d.
Gaussian and Laplace mechanisms and obtain the conditions under which these
mechanisms guarantee privacy. The optimal choice of parameters that ensure
these conditions are derived theoretically. Theoretical analyses and numerical
simulations demonstrate that the i.n.i.d. mechanisms achieve higher utility for
the given privacy requirements compared to their i.i.d. counterparts. One of
the interesting observations is that the Laplace mechanism outperforms Gaussian
even in high dimensions, as opposed to the popular belief, if the irregularity
in coordinate-wise sensitivities is exploited. We also demonstrate how the
i.n.i.d. noise can improve the performance in the private empirical risk
minimization through coordinate descent.
