161 - 170 of 228 results for: MS

Each course session will be devoted to a specific MS&E PhD research area. Advanced students will make presentations designed for first-year doctoral students regardless of area. The presentations will be devoted to: illuminating how people in the area being explored that day think about and approach problems, and illustrating what can and cannot be done when addressing problems by deploying the knowledge, perspectives, and skills acquired by those who specialize in the area in question. Area faculty will attend and participate. During the last two weeks of the quarter groups of first year students will make presentations on how they would approach a problem drawing on two or more of the perspectives to which they have been exposed earlier in the class. Attendance is mandatory and performance will be assessed on the basis of the quality of the students¿ presentations and class participation. Restricted to first year MS&E PhD students.

Formulation of standard linear programming models. Theory of polyhedral convex sets, linear inequalities, alternative theorems, and duality. Variants of the simplex method and the state of art interior-point algorithms. Sensitivity analyses, economic interpretations, and primal-dual methods. Relaxations of harder optimization problems and recent convex conic linear programs. Applications include game equilibrium facility location. Prerequisite: MATH 113 or consent of instructor.

Applications, theories, and algorithms for finite-dimensional linear and nonlinear optimization problems with continuous variables. Elements of convex analysis, first- and second-order optimality conditions, sensitivity and duality. Algorithms for unconstrained optimization, and linearly and nonlinearly constrained problems. Modern applications in communication, game theory, auction, and economics. Prerequisites: MATH 113, 115, or equivalent.

Fundamental theory for solving continuous optimization problems with provable efficiency guarantees. Coverage of both canonical optimization methods and techniques, e.g. gradient descent, mirror descent, stochastic methods, acceleration, higher-order methods, etc. and canonical optimization problems, critical point computation for non-convex functions, smooth-convex function minimization, regression, linear programming, etc. Focus on provable rates for solving broad classes of prevalent problems including both classic problems and those motivated by large-scale computational concerns. Discussion of computational ramifications, fundamental information-theoretic limits, and problem structure. Prerequisite: linear algebra, multivariable calculus, probability, and proofs.

Over the past decade there has been an explosion in activity in designing new provably efficient fast graph algorithms. Leveraging techniques from disparate areas of computer science and optimization researchers have made great strides on improving upon the best known running times for fundamental optimization problems on graphs, in many cases breaking long-standing barriers to efficient algorithm design. In this course we will survey these results and cover the key algorithmic tools they leverage to achieve these breakthroughs. Possible topics include but are not limited to, spectral graph theory, sparsification, oblivious routing, local partitioning, Laplacian system solving, and maximum flow. Prerequisites: calculus and linear algebra.

Optimization in Data Science and Machine Learning

Introduction to theoretical foundations of discrete mathematics and algorithms. Emphasis on providing mathematical tools for combinatorial optimization, i.e. how to efficiently optimize over large finite sets and reason about the complexity of such problems. Topics include: graph theory, minimum cut, minimum spanning trees, matroids, maximum flow, non-bipartite matching, NP-hardness, approximation algorithms, spectral graph theory, and Laplacian systems. Prerequisites: CS 161 is highly recommended, although not required.

The theory of matching with its roots in the work of mathematical giants like Euler and Kirchhoff has played a central and catalytic role in combinatorial optimization for decades. More recently, the growth of online marketplaces for allocating advertisements, rides, or other goods and services has led to new interest and progress in this area. The course starts with classic results characterizing matchings in bipartite and general graphs and explores connections with other branches of mathematics, including game theory and algebraic graph theory. Those results are complemented with models and algorithms developed for modern applications in market design, online advertising, and ride sharing. May be repeated for credit. Prerequisite: 212, CS 261, or equivalent.

Topics in stochastic processes, emphasizing applications. Markov chains in discrete and continuous time; Markov processes in general state space; Lyapunov functions; regenerative process theory; renewal theory; martingales, Brownian motion, and diffusion processes. Application to queueing theory, storage theory, reliability, and finance. Prerequisites: 221 or STATS 217; MATH 113, 115.