Online Geometric Optimization via Projection, Hierarchical Discretization, and Convex Relaxation

We study online optimization problems in which a learner must choose a compressed representation before observing each incoming data point. We focus on two settings: online $k$-means clustering and online weighted low-rank approximation (WLRA). For online $k$-means, we revisit multiplicative-weights methods over discretized experts and show how marginal Johnson–Lindenstrauss projections reduce the effective dimension without requiring uniform distance preservation over the entire stream. We further decouple projected Voronoi assignment from ambient center recovery by maintaining Follow-the-Leader centroids directly in ${\mathbb{R}}^d$, avoiding pseudo-inverse distortion. For online WLRA, we formulate the rank-$k$ comparator class as the Grassmannian $\mathrm{Gr}(k,d)$ and develop a hierarchical region decomposition coupled with tree-structured multiplicative weights. This yields sublinear regret against the best fixed rank-$k$ subspace, while making explicit the exponential cost of Grassmannian discretization. A second Grassmannian algorithm obtains a $(1+\epsilon )$ comparison using a number of regions independent of the horizon. We then introduce a Fantope relaxation that gives polynomial-time online updates and sublinear regret for a weighted projection surrogate against a reduced fractional comparator. Together, these results give a unified view of online approximation under nonconvex geometric structure, supported by empirical evaluations on online low-rank approximation.