As soon as you exit the Dematolian Inn, to the north of you, you can find the Arena.
As with everything else in this series, just because you have the option to fight in here doesn't mean you have to. You will of course be able to fight the first couple of round for each fight type (i.e. doubles) at the beginning no problem. Past that, I advise you come back at a later time when you are stronger...
I repeat, you DON'T have to do all of these fights right now. The game is non-linear in that you will be able to come back here many times before the end of the game.