31 citations · 50 across the 12 of their papers we have counts for
12 papers
Distributionally Robust Linear Regression With Block Lewis Weights
Naren Sarayu Manoj, Kumar Kshitij Patel
We present an algorithm for the group distributionally robust (GDR) least squares problem. Given groups, a parameter vector in , and stacked design matrices and r…
A Geometric Approach to Problems in Optimization and Data Science
Naren Sarayu Manoj
We give new results for problems in computational and statistical machine learning using tools from high-dimensional geometry and probability. We break up our treatment into two pa…
On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models
Aditya Bhaskara, Agastya Vibhuti Jha, Michael Kapralov +3
In a graph bisection problem, we are given a graph with two equally-sized unlabeled communities, and the goal is to recover the vertices in these communities. A popular heurist…
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…
Streaming Algorithms for Ellipsoidal Approximation of Convex Polytopes
Yury Makarychev, Naren Sarayu Manoj, Max Ovsiankin
We give efficient deterministic one-pass streaming algorithms for finding an ellipsoidal approximation of a symmetric convex polytope. The algorithms are near-optimal in that their…
An Optimal Algorithm for Certifying Monotone Functions
Meghal Gupta, Naren Sarayu Manoj
Given query access to a monotone function with certificate complexity and an input , we design an algorithm that outputs a size-$C(f)…
Excess Capacity and Backdoor Poisoning
Naren Sarayu Manoj, Avrim Blum
A backdoor data poisoning attack is an adversarial attack wherein the attacker injects several watermarked, mislabeled training examples into a training set. The watermark does not…
Random Smoothing Might be Unable to Certify Robustness for High-Dimensional Images
Avrim Blum, Travis Dick, Naren Manoj +1
We show a hardness result for random smoothing to achieve certified adversarial robustness against attacks in the ball of radius when . Although random smoothing…
Quantifying Perceptual Distortion of Adversarial Examples
Matt Jordan, Naren Manoj, Surbhi Goel +1
Recent work has shown that additive threat models, which only permit the addition of bounded noise to the pixels of an image, are insufficient for fully capturing the space of impe…