Exit the room with the bonfire, turn left and clear the area of Witchtrees and the Frozen Porcupine hiding in the alcove behind the chest.
Enter the doorway to the building just over the bridge. Climb the steps, and you'll see a Shade carrying a lance and a greatshield. He'll waive to you, and he'll follow you around, but that's just a ploy. He's not your friend. Down a hallway and out a door, you'll find a lever. If you pull it while he's tagging along, he'll reveal his true nature as he backstabs you.
There are two ways to approach the fight with the Shade, and they hinge on a door.
The closed door method
The area around the Lower Garrison bonfire is closed off until you find and pull a lever to open up the massive doors leading to the next area. The advantage of fighting the Shade before opening the door is that it confines him to a relatively small area. The disadvantage is that the relatively small area is full of enemies. Engage in battle, and he won't hesitate to hop down to the lower levels and drink some Estus amid the Frozen Porcupines who won't attack him.
If you want to fight him now, it's best to kill the Fozen Porcupines and the Witchtrees that fill the area, so you and he can fight without interruption. Once he'd dead, reenter the room where you first encountered him, follow the hallway out of the room, exit through a doorway and pull the lever.
There's another — and arguably easier — way though.
The open door method
Exit the room with the Shade, cross a small wood bridge, run down a hallway and pull a lever. Doing so will give the Shade an opportunity to backstab and likely kill you. If you pull the lever and accept the backstab, his strategy will change from the above when you respawn. Hurt him, and he runs through the open doors and down a winding path to relative safety.
The Frozen Covetous Demon
Follow the Shade through the doors and down the path and hop off the short ledge. In the distance you'll see a Frozen Covetous Demon, a snow-covered version of the boss you encounter during the campaign in Earthen Peak. Use a projectile weapon to lure him to your position.
His move set remains the same, and your strategy should focus on locking on him and staying behind him. The key to fighting him in relative safety is to keep the fight close to the small ledge where you dropped off. The Shade is here, but he won't disturb you if you keep your distance.
Once the Frozen Covetous Demon is dead, collect the Ivory Warrior Ring x 1, which causes your attacks to reduce enemy stamina, and make you way to the back of the room to fight the Shade, using every opportunity for a backstab. Killing him includes the chance to drop Royal Swordsman Armor x 1.
When he's down, pillage the various corpses in the area for:
- Dried Root x 1
- Large Club + 8
- Twinkling Titanite x 2
- Dried Root x 1
- Crimson Water x 1
- Smooth & Silky Stone x 3
And continue on your path.