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).

Makes patches from huge resolution .svs slide files using openslide

openslide_patcher Makes patches from huge resolution .svs slide files using openslide Example collage I made from outputs:

2 Dec 23, 2021
Direct Multi-view Multi-person 3D Human Pose Estimation

Implementation of NeurIPS-2021 paper: Direct Multi-view Multi-person 3D Human Pose Estimation [paper] [video-YouTube, video-Bilibili] [slides] This is

Sea AI Lab 251 Dec 30, 2022
This is an official implementation for "Exploiting Temporal Contexts with Strided Transformer for 3D Human Pose Estimation".

Exploiting Temporal Contexts with Strided Transformer for 3D Human Pose Estimation This repo is the official implementation of Exploiting Temporal Con

Vegetabird 241 Jan 07, 2023
Model search is a framework that implements AutoML algorithms for model architecture search at scale

Model search (MS) is a framework that implements AutoML algorithms for model architecture search at scale. It aims to help researchers speed up their exploration process for finding the right model a

Google 3.2k Dec 31, 2022
An improvement of FasterGICP: Acceptance-rejection Sampling based 3D Lidar Odometry

fasterGICP This package is an improvement of fast_gicp Please cite our paper if possible. W. Jikai, M. Xu, F. Farzin, D. Dai and Z. Chen, "FasterGICP:

79 Dec 31, 2022
Standalone pre-training recipe with JAX+Flax

Sabertooth Sabertooth is standalone pre-training recipe based on JAX+Flax, with data pipelines implemented in Rust. It runs on CPU, GPU, and/or TPU, b

Nikita Kitaev 26 Nov 28, 2022
Predicting Event Memorability from Contextual Visual Semantics

Predicting Event Memorability from Contextual Visual Semantics

0 Oct 06, 2021
Adversarial Attacks on Probabilistic Autoregressive Forecasting Models.

Attack-Probabilistic-Models This is the source code for Adversarial Attacks on Probabilistic Autoregressive Forecasting Models. This repository contai

SRI Lab, ETH Zurich 25 Sep 14, 2022
Learning based AI for playing multi-round Koi-Koi hanafuda card games. Have fun.

Koi-Koi AI Learning based AI for playing multi-round Koi-Koi hanafuda card games. Platform Python PyTorch PySimpleGUI (for the interface playing vs AI

Sanghai Guan 10 Nov 20, 2022
Solution of Kaggle competition: Sartorius - Cell Instance Segmentation

Sartorius - Cell Instance Segmentation https://www.kaggle.com/c/sartorius-cell-instance-segmentation Environment setup Build docker image bash .dev_sc

68 Dec 09, 2022
Evaluating Privacy-Preserving Machine Learning in Critical Infrastructures: A Case Study on Time-Series Classification

PPML-TSA This repository provides all code necessary to reproduce the results reported in our paper Evaluating Privacy-Preserving Machine Learning in

Dominik 1 Mar 08, 2022
GNN-based Recommendation Benchma

GRecX A Fair Benchmark for GNN-based Recommendation Preliminary Comparison DiffNet-Yelp dataset (featureless) Algo 73 Oct 17, 2022

This repo contains the implementation of the algorithm proposed in Off-Belief Learning, ICML 2021.

Off-Belief Learning Introduction This repo contains the implementation of the algorithm proposed in Off-Belief Learning, ICML 2021. Environment Setup

Facebook Research 32 Jan 05, 2023
MetaBalance: High-Performance Neural Networks for Class-Imbalanced Data

This repository is the official PyTorch implementation of Meta-Balance. Find the paper on arxiv MetaBalance: High-Performance Neural Networks for Clas

Arpit Bansal 20 Oct 18, 2021
Public repository created to store my custom-made tools for Just Dance (UbiArt Engine)

Woody's Just Dance Tools Public repository created to store my custom-made tools for Just Dance (UbiArt Engine) Development and updates Almost all of

Wodson de Andrade 8 Dec 24, 2022
PyTorch implementations of Generative Adversarial Networks.

This repository has gone stale as I unfortunately do not have the time to maintain it anymore. If you would like to continue the development of it as

Erik Linder-Norén 13.4k Jan 08, 2023
Official repo for our 3DV 2021 paper "Monocular 3D Reconstruction of Interacting Hands via Collision-Aware Factorized Refinements".

Monocular 3D Reconstruction of Interacting Hands via Collision-Aware Factorized Refinements Yu Rong, Jingbo Wang, Ziwei Liu, Chen Change Loy Paper. Pr

Yu Rong 41 Dec 13, 2022
PyTorch implementation for the paper Pseudo Numerical Methods for Diffusion Models on Manifolds

Pseudo Numerical Methods for Diffusion Models on Manifolds (PNDM) This repo is the official PyTorch implementation for the paper Pseudo Numerical Meth

Luping Liu (刘路平) 196 Jan 05, 2023
LSTM built using Keras Python package to predict time series steps and sequences. Includes sin wave and stock market data

LSTM Neural Network for Time Series Prediction LSTM built using the Keras Python package to predict time series steps and sequences. Includes sine wav

Jakob Aungiers 4.1k Jan 02, 2023
LUKE -- Language Understanding with Knowledge-based Embeddings

LUKE (Language Understanding with Knowledge-based Embeddings) is a new pre-trained contextualized representation of words and entities based on transf

Studio Ousia 587 Dec 30, 2022