Online Alternating Direction Method

Abstract

Online optimization has emerged as powerful tool in large scale optimization. In this paper, we introduce efficient online algorithms based on the alternating directions method (ADM). We introduce a new proof technique for ADM in the batch setting, which yields the O(1/T) convergence rate of ADM and forms the basis of regret analysis in the online setting. We consider two scenarios in the online setting, based on whether the solution needs to lie in the feasible set or not. In both settings, we establish regret bounds for both the objective function as well as constraint violation for general and strongly convex functions. Preliminary results are presented to illustrate the performance of the proposed algorithms.

Appears in Proceedings of the 29th International Conference on Machine Learning (ICML 2012)

References in corpus (1)

• The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices

Cited by in corpus (29)

• An Online Convex Optimization Approach to Dynamic Network Resource Allocation
• A General Analysis of the Convergence of ADMM
• Online Learning: A Comprehensive Survey
• Online Energy Price Matrix Factorization for Power Grid Topology Tracking
• Online Alternating Direction Method (longer version)
• Accelerated Variance Reduced Stochastic ADMM
• Convergence of multi-block Bregman ADMM for nonconvex composite problems
• Fast Stochastic Alternating Direction Method of Multipliers
• A Stochastic Alternating Direction Method of Multipliers for Non-smooth and Non-convex Optimization
• Decentralized Sparse Multitask RLS over Networks
• Scalable Stochastic Alternating Direction Method of Multipliers
• One-Pass Learning with Incremental and Decremental Features
• Matrix-Free Solvers for Exact Penalty Subproblems
• Stochastic Alternating Direction Method of Multipliers with Variance Reduction for Nonconvex Optimization
• Adaptive Algorithms for Online Convex Optimization with Long-term Constraints
• Stochastic Primal-Dual Proximal ExtraGradient Descent for Compositely Regularized Optimization
• Stochastic Dual Coordinate Ascent with Alternating Direction Multiplier Method
• Adaptive Stochastic Alternating Direction Method of Multipliers
• Phase Balancing Using Energy Storage in Power Grids under Uncertainty
• Decomposition Methods for Large Scale LP Decoding
• Stochastic Variance-Reduced ADMM
• Sparse Learning with Semi-Proximal-Based Strictly Contractive Peaceman-Rachford Splitting Method
• Accelerated Stochastic ADMM with Variance Reduction
• ADMM LP decoding of non-binary LDPC codes in ${\mathbb{F}}_{2^m}$
• The proximal-proximal gradient algorithm
• Distributed Optimization Using the Primal-Dual Method of Multipliers
• Online and stochastic Douglas-Rachford splitting method for large scale machine learning
• Properties of Pseudocontractive Updates in Convex Optimization
• Online and Stochastic Universal Gradient Methods for Minimizing Regularized Hölder Continuous Finite Sums