I'd say Cornell, Austin and Madison are all (more or less) equally well known for their CS program, but specifically in Machine Learning I do not know. Ask your professors that do Machine Learning, read papers and talk to professors. At this point, word of mouth is the best way to learn about this kind of stuff.
I have a first author publication in a top security conference, strong letters and I got rejected from Berkeley and Stanford. It isn't clear cut, ever.
Not sure. I applied there (haven't heard anything though).
EDIT: I was one of the GaTech acceptances. I went through the College of Computing and I applied to Security or Database Systems.
Are interviews standard in Computer Science? Is this an individual faculty member scouting a recruit, or is everyone who will be admitted going to be interviewed?