Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2605.27985 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918526617387008 |
|---|---|
| author | Lupien, Jean-Luc Pun, Yuen-Man Diouane, Youssef Shames, Iman Lesage-Landry, Antoine |
| author_facet | Lupien, Jean-Luc Pun, Yuen-Man Diouane, Youssef Shames, Iman Lesage-Landry, Antoine |
| contents | In online convex optimization (OCO), a decision-maker is confronted with an unknown environment and seeks to play an optimal sequence of decisions on a short time-scale using only past information. Recent advances in second-order OCO methods have demonstrated tighter regret bounds and improved empirical performance over traditional first-order methods. However, this performance comes at a cost: a matrix inversion is now required, which scales with the cube of the size of the problem. In this work, we propose sketching to mitigate this limitation. Specifically, we present the online sketched Newton-Raphson method (OSNR) which preserves the tight regret bounds obtained with second-order methods while presenting a strict computational improvement in terms of complexity. We discuss three application scenarios of OSNR: online root finding, unconstrained OCO, and time-varying equality-constrained OCO, and present their respective regret and a constraint violation bound for the latter. In all three applications, OSNR achieves sublinear dynamic regret bounds. For the equality-constrained case, the extension OSNR with equality constraints OSNR-EC is shown to yield sublinear cumulative constraint violation. Finally, we illustrate the performance of OSNR and OSNR-EC on two numerical examples, viz., online position tracking and optimal power flow, and observe that OSNR and OSNR-EC exhibit high performance even at low sampling rates. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_27985 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Online Sketched Newton-Raphson Lupien, Jean-Luc Pun, Yuen-Man Diouane, Youssef Shames, Iman Lesage-Landry, Antoine Optimization and Control In online convex optimization (OCO), a decision-maker is confronted with an unknown environment and seeks to play an optimal sequence of decisions on a short time-scale using only past information. Recent advances in second-order OCO methods have demonstrated tighter regret bounds and improved empirical performance over traditional first-order methods. However, this performance comes at a cost: a matrix inversion is now required, which scales with the cube of the size of the problem. In this work, we propose sketching to mitigate this limitation. Specifically, we present the online sketched Newton-Raphson method (OSNR) which preserves the tight regret bounds obtained with second-order methods while presenting a strict computational improvement in terms of complexity. We discuss three application scenarios of OSNR: online root finding, unconstrained OCO, and time-varying equality-constrained OCO, and present their respective regret and a constraint violation bound for the latter. In all three applications, OSNR achieves sublinear dynamic regret bounds. For the equality-constrained case, the extension OSNR with equality constraints OSNR-EC is shown to yield sublinear cumulative constraint violation. Finally, we illustrate the performance of OSNR and OSNR-EC on two numerical examples, viz., online position tracking and optimal power flow, and observe that OSNR and OSNR-EC exhibit high performance even at low sampling rates. |
| title | Online Sketched Newton-Raphson |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2605.27985 |