Search

This paper presents a detailed theoretical analysis of the three stochastic approximation proximal gradient algorithms proposed in our companion paper [A. F. Vidal et al., SIAM J. Imaging Sci., 13 (2020), pp. 1945-1989] to set regularization parameters by marginal maximum likelihood estimation. We prove the convergence of a more general stochastic approximation scheme that includes the three algorithms of [A. F. Vidal et al., SIAM J. Imaging Sci., 13 (2020), pp. 1945-1989] as special cases. This includes asymptotic and nonasymptotic convergence results with natural and easily verifiable conditions, as well as explicit bounds on the convergence rates. Importantly, the theory is also general in that it can be applied to other intractable optimization problems. A main novelty of the work is that the stochastic gradient estimates of our scheme are constructed from inexact proximal Markov chain Monte Carlo samplers. This allows the use of samplers that scale efficiently to large problems and for which we have precise theoretical guarantees. [ABSTRACT FROM AUTHOR]

In [V. Guigues, SIAM J. Optim., 30 (2020), pp. 407-438], an inexact variant of stochastic dual dynamic programming (SDDP) called ISDDP was introduced which uses approximate (instead of exact with SDDP) primal dual solutions of the problems solved in the forward and backward passes of the method. That variant of SDDP was studied in [V. Guigues, SIAM J. Optim., 30 (2020), pp. 407-438] for linear and for differentiable nonlinear multistage stochastic programs (MSPs). In this paper, we extend ISDDP to nondifferentiable MSPs. We first provide formulas for inexact cuts for value functions of convex nondifferentiable optimization problems. We then combine these cuts with SDDP to describe ISDDP for nondifferentiable MSPs and analyze the convergence of the method. More precisely, for a problem with T stages, we show that for errors bounded from ab ove by\varepsilon, the limit superior and limit inferior of sequences of upper and lower bounds on the optimal value of the problem are at most at distance 3\varepsilonT to the optimal value and that for asymptotically vanishing errors ISDDP converges to an optimal policy. Finally, we present the results of encouraging numerical experiments on a multistage nondifferentiable stochastic convex program solved using exact SDDP and the proposed ISDDP. [ABSTRACT FROM AUTHOR]

This paper presents a finite-difference quasi-Newton method for the minimization of noisy functions. The method takes advantage of the scalability and power of BFGS updating, and employs an adaptive procedure for choosing the differencing interval h based on the noise estimation techniques of Hamming [Introduction to Applied Numerical Analysis, Courier Corporation, North Chelmsford, MA, 2012] and Mor\'e and Wild [SIAM J. Sci. Comput., 33 (2011), pp. 1292--1314]. This noise estimation procedure and the selection of h are inexpensive but not always accurate, and to prevent failures the algorithm incorporates a recovery mechanism that takes appropriate action in the case when the line-search procedure is unable to produce an acceptable point. A novel convergence analysis is presented that considers the effect of a noisy line-search procedure. Numerical experiments comparing the method to a function interpolating trust-region method are presented. [ABSTRACT FROM AUTHOR]

Many imaging problems require solving an inverse problem that is ill-conditioned or ill-posed. Imaging methods typically address this difficulty by regularizing the estimation problem to make it wellposed. This often requires setting the value of the so-called regularization parameters that control the amount of regularization enforced. These parameters are notoriously difficult to set a priori and can have a dramatic impact on the recovered estimates. In this work, we propose a general empirical Bayesian method for setting regularization parameters in imaging problems that are convex w.r.t. the unknown image. Our method calibrates regularization parameters directly from the observed data by maximum marginal likelihood estimation and can simultaneously estimate multiple regularization parameters. Furthermore, the proposed algorithm uses the same basic operators as proximal optimization algorithms, namely gradient and proximal operators, and it is therefore straightforward to apply to problems that are currently solved by using proximal optimization techniques. Our methodology is demonstrated with a range of experiments and comparisons with alternative approaches from the literature. The considered experiments include image denoising, nonblind image deconvolution, and hyperspectral unmixing, using synthesis and analysis priors involving the l1, total-variation, total-variation and l1, and total-generalized-variation pseudonorms. A detailed theoretical analysis of the proposed method is presented in our companion paper [V. De Bortoli et al., SIAM J. Imaging Sci., 13 (2020), pp. 1990-2028]. [ABSTRACT FROM AUTHOR]

The classical convergence analysis of quasi-Newton methods assumes that function and gradient evaluations are exact. In this paper, we consider the case when there are (bounded) errors in both computations and establish conditions under which a slight modification of the BFGS algorithm with an Armijo–Wolfe line search converges to a neighborhood of the solution that is determined by the size of the errors. One of our results is an extension of the analysis presented in [R. H. Byrd and J. Nocedal, SIAM J. Numer. Anal., 26 (1989), pp. 727–739], which establishes that, for strongly convex functions, a fraction of the BFGS iterates are good iterates. We present numerical results illustrating the performance of the new BFGS method in the presence of noise. [ABSTRACT FROM AUTHOR]

We consider solving nonlinear optimization problems with a stochastic objective and deterministic equality constraints. We assume for the objective that its evaluation, gradient, and Hessian are inaccessible, while one can compute their stochastic estimates by, for example, subsampling. We propose a stochastic algorithm based on sequential quadratic programming (SQP) that uses a differentiable exact augmented Lagrangian as the merit function. To motivate our algorithm design, we first revisit and simplify an old SQP method Lucidi (J. Optim. Theory Appl. 67(2): 227–245, 1990) developed for solving deterministic problems, which serves as the skeleton of our stochastic algorithm. Based on the simplified deterministic algorithm, we then propose a non-adaptive SQP for dealing with stochastic objective, where the gradient and Hessian are replaced by stochastic estimates but the stepsizes are deterministic and prespecified. Finally, we incorporate a recent stochastic line search procedure Paquette and Scheinberg (SIAM J. Optim. 30(1): 349–376 2020) into the non-adaptive stochastic SQP to adaptively select the random stepsizes, which leads to an adaptive stochastic SQP. The global "almost sure" convergence for both non-adaptive and adaptive SQP methods is established. Numerical experiments on nonlinear problems in CUTEst test set demonstrate the superiority of the adaptive algorithm. [ABSTRACT FROM AUTHOR]