2019

An Introductory Guide to Fano's Inequality with Applications in Statistical Estimation

Scarlett, Jonathan, Cevher, Volkan

Understand

Information theory plays an indispensable role in the development of algorithm-independent impossibility results, both for communication problems and for seemingly distinct areas such as statistics and machine learning.

While numerous information-theoretic tools have been proposed for this purpose, the oldest one remains arguably the most versatile and widespread: Fano's inequality.
In this chapter, we provide a survey of Fano's inequality and its variants in the context of statistical estimation, adopting a versatile framework that covers a wide range of specific problems.
We present a variety of key tools and techniques used for establishing impossibility results via this approach, and provide representative examples covering group testing, graphical model selection, sparse linear regression, density estimation, and convex optimization.

Built on

R. Dorfman, “The detection of defective members of large populations,” Ann. Math. Stats. , vol. 14, no. 4, pp. 436–440, 1943
1943
Earlier work this paper cites.
R. M. Fano, “Class notes for MIT course 6.574: Transmission of information,” 1952
1952
Earlier work this paper cites.
I. A. Ibragimov and R. Z. Khasminskii, “Estimation of infinite-dimensional parameter in Gaussian white noise,” Doklady Akademii Nauk SSSR , vol. 236, no. 5, pp. 1053–1055, 1977
1977
Earlier work this paper cites.
M. Malyutov, “The separating property of random matrices,” Math. Notes Acad. Sci. USSR , vol. 23, no. 1, pp. 84–91, 1978
1978
Earlier work this paper cites.
L. Birgé, “Approximation dans les espaces métriques et théorie de l’estimation,” Prob. Theory and Related Fields , vol. 65, no. 2, pp. 181–237, 1983
1983
Earlier work this paper cites.
T. Lai and H. Robbins, “Asymptotically efficient adaptive allocation rules,” Adv. App. Math. , vol. 6, no. 1, pp. 4 – 22, 1985
1985
Earlier work this paper cites.
T. S. Han and S. Verdú, “Generalizing the Fano inequality,” IEEE Trans. Inf. Theory , vol. 40, no. 4, pp. 1247–1251, 1994
1994
Earlier work this paper cites.
P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire, “Gambling in a rigged casino: The adversarial multi-armed bandit problem,” in IEEE Conf. Found. Comp. Sci. (FOCS) , 1995
1995
Earlier work this paper cites.
B. Yu, “Assouad, Fano, and Le Cam,” in Festschrift for Lucien Le Cam . Springer, 1997, pp. 423–435
1997
Earlier work this paper cites.
Y. Yang and A. Barron, “Information-theoretic determination of minimax rates of convergence,” Annals. Stats. , vol. 27, no. 5, pp. 1564–1599, 1999
1999
Earlier work this paper cites.
Y. Yang, “Minimax nonparametric classification. i. rates of convergence,” IEEE Trans. Inf. Theory , vol. 45, no. 7, pp. 2271–2284, 1999
1999
Earlier work this paper cites.
Z. Bar-Yossef, T. S. Jayram, R. Kumar, and D. Sivakumar, “Information theory methods in communication complexity,” in IEEE Conf. Comp. Complex. , 2002, pp. 93–102
2002
Earlier work this paper cites.
E. Mossel, “Phase transitions in phylogeny,” Trans. AMS , vol. 356, no. 6, pp. 2379–2404, 2004
2004
Earlier work this paper cites.
A. A. Gushchin, “On Fano’s lemma and similar inequalities for the minimax risk,” Prob. Theory and Math. Stats. , vol. 67, pp. 26–37, 2004
2004
Earlier work this paper cites.
L. Birgé, “A new lower bound for multiple hypothesis testing,” IEEE Trans. Inf. Theory , vol. 51, no. 4, pp. 1611–1615, 2005
2005
Earlier work this paper cites.
T. M. Cover and J. A. Thomas, Elements of Information Theory . John Wiley & Sons, Inc., 2006
2006
Earlier work this paper cites.
M. Wainwright, “Information-theoretic limits on sparsity recovery in the high-dimensional and noisy setting,” IEEE Trans. Inf. Theory , vol. 55, no. 12, pp. 5728–5741, Dec. 2009
2009
Earlier work this paper cites.
A. A. Amini and M. J. Wainwright, “High-dimensional analysis of semidefinite relaxations for sparse principal components,” Annals Stats. , vol. 37, no. 5B, pp. 2877–2921, 2009
2009
Earlier work this paper cites.
Y. Polyanskiy, V. Poor, and S. Verdú, “Channel coding rate in the finite blocklength regime,” IEEE Trans. Inf. Theory , vol. 56, no. 5, pp. 2307–2359, May 2010
2010
Earlier work this paper cites.
Y. Polyanskiy and S. Verdú, “Arimoto channel coding converse and rényi divergence,” in Allerton Conf. Comm., Control, Comp. , 2010
2010
Earlier work this paper cites.

Similar

M. Raginsky and A. Rakhlin, “Information-based complexity, feedback and dynamics in convex programming,” IEEE Trans. Inf. Theory , vol. 57, no. 10, pp. 7036–7056, Oct. 2011
2011
Cited alongside, same era.
M. Raginsky and A. Rakhlin, “Lower bounds for passive and active learning,” in Conf. Neur. Inf. Proc. Sys. (NIPS) , 2011
2011
Cited alongside, same era.
V. Y. F. Tan, A. Anandkumar, and A. S. Willsky, “Learning high-dimensional Markov forest distributions: Analysis of error rates,” J. Mach. Learn. Res. , vol. 12, no. May, pp. 1617–1653, 2011
2011
Cited alongside, same era.
A. Guntuboyina, “Lower bounds for the minimax risk using f f -divergences, and applications,” IEEE Trans. Inf. Theory , vol. 57, no. 4, pp. 2386–2399, 2011
2011
Cited alongside, same era.
G. Atia and V. Saligrama, “Boolean compressed sensing and noisy group testing,” IEEE Trans. Inf. Theory , vol. 58, no. 3, pp. 1880–1901, March 2012
2012
Cited alongside, same era.
H. Hassanieh, P. Indyk, D. Katabi, and E. Price, “Nearly optimal sparse Fourier transform,” in ACM Symp. Theory Comp. (STOC) , 2012, pp. 563–578
2012
Cited alongside, same era.
V. Q. Vu and J. Lei, “Minimax rates of estimation for sparse PCA in high dimensions,” in Int. Conf. Art. Intel. Stats. (AISTATS) , 2012, pp. 1278–1286
2012
Cited alongside, same era.
S. Negahban and M. J. Wainwright, “Restricted strong convexity and weighted matrix completion: Optimal bounds with noise,” J. Mach. Learn. Res. , vol. 13, pp. 1665–1697, May 2012
2012
Cited alongside, same era.
G. Raskutti, M. J. Wainwright, and B. Yu, “Minimax-optimal rates for sparse additive models over kernel classes via convex programming,” J. Mach. Learn. Res. , vol. 13, no. Feb, pp. 389–427, 2012
2012
Cited alongside, same era.
A. Agarwal, P. L. Bartlett, P. Ravikumar, and M. J. Wainwright, “Information-theoretic lower bounds on the oracle complexity of stochastic convex optimization,” IEEE Trans. Inf. Theory , vol. 58, no. 5, pp. 3235 – 3249, May 2012
2012
Cited alongside, same era.
N. Santhanam and M. Wainwright, “Information-theoretic limits of selecting binary graphical models in high dimensions,” IEEE Trans. Inf. Theory , vol. 58, no. 7, pp. 4117–4134, July 2012
2012
Cited alongside, same era.
A. Anandkumar, V. Y. F. Tan, F. Huang, and A. S. Willsky, “High-dimensional structure estimation in Ising models: Local separation criterion,” Ann. Stats. , vol. 40, no. 3, pp. 1346–1375, 2012
2012
Cited alongside, same era.

Then

M. Nokleby, M. Rodrigues, and R. Calderbank, “Discrimination on the Grassmann manifold: Fundamental limits of subspace classifiers,” IEEE Trans. Inf. Theory , vol. 61, no. 4, pp. 2133–2147, April 2015
2015
Later among the works it cites.
I. Sason and S. Verdú, “ f f -divergence inequalities,” IEEE Trans. Inf. Theory , vol. 62, no. 11, pp. 5973–6006, Nov. 2016
2016
Later among the works it cites.
J. Scarlett and V. Cevher, “Phase transitions in group testing,” in Proc. ACM-SIAM Symp. Disc. Alg. (SODA) , 2016
2016
Later among the works it cites.
J. Scarlett and V. Cevher, “Converse bounds for noisy group testing with arbitrary measurement matrices,” in IEEE Int. Symp. Inf. Theory , Barcelona, 2016
2016
Later among the works it cites.
——, “On the difficulty of selecting Ising models with approximate recovery,” IEEE Trans. Sig. Inf. Proc. over Networks , vol. 2, no. 4, pp. 625–638, 2016
2016
Later among the works it cites.
G. Dasarathy, A. Singh, M.-F. Balcan, and J. H. Park, “Active learning algorithms for graphical model selection,” in Int. Conf. Art. Intel. Stats. (AISTATS) , 2016
2016
Later among the works it cites.
X. Chen, A. Guntuboyina, and Y. Zhang, “On Bayes risk lower bounds,” J. Mach. Learn. Res. , vol. 17, no. 219, pp. 1–58, 2016. [Online]. Available: http://jmlr.org/papers/v17/16-185.html
2016
Later among the works it cites.
V. Cevher, M. Kapralov, J. Scarlett, and A. Zandieh, “An adaptive sublinear-time block sparse Fourier transform,” in ACM Symp. Theory Comp. (STOC) , 2017
2017
Later among the works it cites.
Y. Yang, M. Pilanci, and M. J. Wainwright, “Randomized sketches for kernels: Fast and optimal nonparametric regression,” Annals Stats. , vol. 45, no. 3, pp. 991–1023, 2017
2017
Later among the works it cites.
A. Xu and M. Raginsky, “Information-theoretic analysis of generalization capability of learning algorithms,” in Conf. Neur. Inf. Proc. Sys. , 2017
2017
Later among the works it cites.
A. Agarwal, S. Agarwal, S. Assadi, and S. Khanna, “Learning with limited rounds of adaptivity: Coin tossing, multi-armed bandits, and ranking from pairwise comparisons,” in Conf. Learn. Theory (COLT) , 2017
2017
Later among the works it cites.
A. Pananjady, C. Mao, V. Muthukumar, M. J. Wainwright, and T. A. Courtade, “Worst-case vs average-case design for estimation from fixed pairwise comparisons,” 2017, http://arxiv.org/abs/1707.06217
Original
2017
Later among the works it cites.
A. Mazumdar and B. Saha, “Query complexity of clustering with side information,” in Conf. Neur. Inf. Proc. Sys. (NIPS) , 2017
2017
Later among the works it cites.
——, “How little does non-exact recovery help in group testing?” in IEEE Int. Conf. Acoust. Sp. Sig. Proc. (ICASSP) , 2017
2017
Later among the works it cites.
——, “Lower bounds on active learning for graphical model selection,” in Int. Conf. Art. Intel. Stats. (AISTATS) , 2017
2017
Later among the works it cites.
O. Johnson, “Strong converses for group testing from finite blocklength results,” IEEE Trans. Inf. Theory , vol. 63, no. 9, pp. 5923–5933, Sept. 2017
2017
Later among the works it cites.
P.-L. Loh, “On lower bounds for statistical learning theory,” Entropy , vol. 19, no. 11, p. 617, 2017
2017
Later among the works it cites.
J. Scarlett, “Tight regret bounds for bayesian optimization in one dimension,” in Int. Conf. Mach. Learn. (ICML) , 2018
2018
Later among the works it cites.
N. B. Shah and M. J. Wainwright, “Simple, robust and optimal ranking from pairwise comparisons,” J. Mach. Learn. Res. , vol. 18, no. 199, pp. 1–38, 2018
2018
Later among the works it cites.
R. Venkataramanan and O. Johnson, “A strong converse bound for multiple hypothesis testing, with applications to high-dimensional estimation,” Elec. J. Stats. , vol. 12, no. 1, pp. 1126–1149, 2018
2018
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…