Elamur Research⌕
☰
home / papers / 2018 / Measuring the Intrinsic Dimension of Objective Landscapes

Measuring the Intrinsic Dimension of Objective Landscapes

Paper · 2018 · Chunyuan Li, Heerad Farkhoor, Rosanne Liu et al.

Summary

The paper asks how many trainable degrees of freedom a neural network problem actually needs, as opposed to how many parameters a model has. Instead of optimizing all D weights directly, the authors freeze a random initialization and a random D×d projection matrix. They then train only a small d-dimensional vector that is mapped into the full weight space. They increase d step by step and record the smallest value at which the model reaches 90% of a directly trained baseline. Performance is measured as validation accuracy, or as shifted total reward for RL. This threshold value is called the intrinsic dimension, d_int90. Experiments cover fully connected and convolutional networks on MNIST, CIFAR-10 and ImageNet, plus RL tasks such as CartPole, Inverted Pendulum, Humanoid and Atari Pong. Many tasks need far fewer dimensions than expected. The measured value also stays fairly stable across models of very different sizes, which suggests that extra parameters mostly enlarge the set of solutions. The measure allows difficulty comparisons across learning paradigms. It also gives a constructive upper bound on a solution's description length and can be used to compress networks.

Key points

  • Sanity check: On a toy problem with D = 1000 and 10 sum constraints, the method recovers the analytically expected intrinsic dimension of 10.
  • Supervised vision tasks:
    • MNIST: FC (D = 199,210) needs d_int90 = 750, and LeNet (D = 44,426) needs 275.
    • CIFAR-10: FC needs 9,000, and LeNet needs 2,900.
    • ImageNet: SqueezeNet needs more than 500,000; at d = 500k it reached only 34.34% accuracy, still below the threshold.
  • RL tasks: Inverted Pendulum needs 4, CartPole 25, Humanoid 700, and Atari Pong (ConvNet) 6,000. By this measure the pendulum is roughly 100× easier than MNIST, and Pong is about as hard as CIFAR-10.
  • Memorization: MNIST with fully shuffled labels requires d_int90 = 190,000 with an FC-5 network. Shuffling pixels raises LeNet's value (650 vs. 275) but leaves the FC network unchanged (750).
  • Convolution ablation and compression:
    • Both local connectivity and weight tying lower intrinsic dimension. On MNIST the values are 290 for standard LeNet, 600 for untied, 425 for FC-tied and 2,000 for FC-LeNet.
    • Subspace training compresses some networks by more than 100×.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Cornell UniversityIthaca · United States134 works · 65,159 citations🎓Duke UniversityDurham · United States37 works · 15,861 citations🏢Uber AISan Francisco · United States2 works · 721 citations

 Fields, topics and concepts

📚 Shelves 2The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 works

Cite

Cite as Chunyuan Li, Heerad Farkhoor, Rosanne Liu and Jason Yosinski. 2018. Measuring the Intrinsic Dimension of Objective Landscapes. arXiv:1804.08838.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.1804.08838 · arXiv 1804.08838

@misc{li2018measuring,
  title = {{Measuring the Intrinsic Dimension of Objective Landscapes}},
  author = {Chunyuan Li, Heerad Farkhoor, Rosanne Liu and Jason Yosinski},
  year = {2018},
  doi = {10.48550/arxiv.1804.08838},
  eprint = {1804.08838},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1804.08838}
}

References

36 references, 4 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym, 2016. find
  2. Francesco Camastra and Alessandro Vinciarelli. Estimating the intrinsic dimension of data with a fractal-based method. IEEE Transactions on pattern analysis and machine intelligence, 24(10): 1404–1407, 2002. find
  3. Wenlin Chen, James T. Wilson, Stephen Tyree, Kilian Q. Weinberger, and Yixin Chen. Compressing neural networks with the hashing trick. CoRR, abs/1504.04788, 2015. URL http://arxiv.org/abs/1504.04788. — [arXiv:1504.04788](https://arxiv.org/abs/1504.04788) ↗
  4. Yann Dauphin and Yoshua Bengio. Big neural networks waste capacity. CoRR, abs/1301.3583, 2013. URL http://arxiv.org/abs/1301.3583. — [arXiv:1301.3583](https://arxiv.org/abs/1301.3583) ↗
  5. Yann Dauphin, Razvan Pascanu, Çaglar Gülçehre, Kyunghyun Cho, Surya Ganguli, and Yoshua Bengio. Identifying and attacking the saddle point problem in high-dimensional non-convex optimization. CoRR, abs/1406.2572, 2014. URL http://arxiv.org/abs/1406.2572. ↗
  6. Misha Denil, Babak Shakibi, Laurent Dinh, Nando de Freitas, et al. Predicting parameters in deep learning. In Advances in Neural Information Processing Systems, pp. 2148–2156, 2013. find
  7. Keinosuke Fukunaga and David R Olsen. An algorithm for finding intrinsic dimensionality of data. IEEE Transactions on Computers, 100(2):176–183, 1971. find
  8. Raja Giryes, Guillermo Sapiro, and Alexander M Bronstein. Deep neural networks with random gaussian weights: a universal classification strategy? IEEE Trans. Signal Processing, 2016. find
  9. Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Artificial Intelligence and Statistics, 2010. find
  10. Ian J. Goodfellow, Oriol Vinyals, and Andrew M. Saxe. Qualitatively characterizing neural network optimization problems. In International Conference on Learning Representations (ICLR 2015), 2015. URL http://arxiv.org/abs/1412.6544. ↗
  11. Song Han, Huizi Mao, and William J Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. ICLR, 2016. find
  12. Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In CVPR, 2015. find
  13. Geoffrey E Hinton and Drew Van Camp. Keeping neural networks simple by minimizing the description length of the weights. In Proceedings of the sixth annual conference on Computational learning theory, pp. 5–13. ACM, 1993. find
  14. Forrest N Iandola, Song Han, Matthew W Moskewicz, Khalid Ashraf, William J Dally, and Kurt Keutzer. Squeezenet: Alexnet-level accuracy with 50x fewer parameters and¡ 0.5 mb model size. arXiv preprint arXiv:1602.07360, 2016. find
  15. Lukasz Kaiser, Aidan N. Gomez, Noam Shazeer, Ashish Vaswani, Niki Parmar, Llion Jones, and Jakob Uszkoreit. One model to learn them all. CoRR, abs/1706.05137, 2017. URL http://arxiv.org/abs/1706.05137. ↗
  16. Balázs Kégl. Intrinsic dimension estimation using packing numbers. In Advances in neural information processing systems, pp. 697–704, 2003. find
  17. Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
  18. James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A. Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabska-Barwinska, Demis Hassabis, Claudia Clopath, Dharshan Kumaran, and Raia Hadsell. Overcoming catastrophic forgetting in neural networks. Proc… find
  19. Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical report, 2009. find
  20. Quoc Le, Tamás Sarlós, and Alex Smola. Fastfood-approximating kernel expansions in loglinear time. In ICML, 2013. find
  21. Elizaveta Levina and Peter J Bickel. Maximum likelihood estimation of intrinsic dimension. In Advances in neural information processing systems, pp. 777–784, 2005. find
  22. Ping Li, T. Hastie, and K. W. Church. Very sparse random projections. In KDD, 2006. find
  23. C. Louizos, K. Ullrich, and M. Welling. Bayesian Compression for Deep Learning. ArXiv e-prints, May 2017. find
  24. V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, and M. Riedmiller. Playing Atari with Deep Reinforcement Learning. ArXiv e-prints, December 2013. find
  25. Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun. Faster r-cnn: Towards real-time object detection with region proposal networks. In Advances in neural information processing systems, pp. 91–99, 2015.
  26. Jorma Rissanen. Modeling by shortest data description. Automatica, 14(5):465–471, 1978. find
  27. Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual recognition challenge. International Journal of Computer Vision, 2015.
  28. T. Salimans, J. Ho, X. Chen, and I. Sutskever. Evolution Strategies as a Scalable Alternative to Reinforcement Learning. ArXiv e-prints, March 2017. find
  29. Kenneth Stanley and Risto Miikkulainen. Evolving neural networks through augmenting topologies. Evolutionary computation, 10(2):99–127, 2002. find
  30. Joshua B Tenenbaum, Vin De Silva, and John C Langford. A global geometric framework for nonlinear dimensionality reduction. science, 290(5500):2319–2323, 2000. find
  31. Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2):26– 31, 2012. find
  32. Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In Intelligent Robots and Systems (IROS), 2012 IEEE/RSJ International Conference on, pp. 5026– 5033. find
  33. Wei Wen, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Learning structured sparsity in deep neural networks. In NIPS, 2016.
  34. Zichao Yang, Marcin Moczulski, Misha Denil, Nando de Freitas, Alex Smola, Le Song, and Ziyu Wang. Deep fried convnets. In Proceedings of the IEEE International Conference on Computer Vision, pp. 1476–1483, 2015. find
  35. Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. ICLR, 2017. find
  36. S UPPLEMENTARY I NFORMATION FOR : M EASURING THE I NTRINSIC D IMENSION OF O BJECTIVE L ANDSCAPES S5 find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/li-2018-measuring-intrinsic-dimension-objective-landscapes/