oracle complexity

A momentum-based linearized augmented Lagrangian method for nonconvex constrained stochastic optimization

  • Qiankun Shi
  • Xiao Wang
  • Hao Wang
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Stochastic Programming Tags , , , , ,

    Nonconvex constrained stochastic optimization has emerged in many important application areas. Subject to general functional constraints it minimizes the sum of an expectation function and a nonsmooth regularizer. Main challenges arise due to the stochasticity in the random integrand and the possibly nonconvex functional constraints. To address these issues we propose a momentum-based linearized augmented … Read more

    Linear Programming using Limited-Precision Oracles

  • Ambros Gleixner
  • Daniel E. Steffy
    • Categories Linear Programming, Optimization Software and Modeling Systems Tags , , , , , , ,

    Since the elimination algorithm of Fourier and Motzkin, many different methods have been developed for solving linear programs. When analyzing the time complexity of LP algorithms, it is typically either assumed that calculations are performed exactly and bounds are derived on the number of elementary arithmetic operations necessary, or the cost of all arithmetic operations … Read more

    Oracle Complexity of Second-Order Methods for Smooth Convex Optimization

  • Ohad Shamir
  • Ron Shiff
    • Categories Convex Optimization, Nonlinear Optimization Tags , ,

    Second-order methods, which utilize gradients as well as Hessians to optimize a given function, are of major importance in mathematical optimization. In this work, we study the oracle complexity of such methods, or equivalently, the number of iterations required to optimize a function to a given accuracy. Focusing on smooth and convex functions, we derive … Read more

    On Lower Complexity Bounds for Large-Scale Smooth Convex Optimization

  • Cristobal Guzman
  • Arkadi Nemirovski
    • Categories Convex and Nonsmooth Optimization, Convex Optimization Tags , , ,

    In this note we present tight lower bounds on the information-based complexity of large-scale smooth convex minimization problems. We demonstrate, in particular, that the k-step Conditional Gradient (a.k.a. Frank-Wolfe) algorithm as applied to minimizing smooth convex functions over the n-dimensional box with n ≥ k is optimal, up to an O(ln n)-factor, in terms of … Read more

    On the oracle complexity of first-order and derivative-free algorithms for smooth nonconvex minimization

  • Coralia Cartis
  • Nicholas I. M. Gould
  • Philippe L. Toint
    • Categories Nonlinear Systems and Least-Squares, Unconstrained Optimization Tags , , , , ,

    The (optimal) function/gradient evaluations worst-case complexity analysis available for the Adaptive Regularizations algorithms with Cubics (ARC) for nonconvex smooth unconstrained optimization is extended to finite-difference versions of this algorithm, yielding complexity bounds for first-order and derivative free methods applied on the same problem class. A comparison with the results obtained for derivative-free methods by Vicente … Read more

    Information-theoretic lower bounds on the oracle complexity of convex optimization

  • Alekh Agarwal
  • Peter L Bartlett
  • Martin J Wainwright
  • Pradeep Ravikumar
    • Categories Convex Optimization, Stochastic Programming Tags ,

    Relative to the large literature on upper bounds on complexity of convex optimization, lesser attention has been paid to the fundamental hardness of these problems. Given the extensive use of convex optimization in machine learning and statistics, gaining an understanding of these complexity-theoretic issues is important. In this paper, we study the complexity of stochastic … Read more