Convex Optimization

A Data Efficient and Feasible Level Set Method for Stochastic Convex Optimization with Expectation Constraints

  • Qihang Lin
  • Selvaprabu Nadarajah
  • Negar Soheili
  • Tianbao Yang
    • Categories Convex Optimization, Stochastic Programming Tags , , ,

    Stochastic convex optimization problems with expectation constraints (SOECs) are encountered in statistics and machine learning, business, and engineering. In data-rich environments, the SOEC objective and constraints contain expectations defined with respect to large datasets. Therefore, efficient algorithms for solving such SOECs need to limit the fraction of data points that they use, which we refer … Read more

    Robust stochastic optimization with the proximal point method

  • Damek Davis
  • Dmitriy Drusvyatskiy
    • Categories Convex Optimization, Stochastic Programming Tags , , , ,

    Standard results in stochastic convex optimization bound the number of samples that an algorithm needs to generate a point with small function value in expectation. In this work, we show that a wide class of such algorithms on strongly convex problems can be augmented with sub-exponential confidence bounds at an overhead cost that is only … Read more

    Distributionally robust chance constrained geometric optimization

  • Jia Liu
  • Abdel Lisser
  • Zhiping Chen
    • Categories Convex Optimization, Robust Optimization, Stochastic Programming Tags , , ,

    This paper discusses distributionally robust geometric programs with individual and joint chance constraints. Seven groups of uncertainty sets are considered: uncertainty sets with first two order moments information, uncertainty sets constrained by the Kullback-Leibler divergence distance with a normal reference distribution or a discrete reference distribution, uncertainty sets with known first moments or known first … Read more

    Tensor Methods for Finding Approximate Stationary Points of Convex Functions

  • Geovani Nunes Grapiglia
  • Yurii Nesterov
    • Categories Convex Optimization Tags , , , ,

    In this paper we consider the problem of finding \epsilon-approximate stationary points of convex functions that are p-times differentiable with \nu-Hölder continuous pth derivatives. We present tensor methods with and without acceleration. Specifically, we show that the non-accelerated schemes take at most O(\epsilon^{-1/(p+\nu-1)}) iterations to reduce the norm of the gradient of the objective below … Read more

    A family of multi-parameterized proximal point algorithms

  • Jianchao Bai
  • Ke Guo
  • Xiaokai Chang
    • Categories Convex Optimization Tags , , ,

    In this paper, a multi-parameterized proximal point algorithm combining with a relaxation step is developed for solving convex minimization problem subject to linear constraints. We show its global convergence and sublinear convergence rate from the prospective of variational inequality. Preliminary numerical experiments on testing a sparse minimization problem from signal processing indicate that the proposed … Read more

    The stochastic multi-gradient algorithm for multi-objective optimization and its application to supervised machine learning

  • Suyun Liu
  • Luis Nunes Vicente
    • Categories Convex Optimization, Multi-Criteria Optimization, Stochastic Programming Tags , , ,

    Optimization of conflicting functions is of paramount importance in decision making, and real world applications frequently involve data that is uncertain or unknown, resulting in multi-objective optimization (MOO) problems of stochastic type. We study the stochastic multi-gradient (SMG) method, seen as an extension of the classical stochastic gradient method for single-objective optimization. At each iteration … Read more

    Optimal K-Thresholding Algorithms for Sparse Optimization Problems

  • Yun-Bin Zhao
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Data-Mining Tags , , , , ,

    The simulations indicate that the existing hard thresholding technique independent of the residual function may cause a dramatic increase or numerical oscillation of the residual. This inherit drawback of the hard thresholding renders the traditional thresholding algorithms unstable and thus generally inefficient for solving practical sparse optimization problems. How to overcome this weakness and develop … Read more

    Acceleration of SVRG and Katyusha X by Inexact Preconditioning

  • Fei Feng
  • Yanli Liu
  • Wotao Yin
    • Categories Convex Optimization, Stochastic Programming Tags , ,

    Empirical risk minimization is an important class of optimization problems with many popular machine learning applications, and stochastic variance reduction methods are popular choices for solving them. Among these methods, SVRG and Katyusha X (a Nesterov accelerated SVRG) achieve fast convergence without substantial memory requirement. In this paper, we propose to accelerate these two algorithms … Read more

    On the Relation between the Extended Supporting Hyperplane Algorithm and Kelley’s Cutting Plane Algorithm

  • Ambros Gleixner
  • Felipe Serrano
  • Robert Schwarz
    • Categories (Mixed) Integer Nonlinear Programming, Convex Optimization Tags , ,

    Recently, Kronqvist et al.rediscovered the supporting hyperplane algorithm of Veinott and demonstrated its computational benefits for solving convex mixed-integer nonlinear programs. In this paper we derive the algorithm from a geometric point of view. This enables us to show that the supporting hyperplane algorithm is equivalent to Kelley’s cutting plane algorithm applied to a particular … Read more

    Variable smoothing for convex optimization problems using stochastic gradients

  • Axel Böhm
  • Radu Ioan Bot
    • Categories Convex Optimization, Stochastic Programming Tags , , ,

    We aim to solve a structured convex optimization problem, where a nonsmooth function is composed with a linear operator. When opting for full splitting schemes, usually, primal-dual type methods are employed as they are effective and also well studied. However, under the additional assumption of Lipschitz continuity of the nonsmooth function which is composed with … Read more