Normal Approximation for Stochastic Gradient Descent via Non-Asymptotic Rates of Martingale CLT

  • Andreas Anastasiou
  • Krishnakumar Balasubramanian
  • Murat A. Erdogdu
    • Categories Nonlinear Optimization, Stochastic Programming Tags , ,

    We provide non-asymptotic convergence rates of the Polyak-Ruppert averaged stochastic gradient descent (SGD) to a normal random vector for a class of twice-differentiable test functions. A crucial intermediate step is proving a non-asymptotic martingale central limit theorem (CLT), i.e., establishing the rates of convergence of a multivariate martingale difference sequence to a normal random vector, … Read more

    Noisy Euclidean Distance Matrix Completion with a Single Missing Node

  • Lucas Pettersson
  • Stefan Sremac
  • Henry Wolkowicz
  • Fei Wang
    • Categories Convex Optimization, Semi-definite Programming, Telecommunications Tags , , , , , ,

    We present several solution techniques for the noisy single source localization problem, i.e.,~the Euclidean distance matrix completion problem with a single missing node to locate under noisy data. For the case that the sensor locations are fixed, we show that this problem is implicitly convex, and we provide a purification algorithm along with the SDP … Read more

    A Log-Barrier Newton-CG Method for Bound Constrained Optimization with Complexity Guarantees

  • Michael J. O'Neill
  • Stephen Wright
    • Categories Bound-constrained Optimization Tags , , ,

    We describe an algorithm based on a logarithmic barrier function, Newton’s method, and linear conjugate gradients, that obtains an approximate minimizer of a smooth function over the nonnegative orthant. We develop a bound on the complexity of the approach, stated in terms of the required accuracy and the cost of a single gradient evaluation of … Read more

    On monotonic estimates of the norm of the minimizers of regularized quadratic functions in Krylov spaces

  • Coralia Cartis
  • Nicholas I. M. Gould
  • Marius Lange
    • Categories Unconstrained Optimization Tags ,

    We show that the minimizers of regularized quadratic functions restricted to their natural Krylov spaces increase in Euclidean norm as the spaces expand. CitationTechnical Report RAL-TR-2019-005, STFC-Rutherford Appleton Laboratory, Oxfordshire, England, April 5th 2019ArticleDownload View PDF

    Derivative-free optimization methods

  • Jeffrey Larson
  • Matt Menickelly
  • Stefan M. Wild
    • Categories Nonlinear Optimization

    In many optimization problems arising from scientific, engineering and artificial intelligence applications, objective and constraint functions are available only as the output of a black-box or simulation oracle that does not provide derivative information. Such settings necessitate the use of methods for derivative-free, or zeroth-order, optimization. We provide a review and perspectives on developments in … Read more

    The Quadratic Cycle Cover Problem: special cases and efficient bounds

  • Frank de Meijer
  • Renata Sotirov
    • Categories Combinatorial Optimization Tags , , ,

    The quadratic cycle cover problem is the problem of finding a set of node-disjoint cycles visiting all the nodes such that the total sum of interaction costs between incident arcs is minimized. In this paper we study the linearization problem for the quadratic cycle cover problem and related lower bounds. In particular, we derive various … Read more

    Discrete Optimization Methods for Group Model Selection in Compressed Sensing

  • Bubacarr Bah
  • Jannis Kurtz
  • Oliver Schaudt
    • Categories Applications - Science and Engineering, Combinatorial Optimization, Integer Programming Tags , , ,

    In this article we study the problem of signal recovery for group models. More precisely for a given set of groups, each containing a small subset of indices, and for given linear sketches of the true signal vector which is known to be group-sparse in the sense that its support is contained in the union … Read more

    Logarithmic-Barrier Decomposition Interior-Point Methods for Stochastic Linear Optimization in a Hilbert Space

  • Baha Alzalg
    • Categories Infinite Dimensional Optimization, Linear Programming, Stochastic Programming

    Several logarithmic-barrier interior-point methods are now available for solving two-stage stochastic optimization problems with recourse in the finite-dimensional setting. However, despite the genuine need for studying such methods in general spaces, there are no infinite-dimensional analogs of these methods. Inspired by this evident gap in the literature, in this paper, we propose logarithmic-barrier decomposition-based interior-point … Read more

    Identifying Effective Scenarios for Sample Average Approximation

  • Lijian Chen
    • Categories Stochastic Programming Tags

    We introduce a method to improve the tractability of the well-known Sample Average Approximation (SAA) without compromising important theoretical properties, such as convergence in probability and the consistency of an independent and identically distributed (iid) sample. We consider each scenario as a polyhedron of the mix of first-stage and second-stage decision variables. According to John’s … Read more

    Tractable semi-algebraic approximation using Christoffel-Darboux kernel

  • Didier Henrion
  • Jean-Bernard Lasserre
  • Swann Marx
  • Edouard Pauwels
  • Tillmann Weisser
    • Categories Semi-definite Programming Tags , , , ,

    We provide a new method to approximate a (possibly discontinuous) function using Christoffel-Darboux kernels. Our knowledge about the unknown multivariate function is in terms of finitely many moments of the Young measure supported on the graph of the function. Such an input is available when approximating weak (or measure-valued) solution of optimal control problems, entropy … Read more