It is shown that the generation linewidth of an auto-oscillator with a nonlinear frequency shift (i.e., an auto-oscillator in which frequency depends on the oscillation amplitude) is substantially larger than the linewidth of a conventional quasilinear auto-oscillator due to the renormalization of the phase noise caused by the nonlinearity of the oscillation frequency. The developed theory, when applied to a spin-torque auto-oscillator, gives a good description of experimentally measured angular and temperature dependences of the linewidth.