Performance Estimation for Smooth and Strongly Convex Sets

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

    We extend recent computer-assisted design and analysis techniques for first-order optimization over structured functions–known as performance estimation–to apply to structured sets. We prove “interpolation theorems” for smooth and strongly convex sets with Slater points and bounded diameter, showing a wide range of extremal questions amount to structured mathematical programs. Prior function interpolation theorems are recovered … Read more

    Sensitivity analysis for linear changes of the constraint matrix of a (mixed-integer) linear program

  • Bardhyl Miftari
  • Quentin Louveaux
  • Guillaume Derval
    • Categories Linear Programming, Linear, Cone and Semidefinite Programming, Robust Optimization

    Understanding how the optimal value of an optimisation problem changes when its input data is modified is an old question in mathematical optimisation. This paper investigates the computation of the optimal values of a family of (possibly mixed-integer) linear optimisation problems in which the constraint matrix is subject to linear perturbations controlled by a scalar … Read more

    Single-Timescale Multi-Sequence Stochastic Approximation Without Fixed Point Smoothness: Theories and Applications

  • Yue Huang
  • Zhaoxian Wu
  • Shiqian Ma
  • Qing Ling
    • Categories Nonlinear Optimization, Stochastic Programming Tags , , ,

    Stochastic approximation (SA) that involves multiple coupled sequences, known as multiple-sequence SA (MSSA), finds diverse applications in the fields of signal processing and machine learning. However, existing theoretical understandings of MSSA are limited: the multi-timescale analysis implies a slow convergence rate, whereas the single-timescale analysis relies on a stringent fixed point smoothness assumption. This paper … Read more

    A stochastic primal-dual splitting algorithm with variance reduction for composite optimization problems

  • Dimitri Papadimitriou
    • Categories Convex and Nonsmooth Optimization, Convex Optimization

    This paper revisits the generic structured primal-dual problem involving the infimal convolution in real Hilbert spaces. For this purpose, we develop a stochastic primal-dual splitting with variance reduction for solving this generic problem. Weak almost sure convergence of the iterates is proved. The linear convergence rate of the primal-dual gap is obtained under an additional … Read more

    Column Elimination: An Iterative Approach to Solving Integer Programs

  • Anthony Karahalios
  • Willem-Jan van Hoeve
    • Categories Branch and Cut Algorithms, Dynamic Programming, Integer Programming Tags , , , , ,

    We present column elimination as a general framework for solving (large-scale) integer programming problems. In this framework, solutions are represented compactly as paths in a directed acyclic graph. Column elimination starts with a relaxed representation, that may contain infeasible paths, and solves a constrained network flow over the graph to find a solution. It then … Read more

    Adaptive Algorithms for Robust Phase Retrieval

  • Zhong Zheng
  • Necdet Serhat Aybat
  • Shiqian Ma
  • Lingzhou Xue
    • Categories Nonsmooth Optimization, Robust Optimization Tags , , ,

    This paper considers the robust phase retrieval, which can be cast as a nonsmooth and nonconvex optimization problem. We propose two first-order algorithms with adaptive step sizes: the subgradient algorithm (AdaSubGrad) and the inexact proximal linear algorithm (AdaIPL). Our contribution lies in the novel design of adaptive step sizes based on quantiles of the absolute … Read more

    Relaxed Proximal Point Algorithm: Tight Complexity Bounds and Acceleration without Momentum

  • Bofan Wang
  • Shiqian Ma
  • Junfeng Yang
  • Danqing Zhou
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization Tags , , , ,

    In this paper, we focus on the relaxed proximal point algorithm (RPPA) for solving convex (possibly nonsmooth) optimization problems. We conduct a comprehensive study on three types of relaxation schedules: (i) constant schedule with relaxation parameter \(\alpha_k\equiv \alpha \in (0, \sqrt{2}]\), (ii) the dynamic schedule put forward by Teboulle and Vaisbourd [TV23], and (iii) the … Read more

    TRFD: A Derivative-Free Trust-Region Method Based on Finite Differences for Composite Nonsmooth Optimization

  • Dânâ Davar
  • Geovani Nunes Grapiglia
    • Categories Nonsmooth Optimization Tags , , ,

    In this work we present TRFD, a derivative-free trust-region method based on finite differences for minimizing composite functions of the form \(f(x)=h(F(x))\), where \(F\) is a black-box function assumed to have a Lipschitz continuous Jacobian, and \(h\) is a known convex Lipschitz function, possibly nonsmooth. The method approximates the Jacobian of \(F\) via forward finite … Read more

    Tuning-Free Bilevel Optimization: New Algorithms and Convergence Analysis

  • Yifan Yang
  • Hao Ban
  • Minhui Huang
  • Shiqian Ma
  • Kaiyi Ji
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Other Topics Tags , , , ,

    Bilevel optimization has recently attracted considerable attention due to its abundant applications in machine learning problems. However, existing methods rely on prior knowledge of problem parameters to determine stepsizes, resulting in significant effort in tuning stepsizes when these parameters are unknown. In this paper, we propose two novel tuning-free algorithms, D-TFBO and S-TFBO. D-TFBO employs … Read more

    A Generalization Result for Convergence in Learning-to-Optimize

  • Michael Sucker
  • Peter Ochs
    • Categories Convex and Nonsmooth Optimization, Nonsmooth Optimization, Optimization in Data Science Tags , ,

    Convergence in learning-to-optimize is hardly studied, because conventional convergence guarantees in optimization are based on geometric arguments, which cannot be applied easily to learned algorithms. Thus, we develop a probabilistic framework that resembles deterministic optimization and allows for transferring geometric arguments into learning-to-optimize. Our main theorem is a generalization result for parametric classes of potentially … Read more