Coordinate Descent with Bandit Sampling

Understand

Coordinate descent methods usually minimize a cost function by updating a random decision variable (corresponding to one coordinate) at a time.

• Ideally, we would update the decision variable that yields the largest decrease in the cost function.
• However, finding this coordinate would require checking all of them, which would effectively negate the improvement in computational tractability that coordinate descent is intended to afford.
• To address this, we propose a new adaptive method for selecting a coordinate.