PaperlayerView exact revision on arXiv

Source-linked AI summary

Centralized and distributed online learning for sparse time-varying optimization

Sophie M. Fosson

arXiv:2001.11939v1math.OCcs.LG

TL;DR

Sparse time-varying optimization lacks dynamic-regret analyses that handle non-differentiable objectives without assuming a specific evolution model. The paper proposes centralized and distributed online strategies and analyzes their dynamic regret, with simulations illustrating practical effectiveness.

  • Problem

    Prior dynamic-regret analyses commonly assume differentiable losses, while sparse problems often use non-differentiable ℓ1 regularization; sparse time-varying work also often assumes an evolution model.

    Source: §1 · p. 3

  • Method

    The paper develops a centralized Douglas-Rachford strategy and a distributed online strategy extending DISTA, and analyzes both using dynamic regret without assuming a specific evolution structure.

    Source: §1 · p. 3

  • Results

    The authors analyze both strategies in terms of dynamic regret and present numerical simulations to illustrate their practical effectiveness.

    Source: §1 · p. 3, §8 · p. 28

  • Takeaways & Limitations

    The analysis and experiments address quadratic, strongly convex optimization problems with ℓ1 regularization, including compressed system identification and indoor moving-target tracking.

    Source: §8 · p. 28

    If the moving-target area is not fixed in advance, matching O-DISTA’s theoretical features requires a system of moving sensors.

    Source: §7.2 · p. 28

Abstract

from arXiv · show

The development of online algorithms to track time-varying systems has drawn a lot of attention in the last years, in particular in the framework of online convex optimization. Meanwhile, sparse time-varying optimization has emerged as a powerful tool to deal with widespread applications, ranging from dynamic compressed sensing to parsimonious system identification. In most of the literature on sparse time-varying problems, some prior information on the system's evolution is assumed to be available. In contrast, in this paper, we propose an online learning approach, which does not employ a given model and is suitable for adversarial frameworks. Specifically, we develop centralized and distributed algorithms, and we theoretically analyze them in terms of dynamic regret, in an online learning perspective. Further, we propose numerical experiments that illustrate their practical effectiveness.

1 Introduction

Sparse time-varying optimization is challenging because common regret analyses require differentiability, while prior approaches often assume a model of system evolution. This paper develops centralized and distributed online strategies without such an evolution model and analyzes them using dynamic regret.

1 Introduction

  • Time-varying optimization concerns tracking solutions as a sequence of optimization problems changes over time, motivating online algorithms that operate on the system’s timescale.The introduction situates this need in applications including big data streams, control, resource allocation, and moving-agent tracking.Source: §1 · p. 1
  • Dynamic regret measures cumulative loss against the per-time best hindsight loss and can reveal tracking behavior that a bounded-error guarantee may miss.For example, it can capture convergence when a system tends toward a constant after a transient period.Source: §1 · p. 2
  • Prior sparse time-varying optimization work mainly addresses dynamic compressed sensing and often assumes prior information about system evolution.Examples include tracking signals modeled as Markov processes.Source: §1 · p. 3
  • Existing time-varying convex-optimization analyses commonly assume differentiable losses, limiting their applicability to sparse problems with ℓ1 regularization.The introduction notes that prior non-differentiable results establish bounded tracking error, but not dynamic regret.Source: §1 · p. 3
  • The paper develops centralized and distributed strategies for sparse time-varying optimization, with dynamic-regret analysis that does not require differentiability or a specific evolution structure.The centralized method uses Douglas-Rachford splitting; the distributed method extends DISTA to the time-varying setting.Source: §1 · p. 3

2 Problem statement

This section formulates sparse time-varying optimization using strongly convex quadratic objectives and frames online tracking through dynamic regret. It motivates the metric, reviews existing regret methods, and presents O-IST as background for the paper’s faster splitting approach and distributed extension.

2 Problem statement

  • The model uses strongly convex quadratic objectives, with strong convexity assumed for its contractivity and convergence benefits.The section identifies time-varying compressed sensing, sparse control, and iterative learning control as application settings.Source: §2 · p. 4

2.0.1 Elastic-net

  • Elastic-net adds an ℓ2 regularizer to Lasso, restoring strong convexity when the measurement count m is below the signal dimension n.Unlike Lasso, Elastic-net can retain more than m nonzero values and promotes grouping among correlated variables.Source: §2.0.1 · p. 5

2.0.2 MPC with sparse control

  • Sparse control reduces active MPC control inputs using an ℓ1 regularizer, with the aim of reducing consumption and transmission costs.Source: §2.0.2 · p. 5

2.0.3 Sparse iterative learning control

  • Iterative learning control optimizes repeated systems online; ℓ1 regularization has been reported effective for reliable sparse control.Source: §2.0.3 · p. 5

2.1 Performance metric: dynamic regret

  • Dynamic regret evaluates online losses against time-varying optima; its behavior reflects path length and captures tracking properties beyond a bounded tracking-error metric.The section states that sublinear dynamic regret means average performance matches the clairvoyant comparator and links bounded or vanishing changes between successive minima to bounded or vanishing estimation error.Source: §2.1 · p. 6

2.2 Summary of previous literature on regret analysis

  • Prior static-regret methods commonly achieve O(T), sometimes O(log T) under strong convexity, but decreasing parameters are unsuitable when tracking horizons may be infinite.Prior dynamic-regret analyses include gradient descent and O-IST, with the latter limited to Elastic-net but not requiring a bounded subgradient.Source: §2.2 · pp. 6–7

2.3 O-IST for quadratic problems

  • O-IST performs soft-thresholding iterations online, with sublinear dynamic regret when path length is sublinear; its slowness can reduce promptness to sudden changes.The paper adapts it to quadratic problems and uses r iterations per time step, with r depending on available time.Source: §2.3 · pp. 7–8
  • The paper develops a faster centralized Douglas–Rachford strategy and a distributed online IST extension, while leaving rigorous regret analysis for distributed splitting to future work.Source: §2.3 · p. 8

3 O-DR: Online Douglas-Rachford splitting

The section adapts Douglas–Rachford splitting to online tracking by performing multiple DR steps at each time. It situates this choice against static online ADMM methods and dynamic tracking approaches with differing assumptions.

3 O-DR: Online Douglas-Rachford splitting

  • In the static framework, DR iterates converge under proper closed convex functions and α ∈ (0, 1); DR is equivalent to ADMM for convex h(x) + g(x).The paper states that the ADMM formulation yields the same theoretical and numerical results.Source: §3 · p. 9
  • O-DR performs r Douglas–Rachford steps per time step, updating estimates with newly revealed quadratic-problem data; the paper uses the Peaceman–Rachford setting with γ = 1 and α = 1.Source: §3 · p. 9, §3.1 · p. 10

3.1 Related literature

  • Earlier online ADMM procedures target static optimization and static regret, often requiring step-size schedules tied to finite T, unlike tracking with potentially infinite horizons.Source: §3.1 · p. 10
  • Other one-step-per-time ADMM tracking analyses address particular settings, including strongly convex time-varying costs for dynamic sharing.That work proves convergence to a neighborhood of the time-varying optimum, while its illustrated dynamic-Lasso experiment does not meet the stated technical conditions.Source: §3.1 · p. 11

4 Dynamic regret analysis for O-DR

The O-DR analysis bounds dynamic regret in relation to the system’s path length. Sublinear path lengths imply sublinear regret, under stated boundedness assumptions on the system rather than on the algorithm’s trajectory or losses.

4 Dynamic regret analysis for O-DR

  • O-DR’s dynamic regret bound depends on the system’s evolution through its path length.Theorem 1 gives the bound for O-DR on Problem (1)–(2).Source: §4 · pp. 11, 14
  • The analysis assumes bounded system evolution, including bounded minimizers and bounded Q_t and φ_t, but does not require bounded algorithm iterates or incurred losses.The authors contrast this with work requiring bounded ∇f_t, which excludes some quadratic costs on non-compact state spaces.Source: §4 · p. 11
  • For the corresponding static problem, batch DR converges Q-linearly to its limit point under strong convexity and smoothness conditions.The contraction parameter is δ.Source: §4 · pp. 11–12
  • Sublinear path lengths imply sublinear dynamic regret for O-DR.The paper identifies this as algorithmic success.Source: §4 · p. 14

5 O-DISTA: Distributed online IST

O-DISTA decentralizes iterative soft thresholding for sparse time-varying optimization using the DISTA framework. Its formulation uses local information and communication, with graph conditions that simplify the analysis.

5 O-DISTA: Distributed online IST

  • O-DISTA decentralizes the IST algorithm from [22] using the DISTA framework and analyzes the distributed method in terms of dynamic regret.The paper reformulates DISTA for Problem (1)–(2) and establishes contraction properties as a basis for that analysis.Source: §5 · p. 15
  • The analysis assumes a connected, d-regular graph with time-invariant topology.The paper describes d-regularity as a technical condition that simplifies the convergence proof; time-invariance models ideal networks without link failures or communication interruptions.Source: §5 · p. 15
  • Each node uses local data and local communication to track the minimizer of the distributed objective.The formulation introduces consensus among local estimates and uses local means to support separate communication and descent steps.Source: §5 · p. 16
  • The distributed surrogate adds a quadratic term for the ℓ1 term and replaces the local mean with a local auxiliary variable, enabling alternating minimization.The resulting generalization of DISTA is presented in batch form and then reformulated online as O-DISTA.Source: §5 · pp. 16–17

6 Dynamic Regret Analysis for O-DISTA

The O-DISTA analysis extends prior regret results to the distributed case, first establishing contractivity and then deriving a dynamic-regret bound. Its boundedness assumptions are weaker than those stated for O-DR.

6 Dynamic Regret Analysis for O-DISTA

  • The dynamic-regret analysis extends the results in [22, Section IV] and uses contractivity as an intermediate result.The section derives intermediate lemmas before evaluating regret.Source: §6 · pp. 17, 20
  • The theorem’s bound uses θ_τ, defined as the maximum over nodes and times of ‖I − τQ_v,t‖₂.The passage also specifies that ‖·‖_F is the Frobenius norm.Source: §6 · pp. 17, 20
  • O-DISTA requires weaker boundedness assumptions than O-DR because its objective sequence is monotone decreasing, a property not generally guaranteed for O-DR.The paper notes that when Q_v,t is constant in time, x⋆_t need not be bounded under the stated O-DISTA assumptions.Source: §6 · p. 19
  • Theorem 2 establishes a dynamic-regret bound for O-DISTA.The analysis extends results for IST to the distributed setting and starts by proving contractivity.Source: §6 · pp. 17, 20

7 Numerical results

The numerical section tests O-IST, O-DR, and O-DISTA on compressed system identification and indoor target tracking. It examines dynamic regret and compares the algorithms’ tracking behavior under different parameter changes and processing times.

7.1 Online compressed system identification

  • The identification experiments use compressed, noisy measurements to estimate a sparse time-varying autoregressive model without known sparsity or support.They test abrupt parameter changes and smooth variation, with runtime limits of 12 ms and 6 ms.Source: §7.1 · pp. 22, 25
  • For step-changing parameters, all algorithms track the true values, but O-DR converges and adapts faster while showing sharper jump-related peaks.Reducing runtime from 12 ms to 6 ms slightly worsens all algorithms but reduces post-jump response delay; O-DR performs almost equally at both runtimes.Source: Figure 2 · p. 23, Figure 3 · p. 23, §7.1 · p. 25
  • With slowly varying parameters, O-DR and O-IST perform similarly after 200 ms, while O-DR is more precise before then when path length is higher.Figures 4 and 5 show the parameter estimates and mean square error for Experiment 2 at the two tested runtimes.Source: Figure 4 · p. 24, Figure 5 · p. 24, §7.1 · p. 25

7.2 Moving target tracking

  • The tracking experiment uses RSS measurements from 36 sensors and 144 measurements to locate a target among 625 cells, comparing centralized and in-network processing.The target moves in a 25 × 25 m2 area; each algorithm runs for 50 ms per iteration.Source: §7.2 · p. 26
  • In indoor tracking, all three algorithms substantially follow the target path; O-DR is most precise and responsive, while O-DISTA is less accurate and other methods show delays or missed corners.The reported distance of 2 m corresponds to movement into an adjacent cell.Source: §7.2 · p. 26, Figure 6 · p. 27, Figure 7 · p. 27

8 Conclusions

The paper develops and analyzes centralized and distributed strategies for sparse time-varying optimization. It evaluates them theoretically using dynamic regret and numerically on compressed system identification and indoor moving target tracking.

8 Conclusions

  • The paper develops and analyzes centralized and distributed strategies for sparse time-varying optimization.The considered problems are quadratic, strongly convex, and ℓ1-regularized.Source: §8 · p. 28
  • The strategies are analyzed in terms of dynamic regret for quadratic, strongly convex optimization problems with ℓ1 regularization.Source: §8 · p. 28
  • Numerical experiments address compressed system identification and indoor moving target tracking.Source: §8 · p. 28
  • Future work will extend the analysis to larger classes of problems.Source: §8 · p. 28
Loading 2001.11939v1…