Regret analysis of an online majorized semi-proximal ADMM for online composite optimization

An online majorized semi-proximal alternating direction method of multiplier (Online-mspADMM) is proposed for a broad class of online linearly constrained composite optimization problems. A majorized technique is adopted to produce subproblems which can be easily solved. Under mild assumptions, we establish \(\mathcal {O}(\sqrt{N})\) $\mathcal{O}(\sqrt{N})$ objective regret and \(\mathcal {O}(\sqrt{N})\) $\mathcal{O}(\sqrt{N})$ constraint violation regret at round N. We apply the Online-mspADMM to solve different types of online regularized logistic regression problems. The numerical results on synthetic data sets verify the theoretical result about regrets.