PaperlayerView exact revision on arXiv

Source-linked AI summary

Adaptive Alternating Minimization Algorithms

Urs Niesen, Devavrat Shah, Gregory Wornell

arXiv:cs/0701043v2cs.ITmath.ITmath.OC

TL;DR

The paper addresses alternating minimization when the optimization sets change over time, extending the fixed-parameter setting. It studies an adaptive version and gives sufficient conditions for convergence and correctness, with applications in mixture decomposition, portfolio selection, and filter design.

Abstract

from arXiv · show

The classical alternating minimization (or projection) algorithm has been successful in the context of solving optimization problems over two variables. The iterative nature and simplicity of the algorithm has led to its application to many areas such as signal processing, information theory, control, and finance. A general set of sufficient conditions for the convergence and correctness of the algorithm is quite well-known when the underlying problem parameters are fixed. In many practical situations, however, the underlying problem parameters are changing over time, and the use of an adaptive algorithm is more appropriate. In this paper, we study such an adaptive version of the alternating minimization algorithm. As a main result of this paper, we provide a general set of sufficient conditions for the convergence and correctness of the adaptive algorithm. Perhaps surprisingly, these conditions seem to be the minimal ones one would expect in such an adaptive setting. We present applications of our results to adaptive decomposition of mixtures, adaptive log-optimal portfolio selection, and adaptive filter design.

I. INTRODUCTION

Alternating minimization is a simple iterative approach to two-variable optimization, but changing problem parameters motivate an adaptive version. The paper gives sufficient convergence conditions for that version and frames its goal in terms of the limiting optimization problem.

A. Background

  • Classical alternating minimization solves two-variable optimization by repeatedly minimizing over one variable while holding the other fixed.The approach is suited to problems where one-variable minimization is easier, and if it converges, its limit is returned as the solution.Source: A. Background · p. 1
  • For fixed sets, general sufficient convergence conditions were already known, including those summarized from [1, Theorem 2].The stated conditions use a nonnegative function δ with three-point and four-point properties.Source: A. Background · p. 2

B. Our Contribution

  • When problem parameters change over time, an adaptive algorithm can reuse the previous tentative solution instead of independently solving each problem instance.The motivation assumes slowly varying systems, where consecutive solutions are likely to be close and the next tentative solution should be easy to compute.Source: B. Our Contribution · p. 2
  • The adaptive goal is asymptotic: as the sets converge to P and Q, the objective should approach the minimum over P × Q.The paper asks for conditions under which lim D(Pn, Qn) equals that limiting-set minimum.Source: B. Our Contribution · p. 3
  • The paper’s main contribution is sufficient conditions for convergence of adaptive alternating minimization, with conditions essentially the same as those in.The precise results are stated in Theorem 4.Source: B. Our Contribution · p. 3

C. Organization

The paper outlines its progression from technical preliminaries to convergence results and applications. The preliminaries define distances and objective values for compact sets, while auxiliary lemmas establish properties used later.

C. Organization

  • The paper moves from notation and technical preliminaries to convergence results, specialized settings, applications, and concluding remarks.The applications cover divergence minimization in statistics and finance, and Hilbert-space methods in adaptive signal processing.Source: C. Organization · p. 3

II. NOTATIONS AND TECHNICAL PRELIMINARIES

  • The Hausdorff distance dH is a metric and satisfies the triangle inequality.It is introduced for sets in a compact metric space.Source: §II · p. 3
  • For compact sets A and B, D(A, B) is the minimum of D over A × B and is well-defined when D is continuous.Compactness and continuity also ensure the minimizing set G(A, B) is nonempty.Source: §II · p. 3

A. Some Lemmas

  • The preliminaries state that a continuous function on a compact metric space has a modulus of continuity tending to zero as its argument tends to zero.The section also introduces auxiliary lemmas for later use.Source: A. Some Lemmas · pp. 3–4

III. ADAPTIVE ALTERNATING MINIMIZATION ALGORITHMS

The section formulates adaptive alternating minimization for sets revealed over time, gives the AAM algorithm, and establishes sufficient conditions for convergence and correctness. Its convergence result uses the three-point and four-point properties, with an additional summability condition for the stronger conclusion that all limit points are optimal.

A. Problem Statement

  • The adaptive problem seeks D(P, Q) when the compact sets P_n and Q_n are revealed over time and converge to P and Q in Hausdorff distance.The goal is to generate points in P_n × Q_n with the desired limiting objective value.Source: A. Problem Statement · p. 4

B. Algorithm

  • AAM alternates minimization over the changing sets, and reduces to classical alternating minimization when P_n=P and Q_n=Q for every n.The algorithm starts from (P_0, Q_0) and recursively updates the two variables; the supplied passage describes this recursion only in part.Source: B. Algorithm · p. 4

C. Sufficient Conditions for Convergence

  • Under compactness, continuity of D, and conditions C1 and C2, AAM converges in objective value, and limit points of subsequences achieving the lim inf belong to G(P, Q).When the additional summability condition involving ω(2ε_n) holds, all limit points belong to G(P, Q).Source: C. Sufficient Conditions for Convergence · p. 5
  • The adaptive convergence conditions add, in essence, uniform continuity of D and summability of ω(2ε_n), which the authors describe as the least expected in this setting.Here ε_n is the sum of the Hausdorff distances from P_n to P and Q_n to Q.Source: C. Sufficient Conditions for Convergence · p. 5

D. Proof of Theorem 4

The proof establishes that AAM limit points associated with the limiting objective value belong to G(P,Q); with the additional condition (16), this extends to every limit point.

D. Proof of Theorem 4

  • Adding inequalities (6) and (8) gives D(Pn, Qn) + D(P, Qn) ≤ D(P, Qn−1) + D(P, Q) + ω(γn) (9), involving the previous iterate and continuity error.Source: D. Proof of Theorem 4 · p. 6
  • Compactness and continuity make D bounded and its modulus of continuity vanish as its argument tends to zero.These properties support the proof's use of Lemma 2 as γ_n and ε_n tend to zero.Source: D. Proof of Theorem 4 · pp. 6–7
  • Limit points of subsequences achieving the lim inf belong to G(P,Q).The proof then shows that condition (16) places every limit point in G(P,Q).Source: D. Proof of Theorem 4 · pp. 7–8
  • Under condition (16), every limit point of the AAM sequence belongs to G(P,Q).The proof combines that condition with membership of limit points in P × Q and continuity of D.Source: D. Proof of Theorem 4 · pp. 7–8

IV. DIVERGENCE MINIMIZATION

This section specializes the adaptive algorithm to divergence minimization and considers applications to mixture decomposition and log-optimal portfolio selection.

IV. DIVERGENCE MINIMIZATION

  • A large class of problems can be formulated as divergence minimization, including channel capacity, rate distortion, log-optimal portfolios, and incomplete-data maximum likelihood.The section applies its results to adaptive mixture decomposition and adaptive log-optimal portfolio selection.Source: §IV · p. 8

A. Setting

The setting uses a compact space of measures and a continuous divergence cost, so the general adaptive convergence theorem applies when the required properties hold.

A. Setting

  • For convex P and Q, the divergence D and function δ satisfy the three-point and four-point properties C1 and C2.These properties were established in.Source: A. Setting · p. 8
  • The space M(Σ,b,B) is compact, and the divergence cost D is continuous and convex in both arguments.The boundedness constraints ensure that D is well defined.Source: A. Setting · p. 8
  • With these properties, Theorem 4 applies to this divergence-minimization setting.The measures are defined over a finite set Σ with positive lower and finite upper bounds.Source: A. Setting · p. 8

B. Application: Decomposition of Mixtures and Log-Optimal Portfolio Selection

The paper applies adaptive divergence minimization to estimating mixture weights from observations and to adaptive log-optimal portfolio selection. The mixture application yields almost-sure convergence of the empirical constraint sets and a limiting-objective result, but not general convergence of the objective values.

B. Application: Decomposition of Mixtures and Log-Optimal Portfolio Selection

  • The mixture problem estimates positive component weights from i.i.d. observations drawn from a mixture of distributions.Each component distribution is assumed to assign probability at least μ0 to every outcome.Source: B. Application: Decomposition of… · p. 9
  • The constrained divergence minimization over Q yields an optimal mixture-weight vector, recovered from the marginal of the optimal Q.The minimizing coefficients have a threshold form: coefficients above c0 for indices through J* and c0 thereafter.Source: B. Application: Decomposition of… · p. 9
  • A positive lower bound on the projected distributions is needed to meet the boundedness condition for applying the general results.When the empirical distribution is close to the true one, the projections are bounded below by p0.Source: B. Application: Decomposition of… · p. 10
  • The empirical constraint set converges to the set constructed from the true distribution almost surely.The passage states this convergence in Hausdorff distance.Source: B. Application: Decomposition of… · p. 10
  • Under AAM, the objective's lim inf is attained in the stated sense almost surely, and its achieving subsequence limit points belong to G(P,Q).The result follows by applying the general results and Theorem 4.Source: B. Application: Decomposition of… · p. 10
  • In this scenario, Theorem 4 does not establish convergence of D(P_n,Q_n) to D(P,Q).The passage notes that the required modulus condition would hold only if D were constant.Source: B. Application: Decomposition of… · p. 10
  • Applying AAM to this special case also gives an adaptive version of Cover’s portfolio optimization algorithm.The standard alternating divergence minimization algorithm is identified with Cover’s algorithm [4].Source: B. Application: Decomposition of… · p. 10

V. PROJECTIONS IN HILBERT SPACE

The section specializes alternating minimization to minimization in Hilbert spaces, where the algorithm is often called POCS. Hilbert-space alternating projections apply to problems including filter design, signal recovery, and spectral estimation.

V. PROJECTIONS IN HILBERT SPACE

  • The section specializes the algorithm to minimization in a Hilbert space.It notes that many problems can be formulated as alternating projections in Hilbert spaces.Source: §V · p. 10
  • Applications include filter design, signal recovery, and spectral estimation.The passage also points to an overview in.Source: §V · p. 10
  • In Hilbert spaces, alternating minimization is often called POCS (Projection Onto Convex Sets).Source: §V · p. 10

A. Setting

The setting uses a compact subset of a Hilbert space with squared distance as its cost. That cost is continuous and convex, and for convex P and Q the cited three-point and four-point properties allow Theorem 4 to apply.

A. Setting

  • The setting takes M to be a compact subset of a Hilbert space with the usual norm-derived metric.The passage states that (M, d) is then a compact metric space.Source: A. Setting · p. 11
  • The cost D(A, B) is the squared distance d(A, B)^2 and is continuous and convex.Source: A. Setting · p. 11
  • For convex P and Q, establishes the three-point and four-point properties C1 and C2, so Theorem 4 applies.Source: A. Setting · p. 11

B. Application: Set Theoretic Signal Processing and Adaptive Filter Design

The application formulates set-theoretic signal processing as minimization over convex compact constraint sets in a Hilbert-space framework. With time-varying constraints converging to limiting sets, the paper applies its results to obtain convergence and correctness for the adaptive algorithm.

B. Application: Set Theoretic Signal Processing and Adaptive Filter Design

VI. CONCLUSIONS

The paper's conclusion is that it establishes sufficient conditions for convergence and correctness of adaptive alternating minimization. It also describes applications across several fields, with detailed treatments from statistics, finance, and signal processing.

VI. CONCLUSIONS

  • The paper provides sufficient conditions for convergence and correctness of a general adaptive alternating minimization algorithm.Source: §VI · p. 12
  • The algorithm has applications in a variety of settings.Source: §VI · p. 12
  • The paper discusses applications in detail for three problems from statistics, finance, and signal processing.Source: §VI · p. 12
Loading cs/0701043v2…