Via an overparameterized linear model with Gaussian features, we provide conditions for good generalization for multiclass classification of minimum-norm interpolating solutions in an asymptotic setting where both the number of underlying features and the number of classes scale with the number of training points. The survival/contamination analysis framework for understanding the behavior of overparameterized learning problems is adapted to this setting, revealing that multiclass classification qualitatively behaves like binary classification in that, as long as there are not too many classes (made precise in the paper), it is possible to generalize well even in settings where regression tasks would not generalize. Besides various technical challenges, it turns out that the key difference from the binary classification setting is that there are relatively fewer training examples of each class in the multiclass setting as the number of classes increases, making the multiclass problem ``harder'' than the binary one.

This article considers the question of how to succinctly approximate a multidimensional convex body by a polytope. Given a convex body K of unit diameter in Euclidean d -dimensional space (where d is a constant) and an error parameter ε > 0, the objective is to determine a convex polytope of low combinatorial complexity whose Hausdorff distance from K is at most ε. By combinatorial complexity , we mean the total number of faces of all dimensions. Classical constructions by Dudley and Bronshteyn/Ivanov show that O (1/ε ( d -1)/2 ) facets or vertices are possible, respectively, but neither achieves both bounds simultaneously. In this article, we show that it is possible to construct a polytope with O (1/ε ( d -1)/2 ) combinatorial complexity, which is optimal in the worst case. Our result is based on a new relationship between ε-width caps of a convex body and its polar body. Using this relationship, we are able to obtain a volume-sensitive bound on the number of approximating caps that are “essentially different.” We achieve our main result by combining this with a variant of the witness-collector method and a novel variable-thickness layered construction of the economical cap covering.

Control strategies for vector systems typically depend on the controller's ability to plan out future control actions. However, in the case where model parameters are random and time-varying, this planning might not be possible. This paper explores the fundamental limits of a simple system, inspired by the intermittent Kalman filtering model, where the actuation direction is drawn uniformly from the unit hypersphere. The model allows us to focus on a fundamental tension in the control of underactuated vector systems - the need to balance the growth of the system in different dimensions. We characterize the stabilizability of$d$-dimensional systems with symmetric gain matrices by providing tight necessary and sufficient conditions that depend on the eigenvalues of the system. The proof technique is slightly different from the standard dynamic programming approach and relies on the fact that the second moment stability of the system can also be understood by examining any arbitrary weighted two-norm of the state.

The Nifty Assignments special session is about promoting and sharing the ideas and ready-to-use materials of successful assignments. Each presenter will introduce their assignment, give a quick demo, and describe its niche in the curriculum and its strengths and weaknesses. The presentations (and the descriptions below) merely introduce the assignment. A key part of Nifty Assignments is the mundane but vital role of distributing the materials - handouts, data files, starter code, rubrics, autograders - that make each assignment ready to adopt. Each assignment presented has complete materials freely available on the Nifty Assignments home page nifty.stanford.edu. If you have an assignment that works well and would be of interest to the CSE community, please consider applying to present at Nifty Assignments.

Convex bodies play a fundamental role in geometric computation, and approximating such bodies is often a key ingredient in the design of efficient algorithms. We consider the question of how to succinctly approximate a multidimensional convex body by a polytope. We are given a convex body K of unit diameter in Euclidean d-dimensional space (where d is a constant) along with an error parameter ε > 0. The objective is to determine a polytope of low combinatorial complexity whose Hausdorff distance from K is at most e. By combinatorial complexity we mean the total number of faces of all dimensions of the polytope. In the mid-1970's, a result by Dudley showed that O(1/ε(d–1)/2) facets suffice, and Bronshteyn and Ivanov presented a similar bound on the number of vertices. While both results match known worst-case lower bounds, obtaining a similar upper bound on the total combinatorial complexity has been open for over 40 years. Recently, we made a first step forward towards this objective, obtaining a suboptimal bound. In this paper, we settle this problem with an asymptotically optimal bound of O(1/ε(d–1)/2). Our result is based on a new relationship between ε-width caps of a convex body and its polar. Using this relationship, we are able to obtain a volume-sensitive bound on the number of approximating caps that are “essentially different.” We achieve our result by combining this with a variant of the witness-collector method and a novel variable-width layered construction.