PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Alternating Direction Method

Huahua Wang, Arindam Banerjee

arXiv:1206.6448v1cs.LGstat.ML

TL;DR

The paper addresses online composite optimization with linear equality constraints, where standard online methods do not explicitly handle such constraints. It introduces single-pass online ADM algorithms and proves objective and constraint-violation regret bounds, while also establishing an O(1/T) batch ADM rate. The paper applies OADM to lasso and total variation, with scope constrained by additional assumptions in some settings.

  • Problem

    Existing online methods do not explicitly handle linear equality constraints, while exact per-round constrained updates can require iterative inner procedures.

  • Method

    The paper develops single-pass online ADM algorithms for two scenarios, using ADM's augmented-Lagrangian structure and analyzing objective and constraint-violation regret.

  • Results

    The paper establishes O(1/T) convergence for batch ADM and regret bounds for objective and constraint violation with general and strongly convex functions.

  • Takeaways & Limitations

    OADM extends online composite optimization to problems with linear equality constraints and supports applications including lasso and total variation.

  • Takeaways & Limitations

    Some regret bounds require additional assumptions, including conditions on B and g; the η = 0 scenario assumes A is square and full rank.

Abstract

from arXiv · show

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.

1. Introduction

The paper develops online alternating direction methods for large-scale composite optimization with linear equality constraints. It introduces OADM algorithms, regret analyses for objective and constraint violation, and preliminary experiments.

  • ADM handles linear equality constraints, enabling distributed optimization through variable splitting in batch settings.
  • The paper introduces efficient online ADM algorithms that make one pass through the updates instead of using a double loop.
  • OADM establishes regret bounds for both objective loss and constraint violation for general and strongly convex functions.
  • The paper analyzes batch ADM, develops online regret results, compares OADM with FOBOS and RDA, and reports preliminary experiments.
  • OADM matches existing online composite-optimization regret bounds while additionally handling linear equality constraints for distributed online optimization.

2. Analysis for Batch ADM

The batch ADM analysis separates objective and constraint convergence and uses a variational-inequality proof to establish an O(1/T) convergence rate. Iterates may remain infeasible at finite steps even though constraint residuals vanish asymptotically.

  • Batch ADM iteratively updates primal and dual variables using an augmented Lagrangian with penalty parameter ρ.
  • The equality constraint need not hold at each iteration, but its residual converges to zero in the long run.
  • The new proof analyzes objective and constraint convergence separately before combining them through a variational inequality.
  • Theorem 1 bounds cumulative objective differences and cumulative constraint residual norms by constants independent of T.
  • Objective values converge to the optimum, although the individual primal iterates need not satisfy the equality constraint.
  • The average iterate after T iterations satisfies the variational inequality with error ϵ = O(1/T).

3. Online ADM

OADM adapts ADM to online, time-varying convex optimization by using a single update pass and allowing equality constraints to be satisfied in the long run. The framework analyzes objective and constraint-violation regret in two feasible-set scenarios.

  • The online problem uses fixed constraint matrices A and B while the loss function f_t changes across rounds.
  • The x-update combines a quadratic penalty with a Bregman-divergence term, which can be linearized when efficient solution of the update is difficult.
  • Solving each regularized online problem exactly with batch ADM would create a double loop, motivating the single-pass OADM updates.
  • OADM permits equality constraints to be satisfied only in the long run and assigns regret to cumulative constraint violation.
  • Each round presents primal and dual variables, then measures both the loss f_t(x_t) + g(z_t) and the residual ∥Ax_t + Bz_t − c∥_2.
  • The framework supports composite objectives with regularizers or convex-set indicators, including generalized lasso, group lasso, robust PCA, and consensus optimization.
  • The analysis assumes bounded subgradients, nonnegative regularization normalized at z_0, initialized variables, and a lower-bound condition on per-round objective differences.

4. Regret Analysis of OADM

OADM analyzes regret for both split-variable objectives and linear-constraint violations. General convex analysis yields sublinear bounds, while logarithmic bounds require strong convexity conditions.

  • OADM considers objective regret from variable splitting and a separate regret measure for constraint violation.
  • General Convex Functions: O(T) regret bounds are established for both the objective and constraint violation under general convex assumptions.
  • General Convex Functions: The bounds require bounded subgradients for f_t but not for g, allowing g to be an indicator of a convex set.
  • General Convex Functions: The constraint-violation bound can become constant under additional assumptions on B and g's subgradient.
  • Strongly Convex Functions: Logarithmic regret bounds are established when both f_t and g are strongly convex, unlike COMID, FOBOS, and RDA's unconstrained analyses.

5. Regret Analysis of OADM with η = 0

With η = 0, OADM uses ADM updates while computing a feasible x-hat from z_t. This enables analysis of feasible objective regret, with logarithmic bounds possible under weaker curvature requirements.

  • When η = 0, OADM has the same updates as ADM and treats z_t as the key primal variable.
  • The algorithm computes x-hat_t from z_t so that the pair satisfies A x-hat_t + B z_t = c.
  • The feasible construction supports regret analysis for x-hat_t and z_t, while the original pair may still violate the equality constraint.
  • A must be invertible to establish the feasible-solution regret bound R2, requiring a square, full-rank matrix.
  • The feasible update requires solving a linear system each iteration, though it is efficient in settings such as consensus optimization where A = I.
  • Strongly Convex Functions: Theorem 6 establishes a logarithmic regret bound without requiring f_t to be strongly convex when g is strongly convex.

6. Connections to Related Work

Under A = I, B = −I, and c = 0, OADM reduces to a constrained form with x = z. Its implicit subgradient updates contrast with FOBOS's explicit, current-point linearization.

  • Setting η = 0, A = I, B = −I, and c = 0 reduces OADM's constraint to x = z.
  • OADM uses implicit subgradients of f_t and g evaluated at the yet-undetermined next iterates.
  • FOBOS instead takes the explicit subgradient of f_t at the current iterate z_t.
  • FOBOS can be viewed as an inexact OADM method that linearizes the objective at z_t.
  • When g is an indicator of a convex set, substituting the scaled update recovers FOBOS and projected gradient descent.

7. Experimental Results

The experiments apply OADM to generalized lasso problems, including lasso and total variation, and compare its convergence, sparsity, and pattern recovery with batch ADM, FOBOS, and RDA. OADM satisfies the online equality constraints, approaches the target sparsity, and generally produces smoother or more trend-following patterns.

  • Setup: OADM solves generalized lasso problems, including lasso and total variation, while comparisons include batch ADM, FOBOS, and RDA.The experiments evaluate objective and constraint convergence, sparse-dimension selection, and total-variation recovery.
  • Setup: OADM’s three updates require O(n) flops, versus batch ADM’s x-update complexity of up to O(n^3) or O(n^2) with cached factorizations.The online updates are not run in parallel.
  • Convergence: NNZs converge near the actual k = 100 before t = 2000, while objective values converge quickly and equality constraints and primal residuals are eventually satisfied.The equality constraints take relatively longer to converge than the objective.
  • Sparsity: OADM is closest to the actual NNZ count of 100, whereas ADM and RDA are sparsest and FOBOS produces many oscillating nonzeros.The comparison uses N = 100, n = 1000, and q = 0.5, averaged over 20 runs.
  • Total Variation: OADM produces smoother total-variation patterns that generally follow the underlying trend, while ADM oscillates and RDA tends to produce flat patterns.FOBOS works well on the first two examples, but FOBOS and RDA both oscillate on the last example.

8. Conclusions

The paper proposes OADM and develops convergence and regret analyses for online optimization. It also demonstrates OADM on lasso and total variation problems.

  • Contributions: OADM is an efficient online learning algorithm based on alternating directions.The paper names the method online ADM (OADM).
  • Contributions: A new proof technique establishes an O(1/T) convergence rate for batch ADM.The same proof technique supports the online regret analysis.
  • Contributions: For general and strongly convex functions, OADM has regret bounds for both objective values and constraint violation.These bounds are established for the online setting.
  • Contributions: Preliminary experiments illustrate OADM on lasso and total variation.The conclusion describes these results as an illustration of efficacy.

A. Proof of Rate of Convergence of ADM

The appendix derives ADM’s convergence rate by combining variational inequalities from the x- and z-updates, summing the resulting inequality over iterations, and dividing by T.

  • Proof setup: The proof begins with variational inequalities corresponding separately to the x_{t+1} and z_{t+1} updates.The inequalities hold for all x ∈ X and z ∈ Z, respectively.
  • Proof setup: Adding the two update inequalities and defining h(w) = f(x) + g(z) produces a joint inequality over w ∈ Ω.This combines the two block updates into one analysis.
  • Telescoping argument: The proof rewrites the resulting terms, substitutes those identities, and sums the inequality over t.The appendix labels these algebraic steps as equations (39)–(41).
  • Rate conclusion: Dividing the summed inequality by T establishes ADM’s convergence rate.The derivation uses convexity of h and of the relevant variational-inequality expression.
Loading 1206.6448v1…