We study the gauge invariance of physical observables in holographic theories under the local diffeomorphism. We find that gauge invariance is intimately related to the holographic renormalization: the local counter terms defined in the boundary cancel most of gauge dependences of the on-shell action as well as the divergences. There is a mismatch in the degrees of freedom between the bulk theory and the boundary one. We resolve this problem by noticing that there is a residual gauge symmetry (RGS). By extending the RGS such that it satisfies infalling boundary condition at the horizon, we can understand the problem in the context of general holographic embedding of a global symmetry at the boundary into the local gauge symmetry in the bulk. (C) 2015 The Authors. Published by Elsevier B.V.