In contemporary deep learning practice, models are often trained to near zero loss i.e. to nearly interpolate the training data. However, the number of parameters in the model is usually far more than the number of data points n, the theoretical minimum needed for interpolation: a phenomenon referred to asoverparameterization. In an interesting piece of work that contributes to the considerable research that has been devoted to understand overparameterization, Bubeck and Sellke considered a natural notion of what it means for a model to interpolate: the model is said to interpolate when the model’s training loss goes below the loss of the conditional expectation of the response given the covariate. For this notion of interpolation and for a broad class of covariate distributions (specifically those satisfying a natural notion of concentration of measure), they showed that overparameterization is necessary for robust interpolation i.e. if the interpolating function is required to beLipschitz. Their main proof technique applies to regression with square loss against a scalar response, but they remark that via a connection to Rademacher complexity and using tools such as the Ledoux-Talagrand contraction inequality, their result can be extended to more general losses, at least in the case of scalar response variables. In this work, we recast the original proof technique of Bubeck and Sellke in terms of a bias-variance type decomposition, and show that this view directly unlocks a generalization to Bregman divergence losses (even for vector-valued responses), without the use of tools such as Rademacher complexity or the Ledoux-Talagrand contraction principle. Bregman divergences are a natural class of losses since for these, the best estimator is the conditional expectation of the response given the covariate, and in particular, include other practical losses such as the cross entropy loss. Our work thus gives a more general understanding of the main proof technique of Bubeck and Sellke and demonstrates its broad utility.

Recent works have demonstrated that neural networks exhibit extreme *simplicity bias* (SB). That is, they learn *only the simplest* features to solve a task at hand, even in the presence of other, more robust but more complex features. Due to the lack of a general and rigorous definition of *features*, these works showcase SB on *semi-synthetic* datasets such as Color-MNIST , MNIST-CIFAR where defining features is relatively easier. In this work, we rigorously define as well as thoroughly establish SB for *one hidden layer* neural networks in the infinite width regime. More concretely, (i) we define SB as the network essentially being a function of a low dimensional projection of the inputs (ii) theoretically, we show that when the data is linearly separable, the network primarily depends on only the linearly separable ($1$-dimensional) subspace even in the presence of an arbitrarily large number of other, more complex features which could have led to a significantly more robust classifier, (iii) empirically, we show that models trained on *real* datasets such as Imagenet and Waterbirds-Landbirds indeed depend on a low dimensional projection of the inputs, thereby demonstrating SB on these datasets, iv) finally, we present a natural ensemble approach that encourages diversity in models by training successive models on features not used by earlier models, and demonstrate that it yields models that are significantly more robust to Gaussian noise.

Abstract. We study the Generalized Min Sum Set Cover (GMSSC) problem, wherein given a collection of hyperedges [Formula: see text] with arbitrary covering requirements [Formula: see text], the goal is to find an ordering of the vertices to minimize the total cover time of the hyperedges; a hyperedge [Formula: see text] is considered covered by the first time when [Formula: see text] and many of its vertices appear in the ordering. We give a [Formula: see text] approximation algorithm for GMSSC, coming close to the best possible bound of 4, already for the classical special case (with all [Formula: see text]) of Min Sum Set Cover (MSSC) studied by Feige, Lovász, and Tetali, and improving upon the previous best known bound of [Formula: see text] due to Im, Sviridenko, and van der Zwaan. Our algorithm is based on transforming the LP solution by a suitable kernel and applying randomized rounding. As part of the analysis of our algorithm, we also derive an inequality on the lower tail of a sum of independent Bernoulli random variables, which might be of independent interest and broader utility. Min Sum Vertex Cover (MSVC) is a well-known special case of MSSC in which the input hypergraph is a graph (i.e., [Formula: see text]) and [Formula: see text] for every edge [Formula: see text]. We give a [Formula: see text] approximation for MSVC and show a matching integrality gap for the natural LP relaxation. This improves upon the previous best [Formula: see text] approximation of Barenholz, Feige, and Peleg. Finally, we revisit MSSC and consider the [Formula: see text] norm of cover-time of the hyperedges. Using a dual fitting argument, we show that the natural greedy algorithm achieves tight, up to NP-hardness, approximation guarantees of [Formula: see text] for all [Formula: see text], giving another proof of the result of Golovin, Gupta, Kumar, and Tangwongsan, and showing its tightness up to NP-hardness. For [Formula: see text], this gives yet another proof of the 4 approximation for MSSC.

In the weighted flow-time problem on a single machine, we are given a set of n jobs, where each job has a processing requirement pj, release date rj, and weight wj. The goal is to find a preemptive schedule which minimizes the sum of weighted flow-time of jobs, where the flow-time of a job is the difference between its completion time and its released date. We give the first pseudopolynomial time constant approximation algorithm for this problem. The algorithm also extends directly to the problem of minimizing the ℓp norm of weighted flow-times. The running time of our algorithm is polynomial in n, the number of jobs, and P, which is the ratio of the largest to the smallest processing requirement of a job. Our algorithm relies on a novel reduction of this problem to a generalization of the multicut problem on trees, which we call the Demand MultiCut problem. Even though we do not give a constant factor approximation algorithm for the Demand MultiCut problem on trees, we show that the specific instances of Demand MultiCut obtained by reduction from weighted flow-time problem instances have more structure in them, and we are able to employ techniques based on dynamic programming. Our dynamic programming algorithm relies on showing that there are near optimal solutions which have nice smoothness properties, and we exploit these properties to reduce the size of the dynamic programming table.

We consider the following general scheduling problem studied recently by Moseley [27]. There are n jobs, all released at time 0, where job j has size pj and an associated arbitrary non-decreasing cost function fj of its completion time. The goal is to find a schedule on m machines with minimum total cost. We give an O(1) approximation for the problem, improving upon the previous O(log log nP) bound (P is the maximum to minimum size ratio), and resolving the open question in [27]. We first note that the scheduling problem can be reduced to a clean geometric set cover problem where points on a line with arbitrary demands, must be covered by a minimum cost collection of given intervals with non-uniform capacity profiles. Unfortunately, current techniques for such problems based on knapsack cover inequalities and low union complexity, completely lose the geometric structure in the non-uniform capacity profiles and incur at least an Ω(log log P) loss. To this end, we consider general covering problems with non-uniform capacities, and give a new method to handle capacities in a way that completely preserves their geometric structure. This allows us to use sophisticated geometric ideas in a black-box way to avoid the Ω(log log P) loss in previous approaches. In addition to the scheduling problem above, we use this approach to obtain O(1) or inverse Ackermann type bounds for several basic capacitated covering problems.

We study the generalized min sum set cover (GMSSC) problem, wherein given a collection of hyperedges E with arbitrary covering requirements {ke ∊ Z+ : e ∊ E}, the goal is to find an ordering of the vertices to minimize the total cover time of the hyperedges; a hyperedge e is considered covered by the first time when ke many of its vertices appear in the ordering. We give a 4.642 approximation algorithm for GMSSC, coming close to the best possible bound of 4, already for the classical special case (with all ke = 1) of min sum set cover (MSSC) studied by Feige, Lovász and Tetali [11], and improving upon the previous best known bound of 12.4 due to Im, Sviridenko and van der Zwaan [20]. Our algorithm is based on transforming the LP solution by a suitable kernel and applying randomized rounding. This also gives an LP-based 4 approximation for MSSC. As part of the analysis of our algorithm, we also derive an inequality on the lower tail of a sum of independent Bernoulli random variables, which might be of independent interest and broader utility. Another well-known special case is the min sum vertex cover (MSVC) problem, in which the input hypergraph is a graph (i.e., |e| = 2) and ke = 1, for every edge e ∊ E. We give a 16/9 ≃ 1.778 approximation for MSVC, and show a matching integrality gap for the natural LP relaxation. This improves upon the previous best 1.999946 approximation of Barenholz, Feige and Peleg [6]. (The claimed 1.79 approximation result of Iwata, Tetali and Tripathi [21] for the MSVC turned out have an unfortunate, seemingly unfixable, mistake in it.) Finally, we revisit MSSC and consider the ℓp norm of cover-time of the hyperedges. Using a dual fitting argument, we show that the natural greedy algorithm simultaneously achieves approximation guarantees of (p + 1)1+1/p, for all p ≥ 1, giving another proof of the result of Golovin, Gupta, Kumar and Tangwongsan [13], and showing its tightness up to NP-hardness. For p = 1, this gives yet another proof of the 4 approximation for MSSC.

In the weighted flow-time problem on a single machine, we are given a set of $n$ jobs, where each job has a processing requirement $p_j$, release date $r_j$, and weight $w_j$. The goal is to find a preemptive schedule which minimizes the sum of weighted flow-time of jobs, where the flow-time of a job is the difference between its completion time and its released date. We give the first pseudo-polynomial time constant approximation algorithm for this problem. The algorithm also extends directly to the problem of minimizing the $\ell_p$ norm of weighted flow-times. The running time of our algorithm is polynomial in $n$, the number of jobs, and $P$, which is the ratio of the largest to the smallest processing requirement of a job. Our algorithm relies on a novel reduction of this problem to a generalization of the multicut problem on trees, which we call the \tt Demand MultiCut problem. Even though we do not give a constant factor approximation algorithm for the \tt Demand MultiCut problem on trees, we show that the specific instances of \tt Demand MultiCut obtained by reduction from weighted flow-time problem instances have more structure in them, and we are able to employ techniques based on dynamic programming. Our dynamic programming algorithm relies on showing that there are near optimal solutions which have nice smoothness properties, and we exploit these properties to reduce the size of the dynamic programming table.

We study the unsplittable flow on a path problem which has received a lot of attention in the research community recently. Given is a path with capacities on its edges and a set of tasks where each task is characterized by a source and a sink vertex, a demand, and a profit. The goal is to find a subset of the tasks of maximum total profit such that all task demands from this subset can be routed simultaneously without violating the capacity constraints. The best known approximation results are a quasi-polynomial time-approximation scheme if the task demands are in a quasi-polynomial range [Bansal et al., STOC 2006] and a polynomial time (2 + ∊)-approximation algorithm [Anagnostopoulos et al., SODA 2014]. Finding a PTAS for it has remained an important open question. In this paper we make progress towards this goal. When the task densities—defined as the ratio of a task's profit and demand—lie in a constant range, we obtain a PTAS. We also improve the QPTAS of Bansal et al. by removing the assumption that the demands need to lie in a quasi-polynomial range. Our third result is a PTAS for the case where we are allowed to shorten the paths of the tasks by at most an ∊-fraction. This is particularly motivated by bandwidth allocation and scheduling applications of our problem if we are allowed to slightly increase the speed of the underlying transmission link/machine. Each of these results critically uses a sparsification lemma which we believe could be of independent interest. The lemma shows that in any (optimal) solution there exists an O(∊)-fraction (measured by weight) of its tasks whose removal creates, on each edge, a slack which is at least as large as the (1/∊)th largest demand using that edge. This slack can then be used to allow slight errors when estimating or rounding quantities arising in the computation.