Solver for Large-Scale Rank-One Semidefinite Relaxations

Overview

STRIDE: spectrahedral proximal gradient descent along vertices

A Solver for Large-Scale Rank-One Semidefinite Relaxations

About

STRIDE is designed for solving high-order semidefinite programming (SDP) relaxations of nonconvex polynomial optimization problems (POPs) that admit rank-one optimal solutions. STRIDE is the first algorithmic framework that blends fast local search on the nonconvex POP with global descent on the convex SDP. Specifically, STRIDE follows a globally convergent trajectory driven by a proximal gradient method (PGM) for solving the SDP, while simultaneously probing long, but safeguarded, rank-one "strides", generated by fast nonlinear programming algorithms on the POP, to seek rapid descent.

If you find STRIDE helpful or use it in your projects, please cite:

@article{Yang21arxiv-stride,
  title={STRIDE along Spectrahedral Vertices for Solving Large-Scale Rank-One Semidefinite Relaxations},
  author={Yang, Heng and Liang, Ling and Toh, Kim-Chuan and Carlone, Luca},
  journal={arXiv preprint arXiv:2105.14033},
  year={2021}
}

Dependencies

In order to run the example code example_quasar.m, please download the following two packages and provide paths to them in example_quasar.m:

  • SDPNAL+: STRIDE uses the ADMM+ subroutine in SDPNAL+ to warmstart.
  • Manopt: in example_quasar.m, STRIDE uses Manopt to perform local search to generate rank-one strides.

Example

We provide a starting example about how to use STRIDE to solve the QUASAR semidefinite relaxation in the script example_quasar.m, you can simply run the script in Matlab.

We also provide an example about using MOSEK to solve the same QUASAR problems, you can run the script example_quasar_mosek.m in Matlab (for which please download MOSEK).

Surprise: you should see STRIDE being 50 times faster on data/quasar_100_1.mat (100 measurements, 20 seconds vs. 1000 seconds) and 30 times faster on data/quasar_50_1.mat (50 measurements, 2 seconds vs. 60 seconds). Note that MOSEK cannot solve larger problems than data/quasar_100_1.mat, but STRIDE has successfully solved problems with up to 1000 measurements (in which case the SDP has millions of constraints, see our paper). However, the goal of STRIDE is not to replace MOSEK -for generic SDP problems that have small to medium size, MOSEK is still the go-to solver- but to provide a solution for large-scale SDPs arising from rank-one semidefinite relaxations that are far beyond the reach of MOSEK.

For more examples of using STRIDE for machine perception applications, please navigate to the repo CertifiablyRobustPerception.

How to use STRIDE

The function signature for STRIDE is

[out,Xopt,yopt,Sopt] = PGDSDP(blk,At,b,C,X0,options)

where PGDSDP stands for projected gradient descent in solving a generic SDP problem (which is the backbone of STRIDE). We now describe the detailed input and out of STRIDE.

Input

  • blk,At,b,C: standard SDP data in SDPT3 format. A standard SDP problem can be fully described by blk,At,b,C, where blk describes the sizes of the positive semidefinite constraints (i.e., blocks, we do not support other conic constraints such as second-order cone and nonnegative orthant), At,b describes the linear constraints, and C describes the linear cost function. blk,At,C should be Matlab cell arrays, while b should be a Matlab array. Please refer to the SDPT3 user guide for details. We provide two example problem data for the QUASAR SDP in the subfolder data. If you are interested in how to generate standard SDP problem data from semidefinite relaxations of polynomial optimization problems, please navigate to the repo CertifiablyRobustPerception.

  • X0: a primal initial guess for the SDP problem. Set X0 = [] if no initial guess is available. A good way of providing an initial primal guess is to use fmincon in Matlab to solve the original polynomial optimization problem (if the POP admits a manifold structure, Manopt should be preferred), obtain a local optimizer, and lift the local optimizer to a rank-one feasible point of the SDP. Please read our paper for more details.

  • options: a Matlab structure that provides more information. There are many available parameters in options, but there are two parameters that are required:

    • options.rrFunName: a string that provides the name of the Matlab function that implements a local search scheme. For example, in the provided example example_quasar.m, we use options.rrFunName = 'local_search_quasar' to tell STRIDE that the function local_search_quasar.m implements the local search scheme.

    • options.SDPNALpath: a string that provides the path to the software package SDPNAL+. STRIDE uses the admmplus subroutine in SDPNAL+ to warmstart. The other optional parameters are described in more details below.

Output

  • Xopt,yopt,Sopt: an (approximate) optimal solution to the SDP. In many cases, STRIDE can solve the SDP to very high accuracy (even better than MOSEK). The printout of STRIDE will show the KKT residuals at Xopt,yopt,Sopt.
  • out: a Matlab structure that contains other information such as run history and runtime.

Available parameters

We now list all the available but optional parameters in options:

  • options.S0: a dual initial guess. Typically it is difficult to have a good guess on the dual variables. If not provided, STRIDE uses ADMM+ to generate dual initial guess. However, in some cases, one can exploit problem structure to provide clever dual initializations, please checkout our paper for details.

  • options.tolADMM: accuracy tolerance for using ADMM+. We note that this is perhaps the most important parameter to tune for a fast performance. Setting options.tolADMM very low (e.g., 1e-12) will ask ADMM+ to provide a very accurate warmstart (in the price of more ADMM+ iterations and runtime) so that the main STRIDE algorithm will converge very fast. Setting options.tolADMM very high (e.g., 1e-4) will not require an accurate warmstart from ADMM+ (so very few ADMM+ iterations and less runtime), but it may take many STRIDE main PGD iterations. We recommend tuning this parameter for each specific problem. For the QUASAR examples in this repo, options.tolADMM = 1e-4 works very well.

  • options.maxiterADMM: maximum ADMM+ iterations, default 1e4.

  • options.tolPGD: accuracy tolerance for STRIDE, in terms of maximum relative KKT residual, default 1e-6.

  • options.pgdStepSize: step size for projected gradient descent. We recommend setting options.pgdStepSize = 10.

  • options.maxiterPGD: maximum outer iterations of STRIDE (in performing projected gradient descent), default 10.

  • options.lbfgsmemory: memory of L-BFGS, default 10.

  • options.maxiterLBFGS: maximum iterations of L-BFGS, default 1000.

  • options.lbfgseps: boolean value to decide if using inexactness in L-BFGS (what we call modified L-BFGS), default options.lbfgseps = true. In practice we found this does not have significant effect on the convergence speed.

  • options.rrOpt: a array that contains the indices of the eigenvectors to be rounded in local search, default options.rrOpt = 1:3 and STRIDE generates rounded hypotheses from the leading 3 eigenvectors.

  • options.rrPar: a Matlab structure that contains all user-defined information needed to perform local search. For a template about how to implement a local search scheme, please see below.

Implement your local search scheme

The function signature for a local search scheme is

[Xhat,fhat,info] = local_search_func(Xbar,C,rrPar,rrOpt,roundonly)

where local_search_func is the string that needs to be passed to STRIDE's function call by using options.rrFunName = 'local_search_func', so that STRIDE can evaluate the local_search_func.m function to generate rank-one hypotheses.

We now explain the input and output of local_search_func.

Input

  • Xbar: a primal SDP iterate, generated by STRIDE's projected gradient descent backbone. Xbar has the same format as X0 and Xopt and is a cell array of positive semidefinite matrices (block structure defined by blk).

  • C: linear cost function, same as the C in standard SDP data.

  • rrPar: a Matlab structure that contains any data that are necessary for performing local search using Xbar. For example, rrPar can contain suitable data from the original POP. This rrPar is provide by using options.rrPar when calling STRIDE.

  • rrOpt: a array that contains the indices of the eigenvectors to be rounded in local search. This rrOpt is provided by using options.rrOpt when calling STRIDE.

  • roundonly: a boolean value that decides if STRIDE should just perform rounding (without local search). If roundonly = true, then the user should specify a routine that generates a rounded feasible POP point from Xbar. If roundonly = false, then the user should specify a routine that not only generates a rounded POP iterate, but also perform local search starting from the rounded POP iterate, using suitable nonlinear programming techniques.

Output

  • Xhat: a rank-one SDP iterate, generated by rounding, local search and lifting from Xbar.

  • fhat: value of the SDP objective function attained by Xhat, by using the cost matrix C.

  • info (optional output): a structure that contains the following information:

    • info.nlpsuccess: a boolean value that indicates whether the local search has been successful (for example, if the nonlinear programming solver has failed, then info.nlpsuccess = false).
    • info.minidx: the index of the eigenvector, from which the local search solution is best. For example, if rrOpt = 1:3, and the local solution obtained from rounding the second eigenvector attained the lowest cost, then info.minidx = 2.
    • info.pobjs: the objective values of all local search solutions.
    • info.diffpobj: which is simply info.diffpobj = info.pobjs(1) - fhat.

Although the local_search_func may sound complicated to implement, it is quite natural, because it is simply how one would implement a local optimization method for the POP. Please see utils/local_search_quasar.m for how we implemented a local search scheme for the QUASAR SDP relaxation. Note that one of the major contributions of STRIDE is to use the original POP to attain fast convergence, so please spend time on implementing this local search function for your problem.

Acknowledgements

STRIDE is implemented by Heng Yang (MIT) and Ling Liang (NUS). We would like to thank the feedback and resources from Prof. Kim-Chuan Toh (NUS), and Prof. Luca Carlone (MIT).

RIFE: Real-Time Intermediate Flow Estimation for Video Frame Interpolation

RIFE - Real Time Video Interpolation arXiv | YouTube | Colab | Tutorial | Demo Table of Contents Introduction Collection Usage Evaluation Training and

hzwer 3k Jan 04, 2023
AutoVideo: An Automated Video Action Recognition System

AutoVideo is a system for automated video analysis. It is developed based on D3M infrastructure, which describes machine learning with generic pipeline languages. Currently, it focuses on video actio

Data Analytics Lab at Texas A&M University 267 Dec 17, 2022
The Pytorch implementation for "Video-Text Pre-training with Learned Regions"

Region_Learner The Pytorch implementation for "Video-Text Pre-training with Learned Regions" (arxiv) We are still cleaning up the code further and pre

Rui Yan 0 Mar 20, 2022
NR-GAN: Noise Robust Generative Adversarial Networks

Lexicon Enhanced Chinese Sequence Labeling Using BERT Adapter Code and checkpoints for the ACL2021 paper "Lexicon Enhanced Chinese Sequence Labelling

Takuhiro Kaneko 59 Dec 11, 2022
Pytorch implementation of the paper "COAD: Contrastive Pre-training with Adversarial Fine-tuning for Zero-shot Expert Linking."

Expert-Linking Pytorch implementation of the paper "COAD: Contrastive Pre-training with Adversarial Fine-tuning for Zero-shot Expert Linking." This is

BoChen 12 Jan 01, 2023
RRxIO - Robust Radar Visual/Thermal Inertial Odometry: Robust and accurate state estimation even in challenging visual conditions.

RRxIO - Robust Radar Visual/Thermal Inertial Odometry RRxIO offers robust and accurate state estimation even in challenging visual conditions. RRxIO c

Christopher Doer 64 Dec 29, 2022
LVI-SAM: Tightly-coupled Lidar-Visual-Inertial Odometry via Smoothing and Mapping

LVI-SAM This repository contains code for a lidar-visual-inertial odometry and mapping system, which combines the advantages of LIO-SAM and Vins-Mono

Tixiao Shan 1.1k Dec 27, 2022
Deep Residual Learning for Image Recognition

Deep Residual Learning for Image Recognition This is a Torch implementation of "Deep Residual Learning for Image Recognition",Kaiming He, Xiangyu Zhan

Kimmy 561 Dec 01, 2022
Code for the bachelors-thesis flaky fault localization

Flaky_Fault_Localization Scripts for the Bachelors-Thesis: "Flaky Fault Localization" by Christian Kasberger. The thesis examines the usefulness of sp

Christian Kasberger 1 Oct 26, 2021
Official implementation of Densely connected normalizing flows

Densely connected normalizing flows This repository is the official implementation of NeurIPS 2021 paper Densely connected normalizing flows. Poster a

Matej Grcić 31 Dec 12, 2022
The code for 'Deep Residual Fourier Transformation for Single Image Deblurring'

Deep Residual Fourier Transformation for Single Image Deblurring Xintian Mao, Yiming Liu, Wei Shen, Qingli Li and Yan Wang code will be released soon

145 Dec 13, 2022
Res2Net for Instance segmentation and Object detection using MaskRCNN

Res2Net for Instance segmentation and Object detection using MaskRCNN Since the MaskRCNN-benchmark of facebook is deprecated, we suggest to use our mm

Res2Net Applications 55 Oct 30, 2022
EDCNN: Edge enhancement-based Densely Connected Network with Compound Loss for Low-Dose CT Denoising

EDCNN: Edge enhancement-based Densely Connected Network with Compound Loss for Low-Dose CT Denoising By Tengfei Liang, Yi Jin, Yidong Li, Tao Wang. Th

workingcoder 115 Jan 05, 2023
Use Python, OpenCV, and MediaPipe to control a keyboard with facial gestures

CheekyKeys A Face-Computer Interface CheekyKeys lets you control your keyboard using your face. View a fuller demo and more background on the project

69 Nov 09, 2022
A repo to show how to use custom dataset to train s2anet, and change backbone to resnext101

A repo to show how to use custom dataset to train s2anet, and change backbone to resnext101

jedibobo 3 Dec 28, 2022
Learning recognition/segmentation models without end-to-end training. 40%-60% less GPU memory footprint. Same training time. Better performance.

InfoPro-Pytorch The Information Propagation algorithm for training deep networks with local supervision. (ICLR 2021) Revisiting Locally Supervised Lea

78 Dec 27, 2022
PyTorch implementation of paper A Fast Knowledge Distillation Framework for Visual Recognition.

FKD: A Fast Knowledge Distillation Framework for Visual Recognition Official PyTorch implementation of paper A Fast Knowledge Distillation Framework f

Zhiqiang Shen 129 Dec 24, 2022
Tweesent-back - Tweesent backend uses fastAPI as the web framework

TweeSent Backend Tweesent backend. This repo uses fastAPI as the web framework.

0 Mar 26, 2022
Pytorch implementation of our paper LIMUSE: LIGHTWEIGHT MULTI-MODAL SPEAKER EXTRACTION.

LiMuSE Overview Pytorch implementation of our paper LIMUSE: LIGHTWEIGHT MULTI-MODAL SPEAKER EXTRACTION. LiMuSE explores group communication on a multi

Auditory Model and Cognitive Computing Lab 17 Oct 26, 2022
A tensorflow implementation of Fully Convolutional Networks For Semantic Segmentation

##A tensorflow implementation of Fully Convolutional Networks For Semantic Segmentation. #USAGE To run the trained classifier on some images: python w

Alex Seewald 13 Nov 17, 2022