The Frontier Caverns are located just beyond The Shadow Fort and you must travel through The Shadow Fort to reach it. There are many quests that will have you travel to the fort. From Gran Soren you can go through the The Ancient Quarry's north entrance and once through then head northwest, through the forest. Once the quest A Fortress Besieged has been completed, there won't be any enemies left in the fort. Otherwise, it will be full of Goblins and Cyclops.
Once inside The Shadow Fort area, there is a Goblin-dug tunnel just to the right of the fort doors that you can fit in just before the fort entrance. Drop down the hole and follow the cave to the Frontier Caverns. The hand icon in the map image below points to the entrance to the tunnel:
- The cavern is full of Goblins and Hobgoblins, and there's quite a bit of gold too. Eventually the Caverns will end into the Proving Grounds, it's usually closed. Unless a quest is activated, or you've reached post-dragon.
- There are 2 quests that can open the gate at the bottom of the stairs: Put the Eye Out and A Challenge.