IIUC, The paper's notation S^(d-1) means the unit sphere in R^d (e.g., the familiar unit circle is S^1 living in R^2). So, i think, x in the algorithm is already a unit vector.
Reference:
Section 2:Preliminaries
...
We use the notation S^d−1 to denote the hypersphere in R^d of radius 1.
Section 3.1
Let x ∈ S^d−1 be a (worst-case) vector on the unit sphere in dimension d.
Reference: Section 2:Preliminaries ... We use the notation S^d−1 to denote the hypersphere in R^d of radius 1.
Section 3.1 Let x ∈ S^d−1 be a (worst-case) vector on the unit sphere in dimension d.