	\begin{algorithmic}[1]
		\State \textbf{Input:} initial point $w_0$, learning rate $\eta$, preconditioner $\hat{D}_0$, probability $p$
		\State $v_0 = \nabla P(w_0)$ \label{SARAHbegin}
		\For{$t = 0,1,2,\ldots$}
		\State $w_{t+1} = w_t - \eta \hat{D}^{-1}_{t}v_t$\label{SARAHpreconditionedstep}
		\State Generate independently batches $i_{t+1}$ for $v_{t+1}$ and $\mathcal{J}_t$ for $\hat{D}_{t+1}$
		\State $v_{t+1} = \begin{cases}
                                \nabla P(w_{t+1}), & \text{with probability } p
                                    \\
                                v_{t} + \nabla f_{i_{t+1}}(w_{t+1}) - \nabla f_{i_{t+1}}(w_t), & \text{with probability } 1 - p
                            \end{cases}$\label{SARAHupdate}
		\State Update the preconditioner $\hat{D}_{t+1}$ %according to \eqref{approx_Hessian_1},\eqref{approx_Hessian_2}
		\EndFor
		\State \textbf{Output:} $\hat{w}_T$ chosen uniformly from $\{w_t\}^T_{t=0}$
	\end{algorithmic}

\begin{algorithmic}
[1]
\State \textbf{Input:} initial point $w_0$, learning rate $\eta$, preconditioner $\hat{D}_0$, probability $p$
\State $v_0 = \nabla P(w_0)$   \For{$t = 0,1,2,\ldots$}
\State $w_{t+1} = w_t - \eta \hat{D}^{-1}_{t}v_t$  \State Generate independently batches $i_{t+1}$ for $v_{t+1}$ and $\mathcal{J}_t$ for $\hat{D}_{t+1}$
\State $v_{t+1} = \begin{cases}
\nabla P(w_{t+1}), & \text{with probability } p
\\
v_{t} + \nabla f_{i_{t+1}}(w_{t+1}) - \nabla f_{i_{t+1}}(w_t), & \text{with probability } 1 - p
\end{cases}$  \State Update the preconditioner $\hat{D}_{t+1}$ %according to \eqref{approx_Hessian_1},\eqref{approx_Hessian_2}
\EndFor
\State \textbf{Output:} $\hat{w}_T$ chosen uniformly from $\{w_t\}^T_{t=0}$
\end{algorithmic}
{
    "title": "stochastic gradient methods with preconditioned updates",
    "id": "2206.00285",
    "abstract": "this work considers the non-convex finite sum minimization problem. there are several algorithms for such problems, but existing methods often work poorly when the problem is badly scaled and/or ill-conditioned, and a primary goal of this work is to introduce methods that alleviate this issue. thus, here we include a preconditioner based on hutchinson's approach to approximating the diagonal of the hessian, and couple it with several gradient-based methods to give new scaled algorithms: scaled sarah and scaled l-svrg. theoretical complexity guarantees under smoothness assumptions are presented. we prove linear convergence when both smoothness and the pl condition are assumed. our adaptively scaled methods use approximate partial second-order curvature information and, therefore, can better mitigate the impact of badly scaled problems. this improved practical performance is demonstrated in the numerical experiments also presented in this work.",
    "categories": "math.oc cs.lg",
    "doi": "",
    "created": "2022-06-01",
    "updated": "2024-01-14",
    "authors": [
        "abdurakhmon sadiev",
        "aleksandr beznosikov",
        "abdulla jasem almansoori",
        "dmitry kamzolov",
        "rachael tappenden",
        "martin tak\u00e1\u010d"
    ],
    "affiliation": [],
    "url": "https://arxiv.org/abs/2206.00285"
}
{
    "ToxicityFilter": {
        "text_to_toxicity_attributes": {
            "arxiv.bbl": {
                "toxicity_score": 0.01237757,
                "severe_toxicity_score": 0.0011920929,
                "identity_attack_score": 0.004180758,
                "insult_score": 0.007607877,
                "profanity_score": 0.015044857,
                "threat_score": 0.0077154995,
                "sexually_explicit_score": 0.012385205,
                "flirtation_score": 0.20258527
            },
            "arxiv.tex": {
                "toxicity_score": 0.012000589,
                "severe_toxicity_score": 0.0011825562,
                "identity_attack_score": 0.0042732526,
                "insult_score": 0.007645877,
                "profanity_score": 0.015488927,
                "threat_score": 0.007870848,
                "sexually_explicit_score": 0.014508383,
                "flirtation_score": 0.26281023
            }
        },
        "reason": null
    }
}
{
    "num_done": {
        "figure": 0,
        "algorithm": 3
    }
}
{
    "NonTrivialRenderingFilter": {
        "white_pixels_ratio": 92.3059250831437,
        "hash": "001f9fcf85830f07",
        "most_frequent_color_ratio": 92.3059250831437
    }
}