Strategy/projects/files/splitting/optima2026_abstract.md
+

optima2026_abstract

OPTIMA 2026 — Abstract Draft

Title: SGD as a Splitting Scheme: Bias Analysis for LASSO via ODE Perspective

Authors: Daniil Merkulov, Ivan Oseledets

Status: Draft (ready to submit when CFP drops — expected ~May 2026)

Prepared: Feanor worker, 2026-04-10

Abstract (~200 words)

We establish a formal connection between stochastic gradient descent (SGD) and operator splitting methods for ordinary differential equations. Specifically, we show that proximal SGD applied to a sum-structured objective F = f + g is equivalent to the Lie-Trotter splitting scheme applied to the gradient-flow ODE ẋ = −∇F(x). This correspondence reframes convergence analysis in terms of splitting accuracy: the first-order error of Lie-Trotter directly explains the O(1/√K) rate of SGD.

As a key consequence, we analyze the effect of splitting order for non-smooth objectives. For the LASSO problem (ℓ₁-regularized least squares), the Lie-Trotter scheme (equivalent to ISTA) converges to the exact minimizer with rate O(1/K). In contrast, the Strang splitting (a second-order scheme in the ODE sense) incurs an irreducible algorithmic bias: the fixed-point of the Strang iteration deviates from the true minimizer by a floor proportional to h²λ², where h is the step size and λ is the regularization parameter. The bias constant C_D = ‖A·sign(θ*)‖²/8 is explicitly characterized.

We further show that randomized Kaczmarz emerges as a limiting case of Lie-Trotter splitting under unit batch size, unifying two classically separate algorithms. Theoretical results are validated numerically on synthetic LASSO instances.

Keywords

SGD, operator splitting, Lie-Trotter, Strang splitting, LASSO, proximal gradient, Kaczmarz, gradient flow, algorithmic bias

Notes for Submission

  • Max length: check CFP (OPTIMA typically 2-4pp extended abstract OR full paper direct)
  • Co-authorship: confirm Oseledets as co-author before submission
  • Grant acknowledgement: РНФ 23-11-00229-П (confirm if Daniil is in grant)
  • Theorem D proof: rigorousness to be verified at April Oseledets meeting (see checklist)
  • Full paper: based on JCAM preprint main_jcam.tex (29pp); LNCS version = 10-14pp condensed

Feanor worker 2026-04-10. Based on: optima2026_outline.md + JCAM paper results (Theorem A: LT zero bias, Theorem D: Strang bias floor C_D=0.767).

Choose icon