PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Learning with Inexact Proximal Online Gradient Descent Algorithms

Rishabh Dixit, Amrit Singh Bedi, Ruchi Tripathi, Ketan Rajawat

arXiv:1806.00202v1math.OC

TL;DR

Changing targets and imperfect gradients complicate online optimization of composite objectives, while large-scale problems may make full-gradient evaluation impractical. The paper proposes inexact proximal OGD and variance-reduced extensions for finite-sum losses. It establishes sublinear dynamic regret under sublinear path length and cumulative error, and tests the algorithms on formation control and dynamic video separation.

  • Problem

    Dynamic composite optimization must track changing optima despite gradient errors, and large-scale finite-sum problems can make full-gradient evaluation impractical.

    Source: §I · p. 2, §IV · p. 12

  • Method

    The paper proposes inexact proximal OGD for composite objectives and variance-reduced extensions that subsample component functions in finite-sum problems.

    Source: §I · pp. 2–3

  • Results

    The proposed method has sublinear dynamic regret when path length and cumulative gradient error are sublinear, and the algorithms are validated on robot formation control and dynamic foreground-background separation.

    Source: §VI · p. 23

  • Takeaways & Limitations

    The algorithms provide a way to track time-varying optima with inexact gradients, including in large-scale settings where full-gradient calculations are not viable.

    Source: §I · pp. 2–3

Abstract

from arXiv · show

We consider non-differentiable dynamic optimization problems such as those arising in robotics and subspace tracking. Given the computational constraints and the time-varying nature of the problem, a low-complexity algorithm is desirable, while the accuracy of the solution may only increase slowly over time. We put forth the proximal online gradient descent (OGD) algorithm for tracking the optimum of a composite objective function comprising of a differentiable loss function and a non-differentiable regularizer. An online learning framework is considered and the gradient of the loss function is allowed to be erroneous. Both, the gradient error as well as the dynamics of the function optimum or target are adversarial and the performance of the inexact proximal OGD is characterized in terms of its dynamic regret, expressed in terms of the cumulative error and path length of the target. The proposed inexact proximal OGD is generalized for application to large-scale problems where the loss function has a finite sum structure. In such cases, evaluation of the full gradient may not be viable and a variance reduced version is proposed that allows the component functions to be sub-sampled. The efficacy of the proposed algorithms is tested on the problem of formation control in robotics and on the dynamic foreground-background separation problem in video.

I. INTRODUCTION

Dynamic optimization must track changing targets, but existing approaches often use heuristics without performance guarantees. This paper develops inexact proximal OGD for composite objectives and extends it to large-scale finite-sum problems with subsampling.

I. INTRODUCTION

  • Inexact proximal OGD handles differentiable losses with non-differentiable regularizers and characterizes dynamic regret using problem variations and cumulative mean squared gradient error.The analysis permits errors in gradient calculations.Source: §I · p. 2

A. Related work and contributions

  • Prior dynamic-regret work largely addressed differentiable objectives; the paper develops bounds for differentiable losses with non-differentiable regularizers and allows inexact gradients.The bounds are also described as improving on and generalizing earlier results for self-concordant functions.Source: §I · p. 2, A. Related work and contributions · pp. 3–4

I. INTRODUCTION

  • For large-scale finite-sum losses, proposed variance-reduced algorithms use subsampling to avoid evaluating the full gradient at every iteration.Tests on dynamic video foreground-background separation report computational efficiency and successful separation.Source: §I · p. 3

A. Related work and contributions

  • The work contributes dynamic-regret bounds for inexact proximal OGD and accelerated proximal OGD algorithms for dynamic settings.Performance is characterized through regret bounds and numerical tests.Source: A. Related work and contributions · p. 4

II. PROBLEM FORMULATION

  • The problem formulation compares learner costs with a time-varying optimum revealed only after each action, using the full regularizer and an inexact loss gradient.Sublinear dynamic regret is obtained when path length and cumulative gradient error are sublinear.Source: §II · pp. 5–6

III. PROPOSED ONLINE ALGORITHM: ASSUMPTIONS AND PERFORMANCE

The paper proposes inexact proximal OGD for composite, time-varying objectives, using a proximal update for the non-differentiable component. Its regret analysis assumes smoothness, strong convexity, bounded target variation, and bounded gradient error.

III. PROPOSED ONLINE ALGORITHM: ASSUMPTIONS AND PERFORMANCE

  • IP-OGD combines an inexact gradient step with a proximal operator for the non-differentiable objective component.The method is motivated by the suitability of proximal methods for composite objectives.Source: §III · p. 8

A. Assumptions

  • The analysis assumes a smooth loss, a Lipschitz-continuous regularizer, and a strongly convex differentiable loss.These conditions support the algorithm's regret analysis.Source: A. Assumptions · pp. 8–9
  • The optimum is assumed to vary in a bounded way, and the gradient-error process has bounded mean squared error.Bounded target variation is described as natural when the tracked target does not change abruptly.Source: A. Assumptions · p. 9

B. Regret Bounds

The regret analysis bounds IP-OGD's dynamic regret under smoothness, strong convexity, bounded target variation, and a step size in a specified range. The bound is sublinear when path length and cumulative error are sublinear.

B. Regret Bounds

  • Under (A1-A3) and 0 < α < 2µ/L2, Theorem 1 states that the dynamic regret of the IP-OGD algorithm is bounded.Source: B. Regret Bounds · p. 10
  • Dynamic regret is sublinear when both path length and cumulative gradient error are sublinear.With zero gradient error, the dynamic regret is O(1 + W_K), matching the rate for strongly convex differentiable functions in.Source: B. Regret Bounds · p. 11
  • The step size may be selected from a specified range and need not depend on W_K.The stated range is 0 < α < 2µ/L^2.Source: B. Regret Bounds · pp. 10–11

IV. IP-OGD FOR LARGE SCALE LEARNING

For finite-sum losses, the paper develops dynamic variants of variance-reduced algorithms to avoid full-gradient calculations. Their error bounds feed into the regret analysis, while stale component gradients support progressive variance reduction as gradient variations diminish.

IV. IP-OGD FOR LARGE SCALE LEARNING

  • The large-scale algorithms avoid calculating the full gradient at every iteration when the loss is a sum of component functions.This addresses settings where processing many measurements or frames per iteration may not be viable.Source: §IV · pp. 11–12
  • Dynamic variance reduction is challenging because time variation can make stale component gradients lose information, but diminishing gradient variation enables progressive variance reduction.The approach exploits gradients from stale component functions.Source: §IV · p. 12
  • Two algorithms inspired by SVRG and ISSG bound cumulative error, which is then incorporated into the overall regret bounds.Their memory use, computational complexity, and regret bounds differ according to how stored gradients are updated.Source: §IV · p. 12, A. Assumptions · p. 13

A. Assumptions

  • The large-scale analysis assumes component-level smoothness and strong convexity, bounded gradients, and component gradient variation measures.The standard gradient-variation measure alone may not capture changes in individual component functions.Source: A. Assumptions · pp. 12–13

B. Online proximal-SVRG algorithm

Online Proximal-SVRG estimates gradients using component samples and periodically refreshed gradient information. Its expected regret bound follows from the inexact algorithm’s bound, while its computational savings come with conditioning and memory trade-offs.

B. Online proximal-SVRG algorithm

  • OP-SVRG stores a mean of obsolete gradients, samples component gradients randomly or cyclically, and refreshes its reference point and stored gradients every K0 iterations.The component and reference-point gradients are used in an inexact-gradient update.Source: B. Online proximal-SVRG algorithm · pp. 13–14
  • The expected OP-SVRG regret bound is obtained by substituting its gradient-error bound into the inexact proximal OGD bound.The cited bound requires a well-conditioned problem, with µ > 0.89L.Source: B. Online proximal-SVRG algorithm · p. 14
  • OP-SVRG has complexity O(Kn(2 + N/K0)), compared with O(KNn) for IP-OGD, and requires extra memory to store m.The stated cost savings are significant only when K0 ≫ 1.Source: B. Online proximal-SVRG algorithm · p. 15

C. Online Proximal gradient method with increasing sample size

This section uses an increasing number of sampled component functions to reduce gradient error over time. The resulting expected regret bound is O(1 + W_K), with improved regret rates available at additional computational cost.

C. Online Proximal gradient method with increasing sample size

  • Increasing the sample size can improve the dynamic regret rates, at the cost of additional computation.The section describes this as an incremental update approach.Source: C. Online Proximal gradient method… · p. 15
  • Algorithm 3 increases the number of sampled component functions over iterations so that the mean-square gradient error diminishes.The sampled set I_k is selected randomly.Source: C. Online Proximal gradient method… · p. 15
  • O(1 + W_K) bounds Algorithm 3’s expected regret for the specified increasing sample sizes, with O(|I_k|) gradient evaluations per iteration and overall complexity O(NKn) to achieve constant cumulative error.The sample size is |I_k| = ⌈N(1 − e^−k)⌉.Source: C. Online Proximal gradient method… · p. 16

V. NUMERICAL RESULTS

The numerical results test IP-OGD on changing robot formations and compare online foreground-background separation methods on static and moving scenes. OP-SVRG also tests whether component sampling can reduce runtime while keeping performance close to the full-gradient case.

1) Problem Formulation:

  • The robot formation update minimizes a constrained weighted least-squares objective with a squared movement penalty to discourage unnecessary movement and encourage faster response.The fusion center gathers follower-bot data, makes decisions, and broadcasts them to the robots.Source: 1) Problem Formulation · pp. 16–17

2) Simulation Results:

  • For ten follower robots tracking a leader, the formation changes from a regular decagon to a non-convex star, and IP-OGD's path length and dynamic regret are sublinear.Gaussian noise with variance 0.3 is added to the exact gradient in the reported run.Source: 2) Simulation Results · p. 18, 1) Problem Formulation · p. 18

B. Dynamic foreground background separation

  • On static backgrounds, IP-OGD does not outperform OPRMF or ReProCS, and ReProCS misclassifies some foreground as background.The paper describes this static-background scenario as relatively easy to extract.Source: Figure 3 · p. 20, B. Dynamic foreground background… · p. 21
  • The video experiments compare IP-OGD with OPRMF and ReProCS and apply large-scale online learning algorithms to trade speed against accuracy.The full-gradient version requires an SVD of the full video matrix at each time step.Source: B. Dynamic foreground background… · pp. 20–22
  • On moving backgrounds, ReProCS keeps treating a stopped car as foreground; IP-OGD is slightly worse than OPRMF but significantly faster.The parking-lot video treats cars being parked as foreground and already parked cars as background.Source: Figure 4 · p. 21, B. Dynamic foreground background… · p. 21
  • With 25% sampling, OP-SVRG runs four times faster than the full-gradient case with very small performance loss.Results include circular and randomly selected component indices at each time step.Source: B. Dynamic foreground background… · p. 22

VI. CONCLUSION

The paper proposes inexact proximal OGD for composite dynamic optimization and establishes sublinear dynamic regret under sublinear target path length and cumulative gradient error. It also presents accelerated variants that avoid full-gradient calculations and validates them on robot formation control and dynamic foreground-background separation.

VI. CONCLUSION

  • Sublinear dynamic regret holds when both target path length and cumulative gradient error are sublinear.The method addresses a differentiable loss with a non-differentiable regularizer and tolerates changes in the optimum and errors in the gradient.Source: §VI · p. 23
  • Two accelerated proximal OGD variants for large-scale problems avoid calculating the full gradient at every time instant.The algorithms are dynamic variants of stochastic variance-reduced gradient descent and incremental hybrid stochastic gradient methods.Source: §VI · p. 23
  • The proposed algorithms are validated on robot formation control and robust subspace tracking for dynamic foreground-background separation.Source: §VI · p. 23

APPENDIX A

Appendix A develops proof bounds for the inexact proximal OGD using strong convexity, smoothness, and the target path length. The bounds account for gradient error and cumulative optimality gap.

APPENDIX A

  • The contraction bound uses strong convexity parameter μ, gradient Lipschitz parameter L, and a step size α in (0, 2μ/L^2).The proof sets ρ^2 = 1 + α^2L^2 − 2αμ and requires ρ < 1.Source: A. Preliminaries · p. 25
  • The proof represents the scaled gradient error by δ_k = ∥αe_k∥ in bounding the iterate difference.Source: A. Preliminaries · p. 25
  • The cumulative optimality-gap argument uses the target path length to bound variation over time.The passage identifies the path-length definition as the basis for the relevant equality.Source: A. Preliminaries · p. 25

APPENDIX B

Appendix B analyzes component-sampled gradients under independent, uniformly selected indices and derives conditions for the resulting bounds. It also states a condition on the strong-convexity-to-smoothness ratio for feasible parameters.

APPENDIX B

  • The sampled component index is independent and uniform, making the gradient error zero-mean under the stated identities.The analysis uses expectation conditioned on previously selected indices.Source: Appendix B · pp. 27–28
  • The parameter condition requires αη < 1 for the stated bound.Source: Appendix B · p. 31
  • When μ/L > 0.89, the appendix states that suitable parameters α, a, and c can be chosen for any given K0.The stated step-size constraint is α < 2μ/L^2, with a > 0 and c > 0.Source: Appendix B · p. 31

APPENDIX C

Appendix C bounds cumulative sampling error by requiring the number of omitted components to be summable. It gives both geometric and inverse-square sampling schedules as examples yielding bounded cumulative error.

APPENDIX C

  • Summable N − |I_k| is required to bound cumulative sampling error; |I_k| = N − N exp(−βk) is one example.The passage states the example's bound holds for any β > 0.Source: Appendix C · p. 32
  • The schedule |I_k| = N − N/k^2 also yields bounded cumulative error.Source: Appendix C · p. 32

SUPPLEMENTARY MATERIAL FOR ”ONLINE LEARNING WITH INEXACT PROXIMAL ONLINE

The formulation seeks a next-step robot pose matching the desired formation shape. The shape is parameterized by a scaled, rotated, and translated base shape, then encoded by linear constraints on the robot positions.

DETAILS OF BOT FORMULATION PROBLEM

  • The next-step robot pose must match the desired formation shape while remaining in the feasible set at the current time.The setup assumes the initial pose differs from the target shape.Source: Appendix D · p. 35
  • The formation is represented using a base shape centered at the origin, with scale, rotation, and translation parameters that may vary over time.The rotation is a 2 × 2 matrix, and the translation moves the base shape in R2.Source: Appendix D · p. 35
  • The formation-shape constraints reduce to linear functions of the next-step robot positions and can be written as A(k)p(k + 1) = 0, with A(k) low rank.The constraints are stated to sufficiently encode the desired formation shape.Source: Appendix D · p. 35

Related papers

Loading 1806.00202v1…