Search

We study statistical properties of the optimal value of the sample average approximation (SAA). The focus is on the tail function of the absolute error induced by the SAA, deriving upper estimates of its outcomes dependent on the sample size. The estimates allow to conclude immediately convergence rates for the optimal value of the SAA. As a crucial point, the investigations are based on new types of conditions from the theory of empirical processes which do not rely on pathwise analytical properties of the goal functions. In particular, continuity in the parameter is not imposed in advance as often in the literature on the SAA method. It is also shown that the new condition is satisfied if the paths of the goal functions are H\"older continuous so that the main results carry over in this case. Moreover, the main results are applied to goal functions whose paths are piecewise H\"older continuous as, e.g., in two-stage mixed-integer programs. The main results are shown for classical risk-neutral stochastic programs, but we also demonstrate how to apply them to the sample average approximation of risk-averse stochastic programs. In this respect, we consider stochastic programs expressed in terms of mean upper semideviations and divergence risk measures. [ABSTRACT FROM AUTHOR]

We introduce a general framework for nonlinear stochastic gradient descent (SGD) for the scenarios when gradient noise exhibits heavy tails. The proposed framework subsumes several popular nonlinearity choices, like clipped, normalized, signed, or quantized gradient, but we also consider novel nonlinearity choices. We establish for the considered class of methods strong convergence guarantees assuming a strongly convex cost function with Lipschitz continuous gradients under very general assumptions on the gradient noise. Most notably, we show that, for a nonlinearity with bounded outputs and for the gradient noise that may not have finite moments of order greater than one, the nonlinear SGD's mean squared error (MSE), or equivalently, the expected cost function's optimality gap, converges to zero at rate O(1/tζ), ζ∈(0,1). In contrast, for the same noise setting, the linear SGD generates a sequence with unbounded variances. Furthermore, for general nonlinearities that can be decoupled componentwise and a class of joint nonlinearities, we show that the nonlinear SGD asymptotically (locally) achieves an O(1/t) rate in the weak convergence sense and explicitly quantify the corresponding asymptotic variance. Experiments show that, while our framework is more general than existing studies of SGD under heavy-tail noise, several easy-to-implement nonlinearities from our framework are competitive with state-of-the-art alternatives on real datasets with heavy-tail noises. [ABSTRACT FROM AUTHOR]

This paper analyzes a two-timescale stochastic algorithm framework for bilevel optimization. Bilevel optimization is a class of problems which exhibits a two-level structure, and its goal is to minimize an outer objective function with variables which are constrained to be the optimal solution to an (inner) optimization problem. We consider the case when the inner problem is unconstrained and strongly convex, while the outer problem is constrained and has a smooth objective function. We propose a two-timescale stochastic approximation (TTSA) algorithm for tackling such a bilevel problem. In the algorithm, a stochastic gradient update with a larger step size is used for the inner problem, while a projected stochastic gradient update with a smaller step size is used for the outer problem. We analyze the convergence rates for the TTSA algorithm under various settings: when the outer problem is strongly convex (resp. weakly convex), the TTSA algorithm finds an O (Kmax-2/3)-optimal (resp. O (Kmax-2/5)-stationary) solution, where Kmax is the total iteration number. As an application, we show that a two-timescale natural actor-critic proximal policy optimization algorithm can be viewed as a special case of our TTSA framework. Importantly, the natural actor-critic algorithm is shown to converge at a rate of O (Kmax-1/4) in terms of the gap in expected discounted reward compared to a global optimal policy. [ABSTRACT FROM AUTHOR]

The stochastic auxiliary problem principle (APP) algorithm is a general stochastic approximation (SA) scheme that turns the resolution of an original convex optimization problem into the iterative resolution of a sequence of auxiliary problems. This framework has been introduced to design decomposition-coordination schemes but also encompasses many well-known SA algorithms such as stochastic gradient descent or stochastic mirror descent. We study the stochastic APP in the case where the iterates lie in a Banach space and we consider an additive error on the computation of the subgradient of the objective. In order to derive convergence results or efficiency estimates for an SA scheme, the iterates must be random variables. This is why we prove the measurability of the iterates of the stochastic APP algorithm. Then, we extend convergence results from the Hilbert space case to the reflexive separable Banach space case. Finally, we derive efficiency estimates for the function values taken at the averaged sequence of iterates or at the last iterate, the latter being obtained by adapting the concept of modified Fejér monotonicity to our framework. [ABSTRACT FROM AUTHOR]

The two-stage stochastic linear complementarity problem (TSLCP), which can be regarded as a special and important reformulation of two-stage stochastic linear programming, has arisen in various fields, such as stochastic programming, game theory, traffic equilibrium, and theoretical economics. Considerable effort has been devoted to designing numerical methods for solving TSLCPs. A popular approach is to integrate the progressive hedging algorithm (PHA) as a sub-algorithm into a discretization framework. In this paper, aiming to solve large-scale TSLCPs, we propose two kinds of stochastic methods: the stochastic approximation method based on projection (SAP) and the dynamic sampling SAP (DS-SAP), both of which offering more direct and improved control of the computational costs of the involved subproblems, especially compared with the PHA. In particular, the linear complementarity subproblems are solved inexactly during each iteration, and the convergence analysis of both SAP and DS-SAP with an inexactness criterion is presented. Moreover, numerical implementations and practical applications demonstrate the efficiency of our proposed methods. [ABSTRACT FROM AUTHOR]

In this work, we present a novel approach for solving stochastic shape optimization problems. Our method is the extension of the classical stochastic gradient method to infinite-dimensional shape manifolds. We prove convergence of the method on Riemannian manifolds and then make the connection to shape spaces. The method is demonstrated on a model shape optimization problem from interface identification. Uncertainty arises in the form of a random partial differential equation, where underlying probability distributions of the random coefficients and inputs are assumed to be known. We verify some conditions for convergence for the model problem and demonstrate the method numerically. [ABSTRACT FROM AUTHOR]

ADAM is a popular variant of stochastic gradient descent for finding a local minimizer of a function. In the constant stepsize regime, assuming that the objective function is differentiable and nonconvex, we establish the convergence in the long run of the iterates to a stationary point under a stability condition. The key ingredient is the introduction of a continuous-time version of Adam, under the form of a nonautonomous ordinary differential equation. This continuous-time system is a relevant approximation of the ADAM iterates, in the sense that the interpolated ADAM process converges weakly toward the solution to the ODE. The existence and the uniqueness of the solution are established. We further show the convergence of the solution toward the critical points of the objective function and quantify its convergence rate under a Lojasiewicz assumption. Then, we introduce a novel decreasing stepsize version of ADAM. Under mild assumptions, it is shown that the iterates are almost surely bounded and converge almost surely to critical points of the objective function. Finally, we analyze the fluctuations of the algorithm by means of a conditional central limit theorem. [ABSTRACT FROM AUTHOR]

In this paper, we study a class of stochastic optimization problems, referred to as the conditional stochastic optimization (CSO), in the form of minx∈X Eξ fξ (Eη ξ [gη (x, ξ)]), which finds a wide spectrum of applications including portfolio selection, reinforcement learning, robust learning, and causal inference. Assuming availability of samples from the distribution P(ξ) and samples from the conditional distribution P(η ξ), we establish the sample complexity of the sample average approximation (SAA) for CSO, under a variety of structural assumptions, such as Lipschitz continuity, smoothness, and error bound conditions. We show that the total sample complexity improves from O (d/∈4) to O (d/∈³) when assuming smoothness of the outer function, and further to O (1/&#8712²) when the empirical function satisfies the quadratic growth condition. We also establish the sample complexity of a modified SAA when ξ and η are independent. Several numerical experiments further support our theoretical findings. [ABSTRACT FROM AUTHOR]

In this paper, we examine the convergence of mirror descent in a class of stochastic optimization problems that are not necessarily convex (or even quasi-convex) and which we call variationally coherent. Since the standard technique of ``ergodic averaging"" offers no tangible benefits beyond convex programming, we focus directly on the algorithm's last generated sample (its ``last iterate""), and we show that it converges with probabiility 1 if the underlying problem is coherent. We further consider a localized version of variational coherence which ensures local convergence of Stochastic mirror descent (SMD) with high probability. These results contribute to the landscape of nonconvex stochastic optimization by showing that (quasi-)convexity is not essential for convergence to a global minimum: rather, variational coherence, a much weaker requirement, suffices. Finally, building on the above, we reveal an interesting insight regarding the convergence speed of SMD: in problems with sharp minima (such as generic linear programs or concave minimization problems), SMD reaches a minimum point in a finite number of steps (a.s.), even in the presence of persistent gradient noise. This result is to be contrasted with existing black-box convergence rate estimates that are only asymptotic. [ABSTRACT FROM AUTHOR]

We study constrained nested stochastic optimization problems in which the objective function is a composition of two smooth functions whose exact values and derivatives are not available. We propose a single timescale stochastic approximation algorithm, which we call the nested averaged stochastic approximation (NASA), to find an approximate stationary point of the problem. The algorithm has two auxiliary averaged sequences (filters) which estimate the gradient of the composite objective function and the inner function value. By using a special Lyapunov function, we show that the NASA achieves the sample complexity of O (1/ε² ) for finding an ε -approximate stationary point, thus outperforming all extant methods for nested stochastic approximation. Our method and its analysis are the same for both unconstrained and constrained problems, without any need of batch samples for constrained nonconvex stochastic optimization. We also present a simplified parameterfree variant of the NASA method for solving constrained single-level stochastic optimization problems, and we prove the same complexity result for both unconstrained and constrained problems. [ABSTRACT FROM AUTHOR]

We study the trade-offs between convergence rate and robustness to gradient errors in designing a first-order algorithm. We focus on gradient descent and accelerated gradient (AG) methods for minimizing strongly convex functions when the gradient has random errors in the form of additive white noise. With gradient errors, the function values of the iterates need not converge to the optimal value; hence, we define the robustness of an algorithm to noise as the asymptotic expected suboptimality of the iterate sequence to input noise power. For this robustness measure, we provide exact expressions for the quadratic case using tools from robust control theory and tight upper bounds for the smooth strongly convex case using Lyapunov functions certified through matrix inequalities. We use these characterizations within an optimization problem which selects parameters of each algorithm to achieve a particular trade-off between rate and robustness. Our results show that AG can achieve acceleration while being more robust to random gradient errors. This behavior is quite different than previously reported in the deterministic gradient noise setting. We also establish some connections between the robustness of an algorithm and how quickly it can converge back to the optimal solution if it is perturbed from the optimal point with deterministic noise. Our framework also leads to practical algorithms that can perform better than other state-of-the-art methods in the presence of random gradient noise. [ABSTRACT FROM AUTHOR]

In this work, we present a globalized stochastic semismooth Newton method for solving stochastic optimization problems involving smooth nonconvex and nonsmooth convex terms in the objective function. We assume that only noisy gradient and Hessian information of the smooth part of the objective function is available via calling stochastic first and second order oracles. The proposed method can be seen as a hybrid approach combining stochastic semismooth Newton steps and stochastic proximal gradient steps. Two inexact growth conditions are incorporated to monitor the convergence and the acceptance of the semismooth Newton steps and it is shown that the algorithm converges globally to stationary points in expectation and almost surely. We present numerical results and comparisons on l1-regularized logistic regression and nonconvex binary classification that demonstrate the efficiency of the algorithm. [ABSTRACT FROM AUTHOR]

In this paper we develop a family of randomized projection methods (RPM) for solving the convex feasibility problem. Our approach is based on several new ideas and tools, including stochastic approximation of convex sets, stochastic reformulations, and conditioning of the convex feasibility problem. In particular, we propose four equivalent stochastic reformulations: stochastic smooth and nonsmooth optimization problems, the stochastic fixed point problem, and the stochastic feasibility problem. The last reformulation asks for a point which belongs to a certain random set with probability one. In this case, RPM can be interpreted as follows: we sample a batch of random sets in an independently and identically distributed fashion, perform projections of the current iterate on all sampled sets, and then combine these projections by averaging with a carefully designed extrapolation step. We prove that under stochastic linear regularity, RPM converges linearly, with a rate that has a natural interpretation as a condition number of the stochastic optimization reformulation and that depends explicitly on the number of sets sampled. In doing so, we extend the concept of condition number to general convex feasibility problems. This condition number depends on the linear regularity constant and an additional key constant which can be interpreted as a Lipschitz constant of the gradient of the stochastic optimization reformulation. Besides providing a general framework for the design and analysis of randomized projection schemes, our results resolve an open problem in the literature related to the theoretical understanding of observed practical efficiency of extrapolated parallel projection methods. In addition, we prove that our method converges sublinearly in the case when the stochastic linear regularity condition is not satisfied. Preliminary numerical results also show a better performance of our extrapolated step-size scheme over its constant step-size counterpart. [ABSTRACT FROM AUTHOR]

The incremental gradient (IG) method is a prominent algorithm for minimizing a finite sum of smooth convex functions and is used in many contexts including large-scale data processing applications and distributed optimization over networks. It is a first-order method that processes the functions one at a time based on their gradient information. The incremental Newton method, on the other hand, is a second-order variant which additionally exploits the curvature information of the underlying functions and can therefore be faster. In this paper, we focus on the case when the objective function is strongly convex and present new convergence rate estimates for the incremental gradient and incremental Newton methods under constant and diminishing step sizes. For a decaying step-size rule ακ = R/κs with s Є (0, 1] and R > 0, we show that the distance of the IG iterates to the optimal solution converges at a rate O(1/κs) (which translates into a O (1/κ2s) rate in the suboptimality of the objective value). For s > 1/2, this improves the previous O(1/√κ) results in distances obtained for the case when functions are nonsmooth under the additional assumption that the functions are smooth. We show that to achieve the fastest O(1/κ) rate with a step size ακ = R/κs, IG needs a step-size parameter R to be a function of the strong convexity constant whereas the incremental Newton method does not. The results are based on viewing the IG method as a gradient descent method with gradient errors, developing upper bounds for the gradient error to derive inequalities that relate distances of the consecutive iterates to the optimal solution and finally applying Chung's lemmas from the stochastic approximation literature to these inequalities to determine their asymptotic behavior. In addition, we construct examples to show tightness of our rate results in terms of their dependency in k. [ABSTRACT FROM AUTHOR]

Convergence of a projected stochastic gradient algorithm is demonstrated for convex objective functionals with convex constraint sets in Hilbert spaces. In the convex case, the sequence of iterates un converges weakly to a point in the set of minimizers with probability one. In the strongly convex case, the sequence converges strongly to the unique optimum with probability one. An application to a class of PDE constrained problems with a convex objective, convex constraint, and random elliptic PDE constraints is shown. Theoretical results are demonstrated numerically. Key words. [ABSTRACT FROM AUTHOR]

We consider a family of algorithms that successively sample and minimize simple stochastic models of the objective function. We show that under reasonable conditions on approximation quality and regularity of the models, any such algorithm drives a natural stationarity measure to zero at the rate O(k-1/4) As a consequence, we obtain the first complexity guarantees for the stochastic proximal point, proximal subgradient, and regularized Gauss{Newton methods for minimizing compositions of convex functions with smooth maps. The guiding principle, underlying the complexity guarantees, is that all algorithms under consideration can be interpreted as approximate descent methods on an implicit smoothing of the problem, given by the Moreau envelope. Specializing to classical circumstances, we obtain the long-sought convergence rate of the stochastic projected gradient method, without batching, for minimizing a smooth function on a closed convex set. [ABSTRACT FROM AUTHOR]

Stochastic gradient methods are scalable for solving large-scale optimization problems that involve empirical expectations of loss functions. Existing results mainly apply to optimization problems where the objectives are one- or two-level expectations. In this paper, we consider the multilevel composition optimization problem that involves compositions of multilevel component functions and nested expectations over a random path. This finds applications in risk-averse optimization and sequential planning. We propose a class of multilevel stochastic gradient methods that are motivated by the method of multitimescale stochastic approximation. First, we propose a basic T-level stochastic compositional gradient algorithm. Then we develop accelerated multilevel stochastic gradient methods by using an extrapolation-interpolation scheme to take advantage of the smoothness of individual component functions. When all component functions are smooth, we show that the convergence rate improves to O(n-4/7+T)) for general objectives and O(n-4/7+T)) for strongly convex objectives. We also provide almost sure convergence and rate of convergence results for nonconvex problems. The proposed methods and theoretical results are validated using numerical experiments. [ABSTRACT FROM AUTHOR]

A solution of two-stage stochastic generalized equations is a pair: a first stage solution which is independent of realization of the random data and a second stage solution which is a function of random variables. This paper studies convergence of the sample average approximation of two-stage stochastic nonlinear generalized equations. In particular, an exponential rate of the convergence is shown by using the perturbed partial linearization of functions. Moreover, sufficient conditions for the existence, uniqueness, continuity, and regularity of solutions of two-stage stochastic generalized equations are presented under an assumption of monotonicity of the involved functions. These theoretical results are given without assuming relatively complete recourse and are illustrated by two-stage stochastic noncooperative games of two players. [ABSTRACT FROM AUTHOR]

In this paper, we propose dynamic sampled stochastic approximated (DS-SA) extragradient methods for stochastic variational inequalities (SVIs) that are robust with respect to an unknown Lipschitz constant L. We propose, to the best of our knowledge, the first provably convergent robust SA method with variance reduction, either for SVIs or stochastic optimization, assuming just an unbiased stochastic oracle within a large sample regime. This widens the applicability and improves, up to constants, the desired efficient acceleration of previous variance reduction methods, all of which still assume knowledge of L (and, hence, are not robust against its estimate). Precisely, compared to the iteration and oracle complexities of O(ϵ-2) of previous robust methods with a small stepsize policy, our robust method uses a DS-SA line search scheme obtaining the faster iteration complexity of O(ϵ-1) with oracle complexity of (lnL)O(dϵ-2) (up to log factors on ϵ-1) for a d-dimensional space. This matches, up to constants, the sample complexity of the sample average approximation estimator which does not assume additional problem information (such as L). Differently from previous robust methods for ill-conditioned problems, we allow an unbounded feasible set and an oracle with multiplicative noise (MN) whose variance is not necessarily uniformly bounded. These properties are appreciated in our complexity estimates which depend only on L and local variances or fourth moments at solutions. The robustness and variance reduction properties of our DS-SA line search scheme come at the expense of nonmartingale-like dependencies (NMDs) due to the needed inner statistical estimation of a lower bound for L. In order to handle an NMD and an MN, our proofs rely on a novel iterative localization argument based on empirical process theory. [ABSTRACT FROM AUTHOR]

In general, multistage stochastic optimization problems are formulated on the basis of continuous distributions describing the uncertainty. Such "infinite" problems are practically impossible to solve as they are formulated, and finite tree approximations of the underlying stochastic processes are used as proxies. In this paper, we demonstrate how one can find guaranteed bounds, i.e., finite tree models, for which the optimal values give upper and lower bounds for the optimal value of the original infinite problem. Typically, there is a gap between the two bounds. However, this gap can be made arbitrarily small by making the approximating trees bushier. We consider approximations in the first-order stochastic sense, in the convex-order sense, and based on subgradient approximations. Their use is shown in a multistage risk-averse production problem. [ABSTRACT FROM AUTHOR]

We propose a distributed version of a stochastic approximation scheme constrained to remain in the intersection of a finite family of convex sets. The projection to the intersection of these sets is also computed in a distributed manner and a "gossip" mechanism is employed to blend the projection iterations with the stochastic approximation using multiple time scales. [ABSTRACT FROM AUTHOR]

In this paper we study stochastic quasi-Newton methods for nonconvex stochastic optimization, where we assume that noisy information about the gradients of the objective function is available via a stochastic first-order oracle (SFO). We propose a general framework for such methods, for which we prove almost sure convergence to stationary points and analyze its worst-case iteration complexity. When a randomly chosen iterate is returned as the output of such an algorithm, we prove that in the worst case, the SFO-calls complexity is O(ε-2) to ensure that the expectation of the squared norm of the gradient is smaller than the given accuracy tolerance ε. We also propose a specific algorithm, namely, a stochastic damped limited-memory BFGS (SdLBFGS) method, that falls under the proposed framework. Moreover, we incorporate the stochastic variance reduced gradient variance reduction technique into the proposed SdLBFGS method and analyze its SFO-calls complexity. Numerical results on a nonconvex binary classification problem using a support vector machine and a multiclass classification problem using neural networks are reported. [ABSTRACT FROM AUTHOR]

We propose an extragradient method with stepsizes bounded away from zero for stochastic variational inequalities requiring only pseudo-monotonicity. We provide convergence and complexity analysis, allowing for an unbounded feasible set, unbounded operator, non-uniform variance of the oracle and, also, we do not require any regularization. Alongside the stochastic approximation procedure, we iteratively reduce the variance of the stochastic error. Our method attains the optimal oracle complexity O(1/∈²) (up to a logarithmic term) and a faster rate O(1/K) in terms of the mean (quadratic) natural residual and the D-gap function, where K is the number of iterations required for a given tolerance ∈>0. Such convergence rate represents an acceleration with respect to the stochastic error. The generated sequence also enjoys a new feature: the sequence is bounded in Lp if the stochastic error has finite p-moment. Explicit estimates for the convergence rate, the oracle complexity and the p-moments are given depending on problem parameters and distance of the initial iterate to the solution set. Moreover, sharper constants are possible if the variance is uniform over the solution set or the feasible set. Our results provide new classes of stochastic variational inequalities for which a convergence rate of O(1/K) holds in terms of the mean-squared distance to the solution set. Our analysis includes the distributed solution of pseudo-monotone Cartesian variational inequalities under partial coordination of parameters between users of a network. [ABSTRACT FROM AUTHOR]

We consider the minimization of a convex expectation-valued objective E[ƒ(x;ø*, ξ)] over a closed and convex set X in a regime where ø* is unavailable and ξ is a suitably deffened random variable. Instead, ø* may be obtained through the solution of a learning problem that requires minimizing a metric E[g(ø;η)] in ø over a closed and convex set ø. To resolve the absence of convergent efficient schemes, we present a coupled stochastic approximation scheme which simultaneously solves both the computational and the learning problems. The obtained schemes are shown to be equipped with almost sure convergence properties in regimes when the function ƒ is either strongly convex or merely convex. Importantly, the scheme displays the optimal rate for both strongly convex and convex problems where the rate statement in the latter regime necessitates the use of averaging. In the second part of the paper, we extend these statements to a class of stochastic variational inequality problems, an object that unifles stochastic convex optimization problems and a range of stochastic equilibrium problems. Analogous almost-sure convergence statements are provided in strongly monotone and merely monotone regimes, the latter facilitated by using an iterative Tikhonov regularization. Again, we note that the schemes admit the optimal rate in strongly monotone and monotone settings, where the latter result requires the additional assumption of weak sharpness. Preliminary numerics demonstrate the performance of the prescribed schemes. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to establish the almost sure weak ergodic convergence of a sequence of iterates (xn) given by xn+1 = (I + λnA(ξn+1,.))-1(xn); where (A(s,.) : s ∈ E) is a collection of maximal monotone operators on a separable Hilbert space, (λn) is an independent identically distributed sequence of random variables on E, and (λn) is a positive sequence in ℓ²nℓ¹. The weighted averaged sequence of iterates is shown to converge weakly to a zero (assumed to exist) of the Aumann expectation E(A(λ1,.)) under the assumption that the latter is maximal. We consider applications to stochastic optimization problems of the form min E(ƒ(λ1, x)) w.r.t. x ∈ ∩mi=1 Xi, where ƒ is a normal convex integrand and (Xi) is a collection of closed convex sets. In this case, the iterations are closely related to a stochastic proximal algorithm recently proposed by Wang and Bertsekas [Incremental Constraint Projection-Proximal Methods for Nonsmooth Convex Optimization, Tech. report, MIT, Cambridge, MA, 2013]. [ABSTRACT FROM AUTHOR]

The question of how to incorporate curvature information into stochastic approximation methods is challenging. The direct application of classical quasi-Newton updating techniques for deterministic optimization leads to noisy curvature estimates that have harmful effects on the robustness of the iteration. In this paper, we propose a stochastic quasi-Newton method that is efficient, robust, and scalable. It employs the classical BFGS update formula in its limited memory form, and is based on the observation that it is beneficial to collect curvature information pointwise, and at spaced intervals. One way to do this is through (subsampled) Hessian-vector products. This technique differs from the classical approach that would compute differences of gradients at every iteration, and where controlling the quality of the curvature estimates can be difficult. We present numerical results on problems arising in machine learning that suggest that the proposed method shows much promise. [ABSTRACT FROM AUTHOR]

We consider convex optimization problems with structures that are suitable for sequential treatment or online sampling. In particular, we focus on problems where the objective function is an expected value, and the constraint set is the intersection of a large number of simpler sets. We propose an algorithmic framework for stochastic first-order methods using random projection/proximal updates and random constraint updates, which contain as special cases several known algorithms as well as many new algorithms. To analyze the convergence of these algorithms in a unified manner, we prove a general coupled convergence theorem. It states that the convergence is obtained from an interplay between two coupled processes: progress toward feasibility and progress toward optimality. Under suitable stepsize assumptions, we show that the optimality error decreases at a rate of O(1/√k) and the feasibility error decreases at a rate of O(log k/k). We also consider a number of typical sampling processes for generating stochastic first-order information and random constraints, which are common in data-intensive applications, online learning, and simulation optimization. By using the coupled convergence theorem as a modular architecture, we are able to analyze the convergence of stochastic algorithms that use arbitrary combinations of these sampling processes. [ABSTRACT FROM AUTHOR]

We present a novel accelerated primal-dual (APD) method for solving a class of deterministic and stochastic saddle point problems (SPPs). The basic idea of this algorithm is to incorporate a multistep acceleration scheme into the primal-dual method without smoothing the objective function. For deterministic SPP, the APD method achieves the same optimal rate of convergence as Nesterov's smoothing technique. Our stochastic APD method exhibits an optimal rate of convergence for stochastic SPP not only in terms of its dependence on the number of the iteration, but also on a variety of problem parameters. To the best of our knowledge, this is the first time that such an optimal algorithm has been developed for stochastic SPP in the literature. Furthermore, for both deterministic and stochastic SPP, the developed APD algorithms can deal with the situation when the feasible region is unbounded, as long as a saddle point exists. In the unbounded case, we incorporate the modified termination criterion introduced by Monteiro and Svaiter in solving an SPP posed as a monotone inclusion, and demonstrate that the rate of convergence of the APD method depends on the distance from the initial point to the set of optimal solutions. Some preliminary numerical results of the APD method for solving both deterministic and stochastic SPPs are also included. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a new stochastic approximation type algorithm, namely, the randomized stochastic gradient (RSG) method, for solving an important class of nonlinear (possibly nonconvex) stochastic programming problems. We establish the complexity of this method for computing an approximate stationary point of a nonlinear programming problem. We also show that this method possesses a nearly optimal rate of convergence if the problem is convex. We discuss a variant of the algorithm which consists of applying a postoptimization phase to evaluate a short list of solutions generated by several independent runs of the RSG method, and we show that such modification allows us to improve significantly the large-deviation properties of the algorithm. These methods are then specialized for solving a class of simulation-based optimization problems in which only stochastic zeroth-order information is available. [ABSTRACT FROM AUTHOR]

In this paper we study new stochastic approximation (SA) type algorithms, namely, the accelerated SA (AC-SA), for solving strongly convex stochastic composite optimization (SCO) problems. Specifically, by introducing a domain shrinking procedure, we significantly improve the large-deviation results associated with the convergence rate of a nearly optimal AC-SA algorithm presented by Ghadimi and Lan in [SIAM J. Optim., 22 (2012), pp 1469-1492], Moreover, we introduce a multistage AC-SA algorithm, which possesses an optimal rate of convergence for solving strongly convex SCO problems in terms of the dependence on not only the target accuracy, but also a number of problem parameters and the selection of initial points. To the best of our knowledge, this is the first time that such an optimal method has been presented in the literature. From our computational results, these AC-SA algorithms can substantially outperform the classical SA and some other SA type algorithms for solving certain classes of strongly convex SCO problems. [ABSTRACT FROM AUTHOR]

In this paper, we derive a randomized version of the mirror-prox method for solving some structured matrix saddle-point problems, such as the maximal eigenvalue minimization problem. Deterministic first-order schemes, such as Nesterov's smoothing techniques or standard mirror-prox methods, require the exact computation of a matrix exponential at every iteration, limiting the size of the problems they can solve. Our method allows us to use stochastic approximations of matrix exponentials. We prove that our randomized scheme decreases significantly the complexity of its deterministic counterpart for large-scale matrix saddle-point problems. Numerical experiments illustrate and confirm our theoretical results. [ABSTRACT FROM AUTHOR]

In this paper we present a generic algorithmic framework, namely, the accelerated stochastic approximation (AC-SA) algorithm, for solving strongly convex stochastic composite optimization (SCO) problems. While the classical stochastic approximation algorithms are asymptotically optimal for solving differentiable and strongly convex problems, the AC-SA algorithm, when employed with proper stepsize policies, can achieve optimal or nearly optimal rates of convergence for solving different classes of SCO problems during a given number of iterations. Moreover, we investigate these AC-SA algorithms in more detail, such as by establishing the large-deviation results associated with the convergence rates and introducing an efficient validation procedure to check the accuracy of the generated solutions. [ABSTRACT FROM AUTHOR]

Often, parameter estimation problems of parameter-dependent PDEs involve multiple right-hand sides. The computational cost and memory requirements of such problems increase linearly with the number of right-hand sides. For many applications this is the main bottleneck of the computation. In this paper we show that problems with multiple right-hand sides can be reformulated as stochastic programming problems by combining the right-hand sides into a few "simultaneous" sources. This effectively reduces the cost of the forward problem and results in problems that are much cheaper to solve. We discuss two solution methodologies: namely sample average approximation and stochastic approximation. To illustrate the effectiveness of our approach we present two model problems, direct current resistivity and seismic tomography. [ABSTRACT FROM AUTHOR]

This paper studies the effect of stochastic errors on two constrained incremental subgradient algorithms. The incremental subgradient algorithms are viewed as decentralized network optimization algorithms as applied to minimize a sum of functions, when each component function is known only to a particular agent of a distributed network. First, the standard cyclic incremental subgradient algorithm is studied. In this, the agents form a ring structure and pass the iterate in a cycle. When there are stochastic errors in the subgradient evaluations, sufficient conditions on the moments of the stochastic errors are obtained that guarantee almost sure convergence when a diminishing step-size is used. In addition, almost sure bounds on the algorithm's performance with a constant step-size are also obtained. Next, the Markov randomized incremental subgradient method is studied. This is a noncyclic version of the incremental algorithm where the sequence of computing agents is modeled as a time nonhomogeneous Markov chain. Such a model is appropriate for mobile networks, as the network topology changes across time in these networks. Convergence results and error bounds for the Markov randomized method in the presence of stochastic errors for diminishing and constant step-sizes are obtained. [ABSTRACT FROM AUTHOR]

In this paper we consider optimization problems where the objective function is given in a form of the expectation. A basic difficulty of solving such stochastic optimization problems is that the involved multidimensional integrals (expectations) cannot be computed with high accuracy. The aim of this paper is to compare two computational approaches based on Monte Carlo sampling techniques, namely, the stochastic approximation (SA) and the sample average approximation (SAA) methods. Both approaches, the SA and SAA methods, have a long history. Current opinion is that the SAA method can efficiently use a specific (say, linear) structure of the considered problem, while the SA approach is a crude subgradient method, which often performs poorly in practice. We intend to demonstrate that a properly modified SA approach can be competitive and even significantly outperform the SAA method for a certain class of convex stochastic problems. We extend the analysis to the case of convex-concave stochastic saddle point problems and present (in our opinion highly encouraging) results of numerical experiments. [ABSTRACT FROM AUTHOR]

Stochastic dominance constraints allow a decision maker to manage risk in an optimization setting by requiring his or her decision to yield a random outcome which stochastically dominates a reference random outcome. We present new integer and linear programming formulations for optimization under first- and second-order stochastic dominance constraints, respectively. These formulations are more compact than existing formulations, and relaxing integrality in the first-order formulation yields a second-order formulation, demonstrating the tightness of this formulation. We also present a specialized branching strategy and heuristics which can be used with the new first-order formulation. Computational tests illustrate the potential benefits of the new formulations. [ABSTRACT FROM AUTHOR]

This work is devoted to a class of stochastic approximation problems with regime switching modulated by a discrete-time Markov chain. Our motivation stems from using stochastic recursive algorithms for tracking Markovian parameters such as those in spreading code optimization in CDMA (code division multiple access) wireless communication. The algorithm uses constant step size to update the increments of a sequence of occupation measures. It is proved that least squares estimates of the tracking errors can be developed. Assume that the adaptation rate is of the same order of magnitude as that of the time-varying parameter, which is more di .cult to deal with than that of slower parameter variations. Due to the time-varying characteristics and Markovian jumps, the usual stochastic approximation (SA) techniques cannot be carried over in the analysis. By a combined use of the SA method and two-time-scale Markov chains, asymptotic properties of the algorithm are obtained, which are distinct from the usual SA results. In this paper, it is shown for the first time that, under simple conditions,a continuous-time interpolation of the iterates converges weakly not to an ODE, as is widely known in the literature, but to a system of ODEs with regime switching, and that a suitably scaled sequence of the tracking errors converges not to a difusion but to a system of switching difusion. As an application of these results, the performance of an adaptive discrete stochastic optimization algorithm is analyzed. [ABSTRACT FROM AUTHOR]