Online Alternating Direction Method (longer version)

Abstract

Online optimization has emerged as powerful tool in large scale optimization. In this pa- per, we introduce efficient online optimization algorithms based on the alternating direction method (ADM), which can solve online convex optimization under linear constraints where the objective could be non-smooth. We introduce new proof techniques for ADM in the batch setting, which yields a O(1/T) convergence rate for ADM and forms the basis for regret anal- ysis in the online setting. We consider two scenarios in the online setting, based on whether an additional Bregman divergence is needed or not. In both settings, we establish regret bounds for both the objective function as well as constraints violation for general and strongly convex functions. We also consider inexact ADM updates where certain terms are linearized to yield efficient updates and show the stochastic convergence rates. In addition, we briefly discuss that online ADM can be used as projection- free online learning algorithm in some scenarios. Preliminary results are presented to illustrate the performance of the proposed algorithms.

Longer version of arXiv:1206.6448

References in corpus (2)

• On the Linear Convergence of the Alternating Direction Method of Multipliers
• Online Alternating Direction Method

Cited by in corpus (8)

• Zeroth-Order Online Alternating Direction Method of Multipliers: Convergence Analysis and Applications
• A Modularized Efficient Framework for Non-Markov Time Series Estimation
• Adaptive Algorithms for Online Convex Optimization with Long-term Constraints
• Fast Stochastic Variance Reduced ADMM for Stochastic Composition Optimization
• SI-ADMM: A Stochastic Inexact ADMM Framework for Stochastic Convex Programs
• Scalable Peaceman-Rachford Splitting Method with Proximal Terms
• DessiLBI: Exploring Structural Sparsity of Deep Networks via Differential Inclusion Paths
• Distributed Online Learning with Multiple Kernels