\relax 
\providecommand\hyper@newdestlabel[2]{}
\providecommand\HyField@AuxAddToFields[1]{}
\providecommand\HyField@AuxAddToCoFields[2]{}
\emailauthor{daniil.merkulov@skolkovotech.ru}{Daniil Merkulov}
\emailauthor{i.oseledets@skoltech.ru}{Ivan Oseledets}
\providecommand \oddpage@label [2]{}
\Newlabel{label1}{a}
\citation{robbins1951stochastic}
\citation{cauchy1847methode}
\@writefile{toc}{\contentsline {section}{\numberline {1}Introduction}{2}{section.1}\protected@file@percent }
\newlabel{strang:finitesum}{{1}{2}{Introduction}{equation.1.1}{}}
\newlabel{strang:euler}{{3}{2}{Introduction}{equation.1.3}{}}
\citation{marchuk1968some,strang1968construction}
\citation{dormand1980family,shampine1986some}
\citation{2020SciPy-NMeth}
\@writefile{toc}{\contentsline {section}{\numberline {2}SGD as a splitting scheme}{3}{section.2}\protected@file@percent }
\newlabel{strang:gradientflow}{{4}{3}{SGD as a splitting scheme}{equation.2.4}{}}
\newlabel{strang:simple_GF}{{5}{3}{SGD as a splitting scheme}{equation.2.5}{}}
\@writefile{lot}{\contentsline {table}{\numberline {1}{\ignorespaces The table describes the correspondence between splitting scheme for discretized Gradient Flow ODE and epoch of SGD}}{4}{table.caption.1}\protected@file@percent }
\@writefile{toc}{\contentsline {section}{\numberline {3}Optimization step with ODE solver}{4}{section.3}\protected@file@percent }
\@writefile{lot}{\contentsline {table}{\numberline {2}{\ignorespaces The table presents ODE, which we need to solve at each step of the algorithm. The last column shows the ODE, which is needed to be solved at each iteration of the algorithm for each given problem.}}{4}{table.caption.2}\protected@file@percent }
\newlabel{thmt@@llsls@data}{{\def \theequation {\@arabic {\c@equation }}\def \theHequation {(restate \theHthmt@dummyctr )3.\@arabic {\c@equation }}\setcounter {equation}{5}}{4}{Optimization step with ODE solver}{table.caption.4}{}}
\@writefile{loe}{\contentsline {theorem}{\ifthmt@listswap Theorem~1\else \numberline {1}Theorem\fi }{4}{theorem.1}\protected@file@percent }
\newlabel{thmt@@llsls}{{1}{4}{}{theorem.1}{}}
\newlabel{strang:LLS_local_solution}{{1}{4}{}{theorem.1}{}}
\newlabel{strang:LLS_local_solution_formula}{{6}{4}{}{equation.3.6}{}}
\citation{kaczmarz1937method,strohmer2009randomized,gower2015randomized}
\citation{needell2014stochastic}
\@writefile{loa}{\contentsline {algocf}{\numberline {1}{\ignorespaces Splitting optimization}}{5}{algocf.1}\protected@file@percent }
\@writefile{lot}{\contentsline {table}{\numberline {3}{\ignorespaces The table shows initial local ODE and paired $\mathcal  {P}_i^k$. Note, that $\bm  {\mathbf  {\eta }}_i \in \mathbb  {R}^b$ , while $\bm  {\mathbf  {\theta }} \in \mathbb  {R}^p$}}{5}{table.caption.4}\protected@file@percent }
\newlabel{strang:splitting_limit_kaczmarz}{{7}{5}{Optimization step with ODE solver}{equation.3.7}{}}
\citation{hansen2018air}
\citation{lecun1998gradient}
\citation{xiao2017fashion}
\@writefile{toc}{\contentsline {section}{\numberline {4}Results}{6}{section.4}\protected@file@percent }
\citation{su2014differential}
\citation{nesterov1983method}
\citation{wibisono2016variational}
\citation{helmke2012optimization}
\citation{evtushenko1994stable}
\citation{blanes2024splitting}
\citation{huang2022dosnet}
\@writefile{toc}{\contentsline {section}{\numberline {5}Related work}{7}{section.5}\protected@file@percent }
\citation{tibshirani1996lasso}
\citation{beck2009fast}
\citation{parikh2014proximal}
\citation{strohmer2009randomized}
\@writefile{toc}{\contentsline {section}{\numberline {6}Conclusions}{8}{section.6}\protected@file@percent }
\bibstyle{elsarticle-num}
\bibdata{biblio}
\bibcite{robbins1951stochastic}{{1}{}{{}}{{}}}
\bibcite{cauchy1847methode}{{2}{}{{}}{{}}}
\bibcite{marchuk1968some}{{3}{}{{}}{{}}}
\bibcite{strang1968construction}{{4}{}{{}}{{}}}
\bibcite{dormand1980family}{{5}{}{{}}{{}}}
\bibcite{shampine1986some}{{6}{}{{}}{{}}}
\bibcite{2020SciPy-NMeth}{{7}{}{{}}{{}}}
\bibcite{kaczmarz1937method}{{8}{}{{}}{{}}}
\bibcite{strohmer2009randomized}{{9}{}{{}}{{}}}
\bibcite{gower2015randomized}{{10}{}{{}}{{}}}
\bibcite{needell2014stochastic}{{11}{}{{}}{{}}}
\bibcite{hansen2018air}{{12}{}{{}}{{}}}
\bibcite{lecun1998gradient}{{13}{}{{}}{{}}}
\bibcite{xiao2017fashion}{{14}{}{{}}{{}}}
\bibcite{su2014differential}{{15}{}{{}}{{}}}
\bibcite{nesterov1983method}{{16}{}{{}}{{}}}
\bibcite{wibisono2016variational}{{17}{}{{}}{{}}}
\bibcite{helmke2012optimization}{{18}{}{{}}{{}}}
\bibcite{evtushenko1994stable}{{19}{}{{}}{{}}}
\bibcite{blanes2024splitting}{{20}{}{{}}{{}}}
\bibcite{huang2022dosnet}{{21}{}{{}}{{}}}
\bibcite{tibshirani1996lasso}{{22}{}{{}}{{}}}
\bibcite{beck2009fast}{{23}{}{{}}{{}}}
\bibcite{parikh2014proximal}{{24}{}{{}}{{}}}
\bibcite{sheng1994global}{{25}{}{{}}{{}}}
\@writefile{toc}{\let\numberline\tmptocnumberline}
\@writefile{toc}{\contentsline {section}{\numberline {Appendix~A}Upper bound on the global splitting error}{12}{appendix.A}\protected@file@percent }
\newlabel{strang:model1}{{A.1}{12}{Upper bound on the global splitting error}{equation.A.1}{}}
\@writefile{loe}{\contentsline {lemma}{\ifthmt@listswap Lemma~1\else \numberline {1}Lemma\fi }{12}{lemma.1}\protected@file@percent }
\newlabel{strang:lemexp}{{1}{12}{}{lemma.1}{}}
\newlabel{strang:lrexp}{{A.2}{12}{}{equation.A.2}{}}
\citation{sheng1994global}
\@writefile{loe}{\contentsline {lemma}{\ifthmt@listswap Lemma~2\else \numberline {2}Lemma\fi }{13}{lemma.2}\protected@file@percent }
\newlabel{strang:lemupper_2}{{2}{13}{}{lemma.2}{}}
\newlabel{strang:lemupper}{{A.3}{13}{}{equation.A.3}{}}
\providecommand*\caption@xref[2]{\@setref\relax\@undefined{#1}}
\newlabel{strang:fig:upper_bound_2}{{A.3a}{14}{\small Global error of the splitting scheme. Initial random full rank matrix $X \in \mathbb {R}^{100 \times 100}$ was splitted by rows. $X_1, X_2 \in \mathbb {R}^{50 \times 100}$. Target matrices were obtained the following way: $A_1 = -X_1^*X_1, A_2 = -X_2^*X_2, A = -X^*X$. So $A_1, A_2$ are negative and lacking full rank, while $A = A_1 + A_2$ has full rank}{figure.caption.8}{}}
\newlabel{sub@strang:fig:upper_bound_2}{{a}{14}{\small Global error of the splitting scheme. Initial random full rank matrix $X \in \mathbb {R}^{100 \times 100}$ was splitted by rows. $X_1, X_2 \in \mathbb {R}^{50 \times 100}$. Target matrices were obtained the following way: $A_1 = -X_1^*X_1, A_2 = -X_2^*X_2, A = -X^*X$. So $A_1, A_2$ are negative and lacking full rank, while $A = A_1 + A_2$ has full rank}{figure.caption.8}{}}
\newlabel{strang:fig:upper_bound_many}{{A.3b}{14}{\small Global upper bound on the splitting scheme in case of $40$ summands in the right-hand side}{figure.caption.8}{}}
\newlabel{sub@strang:fig:upper_bound_many}{{b}{14}{\small Global upper bound on the splitting scheme in case of $40$ summands in the right-hand side}{figure.caption.8}{}}
\@writefile{loe}{\contentsline {theorem}{\ifthmt@listswap Theorem~2\else \numberline {2}Theorem\fi }{14}{theorem.2}\protected@file@percent }
\newlabel{strang:theorem_uppbound}{{2}{14}{}{theorem.2}{}}
\newlabel{strang:global_error_upper_bound}{{A.4}{14}{}{equation.A.4}{}}
\@writefile{toc}{\contentsline {section}{\numberline {Appendix~B}Proofs}{14}{appendix.B}\protected@file@percent }
\@writefile{loe}{\contentsline {theorem}{\ifthmt@listswap Theorem~1\else \numberline {1}Theorem\fi }{14}{theorem.dummy.7}\protected@file@percent }
\newlabel{strang:lls_theorem_theta_from_eta}{{B.1}{15}{Proofs}{equation.B.1}{}}
\newlabel{strang:lls_theorem_eta_from_theta}{{B.2}{15}{Proofs}{equation.B.2}{}}
\newlabel{strang:lls_theorem_eta_star}{{B.3}{15}{Proofs}{equation.B.3}{}}
\citation{kaczmarz1937method}
\citation{strohmer2009randomized}
\citation{gower2015randomized}
\@writefile{toc}{\contentsline {section}{\numberline {Appendix~C}Applications}{16}{appendix.C}\protected@file@percent }
\@writefile{toc}{\contentsline {subsection}{\numberline {Appendix~C.1}Linear least squares}{16}{subsection.C.1}\protected@file@percent }
\@writefile{toc}{\contentsline {subsubsection}{\numberline {Appendix~C.1.1}Problem}{16}{subsubsection.C.1.1}\protected@file@percent }
\newlabel{strang:LLS}{{C.1}{16}{Problem}{equation.C.1}{}}
\newlabel{strang:LLS_grad}{{C.2}{16}{Problem}{equation.C.2}{}}
\newlabel{strang:LLS_GF}{{C.3}{16}{Problem}{equation.C.3}{}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {Appendix~C.1.2}Exact solution of the local problem}{16}{subsubsection.C.1.2}\protected@file@percent }
\@writefile{toc}{\contentsline {subsubsection}{\numberline {Appendix~C.1.3}Kaczmarz as the limit case of splitting}{16}{subsubsection.C.1.3}\protected@file@percent }
\citation{needell2014stochastic}
\newlabel{strang:kaczmarz_derivation}{{C.5}{17}{Kaczmarz as the limit case of splitting}{equation.C.5}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {Appendix~C.2}Binary logistic regression}{17}{subsection.C.2}\protected@file@percent }
\@writefile{toc}{\contentsline {subsubsection}{\numberline {Appendix~C.2.1}Problem}{17}{subsubsection.C.2.1}\protected@file@percent }
\newlabel{strang:LogReg}{{C.6}{17}{Problem}{equation.C.6}{}}
\newlabel{strang:LogReg_grad}{{C.7}{17}{Problem}{equation.C.7}{}}
\newlabel{strang:LogReg_GF}{{C.8}{18}{Problem}{equation.C.8}{}}
\newlabel{strang:LogReg_GF_batch}{{C.9}{18}{Problem}{equation.C.9}{}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {Appendix~C.2.2}Splitting scheme and local problem}{18}{subsubsection.C.2.2}\protected@file@percent }
\newlabel{strang:LogReg_GF_local}{{C.10}{18}{Splitting scheme and local problem}{equation.C.10}{}}
\newlabel{strang:logreg_theta_from_eta}{{C.11}{18}{Splitting scheme and local problem}{equation.C.11}{}}
\newlabel{strang:logreg_eta_ode}{{C.12}{19}{Splitting scheme and local problem}{equation.C.12}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {Appendix~C.3}Softmax Regression}{19}{subsection.C.3}\protected@file@percent }
\@writefile{toc}{\contentsline {subsubsection}{\numberline {Appendix~C.3.1}Problem}{19}{subsubsection.C.3.1}\protected@file@percent }
\newlabel{strang:Softmax}{{C.13}{19}{Problem}{equation.C.13}{}}
\citation{tibshirani1996lasso}
\newlabel{strang:softmax_theta_from_eta}{{C.19}{20}{Problem}{equation.C.19}{}}
\@writefile{toc}{\contentsline {section}{\numberline {Appendix~D}LASSO with Splitting Schemes}{20}{appendix.D}\protected@file@percent }
\newlabel{sec:lasso}{{Appendix~D}{20}{LASSO with Splitting Schemes}{appendix.D}{}}
\newlabel{eq:lasso}{{D.1}{20}{LASSO with Splitting Schemes}{equation.D.1}{}}
\citation{beck2009fast}
\@writefile{toc}{\contentsline {subsection}{\numberline {Appendix~D.1}Lie–Trotter (Proximal Gradient / ISTA)}{21}{subsection.D.1}\protected@file@percent }
\newlabel{eq:lt_step}{{D.2}{21}{Lie–Trotter (Proximal Gradient / ISTA)}{equation.D.2}{}}
\@writefile{loe}{\contentsline {theorem}{\ifthmt@listswap Theorem~3\else \numberline {3}Theorem\fi \thmtformatoptarg {LT zero algorithmic bias}}{21}{theorem.3}\protected@file@percent }
\newlabel{thm:lt_lasso}{{3}{21}{LT zero algorithmic bias}{theorem.3}{}}
\newlabel{eq:lt_rate}{{D.3}{21}{LT zero algorithmic bias}{equation.D.3}{}}
\newlabel{eq:lasso_descent}{{D.4}{21}{Lie–Trotter (Proximal Gradient / ISTA)}{equation.D.4}{}}
\newlabel{eq:lasso_opt_cond}{{D.5}{21}{Lie–Trotter (Proximal Gradient / ISTA)}{equation.D.5}{}}
\newlabel{eq:lasso_one_step}{{D.6}{21}{Lie–Trotter (Proximal Gradient / ISTA)}{equation.D.6}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {Appendix~D.2}Strang Splitting (Strang-ISTA)}{22}{subsection.D.2}\protected@file@percent }
\newlabel{eq:strang_step}{{D.7}{22}{Strang Splitting (Strang-ISTA)}{equation.D.7}{}}
\@writefile{loe}{\contentsline {theorem}{\ifthmt@listswap Theorem~4\else \numberline {4}Theorem\fi \thmtformatoptarg {Strang-ISTA convergence with bias floor}}{22}{theorem.4}\protected@file@percent }
\newlabel{thm:strang_ista_convergence}{{4}{22}{Strang-ISTA convergence with bias floor}{theorem.4}{}}
\newlabel{eq:strang_rate}{{D.8}{22}{Strang-ISTA convergence with bias floor}{equation.D.8}{}}
\newlabel{eq:strang_to_fp}{{D.9}{23}{Strang Splitting (Strang-ISTA)}{equation.D.9}{}}
\@writefile{loe}{\contentsline {remark}{\ifthmt@listswap Remark~1\else \numberline {1}Remark\fi \thmtformatoptarg {Constant $C_D$ and Strang fixed-point shift}}{23}{remark.1}\protected@file@percent }
\newlabel{rem:cd_formula}{{1}{23}{Constant $C_D$ and Strang fixed-point shift}{remark.1}{}}
\newlabel{eq:cd_empirical}{{D.10}{23}{Constant $C_D$ and Strang fixed-point shift}{equation.D.10}{}}
\newlabel{eq:cd_formula}{{D.11}{23}{Constant $C_D$ and Strang fixed-point shift}{equation.D.11}{}}
\newlabel{eq:strang_shift}{{D.12}{24}{Constant $C_D$ and Strang fixed-point shift}{equation.D.12}{}}
\@writefile{loe}{\contentsline {conjecture}{\ifthmt@listswap Conjecture~1\else \numberline {1}Conjecture\fi \thmtformatoptarg {Strang support characterisation}}{24}{conjecture.1}\protected@file@percent }
\newlabel{conj:strang_support}{{1}{24}{Strang support characterisation}{conjecture.1}{}}
\newlabel{eq:strang_support_char}{{D.14}{24}{Strang support characterisation}{equation.D.14}{}}
\@writefile{loe}{\contentsline {remark}{\ifthmt@listswap Remark~2\else \numberline {2}Remark\fi \thmtformatoptarg {Numerical evidence for Conjecture~\ref {conj:strang_support}}}{24}{remark.2}\protected@file@percent }
\newlabel{rem:conj_evidence}{{2}{24}{Numerical evidence for Conjecture~\ref {conj:strang_support}}{remark.2}{}}
\@writefile{loe}{\contentsline {corollary}{\ifthmt@listswap Corollary~1\else \numberline {1}Corollary\fi \thmtformatoptarg {Splitting order matters for sparse optimisation}}{25}{corollary.1}\protected@file@percent }
\newlabel{cor:splitting_order}{{1}{25}{Splitting order matters for sparse optimisation}{corollary.1}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {Appendix~D.3}Numerical Experiments: LT vs Strang-ISTA for LASSO}{25}{subsection.D.3}\protected@file@percent }
\newlabel{sec:lasso_experiments}{{Appendix~D.3}{25}{Numerical Experiments: LT vs Strang-ISTA for LASSO}{subsection.D.3}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {D.4}{\ignorespaces Convergence of LT (ISTA) and Strang-ISTA for LASSO ($h = 0.3/L$, $K = 2000$). LT achieves $F(\bar  {\bm  {\mathbf  {\theta }}}_K) - F^* \to 0$ (zero bias, Theorem~\ref {thm:lt_lasso}); Strang-ISTA stagnates at a positive bias floor $C_D h^2\lambda ^2$ (Theorem~\ref {thm:strang_ista_convergence}).}}{25}{figure.caption.9}\protected@file@percent }
\newlabel{fig:lasso_convergence}{{D.4}{25}{Convergence of LT (ISTA) and Strang-ISTA for LASSO ($h = 0.3/L$, $K = 2000$). LT achieves $F(\bar {\vect {\theta }}_K) - F^* \to 0$ (zero bias, Theorem~\ref {thm:lt_lasso}); Strang-ISTA stagnates at a positive bias floor $C_D h^2\lambda ^2$ (Theorem~\ref {thm:strang_ista_convergence})}{figure.caption.9}{}}
\providecommand\NAT@force@numbers{}\NAT@force@numbers
\@writefile{lof}{\contentsline {figure}{\numberline {D.5}{\ignorespaces Asymptotic bias floor of Strang-ISTA vs $h^2$. The linear fit (dashed) gives slope $C_D \cdot \lambda ^2 \approx 0.96 \times (0.05)^2 = 2.40\times 10^{-3}$ (numerical estimate $C_D \approx 0.96$, Remark~\ref {rem:cd_formula}). The on-support lower bound $\|A\operatorname  {sign}(\bm  {\mathbf  {\theta }}^*)\|^2/8 \approx 0.769$ (eq.~\eqref  {eq:cd_formula}) underestimates $C_D$ because off-support components are activated at the Strang fixed point. LT bias floor is zero across all step sizes.}}{26}{figure.caption.10}\protected@file@percent }
\newlabel{fig:lasso_bias_floor}{{D.5}{26}{Asymptotic bias floor of Strang-ISTA vs $h^2$. The linear fit (dashed) gives slope $C_D \cdot \lambda ^2 \approx 0.96 \times (0.05)^2 = 2.40\times 10^{-3}$ (numerical estimate $C_D \approx 0.96$, Remark~\ref {rem:cd_formula}). The on-support lower bound $\|A\operatorname {sign}(\vect {\theta }^*)\|^2/8 \approx 0.769$ (eq.~\eqref {eq:cd_formula}) underestimates $C_D$ because off-support components are activated at the Strang fixed point. LT bias floor is zero across all step sizes}{figure.caption.10}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {D.6}{\ignorespaces Component-wise fixed-point shift $\bar  {\bm  {\mathbf  {\theta }}}^h - \bm  {\mathbf  {\theta }}^*$ for Strang-ISTA vs the theoretical prediction $(h\lambda /2)\operatorname  {sign}(\bm  {\mathbf  {\theta }}^*)$ (eq.~\eqref  {eq:strang_shift}). Agreement is within numerical precision ($h = 0.3/L$). LT fixed point coincides with $\bm  {\mathbf  {\theta }}^*$ (zero shift).}}{27}{figure.caption.11}\protected@file@percent }
\newlabel{fig:lasso_fp_shift}{{D.6}{27}{Component-wise fixed-point shift $\bar {\vect {\theta }}^h - \vect {\theta }^*$ for Strang-ISTA vs the theoretical prediction $(h\lambda /2)\operatorname {sign}(\vect {\theta }^*)$ (eq.~\eqref {eq:strang_shift}). Agreement is within numerical precision ($h = 0.3/L$). LT fixed point coincides with $\vect {\theta }^*$ (zero shift)}{figure.caption.11}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {D.7}{\ignorespaces Dual variables $|d_j| = |[A^\top (A\bm  {\mathbf  {\theta }}^* - \bm  {\mathbf  {y}})]_j|/\lambda $ at the LT fixed point for all $d{=}20$ components, sorted by magnitude. The horizontal dashed lines mark $|d_j|/\lambda = 1$ (LT activation threshold) and $|d_j|/\lambda = 0.5$ (Strang activation threshold, Conjecture~\ref {conj:strang_support}). Support components $j \in \{0,\ldots  ,5\}$ achieve $|d_j|{=}\lambda $; off-support component $j{=}8$ has $|d_8|{\approx }0.563\lambda > \lambda /2$ and is the only additional component activated by Strang-ISTA.}}{27}{figure.caption.12}\protected@file@percent }
\newlabel{fig:lasso_dual_vars}{{D.7}{27}{Dual variables $|d_j| = |[A^\top (A\vect {\theta }^* - \vect {y})]_j|/\lambda $ at the LT fixed point for all $d{=}20$ components, sorted by magnitude. The horizontal dashed lines mark $|d_j|/\lambda = 1$ (LT activation threshold) and $|d_j|/\lambda = 0.5$ (Strang activation threshold, Conjecture~\ref {conj:strang_support}). Support components $j \in \{0,\ldots ,5\}$ achieve $|d_j|{=}\lambda $; off-support component $j{=}8$ has $|d_8|{\approx }0.563\lambda > \lambda /2$ and is the only additional component activated by Strang-ISTA}{figure.caption.12}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {D.8}{\ignorespaces Support of LT and Strang-ISTA fixed points as a function of step size $h/L$. LT (blue) maintains the true 6-sparse support for all tested $h$. Strang-ISTA (orange) activates one additional off-support component ($j{=}8$, $|d_8|{\approx }0.563\lambda $) for all $h \in [0.1/L,\, 0.7/L]$, consistent with Conjecture~\ref {conj:strang_support}.}}{28}{figure.caption.13}\protected@file@percent }
\newlabel{fig:lasso_support_exp}{{D.8}{28}{Support of LT and Strang-ISTA fixed points as a function of step size $h/L$. LT (blue) maintains the true 6-sparse support for all tested $h$. Strang-ISTA (orange) activates one additional off-support component ($j{=}8$, $|d_8|{\approx }0.563\lambda $) for all $h \in [0.1/L,\, 0.7/L]$, consistent with Conjecture~\ref {conj:strang_support}}{figure.caption.13}{}}
\gdef \@abspage@last{29}