Abstract An algorithm is proposed for solving stochastic and finite sum minimization problems. Based on a trust region methodology, the algorithm employs normalized steps, at least as long as the norms of the stochastic gradient estimates are within a specified interval. The complete algorithm-which dynamically chooses whether or not to employ normalized steps-is proved to have convergence guarantees that are similar to those possessed by a traditional stochastic gradient approach under various sets of conditions related to the accuracy of the stochastic gradient estimates and choice of stepsize sequence. The results of numerical experiments are presented when the method is employed to minimize convex and nonconvex machine learning test problems. These results illustrate that the method can outperform a traditional stochastic gradient approach. Introduction The stochastic gradient (SG) method is the signature strategy for solving stochastic and finite-sum minimization problems. In this iterative approach, each step to update the solution estimate is obtained by taking a negative multiple of an unbiased gradient estimate. With careful choices for the stepsize sequence, the SG method possesses convergence guarantees and has been employed to great success for solving various types of problems, such as those arising in machine learning. For fundamental work on SG, see [19] and [20] . Introduction One disadvantage of the SG method is that stochastic gradients, like the gradients that they approximate, possess no natural scaling. By this, we mean that in order to guarantee convergence, the algorithm needs to choose stepsizes in a problem-dependent manner; e.g., common theoretical guarantees require that the stepsize is proportional to 1/L, where L is a Lipschitz constant for the gradient of the objective function. This is in contrast to Newton's method for minimization, for which one can obtain (local) convergence guarantees with a stepsize of 1. Admittedly, Newton's method is not generally guaranteed to converge from remote starting points with unit stepsizes, but these observations do highlight a shortcoming of first-order methods, namely, that for convergence guarantees the stepsizes need always be chosen in a problem-dependent manner. Introduction The purpose of this paper is to propose a new algorithm for stochastic and finite-sum minimization. Our proposed approach can be viewed as a modification of the SG method. The approach does not completely overcome the issue of requiring problem-dependent stepsizes, but we contend that our approach does, for practical purposes, reduce somewhat this dependence. This is achieved by employing, under certain conditions, normalized steps. We motivate our proposed approach by illustrating how it can be derived from a trust region methodology. This work can be viewed as a first step toward designing new classes of first-and second-order trust region methods for solving stochastic and finite-sum minimization problems. Introduction The use of normalized steps has previously been proposed in the context of (stochastic) gradient methods for solving minimization problems. For example, in a method that is similar to ours, [12] propose an approach that employs normalized steps in every iteration. They show that, if the objective function is M -bounded and strictly-locally-quasi-convex, the stochastic gradients are sufficiently accurate with respect to the true gradients (specifically, when mini-batch sizes are Ω( −2 )), and a sufficiently large number of iterations are run (specifically, Ω( −2 )), then their method will, with high probability, yield a solution estimate that is -optimal. By contrast, our approach, by employing a modified update that does not always involve the use of a normalized step, enjoys convergence guarantees under different assumptions. We argue in this paper that employing normalized steps in all iterations cannot lead to general convergence guarantees, which perhaps explains the additional assumptions required for convergence by [12] . Introduction It is also worthwhile to mention the broader literature. For important work on SG-type methods and their corresponding theoretical analyses, see, e.g., [1] , [3] , [6] , [9] , [10] , [11] , [13] , and [18] . There are also numerous variants of SG methods based on gradient aggregation, iterative averaging, second-order techniques, momentum, acceleration, and beyond; for work on these, see [2] and the references therein. More related to our work are techniques that normalize steplengths based on accumulated gradient information; see, e.g., [7] and [21] . In a different direction, one should also contrast our work with stochastic trust region approaches, such as those in [16] and [5] . The approaches proposed in these papers, which are based on the use of randomized models of the objective function constructed during each iteration, are quite distinct from our proposed method. For example, these approaches follow a traditional trust region strategy of accepting or rejecting each step based on the magnitude of an (approximate) actual-to-predicted reduction ratio. Our method, on the other hand, is closer to the SG method in that it accepts the computed step in every iteration. Another distinction is that these other approaches rely on the use of so-called fully linear models of the objective function to obtain their convergence guarantees. Our convergence guarantees are obtained under straightforward upper bounds on the second moment of the stochastic gradient estimates, and do not require fully linear models. Introduction The paper is organized as follows. Our algorithm and motivation for our specific iterate updating scheme are the subject of §2. In §3, we prove convergence guarantees for the algorithm under various types of assumptions on the stochastic gradient estimates and stepsize choices. The results of numerical experiments on test problems-some convex and some nonconvex-are given in §4. Concluding remarks are given in §5. All norms in the paper are Euclidean, i.e., · := · 2 . Algorithm Our problem of interest is a stochastic optimization problem in which the goal is to minimize over a vector of decision variables, indicated by x ∈ R n , a function f : R n → R defined by the expectation of another function F : R n × Ξ → R that depends on a random variable ξ, i.e., Algorithm where E ξ [·] denotes expectation with respect to the distribution of ξ. Our algorithm is also applicable for finite-sum minimization where the objective takes the form Algorithm Such objectives often arise in sample average approximations of (2.1); e.g., see [22] . Algorithm Description Our algorithm is stated below as TRish, a trust-region-ish algorithm for stochastic optimization. Each iteration involves taking a step along the negative of a stochastic gradient direction. In the context of problem (2.1), this stochastic gradient can be viewed as Algorithm Description , where x k is the current iterate and ξ k is a realization of the random variable ξ. In the context of problem (2.2), it can be viewed as Algorithm Description where i k has been chosen randomly as an index in {1, . . . , N }. In addition, in either case, g k could represent an average of such quantities, i.e., over a set of independently generated realizations {ξ k,j } j∈S k or over independently generated indices {i k,j } j∈S k . This leads to a so-called mini-batch approach with S k representing the mini-batch of samples in the kth iteration. In the algorithm, we simply write g k ≈ ∇f (x k ) to cover all of these situations, since in any case g k represents a stochastic gradient estimate for f at x k . Algorithm Description Algorithm TRish (Trust-region-ish algorithm based on careful step normalization) Algorithm Description Generate a stochastic gradient g k ≈ ∇f (x k ). 5: Set 5: , ∞). 6: end for The scaling of the stochastic gradient employed in TRish can be motivated in the following manner. Given a stochastic gradient g k and a stepsize α k , consider the trust region subproblem 6: end for 3) 6: end for The solution of this subproblem, namely, s k = −α k g k / g k , represents the step that minimizes the first-order model f (x k ) + g T k s of the objective function f at x k subject to s having norm less than or equal to α k . This is the prototypical strategy in a trust region methodology. When the norm of g k falls within the interval [ 6: end for ], TRish takes the step s k . However, if this were to be done no matter the norm of g k , then the resulting algorithm might fail to make progress in expectation. This is illustrated in the following example. 6: end for Example 2.1. Suppose that, at a point x k ∈ R, one has ∇f (x k ) = 1 and obtains g k = 6 with probability Then, 6: end for , where E k denotes expectation given that an algorithm has reached x k as the kth iterate. However, this means that the normalized stochastic gradient satisfies g k g k = 1 with probability 1 3 −1 with probability 2 3 , from which it follows that s k = −α k g k / g k is twice as likely to be a direction of ascent for f at x k than it is to be a direction of descent for f at x k . 6: end for One can argue from this example that, without potentially restrictive assumptions on the objective function f and/or the manner in which the stochastic gradient is computed, one cannot expect to be able to prove convergence guarantees for an algorithm that solely computes steps based on solving the trust region subproblem (2.3). In particular, the existence of any point (let alone more than one) at which the expectation is to follow an ascent direction foils the typical convergence theory for an SG approach; see, e.g., [2] . 6: end for In TRish, we overcome the issue highlighted in Example 2.1 by only choosing the trust region step when the norm of the gradient is within a specified interval; otherwise, we compute a stochastic gradient step with a stepsize that is a multiple of α k . It is for this reason that we refer to the algorithm as a trust-region-ish approach. Overall, as a function of the norm of the stochastic gradient, the norm of the step taken by the algorithm is illustrated in Figure 1 . Note that care has been taken to make sure that the norm of the step is a continuous function of the norm of the stochastic gradient estimate. The plot in Figure 1 illustrates the relationship for moderate values of (γ 1,k , γ 2,k ), but notice that for more extreme values (i.e., γ 1,k 0 and γ 2,k ≈ 0) the function would essentially be flat (except for stochastic gradients that are very small or large in norm), meaning that the stepsize would typically be scaled so that the step norm is approximately α k for all k ∈ N. Our convergence analysis in the next section requires certain restrictions on the choice of stepsizes-as is typical for (stochastic) gradient methods-and require certains restrictions on {γ 1,k } and {γ 2,k }. For example, the issue in Example 2.1 is avoided as long as the pair (γ 1,k , γ 2,k ) is chosen such that the step is not normalized with probability 1 at the given x k , which means that-for this particular function, iterate, and variance in the stochastic gradient estimates-one cannot choose this pair such that |6| ∈ [ approximation of f at x plus a quadratic term with constant L ∈ (0, ∞), i.e., 6: end for It is known that (3.1) holds if the gradient function ∇f is Lipschitz continuous with constant L. This is often referred to as L-smoothness of the function f . 6: end for We also make the following assumption about the stochastic gradients computed in TRish. This assumption is standard in analyses of SG methods; it is easily seen to be satisfied when the variance of the stochastic gradient estimate is uniformly bounded over k ∈ N. Assumption 3.2. For all k ∈ N, the stochastic gradient g k is an unbiased estimator of ∇f (x k ) in the sense that 6: end for Under these assumptions, we prove the following lemma providing fundamental inequalities satisfied by TRish. For ease of reference in this result and throughout the remainder of our analysis, we define the following cases based on those indicated in Line 5 of TRish: 6: end for The following lemma reveals an upper bound for the expected decrease in f for all k ∈ N. 6: end for Lemma 3.1. Under Assumptions 3.1 and 3.2, the iterates of TRish satisfy, for all k ∈ N, 6: end for where E k is the event that ∇f (x k ) T g k ≥ 0 and P k [E k ] is the probability of this event. 6: end for Proof. Proof. For all k ∈ N, let s k := x k+1 − x k represent the step taken by the algorithm. By (3.1), 6: end for Thus, with C i,k for i ∈ {1, 2, 3} respectively representing the events that case 1, case 2, and case 3 occur, and with P k [C i,k ] for i ∈ {1, 2, 3} respectively representing the probabilities of these events, one finds from the law of total probability that 6: end for In the event C 1,k , the algorithm yields 6: end for along with the fact that 6: end for In the event C 2,k , in which g k −1 ≤ γ 1,k and g k −1 ≥ γ 2,k , one finds that 6: end for along with the fact that 6: end for In the event C 3,k , the algorithm yields 6: end for along with the fact that 6: end for Combining (3.4)-(3.10), it follows that 6: end for Applying the upper bound for the last term in (3.2) and rearranging terms yields the result. 6: end for For some (but not all) of our convergence guarantees, we also make the following assumption. 6: end for Assumption 3.3. At any x ∈ R n , the Polyak-Lojasiewicz condition holds with c ∈ (0, ∞), i.e., 6: end for Assumptions 3.1 and 3.3 do not ensure that a stationary point for f exists, though, when combined, they do guarantee that any stationary point for f is a global minimizer of f . Assumption 3.3 holds when f is cstrongly convex, but it is also satisfied for other functions that are not convex. We direct the interested reader to [14] for a discussion on the relationship between the Polyak-Lojasiewicz condition and the related error bounds, essential strong convexity, weak strong convexity, restricted secant inequality, and quadratic growth conditions. In short, when f has a Lipschitz continuous gradient, the Polyak-Lojasiewicz is the weakest of these except for the quadratic growth condition, though these two are equivalent when f is convex. 6: end for We now proceed to prove convergence guarantees for TRish in various cases depending on whether or not the Polyak-Lojasiewicz condition (hereafter referred to as the P-L condition) holds and based on different sets of properties of the sequence of stepsizes and stochastic gradient estimates. Our analysis covers various types of convex and nonconvex objective functions. P-L Condition and Constant Parameters Let us first prove a convergence result for TRish when the P-L condition holds and each sequence {α k }, {γ 1,k }, and {γ 2,k } is constant. This result appears in this section as Theorem 3.1. P-L Condition and Constant Parameters Our first requirement toward proving Theorem 3.1 is the following lemma. P-L Condition and Constant Parameters Lemma 3.2. Under Assumption 3.2, it follows that, for all k ∈ N, P-L Condition and Constant Parameters Proof. Proof. One finds with the law of total probability that P-L Condition and Constant Parameters Then, by Jensen's Inequality, concavity of the square root, and Assumption 3.2, one finds that P-L Condition and Constant Parameters Therefore, by combining the inequalities above, one finds that P-L Condition and Constant Parameters where the second inequality follows by the fact that a ≤ 1 2 (1 + a 2 ) for any a ∈ R. While the upper bound on 2) in Assumption 3.2 is standard in the literature, the quantity on the left-hand side of (3.12)-which Lemma 3.2 shows is bounded in a similar manner-is uniquely important for our analysis. For this reason, we feel that it is useful to provide specific examples illustrating how this quantity is bounded. We state two related examples next. While the upper bound on Example 3.1. Suppose f : R → R and x k are given such that ∇f (x k ) = µ k ∈ R, where without loss of generality one can assume that µ k ≥ 0. In addition, suppose that g k follows a normal distribution with mean µ k and variance σ 2 k . Then, While the upper bound on Let us separately investigate these two terms on the right-hand side. First, one finds that While the upper bound on Second, one finds that While the upper bound on Thus, combining the bounds above, one finds that While the upper bound on Overall, if σ k ≤ σ for some positive σ ∈ R for all k ∈ N, then (3.12) holds with While the upper bound on In addition, suppose that g k follows a normal distribution with mean µ k and covariance matrix Σ k . Then, by Theorem 3.3.3 in [23] , the inner product ∇f (x k ) While the upper bound on T g k follows a normal distribution with mean µ k 2 and variance µ T k Σ k µ k . Hence, following the analysis in Example 3.1, if µ T k Σ k µ k ≤ σ for some positive σ ∈ R for all k ∈ N, then (3.12) holds with h 1 and h 2 from (3.13). While the upper bound on We now prove our first theorem on the behavior of TRish. While the upper bound on 14) While the upper bound on where While the upper bound on Then, for all k ∈ N, the expected optimality gap satisfies While the upper bound on where While the upper bound on Proof. Proof. Combining the results of Lemmas 3.1 and 3.2, it follows that, for all k ∈ N, While the upper bound on Therefore, with (θ 1 , θ 2 ) defined in (3.15)/(3.17), it follows with (3.11) that, for all k ∈ N, While the upper bound on Adding and subtracting f * on the left-hand side, taking total expectations, and rearranging yields While the upper bound on Since 1 − 2cαθ 1 ∈ (0, 1), this represents a contraction inequality. Applying the result repeatedly through iteration k ∈ N, one obtains the desired result. While the upper bound on It is worthwhile to compare the result of Theorem 3.1 with a corresponding result known to hold for a straightforward SG method. For example, from [2, Thm. 4.6] with our notation, it is known that for an SG method with fixed stepsize α = (which may occur, e.g., if c ≈ 0) yields an upper bound for the expected optimality gap that converges to While the upper bound on We can now make a couple of observations. On one hand, if While the upper bound on This quantity is less than M1 2c , i.e., the approximate bound for SG, if, e.g., the parameters satisfy γ 1 ∈ (0, 1) with While the upper bound on then the condition that γ1 γ2 < h2 h2−1 essentially requires that γ 1 ≈ γ 2 , in which case the bound (3.19) is approximately γ1M1 2cM2 , which is less than the bound for SG if γ 1 ∈ (0, 1). Overall, while we are not necessarily recommending that one employes TRish with the parameter settings mentioned in this discussion, we have at least been able to demonstrate in both of these cases that TRish can possess an asymptotic bound on the expected optimality gap that is on par with that for SG. (For a detailed discussion on how to choose (γ 1 , γ 2 ) in practice, see §4.1.) While the upper bound on Besides the conclusions of the previous paragraph, the result of Theorem 3.1 points to fundamental differences between TRish and SG for certain choices of the input parameters. In particular, the result in [2, Thm. 4.6] points to a well-known trade-off for SG with a fixed stepsize: If a relatively large stepsize is employed, then the rate to achieve the asymptotic expected optimality gap involves a better constant at the sake of the upper bound on the gap being relatively large, i.e., αLM1 2c , which is proportional to the stepsize α. On the other hand, one can achieve a smaller upper bound on the expected optimality gap with a smaller α, but at the cost of a worse constant in the rate to achieve that gap. A similar conclusion can be derived from (3.16) for TRish: One can control the constant (1 − 2cαθ 1 ) by the choice of α. However, the effect of α on the expected optimality gap is not exactly the same for TRish as for an SG method. This can be seen in the fact that the left-hand side of (3.19) involves one term that decreases with α, but another term that does not. That said, one can compensate for this in TRish if one ties the difference γ 1 − γ 2 to the stepsize α. This idea can be seen in the first of our two theorems in the next subsection. P-L Condition and Sublinearly Diminishing Stepsizes Let us now consider the behavior of TRish when the P-L condition holds and diminishing stepsizes are employed. Our first theorem in this setting, which makes the same assumptions as Theorem 3.1, but involves different parameter choices, is the following. (The parameter choices in the theorem could be generalized even further. However, we have made certain choices-e.g., to have {γ 1 } be constant-for some amount of simplicity in the proof while still maintaining generality. One could prove a similar result with {γ 2 } constant instead, or with neither {γ 1 } nor {γ 2 } constant, as long as the sequence {γ 1,k − γ 2,k } is proportional to α k , as it is in the following theorem.) P-L Condition and Sublinearly Diminishing Stepsizes for all k ∈ N. Then, for all k ∈ N, the expected optimality gap satisfies P-L Condition and Sublinearly Diminishing Stepsizes where P-L Condition and Sublinearly Diminishing Stepsizes Proof. Proof. First observe that the restrictions on P-L Condition and Sublinearly Diminishing Stepsizes Thus, similar to the proof of Theorem 3.1, for all k ∈ N, P-L Condition and Sublinearly Diminishing Stepsizes Therefore, with δ defined in (3.23), it follows with (3.11) that, for all k ∈ N, P-L Condition and Sublinearly Diminishing Stepsizes Adding and subtracting f * on the left-hand side, taking total expectations, and rearranging yields P-L Condition and Sublinearly Diminishing Stepsizes Let us now prove (3.21) by induction. First, for k = 1, the inequality holds by the definition of φ. Now suppose that (3.21) holds up to k ∈ N; then, for k + 1, one finds from above that P-L Condition and Sublinearly Diminishing Stepsizes where the last two inequalities follow from the definition of φ and since (b + k − 1)(b + k + 1) ≤ (b + k) 2 , respectively. The desired conclusion now follows from this inductive argument. P-L Condition and Sublinearly Diminishing Stepsizes As one might predict from the discussion at the end of §3.1, in Theorem 3.2 we have been able to prove sublinear convergence of the expected optimality gap by tying the rate that {γ 1,k − γ 2,k } vanishes to the rate that {α k } vanishes; in particular, both the differences and the stepsizes diminish sublinearly, as is the case in similar results for SG methods. P-L Condition and Sublinearly Diminishing Stepsizes One might also be interested in the behavior of TRish when the sequences {γ 1,k } and {γ 2,k } are constant while only the stepsizes decrease sublinearly. For example, this might be of interest since otherwise there are additional parameters to estimate and/or to tune. In the remainder of this subsection, we prove a sublinear convergence result under this setting. However, achieving sublinear convergence in this setting requires the following assumption, which can be viewed as a strengthening of (3.2) from Assumption 3.2. P-L Condition and Sublinearly Diminishing Stepsizes Assumption 3.4. There exists a pair (M 3 , M 4 ) ∈ (0, ∞) × (0, ∞) (independent of k) such that, for all k ∈ N, the squared norm of g k satisfies P-L Condition and Sublinearly Diminishing Stepsizes One finds that Assumption 3.4 can be satisfied under reasonable conditions in practice if one employs mini-batch stochastic gradient estimates with sample sizes that increase with k; see, e.g., [9] . For example, in the context of problem (2.1), suppose that (3.27) where the values {ξ k,j } j∈S k are drawn independently according to the distribution of ξ. If one assumes that the variance of each ∇ x F (x k , ξ k,j ) is equal and bounded by M ∈ (0, ∞), then for arbitrary j ∈ S k it follows (see, e.g., [8] ) that P-L Condition and Sublinearly Diminishing Stepsizes Proof. Proof. By Jensen's Inequality, concavity of the square root, and Assumption 3.4, one finds that P-L Condition and Sublinearly Diminishing Stepsizes The result then follows using the same line of argument as used in the proof of Lemma 3.2. P-L Condition and Sublinearly Diminishing Stepsizes The following examples parallel Examples 3.1 and 3.2, but illustrate the attainment of (3.29). P-L Condition and Sublinearly Diminishing Stepsizes Example 3.3. Consider the scenario in Example 3.1. Then, if σ k ≤ α k for all k ∈ N with α k ≤ α for some α ∈ (0, ∞) for all k ∈ N, it follows that (3.29) holds with P-L Condition and Sublinearly Diminishing Stepsizes Example 3.4. Consider the scenario in Example 3.2. Then, if µ T k Σ k µ k ≤ α k for all k ∈ N with α k ≤ α for some α ∈ (0, ∞) for all k ∈ N, it follows that (3.29) holds with h 3 and h 4 from (3.30). P-L Condition and Sublinearly Diminishing Stepsizes Our next theorem on the behavior of TRish is now proved as the following. (For the result, we include Assumptions 3.2 and 3.4 for convenience since, in our proof, we employ results that we have proved using each of these assumptions. Notice, however, that the bound (3. P-L Condition and Sublinearly Diminishing Stepsizes where P-L Condition and Sublinearly Diminishing Stepsizes Then, for all k ∈ N, the expected optimality gap satisfies P-L Condition and Sublinearly Diminishing Stepsizes Proof. Proof. Similar to the proof of Theorem 3.1, for all k ∈ N, P-L Condition and Sublinearly Diminishing Stepsizes k . Therefore, with (β 1 , β 2 ) defined in (3.31)/(3.34), it follows with (3.11) that, for all k ∈ N, P-L Condition and Sublinearly Diminishing Stepsizes k . Adding and subtracting f * on the left-hand side, taking total expectations, and rearranging yields P-L Condition and Sublinearly Diminishing Stepsizes Using this inequality, which has the same form as (3.25), one can apply the same inductive argument as in the remainder of the proof of Theorem 3.2 to achieve the desired result. P-L Condition and Sublinearly Diminishing Stepsizes Overall, we have proved two theorems for TRish when diminishing stepsizes are employed. If the sequence {γ k,1 − γ k,2 } diminishes proportionally with {α k }, then sublinear convergence of the expected optimality gap is achieved under the same assumptions as needed for such a result for an SG method. We followed this with a result for the case when {γ k,1 − γ k,2 } is constant, in which case a sublinear convergence result for the expected optimality gap requires that the stochastic gradient estimates satisfy Assumption 3.4. P-L Condition, Constant Parameters, and Linearly Decreasing Variance Let us now prove a convergence result for TRish when the P-L condition holds, each sequence {α k }, {γ 1,k }, and {γ 2,k } is constant, and the stochastic gradients satisfy the following assumption. P-L Condition, Constant Parameters, and Linearly Decreasing Variance The achievement of linear convergence of the expected optimality gap for SG also requires increasingly accurate gradient estimates along the lines required in Assumption 3.5; see, e.g., [2] . One finds that Assumption 3.5 can be satisfied under reasonable conditions in practice if one employs mini-batch stochastic gradient estimates with sample sizes that increase with k. For example, using estimates as in (3.27 ) and under the same conditions as led to (3.28), one finds that (3.36) holds if the sample sizes increase geometrically, e.g., P-L Condition, Constant Parameters, and Linearly Decreasing Variance for some τ ∈ (1, ∞). Our main result in this section, namely, Theorem 3.4, requires the following. P-L Condition, Constant Parameters, and Linearly Decreasing Variance Lemma 3.4. Under the Assumption 3.5, it follows that, for all k ∈ N, P-L Condition, Constant Parameters, and Linearly Decreasing Variance Proof. Proof. By Jensen's inequality, concavity of the square root, and Assumption 3.5, one finds that P-L Condition, Constant Parameters, and Linearly Decreasing Variance The result then follows using the same line of argument as used in the proof of Lemma 3.2. P-L Condition, Constant Parameters, and Linearly Decreasing Variance The following examples parallel Examples 3.1 and 3.2, but illustrate the attainment of (3.37). P-L Condition, Constant Parameters, and Linearly Decreasing Variance Example 3.5. Consider the scenario in Example 3.1. Then, since (3.36) implies that σ 2 k ≤ M 3 ζ k−1 for all k ∈ N, it follows along with the fact that ζ ∈ (0, 1) that P-L Condition, Constant Parameters, and Linearly Decreasing Variance Hence, it follows that (3.37) holds with P-L Condition, Constant Parameters, and Linearly Decreasing Variance , and λ = ζ. P-L Condition, Constant Parameters, and Linearly Decreasing Variance follows that (3.37) holds with h 5 , h 6 , and λ from (3.39). P-L Condition, Constant Parameters, and Linearly Decreasing Variance Our next theorem on the behavior of TRish is now proved as the following. (For the result, we include Assumptions 3.2 and 3.5 for convenience since, in our proof, we employ results that we have proved using each of these assumptions. Notice, however, that the bound (3.2) in Assumption 3.2 holds under Assumption 3.5 if one considers M 1 ≥ M 5 , M 2 ≥ 1, and any ζ ∈ (0, 1).) Theorem 3.4. Under Assumptions 3.1, 3.2, 3.3, and 3.5, and with a tuple (h 5 , h 6 , λ) satisfying the inequalities in Lemma 3.4, suppose that TRish is run with γ 1 > γ 2 > 0 such that γ1 γ2 < h6 h6−1 (meaning γ 1 − h 6 (γ 1 − γ 2 ) > 0), and with α k = α for all k ∈ N such that P-L Condition, Constant Parameters, and Linearly Decreasing Variance where P-L Condition, Constant Parameters, and Linearly Decreasing Variance Then, for all k ∈ N, the expected optimality gap satisfies P-L Condition, Constant Parameters, and Linearly Decreasing Variance where P-L Condition, Constant Parameters, and Linearly Decreasing Variance cκ1 } > 0, and ρ := max{1 − αcκ 1 , λ, ζ} ∈ (0, 1). P-L Condition, Constant Parameters, and Linearly Decreasing Variance Proof. Proof. As in the proof of Lemma 3.1, it follows with (3.36) and (3.37) that, for all k ∈ N, P-L Condition, Constant Parameters, and Linearly Decreasing Variance Therefore, with (κ 1 , κ 2 ) defined in (3.41)/(3.43), it follows with (3.11) that, for all k ∈ N, P-L Condition, Constant Parameters, and Linearly Decreasing Variance Let us now prove (3.42) by induction. First, for k = 1, the inequality follows by the definition of ω. Then, assuming the inequality holds true for k ∈ N, one finds that P-L Condition, Constant Parameters, and Linearly Decreasing Variance which proves that the conclusion holds for k + 1, as desired. No P-L Condition and Constant Parameters Let us now consider the behavior of TRish when the P-L condition does not hold. Our first such result involves the use of constant {γ 1,k }, {γ 2,k }, and {α k }. No P-L Condition and Constant Parameters Then, with (θ 1 , θ 2 ) defined in (3.15)/ (3.17), it follows that, for all K ∈ N, No P-L Condition and Constant Parameters and No P-L Condition and Constant Parameters Proof. Proof. As in the proof of Theorem 3.1, combining the results of Lemmas 3.1 and 3.2, it follows that the inequality (3.18) holds for all k ∈ N. Taking total expectations, it follows that, for all k ∈ N, No P-L Condition and Constant Parameters Summing both sides for k ∈ {1, . . . , K} yields No P-L Condition and Constant Parameters Rearranging yields (3.44a), then dividing by K yields (3.44b). No P-L Condition and Constant Parameters As in the case of [2, Thm. 4.8], this result shows that while one cannot bound the expected optimality gap as when the P-L condition holds, one can bound the average norm of the gradients of the objective that are observed during the optimization process. No P-L Condition and Sublinearly Diminishing Stepsizes Finally, let us consider the behavior of TRish when the P-L condition does not hold and diminishing stepsizes are employed. For brevity, the following theorem considers both when parameters are chosen as in Theorem 3.2 and as in Theorem 3.3, since in either case the final conclusion is the same. (ii) Suppose Assumption 3.4 holds and, with a pair (h 3 , h 4 ) satisfying the inequalities in Lemma 3.3, suppose that TRish is run with {γ 1,k }, {γ 2,k }, and {α k } chosen as in Theorem 3.3. No P-L Condition and Sublinearly Diminishing Stepsizes Then, with No P-L Condition and Sublinearly Diminishing Stepsizes and No P-L Condition and Sublinearly Diminishing Stepsizes Proof. Proof. First observe that, under the conditions of the theorem, specifically the conditions placed on the stepsize sequence {α k } in Theorem 3.2 or Theorem 3.3, it follows that No P-L Condition and Sublinearly Diminishing Stepsizes Second, following the proofs of Theorem 3.2 or Theorem 3.3, it follows that under conditions (i) or (ii) one finds by taking total expectations in (3.24) or (3.35) that No P-L Condition and Sublinearly Diminishing Stepsizes Without loss of generality, let us assume that condition (ii) holds and the latter inequality above is satisfied. No P-L Condition and Sublinearly Diminishing Stepsizes (The proof is the same if condition (i) holds and the former inequality above is satisfied.) Summing both sides for k ∈ {1, . . . , K} yields No P-L Condition and Sublinearly Diminishing Stepsizes which after rearrangement gives No P-L Condition and Sublinearly Diminishing Stepsizes From (3.46), it follows that the right-hand side converges to a finite limit as K → ∞, giving (3.45a). Then, the limit (3.45b) follows since (3.46) ensures that No P-L Condition and Sublinearly Diminishing Stepsizes A consequence of this theorem is the straightforward fact that No P-L Condition and Sublinearly Diminishing Stepsizes That is, under the conditions of the theorem, the expected squared norms of the gradients at the iterates of the algorithm cannot stay bounded away from zero. Numerical Experiments In this section, we provide the results of numerical experiments to demonstrate the performance of TRish compared to a stochastic gradient (SG) approach. Through solving machine learning test problems involving objective functions of the form (2.2)-some convex and some nonconvex-we demonstrate that TRish can outperform SG with comparable computational effort. Before presenting our results, we first discuss how the parameters of the algorithm might be chosen. Algorithm Parameter Selection Our analysis in §3 provides guidelines on how the stepsizes {α k } and pairs {(γ 1,k , γ 2,k )} should be chosen to guarantee convergence properties for TRish. That said, as for SG, the values required by the theory are often too conservative in practice, whereas one often finds better performance by a parameter tuning scheme. Still, it is worthwhile to comment on how the theoretical analysis might inform parameter selection. For our purposes, since our numerical experiments focus on results obtained with fixed parameters, we shall discuss how the analysis in §3.1 informs parameter selection. Similar conclusions can be drawn based on our other theoretical results. Algorithm Parameter Selection For simplicity, let us assume that the bound (3.2) in Assumption 3.2 holds with M 2 = 1. In this case, the bound (3.2) is equivalent to the restriction that the variance of the stochastic gradient estimate is bounded by Algorithm Parameter Selection If one has an estimate M 1 of M 1 -which, for example, can be obtained by sampling gradients and computing a variance estimate-then, following Lemma 3.2, one can employ the value h 2 = 1 2 M 1 + 1 for parameter selection. In particular, Theorem 3.1 suggests to choose (γ 1 , γ 2 ) such that Algorithm Parameter Selection Naturally, this still leads to flexibility in the precise values of (γ 1 , γ 2 ), but the trade-offs between different choices become similar to the traditional trade-offs one finds for the selection of α in an SG scheme: (i) one can choose values such that γ 1 − γ 2 is large, which leads to fast convergence, but only to a relatively large neighborhood of the solution, or (ii) one can choose values such that γ 1 − γ 2 is small, which leads to slow convergence, but to a relatively small neighborhood of a solution. Overall, one might be discouraged by the idea that the choice of (γ 1 , γ 2 ) requires estimation of the upper bound M 1 . However, this is not dissimilar to the fact that, theoretically, one needs an estimate of the Lipschitz constant L of the gradient in order to choose the stepsize for SG, and clearly also for TRish, such as through the bound (3.14). The good news is that estimating the variance of the stochastic gradient estimates is a reasonable request that could even be done during an initial phase that simply uses SG iterations. Despite all of this commentary, in practice one should expect to achieve better performance by simply tuning parameters for a given problem, as is often done for SG methods. For our experiments described in the following subsections, we chose (γ 1 , γ 2 ) by a simple tuning scheme that also selects the stepsize α. We took care to make sure that the tuning procedure for TRish did not require more effort than the tuning used for the SG method that we have for comparison purposes. Logistic Regression As a first test case, we considered the problem of binary classification through logistic regression using a few datasets available in the well-known LIBSVM repository; see [4] . In particular, for each dataset, with training feature vector z i ∈ R n and training label y i ∈ {−1, 1} for all i ∈ {1, . . . , N }, the objective of this problem has the form Logistic Regression Also available in each case is a testing dataset Logistic Regression . We ran implementations of TRish and SG and compare performance by comparing training loss (i.e., the objective function (4.1) evaluated with the training data) and testing accuracy (i.e., for a given approximate solution, what fraction of the testing set is classified correctly) for iterates throughout the optimization process. We ran each algorithm for one epoch (i.e., until N training pairs have been accessed) with a fixed stepsize α and, for TRish, a fixed parameter pair (γ 1 , γ 2 ). Logistic Regression For both algorithms and all datasets, the stochastic gradient estimates were computed using a minibatch size of 64. For choosing a fair set of parameters for the comparison for each dataset, we first ran SG with a stepsize of 0.1 and computed G as the average norm of stochastic gradient estimates throughout the run. Then, for TRish, we considered the stepsizes α ∈ {10 −1 , 10 −1/2 , 10 0 , 10 1/2 , 10 1 } and parameters Logistic Regression The value G gauges the magnitude of the stochastic gradient estimates, which depends on problem scaling. As seen in our results, these choices of (γ 1 , γ 2 ) ensure that step normalization-i.e., case 2 of TRish-occurs. In practice, one could compute G during an initial SG phase before starting TRish, but to cleanly distinguish between TRish and SG, we computed this value using an independent run of SG.) This resulted in 60 parameter settings with TRish employing stepsizes in the range from 1 2G × 10 −1 (i.e., the minimum γ 2 times the minimum α) to 32 G × 10 1 (i.e., the maximum γ 1 times the maximum α). Hence, for SG, we considered 60 values for α in the range [ . For each dataset, we ran the algorithms with these different parameters settings and selected for each the setting that led to the best average testing accuracy in the last ten iterations of the run. a1a. The first dataset that we considered was a1a in which the feature vectors have length n = 123, the number of points in the training set is N = 1605, and the number of points in the testing set is N = 30956. For tuning, the value G ≈ 0.1746 was determined, yielding a stepsize range of approximately [0.2863, 1832]. After tuning, the selected parameter setting for TRish was (α, γ 1 , γ 2 ) ≈ (0.1, 22.90, 2.863) and the selected parameter setting for SG was α ≈ 0.4471. a1a. The algorithms, TRish and SG, were each run 10 times from the same starting point (the origin). The training losses and testing accuracies, averaged over these 10 runs, are plotted in Figure 2 after 0.1 epoch through the end of the first epoch. (The values during the first 0.1 epoch are not plotted here, nor for the other datasets, so that it is easier to distinguish the differences at the end of the first epoch.) It is worthwhile to note that, during the runs for TRish, case 1 did not occur, case 2 occurred in approximately 99% of the iterations, and case 3 occurred in approximately 1% of the iterations; i.e., step normalization occurred in a large majority of the iterations. The figure shows that TRish yields better training losses throughout the optimization process. However, for this dataset, the performance in terms of testing accuracy is roughly the same for both algorithms. w1a. The second dataset that we considered was w1a in which the feature vectors have length n = 300, the number of points in the training set is N = 2477, and the number of points in the testing set is N = 47272. For tuning, the value G ≈ 0.0887 was determined, yielding a stepsize range of approximately [0.5638, 3608]. After tuning, the selected parameter setting for TRish was (α, γ 1 , γ 2 ) ≈ (0.1, 360.8, 5.638) and the selected parameter setting for SG was α ≈ 0.6541. w1a. The training losses and testing accuracies, averaged over 10 runs when both algorithms were initialized at the same starting point (the origin), are plotted in Figure 3 . During the runs for TRish, case 2 occurred in approximately 99% of the iterations while case 1 and case 3 combined occurred in fewer than 1% of the iterations. For this dataset, TRish outperformed SG both in terms of training losses and testing accuracies throughout the first epoch. rcv1. The third dataset that we considered was rcv1 in which the feature vectors have length n = 47236, the number of points in the training set is N = 20242, and the number of points in the testing set is N = 677399. For tuning, the value G ≈ 0.0497 was determined, yielding a stepsize range of approximately [1.007, 6444] . After tuning, the selected parameter setting for TRish was (α, γ 1 , γ 2 ) ≈ (0.3162, 644.4, 10.07) and the selected parameter setting for SG was α ≈ 10.84. rcv1. The training losses and testing accuracies, averaged over 10 runs when both algorithms were initialized at the same starting point (the origin), are plotted in Figure 4 . During the runs for TRish, case 1 occurred in approximately 27% of the iterations, case 2 occurred in approximately 73% of the iterations, and case 3 did not occur. For this dataset, TRish outperformed SG both in terms of training losses and testing accuracies throughout the first epoch. That said, the testing accuracies appear to near at the end of the first epoch, leading one to wonder about the performance of the methods if the parameters are re-tuned and the algorithms are run for more epochs. rcv1. To address this question, Figure 5 plots the training losses and testing accuracies-averaged over 10 runs-for TRish and SG during two epochs. (For this horizon, tuning led to the parameter setting for TRish as (α, γ 1 , γ 2 ) = (0.1, 376.2, 47.02) and the parameter setting for SG as α ≈ 5.192. For TRish, case 2 occurred in approximately 94% of the iterations, case 3 occurred in approximately 5% of the iterations, and case 1 occurred in fewer than 1% of the iterations.) These plots show a trade-off where, for a longer horizon, the better parameters for TRish do not necessarily offer better results initially, but do offer better results eventually. rcv1. In all of the experiments presented in this section, TRish generally outperforms SG. However, the gains are somewhat limited due to the fact that, by convexity of the problems, both algorithms are tending to neighborhoods around the same optimal solution. The results presented in the next subsection, in which we consider nonconvex optimization problems arising from neural network training, show more substantial benefits from using TRish as compared to SG. Neural Network Training As a second test case, we considered the problem to train convolutional neural networks (CNNs) for image classification. We considered two well-known datasets. The first, the mnist dataset [17] , is a collection of images of hand-written digits. The goal for training the network for this dataset is to classify which of the digits (0 through 9) is written in each image. It includes N = 60000 training samples and N = 10000 testing samples. The second, the cifar-10 dataset [15] , is a collection of color images in ten categories (e.g., airplanes, dogs, and ships). The goal for training the network for this dataset is to classify the image with the correct category. It includes N = 50000 training samples and N = 10000 testing samples. Neural Network Training Implemented using tensorflow, the neural networks that we considered for both datasets are composed of two convolutional layers (involving 32 and 64 filters, respectively, and each followed by an average pooling layer) followed by two fully connected layers. ReLU activation is used at each hidden layer and the objective is defined using the logistic (cross entropy) loss function. The networks vary slightly, e.g., due to the fact that a pixel for each mnist image corresponds to a single feature while a pixel for each cifar-10 image corresponds to three features (for each RGB value since they are color images). As seen in our experimental results, training the network led to a very good classifier for mnist, yielding over 95% testing accuracy. The performance is less impressive for cifar-10 (yielding around 60% accuracy); achieving higher accuracy would require a more sophisticated network and more computational resources than were available. That said, both datasets provide interesting settings for comparing the performance of TRish and SG. Neural Network Training As for the results in §4.2, we compare performance between TRish and SG by comparing training loss and testing accuracy. We tuned parameters using the same setup as in §4.2, except with slightly different parameter choices. In particular, the mini-batch size used when computing stochastic gradients was 128 and, when computing G, we ran SG with a stepsize of 0.01. For TRish, we considered stepsizes α ∈ {10 −3 , 10 −2 , 10 −1 , 10 0 } and parameters γ 1 ∈ { mnist. For mnist, we ran the algorithms for two epochs. For parameter tuning, the value G ≈ 2.8277 was determined, yielding a stepsize range of approximately [2.683 × 10 −5 , 3.435]. After tuning, the selected parameter setting for TRish was (α, γ 1 , γ 2 ) ≈ (1, 1.717, 0.0268) and the selected parameter setting for SG was α ≈ 0.0609.
{'paper_id': '53396174', 'title': 'A Stochastic Trust Region Algorithm Based on Careful Step Normalization', 's2_url': 'https://api.semanticscholar.org/CorpusID:53396174', 'source': 'S2ORC'}