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

optima2026_outline

OPTIMA 2026 — Conference Version Outline

“Stochastic Gradient Algorithms from ODE Splitting Perspective”

Authors: Daniil Merkulov, Ivan Oseledets

Created: 2026-04-10 (Feanor worker)
Status: Pre-CFP planning — CFP not yet published (checked 2026-04-10), expected ~May 2026
Conference: OPTIMA 2026, Sep 22-26, Petrovac (Montenegro), hybrid
Format: Springer LNCS, 10-14 pages (typical for OPTIMA)
Purpose: РНФ 23-11-00229-П grant contribution (if Daniil in grant — confirm with Matukhin)

Why OPTIMA is the Right Venue

OPTIMA is the premier Russian-international optimization conference (Springer LNCS, Scopus/WoS indexed).
The paper fits the “continuous-time analysis of iterative methods” track.
Key selling point for program committee: classical numerical analysis perspective on SGD — uncommon in OPTIMA submissions which tend to be convergence-rate papers.

Proposed Title for OPTIMA Version

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

(Focus: LASSO application — most concrete + surprising result; avoids overpromising generality for 12pp)

Proposed Structure (12pp LNCS)

1. Introduction (1.5pp)

Story: SGD has been analyzed as discrete-time gradient descent, but has not been systematically connected to ODE splitting schemes. This connection yields new theoretical insight: why does the choice of splitting order matter?

Contributions (3 bullets):
1. Show SGD = Lie-Trotter splitting of gradient-flow ODE — interpretive framework
2. For LASSO: prove LT (ISTA-like) has zero algorithmic bias; Strang has floor proportional to h²λ²
3. Kaczmarz algorithm emerges as limiting case of LT splitting (unit batch, h→∞)

Brief related work (4-5 citations, 0.5pp):
- Splitting schemes: Lie (1876), Strang (1968), Blanes/Casas/Murua (Acta Numerica 2024)
- Gradient flow: Helmke & Moore 1994, Su et al. 2014
- SGD convergence: classical Robbins-Monro, not splitting-focused
- Kaczmarz: Strohmer-Vershynin 2009

2. Splitting Schemes: Brief Review (1.5pp)

Content: Define Lie-Trotter and Strang splitting for ODE ẋ = f(x) + g(x).
- Lie-Trotter: Φ_h = exp(h·f) ∘ exp(h·g), first-order accurate
- Strang: Φ_h = exp(h/2·g) ∘ exp(h·f) ∘ exp(h/2·g), second-order accurate
- Local splitting error: LT = O(h²), Strang = O(h³) per step

Key insight (1 paragraph): For non-commuting operators, Strang’s second-order symmetry comes with a “fixed-point shift” that creates bias for non-smooth objectives.

3. SGD as Lie-Trotter Splitting (2pp)

Setup: Gradient flow ODE ẋ = -∇F(x) = -∇f(x) - ∇g(x) where f = data fit, g = regularizer.

Theorem 1 (main interpretive result): SGD with step h on F = f + g is the Lie-Trotter scheme applied to the gradient-flow ODE. The splitting is: exp(h·f): x → x - h∇f(x) (gradient step), exp(h·g): x → prox_g(x) (proximal step).

Consequence: Splitting accuracy order → convergence rate. LT = O(h) global error → SGD convergence bound.

Upper bound (Lemma + Theorem from paper §3): State the global error bound E[F(x̄_K)] - F* ≤ O(1/√K) and its splitting-based derivation.

Note: This section condenses §2-3 of the JCAM version (~8pp → 2pp).

4. Kaczmarz as a Limiting Case (0.5pp)

Mini-theorem: In the case of linear least squares with unit batch and h→∞ normalization, Lie-Trotter scheme → randomized Kaczmarz algorithm (Strohmer-Vershynin 2009).

Why include: Shows framework unifies two classically separate algorithms. Proof is 3 lines.

5. LASSO: Where Splitting Order Matters (4pp) ← CORE OF PAPER

Problem: F(θ) = ½‖Aθ - y‖² + λ‖θ‖₁ → min

5.1 Setup (0.5pp):
- Two splitting schemes: LT = ISTA (standard), Strang = symmetric proximal gradient
- LT scheme: θ_{k+1} = soft(θ_k - h·A^T(Aθ_k - y), hλ)
- Strang scheme: θ_{k+1} = soft(soft(θ_k, hλ/2) - h·A^T(Aθ_k - y), hλ/2)

5.2 Theorem A (LT = zero bias) (1pp):
Statement: LT (ISTA) converges to the true minimizer θ with F(θ̄_K) - F* ≤ ‖θ₀ - θ*‖²/(2hK).
Proof sketch: Descent lemma + subgradient at proximal point. Full proof in [arXiv version].
Corollary*: ISTA has no algorithmic bias from splitting — it matches the classical ISTA analysis.

5.3 Theorem D (Strang = bias floor) (1.5pp):
Statement: Strang-ISTA has F(θ̄_K) - F* ≤ ‖θ₀ - θ*‖²/(2hK) + C_D · h² · λ²
where C_D = ‖A·sign(θ*)‖²/8.
Interpretation: For fixed stepsize h, Strang cannot converge below C_D · h²λ² — there is a bias floor.
Proof sketch: Modified objective at Strang fixed point differs from F by a fixed-point shift of magnitude hλ/2 · sign(θ*).
Key insight*: Strang is 2nd-order in the ODE sense, but this symmetry creates a fixed-point shift for non-smooth objectives.

5.4 Numerical Validation (1pp):
- Figure 1: Convergence of LT vs Strang-ISTA (F(θ_k) - F vs iterations). Show bias floor for Strang.
- Figure 2: C_D estimation — empirical vs formula. Show C_D ≈ 0.77 matches ‖A·sign(θ)‖²/8.
- Small experiment: n=50, m=30, random A, λ=0.1 (reproducible in 10 lines Python)

Note: Figures already generated in Strategy/phd/figures/: lasso_convergence.pdf, lasso_bias_floor.pdf

6. Discussion and Conclusion (0.5pp)

Summary: SGD viewed as splitting scheme enables unified analysis. Splitting order is NOT neutral for non-smooth problems — Strang introduces irreducible bias that LT avoids.

Open questions (1-2 sentences):
- Can the Strang bias be corrected with an adaptive debiasing step?
- Extension to mini-batch and non-convex objectives?

Future work pointer to journal paper (JCAM, in preparation).

What to Cut from JCAM Version

For OPTIMA (12pp vs 29pp JCAM), remove or heavily compress:
- Detailed proof of Theorem A (keep sketch only)
- Detailed proof of Theorem D (keep 4-step sketch, defer full proof to journal)
- C_D derivation details (state result, show numerics)
- Softmax regression experiments (keep only LASSO experiments — 2 figures)
- Appendix (if any)
- Extended introduction (compress from 4pp to 1.5pp)

What to Keep

  • All 3 main theorems (conceptual + statement)
  • Kaczmarz connection (short)
  • LASSO figures (2 figures)
  • C_D = ‖A·sign(θ*)‖²/8 formula

Pre-CFP Checklist

  • JCAM version (main_jcam.tex) exists and compiles — 29pp
  • All figures generated (lasso_convergence.pdf, lasso_bias_floor.pdf, lasso_fixed_point_shift.pdf)
  • C_D numerical validation ✅ C_D=0.767 (scripts/article3_cd_estimation.py)
  • Related work drafted (Blanes 2024, DOSnet, Kaczmarz)
  • OPTIMA LNCS template — download llncs2e.zip from Springer when CFP drops
  • Confirm Oselodets co-authorship for conference version
  • Confirm RNF grant number in acknowledgements (23-11-00229-П)
  • Verify Theorem D proof fully rigorous (blocking item — April Oselodets meeting)

Estimated Writing Time (after CFP drops)

  • ~2-3 days focused work (condensing from JCAM → conference format)
  • Splitting: cut Section 3 details (1 day) + adapt figures (0.5 day) + review (0.5 day)
  • Realistic: start writing 1 week after CFP drops (abstract first, then full paper)

Feanor worker 2026-04-10: Created pre-CFP outline for OPTIMA 2026 conference version. Based on: article3_submission_plan.md + splitting_literature_review_2024_2026.md. CFP confirmed NOT published as of Apr 10 (conf-optima.ru).

Choose icon