CSE 291C-b, Spring 2026 Topics on Numerical Methods

University of California, San Diego

Instructor

• CK Cheng, Office: CSE2130, email: ckcheng+291@ucsd.edu, tel: 858 534-6184
• Office hour: TBA

Teaching Assistant

• Ying Yuan, yiy090@ucsd.edu
• Office hours: TBA

Discussion Forum

• TBA

Schedule

• Lectures: 2:00-3:20PM TTH, Room: DIB 122

References

• Lectures on Convex Optimization, Y. Nesterov, Springer, 2018.
• Linear and Nonlinear Programming, D.G. Luenberger and Y. Ye, Fifth Edition, Springer, 2021.
• Nonlinear Programming, Third Edition, D.P. Bertsekas, Athena Scientific, 2016.
• Numerical Optimization, J. Nocedal and S.J. Wright, Second Edition, Springer, 2006.
• An Introduction to Optimization on Smooth Manifolds, N. Boumal, Cambridge, 2023.
• Convex Optimization Algorithms, D.P. Bertsekas, Athena Scientific, 2015.
Random Matrix Methods for Machine Learning, R. Couillet and Z. Liao, Cambridge, 2022.
• Matrix Mathematics, A Scond Course in Linear Algebra, Second Edition, S.R. Garcia, and R. A. Horn, Cambridge, 2023.
• Matrix Computations, G.H. Golub and C.F. Van Loan, Fouth Edition, Johns Hopkins, 2013
• Numerical Recipes: The Art of Scientific Computing, Third Edition, W.H. Press, S.A. Teukolsky, W.T. Vetterling, and B.P. Flannery, Cambridge University Press, 2007.
• Convex Optimization, S. Boyd and L. Vandenberghe, Cambridge, 2004
• Numerical Optimizatin, J. Nocedal and S.J. Wright, Second Edition, Springer, 20009.
• Electronic Circuit and System Simulation Methods, T.L. Pillage, R.A. Rohrer, C. Visweswariah, McGraw-Hill, 1998

Prerequisite

Basic knowledge of linear algebra, numerical methods, convex optimization, or intention of conducting projects related to scientific computation.

Content

We cover topics on numerical methods for dynamic system analysis and optimization algorithms. Our scope aims at systems in high-dimensional space with temporal behavior. We discuss techniques such as integration methods, first-order methods, random matrix theory, and Gumbel tricks.

Lecture Notes

• 1. Gumbel Softmax Trick:
• Huijben, I.A., Kool, W., Paulus, M.B. and Van Sloun, R.J., 2022. A review of the gumbel-max trick and its extensions for discrete stochasticity in machine learning. IEEE transactions on pattern analysis and machine intelligence, 45(2), pp.1353-1371. pdf.
• Li, Y., Liu, J., Lin, G., Hou, Y., Mou, M. and Zhang, J., 2021. Gumbel-softmax-based optimization: a simple general framework for optimization problems on graphs. Computational Social Networks, 8(1), p.5. pdf.
• Balog, M., Tripuraneni, N., Ghahramani, Z. and Weller, A., 2017, July. Lost relatives of the Gumbel trick. In International Conference on Machine Learning (pp. 371-379). PMLR. pdf.
• 2. Neural Scaling Laws:
• Hoffmann, J., Borgeaud, S., Mensch, A., Buchatskaya, E., Cai, T., Rutherford, E., Casas, D.D.L., Hendricks, L.A., Welbl, J., Clark, A. and Hennigan, T., 2022. Training compute-optimal large language models. arXiv preprint arXiv:2203.15556, 10. pdf.
• Tissue, H., Wang, V. and Wang, L., 2024. Scaling law with learning rate annealing. arXiv preprint arXiv:2408.11029. analysis and machine intelligence, 45(2), pp.1353-1371. pdf.
• Nakkiran, P., Kaplun, G., Bansal, Y., Yang, T., Barak, B. and Sutskever, I., 2021. Deep double descent: Where bigger models and more data hurt. Journal of Statistical Mechanics: Theory and Experiment, 2021(12), p.124003. pdf.
• 3. Random Matrix Methods:
• Martin, C.H. and Mahoney, M.W., 2021. Implicit self-regularization in deep neural networks: Evidence from random matrix theory and implications for learning. Journal of Machine Learning Research, 22(165), pp.1-73. pdf.
• Seddik, M.E.A., Louart, C., Tamaazousti, M. and Couillet, R., 2020, November. Random matrix theory proves that deep learning representations of gan-data behave as gaussian mixtures. In International Conference on Machine Learning (pp. 8573-8582). PMLR. pdf.
• Random Matrix Methods for Machine Learning, R. Couillet and Z. Liao, Cambridge, 2022.
• Lectures on Randome Matrices, R. Speicher, EMS Press, 2024.
• Topics in Random Matrix Theory, T. Tao, Ameican Mathematical Society, 2012.
• A Dynamical Approach to Random Matrix Theory, L. Erdos, H-T Yau, Ameican Mathematical Society, 2017.
• 4. Gradient Descent:
• Lecture Notes on Optimization for Machine Learning, A. Cutkowskyy. pdf.
• Above document was updated 4/16/2026
• 1. Introduction pptx.
• 1.1. Motivation ppt.
• 2. Formulation ppt.
• 3. Matrix Solvers:
• (1) Sparse direct method by Xiaoye Sherry Li, ppt
• (2) Steepest descent methods ppt,
• Conjugate gradient tutorial by CK Cheng pdf,
• Nesterov Method: Differential Equation by Su, Boyd and Candes. pdf,
• Nesterov Method: Gradient and Mirror descent by Zhu and Orecchia pdf,
• Graident descent survey by S. Ruder: https://arxiv.org/pdf/1609.04747.pdf
• (3) Krylov subspace methods and multigrid methods ppt.
• 4. Integration:
• (1) One step methods pptx,
• (2) Multistep methods pptx.
• 5. Sensitivity: pptx,
• 6. Koopman Operator: pdf file, Notes on Koopman Operator Theory, S.L. Brunton, Universitat von Washington, 2019.
Lecture Notes, Part II: Nonlinear Programming (lecture notes by D.P. Bertsekas, Term of Use: http://ocw.mit.edu/terms.)
Slides pdf
Lecture Notes, Part III: Convex Optimization Methods (lecture notes by D.P. Bertsekas, Term of Use: http://ocw.mit.edu/terms.)
• 1. Introduction pdf
• 2. Overall view pdf
• 3. Subgradient methods
• I pdf
• II pdf
• 4. Approximation methods pdf
• 5. Proximal methods
• I. pdf
• II pdf
• ADMM by R. Tibshirani pdf
• III pdf
• 6. Advanced Approaches
• Extension of gradient projection methods I pdf
• Extension of gradient projection methods II pdf
• Extension of incremental methods pdf
• Extension of proximal methods pdf
• Distributed asynchronous methods pdf
Integer Programming
• Integer Programming by Larrosa, Oliveras, and Rodriguez-Carbonell, pdf
• Integer Programming by Kolter and Shah, pdf
• Integer Programming by Cornuejols, Trick and Saltzman, pdf
Standard Cell Design using SAT Packages
• Standard Cell Library Analsys and Synthesis, CK Cheng talk, pdf
• The Scope and Challenges of Scaling in Advanced Technologies, CK Cheng talk, 2023, pdf
Papers
• Nesterov's Fast Gradient Method
  • Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights, W. Su et al. Journal of Machine Learning Researech, 2016, pdf file.
  • Understanding the Accelerated Phenomenon via High-Resolution Differential Equations, B. Shi, et al., Mathematical Programming, 2022, pdf file.
  • Fast Iterative Shrinkage-Thresholding Algorithm for Lineare Inverse Problems, A. Beck, and M. Teboulle, SIAM J. Imageing Sciences, 2009, pdf file,
• Koopman Operator
• Notes on Koopman Operator Theory, S.L. Brunton, pdf file,
• Modern Koopman Theory for Dynamical Systems, S.L. Brunton, et al., Learnining for Robust Dynamic Decomposition: Linear and Nonlinear Disambiguatoin Optimization, P.J. Baddoo, et al., Proceedings Royal Society, 2021. pdf file,
• Kernel Learnining for Robust Dynamic Decomposition: Linear and Nonlinear Disambiguatoin Optimization, P.J. Baddoo, et al., Proceedings Royal Society, 2021. pdf file,
• Matrix Calculus (Sensitivity)
• Matrix Calculus, Lecture Note of A. Edelman and S.G. Johnson scribed by P. Bright, MIT, 2023, pdf file,
• Adjoint Network in Time, Circuit Theory of Time Domain Adjoint Sensitivity, J. Li, D. Ahsanullah, Z. Gao, R. Rohrer, IEEE Trans. on Computer-Aided Design, 2023, pdf file,
• Quasi-Newton Methods
• Two classes of multisecant methods for nonlinear acceleration, Numerical Linear Algebra with Applications, H. Fang and Y. Saad, 2009, 16:197-221, pdf file,
• Quasi-Newton optimization origin of the BFGS update, lecture note of S.G. Johnson updated 5/3/2021. pdf file,
• BFGS in a nutshell: an introduction to quasi-Neweton methods, A. Lam, Towards Data Science, 12/25/2020. pdf file,
• Optimization on Stiefel Manifolds
• Sequential subspace methods on Stiefel manifold optimization problems, P. Chen, C.K. Cheng, and C. Holtz, arXiv, 4/2024. pdf file,
• Optimization algorithms exploiting unitary constraints, J.H. Manton, IEEE Trans. on Signal Processing, 3/2002. pdf file,
• Notes on optimization on Stiefel manifolds, H.D. Tagare, 1/24/2011. pdf file,
• Random Algorithms
• On Variants of the Johnson-Lindenstrauss Lemma, J. Matousek, Wiley InterScience, 2008, pdf file,
• Why Are Big Data Matrices Approximately Low Rank?, M. Udell and A. Townsend, SIAM J. Math. Data Sci. 2019, pdf file,
• Fast and Accurate Randomized Algorithms for Linear Systems and Eigenvalue Problems, Y. Nakatsukasa and J.A. Tropp, arxiv.org, 2021, pdf file,
• A Fast Randomized Algorithm for the Approximation of Matrices, F. Woolfe, E. Liberty, V. Rokhlin, M. Tygert, Appl. Comput. Harmon, Anal, 2008, pdf file,
• Randomized Algorithms for Low-Rank Matrix Approximation: Design, Analysis, and Applications, J.A> Tropp, and R.J. Webber, arxiv.org, 2023 pdf file,
• Baysian Learning via Stochastic Gradient Langevin Dynamics, M. Welling and Y.W. Teh, Int. Conf. on Machine Learning, 2011. pdf file,
• Physical Layout
• Initial Analytical Placement by P. Chen, CK Cheng, A. Chern, C. Holtz, A. Li, and Y. Wang, ISPD, 2023, pdf file,

Project

• Project Outlines (what are we looking for?) pdf, pptx.