Convex Optimization

The Role of Level-Set Geometry on the Performance of PDHG for Conic Linear Optimization

  • Zikai Xiong
  • Robert M. Freund
    • Categories Convex Optimization, Linear Programming, Linear, Cone and Semidefinite Programming Tags , , , , ,

    We consider solving huge-scale instances of (convex) conic linear optimization problems, at the scale where matrix-factorization-free methods are attractive or necessary. The restarted primal-dual hybrid gradient method (rPDHG) — with heuristic enhancements and GPU implementation — has been very successful in solving huge-scale linear programming (LP) problems; however its application to more general conic convex … Read more

    Convex optimization on CAT(0) cubical complexes

  • Adrian Lewis
    • Categories Convex Optimization Tags , , , ,

    We consider geodesically convex optimization problems involving distances to a finite set of points A in a CAT(0) cubical complex. Examples include the minimum enclosing ball problem, the weighted mean and median problems, and the feasibility and projection problems for intersecting balls with centers in A. We propose a decomposition approach relying on standard Euclidean … Read more

    Faster Convergence of Stochastic Accelerated Gradient Descent under Interpolation

  • Aaron Mishkin
  • Mert Pilanci
  • Mark Schmidt
    • Categories Convex Optimization, Stochastic Programming Tags , , ,

    We prove new convergence rates for a generalized version of stochastic Nesterov acceleration under interpolation conditions. Unlike previous analyses, our approach accelerates any stochastic gradient method which makes sufficient progress in expectation. The proof, which proceeds using the estimating sequences framework, applies to both convex and strongly convex functions and is easily specialized to accelerated … Read more

    Slow convergence of the moment-SOS hierarchy for an elementary polynomial optimization problem

  • Didier Henrion
  • Adrien Le Franc
  • Victor Magron
    • Categories Convex Optimization, Nonlinear Optimization Tags , ,

    We describe a parametric univariate quadratic optimization problem for which the moment-SOS hierarchy has finite but increasingly slow convergence when the parameter tends to its limit value. We estimate the order of finite convergence as a function of the parameter. ArticleDownload View PDF

    Scalable Projection-Free Optimization Methods via MultiRadial Duality Theory

  • Thabo Samakhoana
  • Benjamin Grimmer
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization Tags , , ,

    Recent works have developed new projection-free first-order methods based on utilizing linesearches and normal vector computations to maintain feasibility. These oracles can be cheaper than orthogonal projection or linear optimization subroutines but have the drawback of requiring a known strictly feasible point to do these linesearches with respect to. In this work, we develop new … Read more

    The stochastic Ravine accelerated gradient method with general extrapolation coefficients

  • Hédy Attouch
  • Jalal Fadili
  • Vyacheslav Kungurtsev
    • Categories Convex Optimization, Nonlinear Optimization Tags ,

    Abstract: In a real Hilbert space domain setting, we study the convergence properties of the stochastic Ravine accelerated gradient method for convex differentiable optimization. We consider the general form of this algorithm where the extrapolation coefficients can vary with each iteration, and where the evaluation of the gradient is subject to random errors. This general … Read more

    On Averaging and Extrapolation for Gradient Descent

  • Alan Luner
  • Benjamin Grimmer
    • Categories Convex Optimization, Semi-definite Programming Tags , , , ,

    This work considers the effect of averaging, and more generally extrapolation, of the iterates of gradient descent in smooth convex optimization. After running the method, rather than reporting the final iterate, one can report either a convex combination of the iterates (averaging) or a generic combination of the iterates (extrapolation). For several common stepsize sequences, … Read more

    A new proximal gradient algorithm for solving mixed variational inequality problems with a novel explicit stepsize and applications

  • Pham Thi Hoai
    • Categories Complementarity and Variational Inequalities, Convex Optimization, Nonlinear Optimization Tags , , , ,

    In this paper, we propose a new algorithm for solving monotone mixed variational inequality problems in real Hilbert spaces based on proximal gradient method. Our new algorithm uses a novel explicit stepsize which is proved to be increasing to a positive value. This property plays an important role in improving the speed of the algorithm. … Read more

    Variance Reduction and Low Sample Complexity in Stochastic Optimization via Proximal Point Method

  • Jiaming Liang
    • Categories Convex Optimization, Stochastic Programming Tags , , , , ,

    This paper proposes a stochastic proximal point method to solve a stochastic convex composite optimization problem. High probability results in stochastic optimization typically hinge on restrictive assumptions on the stochastic gradient noise, for example, sub-Gaussian distributions. Assuming only weak conditions such as bounded variance of the stochastic gradient, this paper establishes a low sample complexity … Read more