  Block coordinate descent is a powerful algorithmic template suitable for big
data optimization. This template admits a lot of variants including block
gradient descent (BGD), which performs gradient descent on a selected block of
variables, while keeping other variables fixed. For a very long time, the
stepsize for each block has tacitly been set to one divided by the block-wise
Lipschitz smoothness constant, imitating the vanilla stepsize rule for gradient
descent (GD). However, such a choice for BGD has not yet been able to
theoretically justify its empirical superiority over GD, as existing
convergence rates for BGD have worse constants than GD in the deterministic
cases.
  To discover such theoretical justification, we set up a simple environment
where we consider BGD applied to least-squares with two blocks of variables.
Assuming the data matrix corresponding to each block is orthogonal, we find
optimal stepsizes of BGD in closed form, which provably lead to asymptotic
convergence rates twice as fast as GD with Polyak's momentum; this means, under
that orthogonality assumption, one can accelerate BGD by just tuning stepsizes
and without adding any momentum. An application that satisfies this assumption
is \textit{generalized alternating projection} between two subspaces, and
applying our stepsizes to it improves the prior convergence rate that was once
claimed, slightly inaccurately, to be optimal. The main proof idea is to
minimize, in stepsize variables, the spectral radius of a matrix that controls
convergence rates.
