88 citations · 162 across the 38 of their papers we have counts for
14 papers · 1 filter
First Order Stochastic Optimization with Oblivious Noise
Ilias Diakonikolas, Sushrut Karmalkar, Jongho Park +1
We initiate the study of stochastic optimization with oblivious noise, broadly generalizing the standard heavy-tailed noise setup. In our setting, in addition to random observation…
Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions
Ilias Diakonikolas, Sushrut Karmalkar, Jongho Park +1
We demonstrate the first algorithms for the problem of regression for generalized linear models (GLMs) in the presence of additive oblivious noise. We assume we have sample access…
Buying Information for Stochastic Optimization
Mingchen Ma, Christos Tzamos
Stochastic optimization is one of the central problems in Machine Learning and Theoretical Computer Science. In the standard model, the algorithm is given a fixed distribution know…
Weitzman's Rule for Pandora's Box with Correlations
Evangelia Gergatsouli, Christos Tzamos
Pandora's Box is a central problem in decision making under uncertainty that can model various real life scenarios. In this problem we are given boxes, each with a fixed openin…
A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning
Ilias Diakonikolas, Christos Tzamos, Daniel M. Kane
The Forster transform is a method of regularizing a dataset by placing it in {\em radial isotropic position} while maintaining some of its essential properties. Forster transforms…
Graph Connectivity with Noisy Queries
Dimitris Fotakis, Evangelia Gergatsouli, Charilaos Pipis +2
Graph connectivity is a fundamental combinatorial optimization problem that arises in many practical applications, where usually a spanning subgraph of a network is used for its op…