31 citations · 48 across the 9 of their papers we have counts for
4 papers · 1 filter
Dueling Optimization with a Monotone Adversary
Avrim Blum, Meghal Gupta, Gene Li +3
We introduce and study the problem of dueling optimization with a monotone adversary, which is a generalization of (noiseless) dueling convex optimization. The goal is to design an…
Near-Optimal Streaming Ellipsoidal Rounding for General Convex Polytopes
Yury Makarychev, Naren Sarayu Manoj, Max Ovsiankin
We give near-optimal algorithms for computing an ellipsoidal rounding of a convex polytope whose vertices are given in a stream. The approximation factor is linear in the dimension…
The Change-of-Measure Method, Block Lewis Weights, and Approximating Matrix Block Norms
Naren Sarayu Manoj, Max Ovsiankin
Given a matrix , a partitioning of into groups , an outer norm , and a collection of inner norms such that either $p…
Interpolation Learning With Minimum Description Length
Naren Sarayu Manoj, Nathan Srebro
We prove that the Minimum Description Length learning rule exhibits tempered overfitting. We obtain tempered agnostic finite sample learning guarantees and characterize the asympto…