An overview of replica symmetry breaking

For more info about our services contact : help@bestpfe.com

Table of contents

Introduction
1 The replica method and the inverse Ising problem with sparse weights
1.1 The replica method for spin glass models
1.1.1 Introduction to spin glass models
1.1.2 Goal of the replica method
1.1.3 Example of replica-symmetric calculation: the Sherrington-Kirkpatrick model
Averaging the replicated partition function
Taking the limit N ! 1 first
Choosing an ansatz
Taking the limit n ! 0
1.1.4 An overview of replica symmetry breaking
Pure states and ergodicity breaking
Physical parameters
Physical meaning of the overlap matrix Q
1-step replica symmetry breaking
Beyond 1RSB
1.2 An introduction on statistical inference
Teacher-student scenario
Estimators
Bayes optimal versus mismatched case
1.3 Inverse Ising problem with sparse teacher couplings
1.3.1 Introduction of the inverse Ising problem
The maximum likelihood estimator
The pseudo likelihood and local estimators
Teacher-student scenario
Statistical mechanics analysis: general framework
Revisiting the fully-connected case
1.3.2 Details of the sparsely-connected case
Difficulty of the sparse case and oracle estimator
Ansatz on the estimator
Properties of h and ha Average free energy in the sparsely-connected case
1.3.3 Properties of the direct problem
Marginal distribution of the teacher model
Inverse correlation function
1.3.4 Applicable range of the ansatz
Zero gradient conditions for Validity of the ansatz on tree-like graphs
1.3.5 Numerical experiments RR graph case ER graph case
Square lattice case for comparison
Comparison with interaction screening
1.3.6 Discussion and limits
2 Universality of phase transitions in noiseless linear regression 
2.1 Belief propagation
2.1.1 Factor graphs
2.1.2 An easy example: the Ising chain
2.1.3 BP on tree-like networks
BP equations
Simplification for pairwise models
Useful quantities
Bethe free energy
2.1.4 BP on loopy graphs
2.2 Theoretical background on linear regression
2.2.1 Introduction to linear regression
2.2.2 Sparse linear regression
Why sparse?
Bayes-optimal versus `1 reconstruction
Two types of matrices
Replica analysis for i.i.d. and right rotationally invariant matrices
Theoretical phase transitions
2.2.3 Approximate message passing algorithms
2.3 Universal transitions in noiseless compressed sensing
2.3.1 Equivalence between right rotationally invariant and Gaussian i.i.d. matrices
2.3.2 Universal transitions for structured matrices
Some types of structured matrices
Numerical results
2.3.3 Discussion and limits of the universality
3 Asymptotic errors for convex penalized linear regression 
3.1 Definition of the problem
3.2 Statistical physics result: the replica formula
3.3 Vector approximate passing and its state evolution
3.3.1 MAP formulation of Vector approximate message passing
3.3.2 Equality of ˆx and VAMP’s fixed point
3.3.3 State evolution of VAMP
3.3.4 Equivalence of state evolution and replica equations
3.4 A simplified algorithm: Oracle VAMP
3.4.1 Idea of the proof
3.4.2 Definition of Oracle VAMP
3.4.3 Strong convexity and smoothness of a convex function
3.4.4 Lipschitz constants of Oracle VAMP’s operators
3.5 Smoothed problem and its convergence
3.5.1 Definition of the modified problem
3.5.2 Bounds on variance parameters A1 and A2
3.5.3 A note on non-separable denoisers
3.5.4 Convergence bound on Oracle VAMP
3.6 Analytic continuation and end of the proof
3.7 Applications and numerical experiments
3.7.1 Linear regression with row orthogonal matrices
3.7.2 Overparametrization and double descent
4 Asymptotic errors for convex generalized linear models 
4.1 Introduction of the problem
4.2 Statistical physics result: the replica formula
4.2.1 Replica free energy
4.2.2 Sketch of proof
4.3 MLVAMP and its state evolution
4.3.1 MAP formulation of two-layer VAMP
4.3.2 Equality of ˆx and MLVAMP’s fixed point
4.3.3 State evolution of MLVAMP and its fixed point
4.4 Oracle MLVAMP as a dynamical system
4.4.1 Definition of Oracle MLVAMP
4.4.2 Compact form of Oracle MLVAMP
4.4.3 Recast of Oracle VAMP as a linear system
4.4.4 Lipschitz constants and constraint matrices
4.4.5 Bounds on variance parameters
4.5 Smoothed problem and end of the proof
4.5.1 Convergence of the smoothed problem
4.5.2 Analytic continuation
4.6 Numerical experiments
4.6.1 Matrix parameters and singular values
4.6.2 Regularization: elastic net
4.6.3 Loss functions
5 Rademacher complexity and replica free energy 
5.1 Convergence bounds on the generalization gap
5.1.1 A friendly introduction to the generalization problem
5.1.2 The Vapnik-Chervonenkis theorem on uniform convergence
5.1.3 The Rademacher complexity
Rademacher bound on uniform convergence
Recovering the VC uniform convergence bound
5.2 Rademacher complexities on some hypothesis classes for i.i.d. data
5.2.1 Linear model
5.2.2 Perceptron model
5.3 The statistical physics approach
5.3.1 The Gardner capacity for classification problems
5.3.2 The Rademacher complexity and the ground state energy
5.3.3 A flavor of understanding of Rademacher bounds on generalization
5.4 Consequences and bounds for simple models
5.4.1 Ground state energies of the perceptron
5.4.2 Computing the ground state energy with the replica method
Reminder on the replica ansatz and calculation
General expressions of RS and 1RSB free energy for Gaussian i.i.d. data
Spherical perceptron
Binary perceptron
5.4.3 Teacher-student scenario versus worst case Rademacher
5.4.4 Committee machine with Gaussian weights
5.4.5 Extension to rotationally invariant matrices