Showing 1–57 of 57 results for author_id: panchenko_d_1

Performance of Bayesian linear regression in a model with mismatch

Authors: Jean Barbier, Wei-Kuo Chen, Dmitry Panchenko, Manuel Sáenz

Abstract: In this paper we analyze, for a model of linear regression with gaussian covariates, the performance of a Bayesian estimator given by the mean of a log-concave posterior distribution with gaussian prior, in the high-dimensional limit where the number of samples and the covariates' dimension are large and proportional. Although the high-dimensional analysis of Bayesian estimators has been previousl… ▽ More In this paper we analyze, for a model of linear regression with gaussian covariates, the performance of a Bayesian estimator given by the mean of a log-concave posterior distribution with gaussian prior, in the high-dimensional limit where the number of samples and the covariates' dimension are large and proportional. Although the high-dimensional analysis of Bayesian estimators has been previously studied for Bayesian-optimal linear regression where the correct posterior is used for inference, much less is known when there is a mismatch. Here we consider a model in which the responses are corrupted by gaussian noise and are known to be generated as linear combinations of the covariates, but the distributions of the ground-truth regression coefficients and of the noise are unknown. This regression task can be rephrased as a statistical mechanics model known as the Gardner spin glass, an analogy which we exploit. Using a leave-one-out approach we characterize the mean-square error for the regression coefficients. We also derive the log-normalizing constant of the posterior. Similar models have been studied by Shcherbina and Tirozzi and by Talagrand, but our arguments are much more straightforward. An interesting consequence of our analysis is that in the quadratic loss case, the performance of the Bayesian estimator is independent of a global "temperature" hyperparameter and matches the ridge estimator: sampling and optimizing are equally good. △ Less

Submitted 10 November, 2021; v1 submitted 14 July, 2021; originally announced July 2021.

Strong replica symmetry for high-dimensional disordered log-concave Gibbs measures

Authors: Jean Barbier, Dmitry Panchenko, Manuel Sáenz

Abstract: We consider a generic class of log-concave, possibly random, (Gibbs) measures. We prove the concentration of an infinite family of order parameters called multioverlaps. Because they completely parametrise the quenched Gibbs measure of the system, this implies a simple representation of the asymptotic Gibbs measures, as well as the decoupling of the variables in a strong sense. These results may p… ▽ More We consider a generic class of log-concave, possibly random, (Gibbs) measures. We prove the concentration of an infinite family of order parameters called multioverlaps. Because they completely parametrise the quenched Gibbs measure of the system, this implies a simple representation of the asymptotic Gibbs measures, as well as the decoupling of the variables in a strong sense. These results may prove themselves useful in several contexts. In particular in machine learning and high-dimensional inference, log-concave measures appear in convex empirical risk minimisation, maximum a-posteriori inference or M-estimation. We believe that they may be applicable in establishing some type of "replica symmetric formulas" for the free energy, inference or generalisation error in such settings. △ Less

Submitted 22 February, 2022; v1 submitted 27 September, 2020; originally announced September 2020.

Journal ref: Inf. Inference, 11, no. 3 (2022) 1079-1108

Strong replica symmetry in high-dimensional optimal Bayesian inference

Authors: Jean Barbier, Dmitry Panchenko

Abstract: We consider generic optimal Bayesian inference, namely, models of signal reconstruction where the posterior distribution and all hyperparameters are known. Under a standard assumption on the concentration of the free energy, we show how replica symmetry in the strong sense of concentration of all multioverlaps can be established as a consequence of the Franz-de Sanctis identities; the identities t… ▽ More We consider generic optimal Bayesian inference, namely, models of signal reconstruction where the posterior distribution and all hyperparameters are known. Under a standard assumption on the concentration of the free energy, we show how replica symmetry in the strong sense of concentration of all multioverlaps can be established as a consequence of the Franz-de Sanctis identities; the identities themselves in the current setting are obtained via a novel perturbation coming from exponentially distributed "side-observations" of the signal. Concentration of multioverlaps means that asymptotically the posterior distribution has a particularly simple structure encoded by a random probability measure (or, in the case of binary signal, a non-random probability measure). We believe that such strong control of the model should be key in the study of inference problems with underlying sparse graphical structure (error correcting codes, block models, etc) and, in particular, in the rigorous derivation of replica symmetric formulas for the free energy and mutual information in this context. △ Less

Submitted 22 February, 2022; v1 submitted 6 May, 2020; originally announced May 2020.

Journal ref: Communications in Mathematical Physics 393, no. 3 (2022) 1199-1239

Extending the Parisi formula along a Hamilton-Jacobi equation

Authors: Jean-Christophe Mourrat, Dmitry Panchenko

Abstract: We study the free energy of mixed $p$-spin spin glass models enriched with an additional magnetic field given by the canonical Gaussian field associated with a Ruelle probability cascade. We prove that this free energy converges to the Hopf-Lax solution of a certain Hamilton-Jacobi equation. Using this result, we give a new representation of the free energy of mixed $p$-spin models with soft spins… ▽ More We study the free energy of mixed $p$-spin spin glass models enriched with an additional magnetic field given by the canonical Gaussian field associated with a Ruelle probability cascade. We prove that this free energy converges to the Hopf-Lax solution of a certain Hamilton-Jacobi equation. Using this result, we give a new representation of the free energy of mixed $p$-spin models with soft spins. △ Less

Submitted 9 November, 2019; v1 submitted 31 October, 2019; originally announced October 2019.

Comments: 16 pages

MSC Class: 82B44; 82D30; 60G15; 60F10

Journal ref: Electron. J. Probab. 25 (23), 1-17 (2020)

The generalized TAP free energy II

Authors: Wei-Kuo Chen, Dmitry Panchenko, Eliran Subag

Abstract: In a recent paper [14], we developed the generalized TAP approach for mixed $p$-spin models with Ising spins at positive temperature. Here we extend these results in two directions. We find a simplified representation for the energy of the generalized TAP states in terms of the Parisi measure of the model and, in particular, show that the energy of all states at a given distance from the origin is… ▽ More In a recent paper [14], we developed the generalized TAP approach for mixed $p$-spin models with Ising spins at positive temperature. Here we extend these results in two directions. We find a simplified representation for the energy of the generalized TAP states in terms of the Parisi measure of the model and, in particular, show that the energy of all states at a given distance from the origin is the same. Furthermore, we prove the analogues of the positive temperature results at zero temperature, which concern the ground-state energy and the organization of ground-state configurations in space. △ Less

Submitted 3 March, 2019; originally announced March 2019.

Comments: 28 pages

MSC Class: 60F10; 60G15; 60K35; 82B44

Journal ref: Commun. Math. Phys., 381, no. 1 (2021) 257--291

The generalized TAP free energy

Authors: Wei-Kuo Chen, Dmitry Panchenko, Eliran Subag

Abstract: We consider the mixed $p$-spin mean-field spin glass model with Ising spins and investigate its free energy in the spirit of the TAP approach, named after Thouless, Anderson, and Palmer. More precisely, we define and compute the generalized TAP correction, and establish the corresponding generalized TAP representation for the free energy. In connection with physicists' replica theory, we introduce… ▽ More We consider the mixed $p$-spin mean-field spin glass model with Ising spins and investigate its free energy in the spirit of the TAP approach, named after Thouless, Anderson, and Palmer. More precisely, we define and compute the generalized TAP correction, and establish the corresponding generalized TAP representation for the free energy. In connection with physicists' replica theory, we introduce the notion of generalized TAP states, which are the maximizers of the generalized TAP free energy, and show that their order parameters match the order parameter of the ancestor states in the Parisi ansatz. We compute the critical point equations of the TAP free energy that generalize the classical TAP equations for pure states. Furthermore, we give an exact description of the region where the generalized TAP correction is replica symmetric, in which case it coincides with the classical TAP correction, and show that Plefka's condition is necessary for this to happen. In particular, our result shows that the generalized TAP correction is not always replica symmetric on the points corresponding to the Edwards-Anderson parameter. △ Less

Submitted 19 October, 2020; v1 submitted 12 December, 2018; originally announced December 2018.

MSC Class: 60F10; 60G15; 60K35; 82B44

Journal ref: Pure and Applied Mathematics 76 (7), 1329-1415 (2023)

On the TAP free energy in the mixed $p$-spin models

Authors: Wei-Kuo Chen, Dmitry Panchenko

Abstract: In [Physical Magazine, 35(3):593-601, 1977], Thouless, Anderson, and Palmer derived a representation for the free energy of the Sherrington-Kirkpatrick model, called the TAP free energy, written as the difference of the energy and entropy on the extended configuration space of local magnetizations with an Onsager correction term. In the setting of mixed $p$-spin models with Ising spins, we prove t… ▽ More In [Physical Magazine, 35(3):593-601, 1977], Thouless, Anderson, and Palmer derived a representation for the free energy of the Sherrington-Kirkpatrick model, called the TAP free energy, written as the difference of the energy and entropy on the extended configuration space of local magnetizations with an Onsager correction term. In the setting of mixed $p$-spin models with Ising spins, we prove that the free energy can indeed be written as the supremum of the TAP free energy over the space of local magnetizations whose Edwards-Anderson order parameter (self-overlap) is to the right of the support of the Parisi measure. Furthermore, for generic mixed $p$-spin models, we prove that the free energy is equal to the TAP free energy evaluated on the local magnetization of any pure state. △ Less

Submitted 12 January, 2019; v1 submitted 11 September, 2017; originally announced September 2017.

MSC Class: 60K35; 60G15; 60F10; 82B44

Journal ref: Comm. Math. Phys., 362 no. 1 (2018) 219-252

Suboptimality of local algorithms for a class of max-cut problems

Authors: Wei-Kuo Chen, David Gamarnik, Dmitry Panchenko, Mustazee Rahman

Abstract: We show that in random $K$-uniform hypergraphs of constant average degree, for even $K \geq 4$, local algorithms defined as factors of i.i.d. can not find nearly maximal cuts, when the average degree is sufficiently large. These algorithms have been used frequently to obtain lower bounds for the max-cut problem on random graphs, but it was not known whether they could be successful in finding near… ▽ More We show that in random $K$-uniform hypergraphs of constant average degree, for even $K \geq 4$, local algorithms defined as factors of i.i.d. can not find nearly maximal cuts, when the average degree is sufficiently large. These algorithms have been used frequently to obtain lower bounds for the max-cut problem on random graphs, but it was not known whether they could be successful in finding nearly maximal cuts. This result follows from the fact that the overlap of any two nearly maximal cuts in such hypergraphs does not take values in a certain non-trivial interval - a phenomenon referred to as the overlap gap property - which is proved by comparing diluted models with large average degree with appropriate fully connected spin glass models and showing the overlap gap property in the latter setting. △ Less

Submitted 8 August, 2018; v1 submitted 17 July, 2017; originally announced July 2017.

Comments: Final version; to appear in Ann. Probab

Journal ref: Annals of Probability 2019, Vol. 47, No. 3, 1587-1618

Disorder chaos in some diluted spin glass models

Authors: Wei-Kuo Chen, Dmitry Panchenko

Abstract: We prove disorder chaos at zero temperature for three types of diluted models with large connectivity parameter: $K$-spin antiferromagnetic Ising model for even $K\geq 2$, $K$-spin spin glass model for even $K\geq 2$, and random $K$-sat model for all $K\geq 2$. We show that modifying even a small proportion of clauses results in near maximizers of the original and modified Hamiltonians being nearl… ▽ More We prove disorder chaos at zero temperature for three types of diluted models with large connectivity parameter: $K$-spin antiferromagnetic Ising model for even $K\geq 2$, $K$-spin spin glass model for even $K\geq 2$, and random $K$-sat model for all $K\geq 2$. We show that modifying even a small proportion of clauses results in near maximizers of the original and modified Hamiltonians being nearly orthogonal to each other with high probability. We use a standard technique of approximating diluted models by appropriate fully connected models and then apply disorder chaos results in this setting, which include both previously known results as well as new examples motivated by the random $K$-sat model. △ Less

Submitted 21 March, 2017; originally announced March 2017.

MSC Class: 60F10; 60G15; 60K35; 82B44

Journal ref: Annals of Applied Probability, 28 no. 3 (2018) 1356-1378

On the $K$-sat model with large number of clauses

Authors: Dmitry Panchenko

Abstract: We show that in the $K$-sat model with $N$ variables and $αN$ clauses, the expected ratio of the smallest number of unsatisfied clauses to the number of variables is $α/2^K - \sqrtα c_*(N)/2^K$ up to smaller order terms $o(\sqrtα)$ as $α\to\infty$ uniformly in $N$, where $c_*(N)$ is the expected normalized maximum energy of some specific mixed $p$-spin spin glass model. The formula for the limit o… ▽ More We show that in the $K$-sat model with $N$ variables and $αN$ clauses, the expected ratio of the smallest number of unsatisfied clauses to the number of variables is $α/2^K - \sqrtα c_*(N)/2^K$ up to smaller order terms $o(\sqrtα)$ as $α\to\infty$ uniformly in $N$, where $c_*(N)$ is the expected normalized maximum energy of some specific mixed $p$-spin spin glass model. The formula for the limit of $c_*(N)$ is well known in the theory of spin glasses. △ Less

Submitted 1 April, 2017; v1 submitted 22 August, 2016; originally announced August 2016.

MSC Class: 60F10; 60G15; 60K35; 82B44

Journal ref: Random Structures and Algorithms, 52 no. 3 (2018) 536-542

Temperature chaos in some spherical mixed $p$-spin models

Authors: Wei-Kuo Chen, Dmitry Panchenko

Abstract: We give two types of examples of the spherical mixed even-$p$-spin models for which chaos in temperature holds. These complement some known results for the spherical pure $p$-spin models and for models with Ising spins. For example, in contrast to a recent result of Subag who showed absence of chaos in temperature in the spherical pure $p$-spin models for $p\geq 3$, we show that even a smaller ord… ▽ More We give two types of examples of the spherical mixed even-$p$-spin models for which chaos in temperature holds. These complement some known results for the spherical pure $p$-spin models and for models with Ising spins. For example, in contrast to a recent result of Subag who showed absence of chaos in temperature in the spherical pure $p$-spin models for $p\geq 3$, we show that even a smaller order perturbation induces temperature chaos. △ Less

Submitted 18 December, 2016; v1 submitted 8 August, 2016; originally announced August 2016.

Comments: 14 pages, Minor revision

MSC Class: 60K35; 60G15; 60F10; 82B44

Journal ref: Journal of Statistical Physics, 166 no. 5 (2017) 1151-1162

Free energy in the mixed p-spin models with vector spins

Authors: Dmitry Panchenko

Abstract: Using the synchronization mechanism developed in the previous work on the Potts spin glass model, arXiv:1512.00370, we obtain the analogue of the Parisi formula for the free energy in the mixed even $p$-spin models with vector spins, which include the Sherrington-Kirkpatrick model with vector spins interacting through their scalar product. As a special case, this also establishes the sharpness of… ▽ More Using the synchronization mechanism developed in the previous work on the Potts spin glass model, arXiv:1512.00370, we obtain the analogue of the Parisi formula for the free energy in the mixed even $p$-spin models with vector spins, which include the Sherrington-Kirkpatrick model with vector spins interacting through their scalar product. As a special case, this also establishes the sharpness of Talagrand's upper bound for the free energy of multiple mixed $p$-spin systems coupled by constraining their overlaps. △ Less

Submitted 27 December, 2015; v1 submitted 14 December, 2015; originally announced December 2015.

MSC Class: 60F10; 60G15; 60K35; 82B44

Journal ref: Annals of Probability, 46 no. 2 (2018) 865-896

Free energy in the Potts spin glass

Authors: Dmitry Panchenko

Abstract: We study the Potts spin glass model, which generalizes the Sherrington-Kirkpatrick model to the case when spins take more than two values but their interactions are counted only if the spins are equal. We obtain the analogue of the Parisi variational formula for the free energy, with the order parameter now given by a monotone path in the set of positive-semidefinite matrices. The main idea of the… ▽ More We study the Potts spin glass model, which generalizes the Sherrington-Kirkpatrick model to the case when spins take more than two values but their interactions are counted only if the spins are equal. We obtain the analogue of the Parisi variational formula for the free energy, with the order parameter now given by a monotone path in the set of positive-semidefinite matrices. The main idea of the paper is a novel synchronization mechanism for blocks of overlaps. This mechanism can be used to solve a more general version of the Sherrington-Kirkpatrick model with vector spins interacting through their scalar product, which includes the Potts spin glass as a special case. As another example of application, one can show that Talagrand's bound for multiple copies of the mixed $p$-spin model with constrained overlaps is asymptotically sharp. We consider these problems in the subsequent paper, arXiv:1512.04441, and illustrate the main new idea on the technically more transparent case of the Potts spin glass. △ Less

Submitted 11 November, 2016; v1 submitted 1 December, 2015; originally announced December 2015.

MSC Class: 60K35; 60G15; 60F10; 82B44

Journal ref: Annals of Probability, 46 no. 2 (2018) 829-864

Fluctuations of the free energy in the mixed $p$-spin models with external field

Authors: Wei-Kuo Chen, Partha Dey, Dmitry Panchenko

Abstract: We show that the free energy in the mixed $p$-spin models of spin glasses does not superconcentrate in the presence of external field, which means that its variance is of the order suggested by the Poincaré inequality. This complements the result of Chatterjee who showed that the free energy superconcentrates when there is no external field. For models without odd $p$-spin interactions for… ▽ More We show that the free energy in the mixed $p$-spin models of spin glasses does not superconcentrate in the presence of external field, which means that its variance is of the order suggested by the Poincaré inequality. This complements the result of Chatterjee who showed that the free energy superconcentrates when there is no external field. For models without odd $p$-spin interactions for $p\geq 3$, we prove the central limit theorem for the free energy at any temperature and give an explicit formula for the limiting variance. Although we only deal with the case of Ising spins, all our results can be extended to the spherical models as well. △ Less

Submitted 3 November, 2015; v1 submitted 23 September, 2015; originally announced September 2015.

Comments: Version 2: 12 pages, new co-author, new title and new results

MSC Class: 60K35; 82B44

Journal ref: Probab. Theory Related Fields 168, no. 1-2, 41-53 (2017)

Chaos in temperature in generic 2p-spin models

Authors: Dmitry Panchenko

Abstract: We prove chaos in temperature for even $p$-spin models which include sufficiently many $p$-spin interaction terms. Our approach is based on a new invariance property for coupled asymptotic Gibbs measures, similar in spirit to the invariance property that appeared in the proof of ultrametricity in arXiv:1112.1003, used in combination with Talagrand's analogue of Guerra's replica symmetry breaking b… ▽ More We prove chaos in temperature for even $p$-spin models which include sufficiently many $p$-spin interaction terms. Our approach is based on a new invariance property for coupled asymptotic Gibbs measures, similar in spirit to the invariance property that appeared in the proof of ultrametricity in arXiv:1112.1003, used in combination with Talagrand's analogue of Guerra's replica symmetry breaking bound for coupled systems. △ Less

Submitted 12 December, 2023; v1 submitted 12 February, 2015; originally announced February 2015.

MSC Class: 60K35; 60G09; 82B44

Journal ref: Commun. Math. Phys. 346, no. 2, 703-739 (2016)

Introduction to the SK model

Authors: Dmitry Panchenko

Abstract: This is a review paper for the "Current Developments in Mathematics 2014" conference. This is a review paper for the "Current Developments in Mathematics 2014" conference. △ Less

Submitted 29 November, 2014; originally announced December 2014.

Journal ref: Current Developments in Mathematics 2014, no. 1, 231-291 (2016)

Some examples of quenched self-averaging in models with Gaussian disorder

Authors: Wei-Kuo Chen, Dmitry Panchenko

Abstract: In this paper we give an elementary approach to several results of Chatterjee in arXiv:0907.3381 and arXiv:1404.7178, as well as some generalizations. First, we prove quenched disorder chaos for the bond overlap in the Edwards-Anderson type models with Gaussian disorder. The proof extends to systems at different temperatures and covers a number of other models, such as the mixed $p$-spin model, Sh… ▽ More In this paper we give an elementary approach to several results of Chatterjee in arXiv:0907.3381 and arXiv:1404.7178, as well as some generalizations. First, we prove quenched disorder chaos for the bond overlap in the Edwards-Anderson type models with Gaussian disorder. The proof extends to systems at different temperatures and covers a number of other models, such as the mixed $p$-spin model, Sherrington-Kirkpatrick model with multi-dimensional spins and diluted $p$-spin model. Next, we adapt the same idea to prove quenched self-averaging of the bond magnetization for one system and use it to show quenched self-averaging of the site overlap for random field models with positively correlated spins. Finally, we show self-averaging for certain modifications of the random field itself. △ Less

Submitted 7 September, 2014; originally announced September 2014.

Comments: 17 pages

MSC Class: 60K35; 82B44

Journal ref: Ann. Inst. H. Poincaré Probab. Statist., 53 no. 1 (2017) 243-258

Structure of finite-RSB asymptotic Gibbs measures in the diluted spin glass models

Authors: Dmitry Panchenko

Abstract: We suggest a possible approach to proving the Mézard-Parisi formula for the free energy in the diluted spin glass models, such as diluted K-spin or random K-sat model at any positive temperature. In the main contribution of the paper, we show that a certain small modification of the Hamiltonian in any of these models forces all finite-RSB asymptotic Gibbs measures in the sense of the overlaps to s… ▽ More We suggest a possible approach to proving the Mézard-Parisi formula for the free energy in the diluted spin glass models, such as diluted K-spin or random K-sat model at any positive temperature. In the main contribution of the paper, we show that a certain small modification of the Hamiltonian in any of these models forces all finite-RSB asymptotic Gibbs measures in the sense of the overlaps to satisfy the Mézard-Parisi ansatz for the distribution of spins. Unfortunately, what is still missing is a description of the general full-RSB asymptotic Gibbs measures. If one could show that the general case can be approximated by finite-RSB case in the right sense then one could a posteriori remove the small modification of the Hamiltonian to recover the Mézard-Parisi formula for the original model. △ Less

Submitted 24 February, 2015; v1 submitted 18 June, 2014; originally announced June 2014.

MSC Class: 60K35; 60G09; 82B44

Journal ref: Journal of Statistical Physics 162, no. 1 (2016) 1-42

The free energy in a multi-species Sherrington-Kirkpatrick model

Authors: Dmitry Panchenko

Abstract: The authors of [Ann. Henri Poincaré 16 (2015) 691-708] introduced a multi-species version of the Sherrington-Kirkpatrick model and suggested the analogue of the Parisi formula for the free energy. Using a variant of Guerra's replica symmetry breaking interpolation, they showed that, under certain assumption on the interactions, the formula gives an upper bound on the limit of the free energy. In t… ▽ More The authors of [Ann. Henri Poincaré 16 (2015) 691-708] introduced a multi-species version of the Sherrington-Kirkpatrick model and suggested the analogue of the Parisi formula for the free energy. Using a variant of Guerra's replica symmetry breaking interpolation, they showed that, under certain assumption on the interactions, the formula gives an upper bound on the limit of the free energy. In this paper we prove that the bound is sharp. This is achieved by developing a new multi-species form of the Ghirlanda-Guerra identities and showing that they force the overlaps within species to be completely determined by the overlaps of the whole system. △ Less

Submitted 22 December, 2015; v1 submitted 24 October, 2013; originally announced October 2013.

Comments: Published at http://dx.doi.org/10.1214/14-AOP967 in the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

Report number: IMS-AOP-AOP967

Journal ref: Annals of Probability 2015, Vol. 43, No. 6, 3494-3513

Structure of 1-RSB asymptotic Gibbs measures in the diluted p-spin models

Authors: Dmitry Panchenko

Abstract: In this paper we study asymptotic Gibbs measures in the diluted p-spin models in the so called 1-RSB case, when the overlap takes two values $q_*, q^*\in [0,1].$ When the external field is not present and the overlap is not equal to zero, we prove that such asymptotic Gibbs measures are described by the Mézard-Parisi ansatz conjectured in [MP]. When the external field is present, we prove that the… ▽ More In this paper we study asymptotic Gibbs measures in the diluted p-spin models in the so called 1-RSB case, when the overlap takes two values $q_*, q^*\in [0,1].$ When the external field is not present and the overlap is not equal to zero, we prove that such asymptotic Gibbs measures are described by the Mézard-Parisi ansatz conjectured in [MP]. When the external field is present, we prove that the overlap can not be equal to zero and all 1-RSB asymptotic Gibbs measures are described by the Mézard-Parisi ansatz. Finally, we give a characterization of the exceptional case when there is no external field and the smallest overlap value is equal to zero, although it does not go as far as the Mézard-Parisi ansatz. Our approach is based on the cavity computations combined with the hierarchical exchangeability of pure states. △ Less

Submitted 8 August, 2013; originally announced August 2013.

MSC Class: 60K35; 60G09; 82B44

Journal ref: Journal of Statistical Physics: Volume 155, Issue 1 (2014), pp. 1-22

Hierarchical exchangeability of pure states in mean field spin glass models

Authors: Dmitry Panchenko

Abstract: The main result in this paper is motivated by the Mézard-Parisi ansatz which predicts a very special structure for the distribution of spins in diluted mean field spin glass models, such as the random K-sat model. Using the fact that one can safely assume the validity of the Ghirlanda-Guerra identities in these models, we prove hierarchical exchangeability of pure states for the asymptotic Gibbs m… ▽ More The main result in this paper is motivated by the Mézard-Parisi ansatz which predicts a very special structure for the distribution of spins in diluted mean field spin glass models, such as the random K-sat model. Using the fact that one can safely assume the validity of the Ghirlanda-Guerra identities in these models, we prove hierarchical exchangeability of pure states for the asymptotic Gibbs measures, which allows us to apply a representation result for hierarchically exchangeable arrays recently proved in arXiv:1301.1259. Comparing this representation with the predictions of the Mézard-Parisi ansatz, one can see that the key property still missing is that the multi-overlaps between pure states depend only on their overlaps. △ Less

Submitted 8 July, 2013; originally announced July 2013.

MSC Class: 60K35; 60G09; 82B44

Journal ref: Probability Theory and Related Fields, 161 no. 3 (2015) 619-650

On the replica symmetric solution of the K-sat model

Authors: Dmitry Panchenko

Abstract: In this paper we translate Talagrand's solution of the K-sat model at high temperature into the language of asymptotic Gibbs measures. Using exact cavity equations in the infinite volume limit allows us to remove many technicalities of the inductions on the system size, which clarifies the main ideas of the proof. This approach also yields a larger region of parameters where the system is in a pur… ▽ More In this paper we translate Talagrand's solution of the K-sat model at high temperature into the language of asymptotic Gibbs measures. Using exact cavity equations in the infinite volume limit allows us to remove many technicalities of the inductions on the system size, which clarifies the main ideas of the proof. This approach also yields a larger region of parameters where the system is in a pure state and, in particular, for small connectivity parameter we prove the replica symmetric formula for the free energy at any temperature. △ Less

Submitted 22 April, 2013; originally announced April 2013.

MSC Class: 60K35; 82B44

Journal ref: Electron. J. Probab. 19 (2014), no. 67, 1-17

A hierarchical version of the de Finetti and Aldous-Hoover representations

Authors: Tim Austin, Dmitry Panchenko

Abstract: We consider random arrays indexed by the leaves of an infinitary rooted tree of finite depth, with the distribution invariant under the rearrangements that preserve the tree structure. We call such arrays hierarchically exchangeable and prove that they satisfy an analogue of de Finetti's theorem. We also prove a more general result for arrays indexed by several trees, which includes a hierarchical… ▽ More We consider random arrays indexed by the leaves of an infinitary rooted tree of finite depth, with the distribution invariant under the rearrangements that preserve the tree structure. We call such arrays hierarchically exchangeable and prove that they satisfy an analogue of de Finetti's theorem. We also prove a more general result for arrays indexed by several trees, which includes a hierarchical version of the Aldous-Hoover representation. △ Less

Submitted 21 July, 2013; v1 submitted 7 January, 2013; originally announced January 2013.

Comments: v2: new coauthor and new proof of a more general result; v4: some minor changes

MSC Class: 60G09; 60K35

Journal ref: Probability Theory and Related Fields 159 no. 3 (2014) 809-823

The Sherrington-Kirkpatrick model: an overview

Authors: Dmitry Panchenko

Abstract: The goal of this paper is to review some of the main ideas that emerged from the attempts to confirm mathematically the predictions of the celebrated Parisi ansatz in the Sherrington-Kirkpatrick model. We try to focus on the big picture while sketching the proofs of only a few selected results, but an interested reader can find most of the missing details in [31] and [44]. The goal of this paper is to review some of the main ideas that emerged from the attempts to confirm mathematically the predictions of the celebrated Parisi ansatz in the Sherrington-Kirkpatrick model. We try to focus on the big picture while sketching the proofs of only a few selected results, but an interested reader can find most of the missing details in [31] and [44]. △ Less

Submitted 5 November, 2012; originally announced November 2012.

Comments: This is an overview article for the Journal of Statistical Physics

MSC Class: 60K35; 82B44

Journal ref: J. Stat. Phys. 149 no. 2 (2012) 362-383

An approach to chaos in some mixed p-spin models

Authors: Wei-Kuo Chen, Dmitry Panchenko

Abstract: We consider the problems of chaos in disorder and temperature for coupled copies of the mixed p-spin models. Under certain assumptions on the parameters of the models we will first prove a weak form of chaos by showing that the overlap is concentrated around its Gibbs average depending on the disorder and then obtain several results toward strong chaos by providing control of the overlap between t… ▽ More We consider the problems of chaos in disorder and temperature for coupled copies of the mixed p-spin models. Under certain assumptions on the parameters of the models we will first prove a weak form of chaos by showing that the overlap is concentrated around its Gibbs average depending on the disorder and then obtain several results toward strong chaos by providing control of the overlap between two systems in terms of their Parisi measures. △ Less

Submitted 10 January, 2012; originally announced January 2012.

Comments: 14 pages

MSC Class: 60K35; 82B44

Journal ref: Probab. Theory Related Fields 157 (2013), no. 1-2, 389-404

The Parisi formula for mixed $p$-spin models

Authors: Dmitry Panchenko

Abstract: The Parisi formula for the free energy in the Sherrington-Kirkpatrick and mixed $p$-spin models for even $p\geq2$ was proved in the seminal work of Michel Talagrand [Ann. of Math. (2) 163 (2006) 221-263]. In this paper we prove the Parisi formula for general mixed $p$-spin models which also include $p$-spin interactions for odd $p$. Most of the ideas used in the paper are well known and can now be… ▽ More The Parisi formula for the free energy in the Sherrington-Kirkpatrick and mixed $p$-spin models for even $p\geq2$ was proved in the seminal work of Michel Talagrand [Ann. of Math. (2) 163 (2006) 221-263]. In this paper we prove the Parisi formula for general mixed $p$-spin models which also include $p$-spin interactions for odd $p$. Most of the ideas used in the paper are well known and can now be combined following a recent proof of the Parisi ultrametricity conjecture in [Ann. of Math. (2) 177 (2013) 383-393]. △ Less

Submitted 31 March, 2014; v1 submitted 19 December, 2011; originally announced December 2011.

Comments: Published in at http://dx.doi.org/10.1214/12-AOP800 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

Report number: IMS-AOP-AOP800

Journal ref: Annals of Probability 2014, Vol. 42, No. 3, 946-958

The Parisi ultrametricity conjecture

Authors: Dmitry Panchenko

Abstract: In this paper we prove that the support of a random measure on the unit ball of a separable Hilbert space that satisfies the Ghirlanda-Guerra identities must be ultrametric with probability one. This implies the Parisi ultrametricity conjecture in mean-field spin glass models, such as the Sherrington-Kirkpatrick and mixed $p$-spin models, for which Gibbs' measures are known to satisfy the Ghirland… ▽ More In this paper we prove that the support of a random measure on the unit ball of a separable Hilbert space that satisfies the Ghirlanda-Guerra identities must be ultrametric with probability one. This implies the Parisi ultrametricity conjecture in mean-field spin glass models, such as the Sherrington-Kirkpatrick and mixed $p$-spin models, for which Gibbs' measures are known to satisfy the Ghirlanda-Guerra identities in the thermodynamic limit. △ Less

Submitted 1 March, 2015; v1 submitted 5 December, 2011; originally announced December 2011.

Comments: arXiv admin note: text overlap with arXiv:1108.0379

MSC Class: 60K35; 82B44

Journal ref: Ann. of Math. (2), Vol. 177, No. 1 (2013) 383-393

A new representation of the Ghirlanda-Guerra identities with applications

Authors: Dmitry Panchenko

Abstract: In this paper we obtain a new family of identities for random measures on the unit ball of a separable Hilbert space which arise as the asymptotic analogues of the Gibbs measures in the Sherrington-Kirkpatrick and $p$-spin models and which are known to satisfy the Ghirlanda-Guerra identities. We give several applications of the new identities to structural results for such measures. In this paper we obtain a new family of identities for random measures on the unit ball of a separable Hilbert space which arise as the asymptotic analogues of the Gibbs measures in the Sherrington-Kirkpatrick and $p$-spin models and which are known to satisfy the Ghirlanda-Guerra identities. We give several applications of the new identities to structural results for such measures. △ Less

Submitted 29 November, 2011; v1 submitted 1 August, 2011; originally announced August 2011.

MSC Class: 60K35; 82B44

Ghirlanda-Guerra identities and ultrametricity: An elementary proof in the discrete case

Authors: Dmitry Panchenko

Abstract: In this paper we give another proof of the fact that a random overlap array, which satisfies the Ghirlanda-Guerra identities and whose elements take values in a finite set, is ultrametric with probability one. The new proof bypasses random change of density invariance principles for directing measures of such arrays and, in addition to the Dobvysh-Sudakov representation, is based only on elementar… ▽ More In this paper we give another proof of the fact that a random overlap array, which satisfies the Ghirlanda-Guerra identities and whose elements take values in a finite set, is ultrametric with probability one. The new proof bypasses random change of density invariance principles for directing measures of such arrays and, in addition to the Dobvysh-Sudakov representation, is based only on elementary algebraic consequences of the Ghirlanda-Guerra identities. △ Less

Submitted 20 June, 2011; originally announced June 2011.

MSC Class: 60K35; 82B44

Journal ref: C. R. Acad. Sci. Paris, Ser. I {349} (2011) 813-816

A unified stability property in spin glasses

Authors: Dmitry Panchenko

Abstract: Gibbs' measures in the Sherrington-Kirkpatrick type models satisfy two asymptotic stability properties, the Aizenman-Contucci stochastic stability and the Ghirlanda-Guerra identities, which play a fundamental role in our current understanding of these models. In this paper we show that one can combine these two properties very naturally into one unified stability property. Gibbs' measures in the Sherrington-Kirkpatrick type models satisfy two asymptotic stability properties, the Aizenman-Contucci stochastic stability and the Ghirlanda-Guerra identities, which play a fundamental role in our current understanding of these models. In this paper we show that one can combine these two properties very naturally into one unified stability property. △ Less

Submitted 2 November, 2011; v1 submitted 20 June, 2011; originally announced June 2011.

MSC Class: 60K35; 82B44

Journal ref: Comm. Math. Phys., Vol. 313 No. 3 (2012) 781-790

A deletion-invariance property for random measures satisfying the Ghirlanda-Guerra identities

Authors: Dmitry Panchenko

Abstract: We show that if a discrete random measure on the unit ball of a separable Hilbert space satisfies the Ghirlanda-Guerra identities then by randomly deleting half of the points and renormalizing the weights of the remaining points we obtain the same random measure in distribution up to rotations. We show that if a discrete random measure on the unit ball of a separable Hilbert space satisfies the Ghirlanda-Guerra identities then by randomly deleting half of the points and renormalizing the weights of the remaining points we obtain the same random measure in distribution up to rotations. △ Less

Submitted 30 May, 2011; originally announced May 2011.

MSC Class: 60K35; 82B44

Journal ref: C. R. Acad. Sci. Paris, Ser. I 349 (2011) 579-581

Spin glass models from the point of view of spin distributions

Authors: Dmitry Panchenko

Abstract: In many spin glass models, due to the symmetry among sites, any limiting joint distribution of spins under the annealed Gibbs measure admits the Aldous-Hoover representation encoded by a function $σ:[0,1]^4\to\{-1,+1\}$, and one can think of this function as a generic functional order parameter of the model. In a class of diluted models, and in the Sherrington-Kirkpatrick model, we introduce novel… ▽ More In many spin glass models, due to the symmetry among sites, any limiting joint distribution of spins under the annealed Gibbs measure admits the Aldous-Hoover representation encoded by a function $σ:[0,1]^4\to\{-1,+1\}$, and one can think of this function as a generic functional order parameter of the model. In a class of diluted models, and in the Sherrington-Kirkpatrick model, we introduce novel perturbations of the Hamiltonian that yield certain invariance and self-consistency equations for this generic functional order parameter and we use these invariance properties to obtain representations for the free energy in terms of $σ$. In the setting of the Sherrington-Kirkpatrick model, the self-consistency equations imply that the joint distribution of spins is determined by the joint distributions of the overlaps, and we give an explicit formula for $σ$ under the Parisi ultrametricity hypothesis. In addition, we discuss some connections with the Ghirlanda-Guerra identities and stochastic stability and describe the expected Parisi ansatz in the diluted models in terms of $σ$. △ Less

Submitted 24 May, 2013; v1 submitted 15 May, 2010; originally announced May 2010.

Comments: Published in at http://dx.doi.org/10.1214/11-AOP696 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

Report number: IMS-AOP-AOP696

Journal ref: Annals of Probability 2013, Vol. 41, No. 3A, 1315-1361

The Ghirlanda-Guerra identities for mixed p-spin model

Authors: Dmitry Panchenko

Abstract: We show that, under the conditions known to imply the validity of the Parisi formula, if the generic Sherrington-Kirkpatrick Hamiltonian contains a $p$-spin term then the Ghirlanda-Guerra identities for the $p$th power of the overlap hold in a strong sense without averaging. This implies strong version of the extended Ghirlanda-Guerra identities for mixed $p$-spin models than contain terms for a… ▽ More We show that, under the conditions known to imply the validity of the Parisi formula, if the generic Sherrington-Kirkpatrick Hamiltonian contains a $p$-spin term then the Ghirlanda-Guerra identities for the $p$th power of the overlap hold in a strong sense without averaging. This implies strong version of the extended Ghirlanda-Guerra identities for mixed $p$-spin models than contain terms for all even $p\geq 2$ and $p=1.$ △ Less

Submitted 10 February, 2010; originally announced February 2010.

MSC Class: 60K35; 82B44

Journal ref: C.R.Acad.Sci.Paris, Ser. I 348 (2010) 189-192.

On the Dovbysh-Sudakov representation result

Authors: Dmitry Panchenko

Abstract: We present a detailed proof of the Dovbysh-Sudakov representation for symmetric positive definite weakly exchangeable infinite random arrays, called Gram-de Finetti matrices, which is based on the representation result of Aldous and Hoover for arbitrary (not necessarily positive definite) symmetric weakly exchangeable arrays. We present a detailed proof of the Dovbysh-Sudakov representation for symmetric positive definite weakly exchangeable infinite random arrays, called Gram-de Finetti matrices, which is based on the representation result of Aldous and Hoover for arbitrary (not necessarily positive definite) symmetric weakly exchangeable arrays. △ Less

Submitted 10 May, 2009; originally announced May 2009.

MSC Class: 60G09; 82B44

Journal ref: Vol. 15 (2010) Elect. Comm. in Probab. 330-338

A connection between the Ghirlanda--Guerra identities and ultrametricity

Authors: Dmitry Panchenko

Abstract: We consider a symmetric positive definite weakly exchangeable infinite random matrix and show that, under the technical condition that its elements take a finite number of values, the Ghirlanda--Guerra identities imply ultrametricity. We consider a symmetric positive definite weakly exchangeable infinite random matrix and show that, under the technical condition that its elements take a finite number of values, the Ghirlanda--Guerra identities imply ultrametricity. △ Less

Submitted 27 January, 2010; v1 submitted 3 October, 2008; originally announced October 2008.

Comments: Published in at http://dx.doi.org/10.1214/09-AOP484 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

Report number: IMS-AOP-AOP484 MSC Class: 60K35; 82B44 (Primary)

Journal ref: Annals of Probability 2010, Vol. 38, No. 1, 327-347

Log-concavity property of the error probability with application to local bounds for wireless communications

Authors: Andrea Conti, Dmitry Panchenko, Sergiy Sidenko, Velio Tralli

Abstract: A clear understanding the behavior of the error probability (EP) as a function of signal-to-noise ratio (SNR) and other system parameters is fundamental for assessing the design of digital wireless communication systems.We propose an analytical framework based on the log-concavity property of the EP which we prove for a wide family of multidimensional modulation formats in the presence of Gaussi… ▽ More A clear understanding the behavior of the error probability (EP) as a function of signal-to-noise ratio (SNR) and other system parameters is fundamental for assessing the design of digital wireless communication systems.We propose an analytical framework based on the log-concavity property of the EP which we prove for a wide family of multidimensional modulation formats in the presence of Gaussian disturbances and fading. Based on this property, we construct a class of local bounds for the EP that improve known generic bounds in a given region of the SNR and are invertible, as well as easily tractable for further analysis. This concept is motivated by the fact that communication systems often operate with performance in a certain region of interest (ROI) and, thus, it may be advantageous to have tighter bounds within this region instead of generic bounds valid for all SNRs. We present a possible application of these local bounds, but their relevance is beyond the example made in this paper. △ Less

Submitted 20 February, 2009; v1 submitted 6 October, 2007; originally announced October 2007.

Journal ref: IEEE Trans. Inform. Theory, 2009, vol. 55, no. 6, 2766-2775.

On differentiability of the Parisi formula

Authors: Dmitry Panchenko

Abstract: It was proved by Michel Talagrand in [10] that the Parisi formula for the free energy in the Sherrington-Kirkpatrick model is differentiable with respect to inverse temperature parameter. We present a simpler proof of this result by using approximate solutions in the Parisi formula and give one example of application of the differentiability to prove non self-averaging of the overlap outside of… ▽ More It was proved by Michel Talagrand in [10] that the Parisi formula for the free energy in the Sherrington-Kirkpatrick model is differentiable with respect to inverse temperature parameter. We present a simpler proof of this result by using approximate solutions in the Parisi formula and give one example of application of the differentiability to prove non self-averaging of the overlap outside of the replica symmetric region. △ Less

Submitted 4 May, 2008; v1 submitted 10 September, 2007; originally announced September 2007.

MSC Class: 60K35; 82B44

Journal ref: Vol. 13 (2008) Elect. Comm. in Probab. 241-247

Guerra's interpolation using Derrida-Ruelle cascades

Authors: Dmitry Panchenko, Michel Talagrand

Abstract: New results about Poisson-Dirichlet point processes and Derrida-Ruelle cascades allow us to express Guerra's interpolation entirely in the language of Derrida-Ruelle cascades and to streamline Guerra's computations. Moreover, our approach clarifies the nature of the error terms along the interpolation. New results about Poisson-Dirichlet point processes and Derrida-Ruelle cascades allow us to express Guerra's interpolation entirely in the language of Derrida-Ruelle cascades and to streamline Guerra's computations. Moreover, our approach clarifies the nature of the error terms along the interpolation. △ Less

Submitted 30 August, 2007; v1 submitted 27 August, 2007; originally announced August 2007.

Comments: v2: some minor corrections

MSC Class: 60K35; 82B44

A note on Talagrand's positivity principle

Authors: Dmitry Panchenko

Abstract: Talagrand's positivity principle states that one can slightly perturb a Hamiltonian in the Sherrington-Kirkpatrick model in such a way that the overlap of two configurations under the perturbed Gibbs' measure will become typically nonnegative. In this note we observe that abstracting from the setting of the SK model only improves the result and does not require any modifications in Talagrand's a… ▽ More Talagrand's positivity principle states that one can slightly perturb a Hamiltonian in the Sherrington-Kirkpatrick model in such a way that the overlap of two configurations under the perturbed Gibbs' measure will become typically nonnegative. In this note we observe that abstracting from the setting of the SK model only improves the result and does not require any modifications in Talagrand's argument. In this version, for example, positivity principle immediately applies to the setting of Aizenman-Sims-Starr interpolation. Also, abstracting from the SK model improves the conditions in the Ghirlanda-Guerra identities and as a consequence results in a perturbation of smaller order necessary to ensure positivity of the overlap. △ Less

Submitted 17 August, 2007; originally announced August 2007.

MSC Class: 60K35; 82B44

Journal ref: Vol. 12 (2007) Elect. Comm. in Probab. 401-410

Exponential control of overlap in the replica method for p-spin Sherrington-Kirkpatrick model

Authors: Dmitry Panchenko

Abstract: Recently, Michel Talagrand computed the large deviations limit $\lim_{N\to\infty}(Na)^{-1}\log \e Z_N^a$ for the moments of the partition function $Z_N$ in the Sherrington-Kirkpatrick model for all real $a\geq 0.$ For $a\geq 1$ the limit is given by Guerra's inverse bound and this result extends the classical physicist's replica method that corresponds to integer $a.$ We give a new proof for… ▽ More Recently, Michel Talagrand computed the large deviations limit $\lim_{N\to\infty}(Na)^{-1}\log \e Z_N^a$ for the moments of the partition function $Z_N$ in the Sherrington-Kirkpatrick model for all real $a\geq 0.$ For $a\geq 1$ the limit is given by Guerra's inverse bound and this result extends the classical physicist's replica method that corresponds to integer $a.$ We give a new proof for $a\geq 1$ in the case of the pure $p$-spin SK model that provides a strong exponential control of the overlap. △ Less

Submitted 30 January, 2007; originally announced January 2007.

MSC Class: 60K35; 82B44

Journal ref: Journal of Statistical Physics, 2008, Vol. 130, No. 5, 831-842.

On the overlap in the multiple spherical SK models

Authors: Dmitry Panchenko, Michel Talagrand

Abstract: In order to study certain questions concerning the distribution of the overlap in Sherrington--Kirkpatrick type models, such as the chaos and ultrametricity problems, it seems natural to study the free energy of multiple systems with constrained overlaps. One can write analogues of Guerra's replica symmetry breaking bound for such systems but it is not at all obvious how to choose informative fu… ▽ More In order to study certain questions concerning the distribution of the overlap in Sherrington--Kirkpatrick type models, such as the chaos and ultrametricity problems, it seems natural to study the free energy of multiple systems with constrained overlaps. One can write analogues of Guerra's replica symmetry breaking bound for such systems but it is not at all obvious how to choose informative functional order parameters in these bounds. We were able to make some progress for spherical pure $p$-spin SK models where many computations can be made explicitly. For pure 2-spin model we prove ultrametricity and chaos in an external field. For the pure $p$-spin model for even $p>4$ without an external field we describe two possible values of the overlap of two systems at different temperatures. We also prove a somewhat unexpected result which shows that in the 2-spin model the support of the joint overlap distribution is not always witnessed at the level of the free energy and, for example, ultrametricity holds only in a weak sense. △ Less

Submitted 27 November, 2007; v1 submitted 4 April, 2006; originally announced April 2006.

Comments: Published in at http://dx.doi.org/10.1214/009117907000000015 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

Report number: IMS-AOP-AOP324 MSC Class: 60K35; 82B44 (Primary)

Journal ref: Annals of Probability 2007, Vol. 35, No. 6, 2321-2355

Cavity method in the spherical Sherrington-Kirkpatrick model

Authors: Dmitry Panchenko

Abstract: We develop a cavity method in the spherical Sherrington-Kirkpatrick model at high temperature and small external field. As one application we compute the limit of the covariance matrix for fluctuations of the overlap and magnetization. We develop a cavity method in the spherical Sherrington-Kirkpatrick model at high temperature and small external field. As one application we compute the limit of the covariance matrix for fluctuations of the overlap and magnetization. △ Less

Submitted 18 August, 2007; v1 submitted 4 April, 2006; originally announced April 2006.

Comments: updated version, results rewritten for general SK type Hamiltonian

MSC Class: 60K35; 82B44

Journal ref: Ann. Inst. H. Poincare Probab. Statist. Volume 45, Number 4 (2009), 1020-1047.

A question about Parisi functional

Authors: Dmitry Panchenko

Abstract: We conjecture that the Parisi functional in the SK model is convex in the functional order parameter and prove a partial result that shows the convexity along one-sided directions. A consequence of this result is log-convexity of L_1 norm for a class or random variables. We conjecture that the Parisi functional in the SK model is convex in the functional order parameter and prove a partial result that shows the convexity along one-sided directions. A consequence of this result is log-convexity of L_1 norm for a class or random variables. △ Less

Submitted 22 December, 2004; originally announced December 2004.

Journal ref: 2005 Elect. Comm. in Probab. 10

Free energy in the generalized Sherrington-Kirkpatrick mean field model

Authors: Dmitry Panchenko

Abstract: Recently Michel Talagrand gave a rigorous proof of the Parisi formula in the Sherrington-Kirkpatrick model. In this paper we build upon the methodology developed by Talagrand and extend his result to the class of SK type models in which the spins have arbitrary prior distribution on a bounded subset of the real line. Recently Michel Talagrand gave a rigorous proof of the Parisi formula in the Sherrington-Kirkpatrick model. In this paper we build upon the methodology developed by Talagrand and extend his result to the class of SK type models in which the spins have arbitrary prior distribution on a bounded subset of the real line. △ Less

Submitted 14 June, 2005; v1 submitted 18 May, 2004; originally announced May 2004.

Comments: 60 pages

MSC Class: 60K35; 82B44

Journal ref: 2005 Rev. Math. Phys. 17 No. 7

Free energy in the Sherrington-Kirkpatrick model with constrained magnetization

Authors: Dmitry Panchenko

Abstract: This paper has been withdrawn since a trivial proof of the result has been pointed out to the author. This paper has been withdrawn since a trivial proof of the result has been pointed out to the author. △ Less

Submitted 12 October, 2004; v1 submitted 18 May, 2004; originally announced May 2004.

Comments: This paper has been withdrawn since a trivial proof of the result has been pointed out to the author

A note on the free energy of the coupled system in the Sherrington-Kirkpatrick model

Authors: Dmitry Panchenko

Abstract: In this paper we consider a system of spins that consists of two configurations $\vsi^1,\vsi^2\inΣ_N=\{-1,+1\}^N$ with Gaussian Hamiltonians $H_N^1(\vsi^1)$ and $H_N^2(\vsi^2)$ correspondingly, and these configurations are coupled on the set where their overlap is fixed $\{R_{1,2}=N^{-1}\sum_{i=1}^N σ_i^1σ_i^2 = u_N\}.$ We prove the existence of the thermodynamic limit of the free energy of this… ▽ More In this paper we consider a system of spins that consists of two configurations $\vsi^1,\vsi^2\inΣ_N=\{-1,+1\}^N$ with Gaussian Hamiltonians $H_N^1(\vsi^1)$ and $H_N^2(\vsi^2)$ correspondingly, and these configurations are coupled on the set where their overlap is fixed $\{R_{1,2}=N^{-1}\sum_{i=1}^N σ_i^1σ_i^2 = u_N\}.$ We prove the existence of the thermodynamic limit of the free energy of this system given that $\lim_{N\to\infty}u_N = u\in[-1,1]$ and give the analogue of the Aizenman-Sims-Starr variational principle that describes this limit via random overlap structures. △ Less

Submitted 18 May, 2004; originally announced May 2004.

Comments: 16 pages

MSC Class: 60K35; 82B44

Journal ref: 2005 Markov Process. Related Fields 11 No. 1

A central limit theorem for weighted averages of spins in the high temperature region of the Sherrington-Kirkpatrick model

Authors: Dmitry Panchenko

Abstract: In this paper we prove that in the high temperature region of the Sherrington-Kirkpatrick model for a typical realization of the disorder the weighted average of spins $\sum_{i\leq N} t_i σ_i$ will be approximately Gaussian provided that $\max_{i\leq N}|t_i|/\sum_{i\leq N} t_i^2$ is small. In this paper we prove that in the high temperature region of the Sherrington-Kirkpatrick model for a typical realization of the disorder the weighted average of spins $\sum_{i\leq N} t_i σ_i$ will be approximately Gaussian provided that $\max_{i\leq N}|t_i|/\sum_{i\leq N} t_i^2$ is small. △ Less

Submitted 18 May, 2004; originally announced May 2004.

Comments: 25 pages

MSC Class: 60F05; 60K35

Journal ref: 2005 Elect. J. of Probab. 10

Bounds for diluted mean-fields spin glass models

Authors: Dmitry Panchenko, Michel Talagrand

Abstract: In an important recent paper, \cite{FL}, S. Franz and M. Leone prove rigorous lower bounds for the free energy of the diluted $p$-spin model and the $K$-sat model at any temperature. We show that the results for these two models are consequences of a single general principle. Our calculations are significantly simpler than those of \cite{FL}, even in the replica-symmetric case. In an important recent paper, \cite{FL}, S. Franz and M. Leone prove rigorous lower bounds for the free energy of the diluted $p$-spin model and the $K$-sat model at any temperature. We show that the results for these two models are consequences of a single general principle. Our calculations are significantly simpler than those of \cite{FL}, even in the replica-symmetric case. △ Less

Submitted 18 May, 2004; originally announced May 2004.

Comments: 17 pages

MSC Class: 60K35; 82D30; 82B44

Journal ref: 2004 Prob. Theory Related Fields 130 No. 3

Complexities of convex combinations and bounding the generalization error in classification

Authors: Vladimir Koltchinskii, Dmitry Panchenko

Abstract: We introduce and study several measures of complexity of functions from the convex hull of a given base class. These complexity measures take into account the sparsity of the weights of a convex combination as well as certain clustering properties of the base functions involved in it. We prove new upper confidence bounds on the generalization error of ensemble (voting) classification algorithms… ▽ More We introduce and study several measures of complexity of functions from the convex hull of a given base class. These complexity measures take into account the sparsity of the weights of a convex combination as well as certain clustering properties of the base functions involved in it. We prove new upper confidence bounds on the generalization error of ensemble (voting) classification algorithms that utilize the new complexity measures along with the empirical distributions of classification margins, providing a better explanation of generalization performance of large margin classification methods. △ Less

Submitted 25 August, 2005; v1 submitted 18 May, 2004; originally announced May 2004.

Comments: Published at http://dx.doi.org/10.1214/009053605000000228 in the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

Report number: IMS-AOS-AOS0037 MSC Class: 62G05 (Primary) 62G20; 60F15 (Secondary)

Journal ref: Annals of Statistics 2005, Vol. 33, No. 4, 1455-1496

Deviation inequality for monotonic Boolean functions with application to a number of k-cycles in a random graph

Authors: Dmitry Panchenko

Abstract: Using Talagrand's concentration inequality on the discrete cube {0,1}^m we show that given a real-valued function Z(x)on {0,1}^m that satisfies certain monotonicity conditions one can control the deviations of Z(x) above its median by a local Lipschitz norm of Z(x) at the point x. As one application, we give a simple proof of a nearly optimal deviation inequality for the number of k-cycles in a… ▽ More Using Talagrand's concentration inequality on the discrete cube {0,1}^m we show that given a real-valued function Z(x)on {0,1}^m that satisfies certain monotonicity conditions one can control the deviations of Z(x) above its median by a local Lipschitz norm of Z(x) at the point x. As one application, we give a simple proof of a nearly optimal deviation inequality for the number of k-cycles in a random graph. △ Less

Submitted 18 May, 2004; originally announced May 2004.

Comments: 11 pages, 1 figure

MSC Class: 60E15

Journal ref: 2004 Rand. Structures Algorithms 24 No. 1

Symmetrization approach to concentration inequalities for empirical processes

Authors: Dmitry Panchenko

Abstract: We introduce a symmetrization technique that allows us to translate a problem of controlling the deviation of some functionals on a product space from their mean into a problem of controlling the deviation between two independent copies of the functional. As an application we give a new easy proof of Talagrand's concentration inequality for empirical processes, where besides symmetrization we us… ▽ More We introduce a symmetrization technique that allows us to translate a problem of controlling the deviation of some functionals on a product space from their mean into a problem of controlling the deviation between two independent copies of the functional. As an application we give a new easy proof of Talagrand's concentration inequality for empirical processes, where besides symmetrization we use only Talagrand's concentration inequality on the discrete cube {-1,+1}^n. As another application of this technique we prove new Vapnik-Chervonenkis type inequalities. For example, for VC-classes of functions we prove a classical inequality of Vapnik and Chervonenkis only with normalization by the sum of variance and sample variance. △ Less

Submitted 18 May, 2004; originally announced May 2004.

Comments: 15 pages

MSC Class: 62G05

Journal ref: 2003 Ann. Probab. 31 No.4

Bounding the generalization error of convex combinations of classifiers: balancing the dimensionality and the margins

Authors: Vladimir Koltchinskii, Dmitry Panchenko, Fernando Lozano

Abstract: A problem of bounding the generalization error of a classifier f in H, where H is a "base" class of functions (classifiers), is considered. This problem frequently occurs in computer learning, where efficient algorithms of combining simple classifiers into a complex one (such as boosting and bagging) have attracted a lot of attention. Using Talagrand's concentration inequalities for empirical pr… ▽ More A problem of bounding the generalization error of a classifier f in H, where H is a "base" class of functions (classifiers), is considered. This problem frequently occurs in computer learning, where efficient algorithms of combining simple classifiers into a complex one (such as boosting and bagging) have attracted a lot of attention. Using Talagrand's concentration inequalities for empirical processes, we obtain new sharper bounds on the generalization error of combined classifiers that take into account both the empirical distribution of "classification margins'' and an "approximate dimension" of the classifiers and study the performance of these bounds in several experiments with learning algorithms. △ Less

Submitted 18 May, 2004; originally announced May 2004.

Comments: 35 pages, 7 figures

MSC Class: 62G05

Journal ref: 2003 Ann. Appl. Probab. 13 No. 1

Empirical margin distributions and bounding the generalization error of combined classifiers

Authors: Vladimir Koltchinskii, Dmitry Panchenko

Abstract: We prove new probabilistic upper bounds on generalization error of complex classifiers that are combinations of simple classifiers. Such combinations could be implemented by neural networks or by voting methods of combining the classifiers, such as boosting and bagging. The bounds are in terms of the empirical distribution of the margin of the combined classifier. They are based on the methods o… ▽ More We prove new probabilistic upper bounds on generalization error of complex classifiers that are combinations of simple classifiers. Such combinations could be implemented by neural networks or by voting methods of combining the classifiers, such as boosting and bagging. The bounds are in terms of the empirical distribution of the margin of the combined classifier. They are based on the methods of the theory of Gaussian and empirical processes (comparison inequalities, symmetrization method, concentration inequalities) and they improve previous results of Bartlett (1998) on bounding the generalization error of neural networks in terms of l_1-norms of the weights of neurons and of Schapire, Freund, Bartlett and Lee (1998) on bounding the generalization error of boosting. We also obtain rates of convergence in Levy distance of empirical margin distribution to the true margin distribution uniformly over the classes of classifiers and prove the optimality of these rates. △ Less

Submitted 17 May, 2004; originally announced May 2004.

Comments: 35 pages, 1 figure

MSC Class: 60F20; 62H30

Journal ref: 2002 Ann. Statist. Vol. 30 No. 1

Some extensions of an inequality of Vapnik and Chervonenkis

Authors: Dmitry Panchenko

Abstract: The inequality of Vapnik and Chervonenkis controls the expectation of the function by its sample average uniformly over a VC-major class of functions taking into account the size of the expectation. Using Talagrand's kernel method we prove a similar result for the classes of functions for which Dudley's uniform entropy integral or bracketing entropy integral is finite. The inequality of Vapnik and Chervonenkis controls the expectation of the function by its sample average uniformly over a VC-major class of functions taking into account the size of the expectation. Using Talagrand's kernel method we prove a similar result for the classes of functions for which Dudley's uniform entropy integral or bracketing entropy integral is finite. △ Less

Submitted 17 May, 2004; originally announced May 2004.

Comments: 12 pages

MSC Class: 60G20

Journal ref: 2002 Elect. Comm. in Probab. 7 55-65

A note on Talagrand's concentration inequality for empirical processes

Authors: Dmitry Panchenko

Abstract: In this paper we revisit Talagrand's proof of concentration inequality for empirical processes. We give a different shorter proof of the main technical lemma that guarantees the existence of a certain kernel. Our proof provides the almost optimal value of the constant involved in the statement of this lemma. In this paper we revisit Talagrand's proof of concentration inequality for empirical processes. We give a different shorter proof of the main technical lemma that guarantees the existence of a certain kernel. Our proof provides the almost optimal value of the constant involved in the statement of this lemma. △ Less

Submitted 11 April, 2021; v1 submitted 17 May, 2004; originally announced May 2004.

MSC Class: 60G20

Journal ref: 2001 Elect. Comm. in Probab. 6, 55-65

Some Local Measures of Complexity of Convex Hulls and Generalization Bounds

Authors: Olivier Bousquet, Vladimir Koltchinskii, Dmitry Panchenko

Abstract: We investigate measures of complexity of function classes based on continuity moduli of Gaussian and Rademacher processes. For Gaussian processes, we obtain bounds on the continuity modulus on the convex hull of a function class in terms of the same quantity for the class itself. We also obtain new bounds on generalization error in terms of localized Rademacher complexities. This allows us to pr… ▽ More We investigate measures of complexity of function classes based on continuity moduli of Gaussian and Rademacher processes. For Gaussian processes, we obtain bounds on the continuity modulus on the convex hull of a function class in terms of the same quantity for the class itself. We also obtain new bounds on generalization error in terms of localized Rademacher complexities. This allows us to prove new results about generalization performance for convex hulls in terms of characteristics of the base class. As a byproduct, we obtain a simple proof of some of the known bounds on the entropy of convex hulls. △ Less

Submitted 17 May, 2004; originally announced May 2004.

Comments: 15 pages

MSC Class: 60G35

Journal ref: 2002 Lecture Notes on Artificial Intelligence 2375

Rademacher processes and bounding the risk of function learning

Authors: Vladimir Koltchinskii, Dmitry Panchenko

Abstract: We construct data dependent bounds on the risk in function learning problems. The bounds are based on the local norms of the Rademacher process indexed by the underlying function class and they do not require prior knowledge about the distribution of the training examples or any specific properties of the function class. We construct data dependent bounds on the risk in function learning problems. The bounds are based on the local norms of the Rademacher process indexed by the underlying function class and they do not require prior knowledge about the distribution of the training examples or any specific properties of the function class. △ Less

Submitted 17 May, 2004; originally announced May 2004.

Comments: 14 pages

MSC Class: 60G35

Journal ref: 2000 In: High Dimensional Probability II pp. 443 - 459