The Power of Second Order Methods for Sequence Preconditioning

• URL: http://arxiv.org/abs/2605.08390v1
• Date: Fri, 08 May 2026 18:56:18 GMT
• Title: The Power of Second Order Methods for Sequence Preconditioning
• Abstract summary: We show that the Vovk-Azoury-Warmuth (VAW) algorithm is naturally matched to the Universal Sequence Preconditioning (USP) regime.<n>We prove that combining USP with VAW achieves polylogarithmic regret $O left( log3 Tright)$ even in the presence of asymmetric hidden transition matrices.<n>We extend the applicability of USP beyond bounded-spectrum systems by providing new complex-analytic bounds on Chebyshevs.
• Score: 15.021303911702121
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Sequence prediction methods for dynamical systems with long memory, i.e. marginally stable systems, typically achieve regret that grows polynomially with the hidden dimension of the underlying generative model. Universal Sequence Preconditioning (USP) is a method that compresses any sequence which comes from a linear dynamical system into a "preconditioned" sequence which requires exponentially shorter memory for accurate prediction. However, the preconditioned sequence yields exponentially larger diameters and gradients, hindering USP from unlocking optimal regret bounds. Inspired by the minimum description length principle, we show that the Vovk-Azoury-Warmuth (VAW) algorithm is naturally matched to the USP regime. Indeed, it takes advantage of the memory compression while remaining robust to the exponential explosion of the diameter. We prove that combining USP with VAW achieves astoundingly strong results: for any marginally-stable linear dynamical system, this algorithm achieves polylogarithmic regret $O \left( \log^3 T \right)$ even in the presence of asymmetric hidden transition matrices. Finally, we extend the applicability of USP beyond bounded-spectrum systems by providing new complex-analytic bounds on Chebyshev polynomials, allowing for systems with constant complex arguments.

Related papers

• PRISM: Parallel Residual Iterative Sequence Model [52.26239951489612]
  We propose PRISM (Parallel Residual Iterative Sequence Model) to resolve this tension.<n>PRISM introduces a solver-inspired inductive bias that captures key structural properties of multi-step refinement in a parallelizable form.<n>We prove that this formulation achieves Rank-$L$ accumulation, structurally expanding the update manifold beyond the single-step Rank-$1$ bottleneck.
  arXiv  Detail & Related papers  (2026-02-11T12:39:41Z)
• Universal Sequence Preconditioning [15.021303911702121]
  We study the problem of preconditioning in sequential prediction.<n>We show that convolving the target sequence corresponds to applying a lens of the hidden transition matrix.<n>We prove that this approach reduces regret for prediction algorithms.
  arXiv  Detail & Related papers  (2025-02-10T15:10:06Z)
• The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspective [55.15192437680943]
  We study the sample complexity of online reinforcement learning in the general setting of nonlinear dynamical systems with continuous state and action spaces.<n>Our algorithm achieves a policy regret of $mathcalO(N epsilon2 + mathrmln(m(epsilon)/epsilon2)$, where $epsilon$ is the time horizon.<n>In the special case where the dynamics are parametrized by a compact and real-valued set of parameters, we prove a policy regret of $mathcalO(sqrt
  arXiv  Detail & Related papers  (2025-01-27T10:01:28Z)
• Tree-like process tensor contraction for automated compression of environments [0.0]
  We show that orders-of- improvement of ACE is possible by changing the order of PT-MPO contraction from a sequential to a tree-like scheme. The drawbacks of the preselection approach are that the MPO compression is suboptimal and that it is more prone to error accumulation than sequential combination and compression.
  arXiv  Detail & Related papers  (2024-05-26T12:32:57Z)
• Sub-linear Regret in Adaptive Model Predictive Control [56.705978425244496]
  We present STT-MPC (Self-Tuning Tube-based Model Predictive Control), an online oracle that combines the certainty-equivalence principle and polytopic tubes. We analyze the regret of the algorithm, when compared to an algorithm initially aware of the system dynamics.
  arXiv  Detail & Related papers  (2023-10-07T15:07:10Z)
• A relaxed proximal gradient descent algorithm for convergent plug-and-play with proximal denoiser [6.2484576862659065]
  This paper presents a new convergent Plug-and-fidelity Descent (Play) algorithm. The algorithm converges for a wider range of regular convexization parameters, thus allowing more accurate restoration of an image.
  arXiv  Detail & Related papers  (2023-01-31T16:11:47Z)
• DBA: Efficient Transformer with Dynamic Bilinear Low-Rank Attention [53.02648818164273]
  We present an efficient yet effective attention mechanism, namely the Dynamic Bilinear Low-Rank Attention (DBA) DBA compresses the sequence length by input-sensitive dynamic projection matrices and achieves linear time and space complexity. Experiments over tasks with diverse sequence length conditions show that DBA achieves state-of-the-art performance.
  arXiv  Detail & Related papers  (2022-11-24T03:06:36Z)
• Softmax Policy Gradient Methods Can Take Exponential Time to Converge [60.98700344526674]
  The softmax policy gradient (PG) method is arguably one of the de facto implementations of policy optimization in modern reinforcement learning. We demonstrate that softmax PG methods can take exponential time -- in terms of $mathcalS|$ and $frac11-gamma$ -- to converge.
  arXiv  Detail & Related papers  (2021-02-22T18:56:26Z)
• Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
  We investigate online convex optimization in non-stationary environments. We choose the dynamic regret as the performance measure. We show that it is possible to further enhance the dynamic regret by exploiting the smoothness condition.
  arXiv  Detail & Related papers  (2020-07-07T14:10:57Z)
• No-Regret Prediction in Marginally Stable Systems [37.178095559618654]
  We consider the problem of online prediction in a marginally stable linear dynamical system. By applying our techniques to learning an autoregressive filter, we also achieve logarithmic regret in the partially observed setting.
  arXiv  Detail & Related papers  (2020-02-06T01:53:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.