Stochastic optimization

Correlation gap

In stochastic programming, the correlation gap is the worst-case ratio between the cost when the random variables are correlated to the cost when the random variables are independent. As an example, consider the following optimization problem. A teacher wants to know whether to come to class or not. There are n potential students. For each student, there is a probability of 1/n that the student will attend the class. If at least one student attends, then the teacher must come and his cost is 1. If no students attend, then the teacher can stay at home and his cost is 0. The goal of the teacher is to minimize his cost. This is a stochastic-programming problem, because the constraints are not known in advance – only their probabilities are known. Now, there are two cases regarding the correlation between the students: * Case #1: the students are uncorrelated: each student decides whether to come to class or not by tossing a coin with probability , independently of the others. The expected cost in this case is . * Case #2: the students are correlated: one student is selected at random and comes to class, while the others stay at home. Note that the probability of each student to come is still . However, now the cost is 1. The correlation gap is the cost in case #2 divided by the cost in case #1, which is . prove that the correlation gap is bounded in several cases. For example, when the cost function is a submodular set function (as in the above example), the correlation gap is at most (so the above example is a worst-case). An upper bound on the correlation gap implies an upper bound on the loss that results from ignoring the correlation. For example, suppose we have a stochastic programming problem with a submodular cost function. We know the marginal probabilities of the variables, but we do not know whether they are correlated or not. If we just ignore the correlation and solve the problem as if the variables are independent, the resulting solution is a -approximation to the optimal solution. (Wikipedia).

Video thumbnail

Conceptual Questions about Correlation

Please Subscribe here, thank you!!! https://goo.gl/JQ8Nys Conceptual Questions about Correlation

From playlist Statistics

Video thumbnail

Intro to the Correlation Coefficient

Brief intro to the correlation coefficient. What it means to have negative correlation, positive correlation or zero correlation. Pearson's, sample and population formulas.

From playlist Correlation

Video thumbnail

Covariance (8 of 17) What is the Correlation Coefficient?

Visit http://ilectureonline.com for more math and science lectures! To donate:a http://www.ilectureonline.com/donate https://www.patreon.com/user?u=3236071 We will learn what is and how to find the correlation coefficient of 2 data sets and see how it corresponds to the graph of the data

From playlist COVARIANCE AND VARIANCE

Video thumbnail

Limits of correlation (applied)

Correlation is a standardized covariance (i.e., translated into unit-less form with volatilities). It cannot be used alone: (i) it can be "distorted" by low volatilities, and (ii) it does not give information revealed by the scatter (in this example, both hedge fund series are similarly co

From playlist Statistics: Introduction

Video thumbnail

Covariance Definition and Example

What is covariance? How do I find it? Step by step example of a solved covariance problem for a sample, along with an explanation of what the results mean and how it compares to correlation. 00:00 Overview 03:01 Positive, Negative, Zero Correlation 03:19 Covariance for a Sample Example

From playlist Correlation

Video thumbnail

Correlation Coefficient

This video explains how to find the correlation coefficient which describes the strength of the linear relationship between two variables x and y. My Website: https://www.video-tutor.net Patreon: https://www.patreon.com/MathScienceTutor Amazon Store: https://www.amazon.com/shop/theorga

From playlist Statistics

Video thumbnail

Covariance (1 of 17) What is Covariance? in Relation to Variance and Correlation

Visit http://ilectureonline.com for more math and science lectures! To donate:a http://www.ilectureonline.com/donate https://www.patreon.com/user?u=3236071 We will learn the difference between the variance and the covariance. A variance (s^2) is a measure of how spread out the numbers of

From playlist COVARIANCE AND VARIANCE

Video thumbnail

Covariance (12 of 17) Covariance Matrix wth 3 Data Sets and Correlation Coefficients

Visit http://ilectureonline.com for more math and science lectures! To donate:a http://www.ilectureonline.com/donate https://www.patreon.com/user?u=3236071 We will find the correlation coefficients of the 3 data sets form the previous 2 videos. Next video in this series can be seen at:

From playlist COVARIANCE AND VARIANCE

Video thumbnail

Correlation induced metallic, half-metallic and superconducting by H. R. Krishnamurthy

DISCUSSION MEETING NOVEL PHASES OF QUANTUM MATTER ORGANIZERS: Adhip Agarwala, Sumilan Banerjee, Subhro Bhattacharjee, Abhishodh Prakash and Smitha Vishveshwara DATE: 23 December 2019 to 02 January 2020 VENUE: Ramanujan Lecture Hall, ICTS Bangalore Recent theoretical and experimental

From playlist Novel Phases of Quantum Matter 2019

Video thumbnail

Tunable gaps and bandwidths in twisted double bilayer graphene system by Mandar Deshmukh

DISCUSSION MEETING NOVEL PHASES OF QUANTUM MATTER ORGANIZERS: Adhip Agarwala, Sumilan Banerjee, Subhro Bhattacharjee, Abhishodh Prakash and Smitha Vishveshwara DATE: 23 December 2019 to 02 January 2020 VENUE: Ramanujan Lecture Hall, ICTS Bangalore Recent theoretical and experimental

From playlist Novel Phases of Quantum Matter 2019

Video thumbnail

André Marie Tremblay - High temperature superconductors: Where is the mystery?

PROGRAM: STRONGLY CORRELATED SYSTEMS: FROM MODELS TO MATERIALS DATES: Monday 06 Jan, 2014 - Friday 17 Jan, 2014 VENUE: Department of Physics, IISc Campus, Bangalore PROGRAM LINK : http://www.icts.res.in/program/MTM2014 The realistic description of materials with strong electron-electro

From playlist Strongly correlated systems: From models to materials

Video thumbnail

Quantum Transport, Lecture 13: Superconductivity

Instructor: Sergey Frolov, University of Pittsburgh, Spring 2013 http://sergeyfrolov.wordpress.com/ Summary: basics of superconductivity, Cooper pairing, energy gap, Andreev reflection. Quantum Transport course development supported in part by the National Science Foundation under grant DM

From playlist Quantum Transport

Video thumbnail

AQC 2016 - Inhomogeneous Quasi-adiabatic Driving of Quantum Critical Dynamics

A Google TechTalk, June 27, 2016, presented by Masoud Mohseni (Google) ABSTRACT: We introduce an inhomogeneous protocol to drive a weakly disordered quantum spin chain quasi-adiabatically across a quantum phase transition and minimize the residual energy of the final state. The number of

From playlist Adiabatic Quantum Computing Conference 2016

Video thumbnail

Lec 16 | MIT 5.74 Introductory Quantum Mechanics II, Spring 2009

Lecture 16: Characterizing Fluctuations View the complete course: http://ocw.mit.edu/5-74S09 License: Creative Commons BY-NC-SA More information at http://ocw.mit.edu/terms More courses at http://ocw.mit.edu

From playlist MIT 5.74 Introductory Quantum Mechanics II, Spring 2009

Video thumbnail

MIP* = RE - Henry Yuen

Computer Science/Discrete Mathematics Seminar I Topic: MIP* = RE Speaker: Henry Yuen Affiliation: University of Toronto Date: February 03, 2020 For more video please visit http://video.ias.edu

From playlist Mathematics

Video thumbnail

Anna Keselman: "Spectral Signatures of Quasiparticle Interactions in Antiferromagnets"

Tensor Methods and Emerging Applications to the Physical and Data Sciences 2021 Workshop II: Tensor Network States and Applications "Spectral Signatures of Quasiparticle Interactions in Antiferromagnets" Anna Keselman - Kavli Institute for Theoretical Physics Abstract: Elementary excitat

From playlist Tensor Methods and Emerging Applications to the Physical and Data Sciences 2021

Video thumbnail

Introduction to Correlation

Please Subscribe here, thank you!!! https://goo.gl/JQ8Nys Introduction to Correlation

From playlist Statistics

Video thumbnail

Continuous Mott transitions in a model Hamiltonian system by N S Vidhyadhiraja

29 May 2017 to 02 June 2017 VENUE: Ramanujan Lecture Hall, ICTS Bangalore This program aims to bring together people working on classical and quantum systems with disorder and interactions. The extensive exploration, through experiments, simulations and model calculations, of growing cor

From playlist Correlation and Disorder in Classical and Quantum Systems

Related pages

Robust optimization | Independence (probability theory) | Info-gap decision theory | Submodular set function | Bayesian-optimal pricing | Stochastic programming